`

Codeforces Beta Round #96 (Div. 2)【完整题解】

阅读更多
KIDx 的解题报告
题目链接:http://codeforces.com/contest/133
以下省略头文件,前三题是水题,不解释

A题

#define M 105
char s[M];
int main()
{
	bool flag;
	int i, len;
	while (gets (s))
	{
		flag = false;
		len = strlen (s);
		for (i = 0; i < len; i++)
			if (s[i] == 'H' || s[i] == 'Q' || s[i] == '9')
			{
				flag = true;
				break;
			}
		if (flag)
			puts ("YES");
		else puts ("NO");
	}
	return 0;
}


B题
#define M 105
int mod = 1000003;
string s, b;
map<char, string> m;
int main()
{
	int i, res, a;
	m['>'] = "1000";
	m['<'] = "1001";
	m['+'] = "1010";
	m['-'] = "1011";
	m['.'] = "1100";
	m[','] = "1101";
	m['['] = "1110";
	m[']'] = "1111";
	while (cin >> s)
	{
		b = "";
		for (i = 0; i < s.size(); i++)
			b += m[s[i]];
		res = 0, a = 1;
		for (i = b.size() - 1; i >= 0; i--)
		{
			if (b[i] == '1')
				res = (res + a) % mod;
			a = (a << 1) % mod;
		}
		printf ("%d\n", res);
	}
	return 0;
}


C题
#define M 105
int mod = 256;
char s[M], p[M];
int main(
{
	int i, k, pre, j;
	while (gets (s))
	{
		pre = 0;
		for (i = 0; i < strlen(s); i++)
		{
			int tp = int(s[i]);
			k = 0;
			while (tp)    //讲tp转成2进制存到p
			{
				p[k++] = (tp % 2) + '0';
				tp >>= 1;
			}
			while (k < 8)    //补0
				p[k++] = '0';
			p[k] = 0;
			for (j = 0; j < k; j++)
			{
				if (p[j] == '1')
					tp += pow (2.0, k-j-1);
			}
			printf ("%d\n", ((pre-tp)%mod+mod)%mod);    //将解限制到最小非负整数
			pre = tp;
		}
	}
	return 0;
}


D题
表示偶的英语水平太特么烂,很久才看懂:
0-9表示颜色,输入一堆颜色像素
相同颜色所组成的一个长方形算一个【看做整体】
初始时:
BP为左上角那整的颜色,DP向右指到这整的最远边,CP向上【DP的左方】指到这整的远边
变换状态:
若DP所指的next为0或者空:【BP不变】
①若CP此时在DP左边,则DP不变,CP变成DP的右边,同时显然的CP会指到当前整的CP方向最远处,此转换消耗一个步数
②若CP此时在DP右边,则DP顺时针转90°,CP变成DP的左边,同时DP与CP都会指到当前各自方向的最远处,此转换消耗一个步数
若DP所指的next有颜色(1-9):
向DP方向走一步,同时DP指到该DP方向的最远处,且BP变为该块的颜色,此转换消耗一个步数
然后还要找循环节,不然会超时:
定义一个hash[i][j][CP][DP]表示第一次走到i,j时方向为CP,DP这一状态的步数,设第二次再次获得此状态的步数为times,则循环时间loop = times - hash[i][j][CP][DP]

如图所示:
如果有循环节:
那么k必然>=times,观察可知:原来的模拟k次,其实相当于模拟:(times - loop + (k-times) % loop)次

#define M 55
char map[M][M];
int x_move[4] = {-1, 0, 1, 0};    //四个方向:分别表示:上,右,下,左
int y_move[4] = {0, 1, 0, -1};
int hash[M][M][5][5];
int r, c, k, i, BP, CP, DP, bx, by, dir, tx, ty, loop, times;
void init ()    //设置初始状态
{
	BP = map[0][0] - '0';
	CP = -1;
	DP = 1;
	tx = ty = 0;
	do{    //沿DP方向指到该块最远处
		bx = tx, by = ty;
		tx += x_move[DP];
		ty += y_move[DP];
	}while (!(tx < 0 || ty < 0 || tx >= r || ty >= c) &&
		map[tx][ty] - '0' == BP);
	times = 0;
}
void moni ()    //模拟
{
	tx = bx + x_move[DP];
	ty = by + y_move[DP];
	if (tx < 0 || ty < 0 || tx >= r || ty >= c || map[tx][ty] == '0')
	{
		if (CP == 1)
			DP = (DP + 1) % 4;
		CP = -CP;
	}
	else
	{
		BP = map[tx][ty] - '0';
		do{    //沿DP方向指到该块最远处
			bx = tx, by = ty;
			tx += x_move[DP];
			ty += y_move[DP];
		}while (!(tx < 0 || ty < 0 || tx >= r || ty >= c) &&
			map[tx][ty] - '0' == BP);
	}
	dir = (DP+CP) % 4;    //CP是-1时在DP左边,是1时在DP右边,dir为CP方向
	tx = bx, ty = by;
	do{    //沿CP方向指到该块最远处
		bx = tx, by = ty;
		tx += x_move[dir];
		ty += y_move[dir];
	}while (!(tx < 0 || ty < 0 || tx >= r || ty >= c) &&
		map[tx][ty] - '0' == BP);
}
int main()
{
	while (~scanf ("%d%d", &r, &k))
	{
		memset (hash, 0, sizeof(hash));
		for (i = 0; i < r; i++)
			scanf ("%s", map[i]);
		c = strlen (map[0]);
		init();
		loop = 0;
		while (times < k)
		{
			moni ();
			if (hash[bx][by][CP+1][DP] > 0)    //有重复状态,即找到循环节
			{
				loop = times - hash[bx][by][CP+1][DP];
				break;
			}
			else hash[bx][by][CP+1][DP] = times;
			times++;
		}
		if (loop > 0)    //有循环节,重新模拟times-loop+(k-times)%loop次
		{
			k = times - loop + (k-times) % loop;
			init();
			while (k--) {moni ();}
		}
		printf ("%d\n", BP);
	}
	return 0;
}


E题
算法:DP
题意很简单:
F表示向前走,T表示转弯,给一个FT组成的串,F可以变T,T可以变F,一个字符可以变多次,问变n次后最多能走多远
状态的表示:
f[i][j][k]表示向前走的最长距离
g[i][j][k]表示向前走的最短距离【则(-g[i][j][k])表示向后走的最长距离】
i表示完成前i-1个字符命令
j表示完成前i-1个字符命令一共作了j次变换
k表示方向,k = 0 表示正在向前走,k = 1 表示正在向后走

#define inf 0x3fffffff
#define M 105
#define N 55
int f[M][N][2], g[M][N][2], d[2] = {1, -1}, tp, k2, i, j, k, num;
char s[M];          //d[1] = -1,说明向后走1步,也就是向前走-1步
void dp (int f[][N][2], int key)
{
	tp = f[i][j][k], k2 = k;
	if (num & 1)    //变奇数次,s[i]肯定变成另一个字符
	{
		if (s[i] == 'T') tp += d[k];    //变成f,所以向前状态k方向走
		else k2 = !k;    //变成T,下一状态的方向k2变向
	}
	else    //s[i]不变
	{
		if (s[i] == 'T') k2 = !k;    //k2换向
		else tp += d[k];    //向k方向走
	}
	if (key)
		f[i+1][j+num][k2] = max (f[i+1][j+num][k2], tp);
	else f[i+1][j+num][k2] = min (f[i+1][j+num][k2], tp);
}
int main()
{
	int n, len;
	while (~scanf ("%s", s))
	{
		len = strlen (s);
		scanf ("%d", &n);
		for (i = 0; i < M; i++)
			for (j = 0; j < N; j++)
				f[i][j][0] = f[i][j][1] = -inf,
				g[i][j][0] = g[i][j][1] = inf;
		f[0][0][0] = f[0][0][1] = g[0][0][0] = g[0][0][1] = 0;
		for (i = 0; i < len; i++)
			for (j = 0; j <= n; j++)
				for (k = 0; k < 2; k++)
					for (num = 0; j + num <= n; num++)  //num表示让当前字符变多少次
					{
						if (f[i][j][k] > -inf) dp (f, 1); //对f进行dp
						if (g[i][j][k] < inf) dp (g, 0); //对g进行dp
					}
		printf ("%d\n",
			max (f[len][n][0],
			max (f[len][n][1],
			max (-g[len][n][0], -g[len][n][1]))));
	}
	return 0;
}
  • 大小: 2.2 KB
1
0
分享到:
评论

相关推荐

    Codeforces Round #723 (Div. 2).md

    Codeforces Round #723 (Div. 2).md

    Codeforces Round 961 (Div. 2):深度解析与实战技巧.pdf

    ### Codeforces Round 961 (Div. 2):深度解析与实战技巧 #### 引言 Codeforces 是一个国际知名的在线编程竞赛平台,它汇聚了来自世界各地的编程爱好者和专业人士。每一轮比赛都旨在测试参赛者的算法思维、编程...

    Codeforces Round 961 (Div. 2) 编程竞赛的详细解析

    codeforces round 961 (div. 2)

    Codeforces Round #627 (Div. 3) C. Frog Jumps(思维)

    传送门 题意: 开始位置在0,问能否跳到n+1位置 每步只能跳d 在1——n每个位置有方向,L,R,求d的最小值 思路: 只用找相邻两个R之间的最大值即可 代码: #include #include ...typedef long long l

    Codeforces Round #627 (Div. 3) B. Yet Another Palindrome Problem

    就是把所有相等的数放到一个vector里,如果他出现大于2次,看最远的间距是否大于2即可,找到一个就可以 代码: #include #include #include #include #include #include #include #include #include #include #...

    codeforces round 961 (div. 2)

    ### Codeforces Round 961 (Div. 2) A题解析 #### 题目背景 Codeforces Round 961 (Div. 2) 是一场针对中级水平程序员的编程竞赛,通常会包含几个不同难度级别的题目。A题作为入门级题目,旨在测试参赛者的基础算法...

    codeforces round 962 (div. 3)tion-ma笔记

    codeforces round 962 (div. 3)tion-ma笔记

    Codeforces Round #629 (Div. 3) E.Tree Queries (DFS)

    Codeforces Round #629 (Div. 3) E.Tree Queries (DFS) 思路:若ai 在路径上 ,则ai的父结点一定在路径上,若ai是路径上某个结点的子结点,则ai的父结点一定在路径上,综上只需考虑ai的父节点就行了。对每个ai判断...

    codeforces round 962 (div. 3).docx

    Codeforces Round 962 (Div. 3) 是一场编程竞赛,其中包含了多个编程题目,每个题目都有其独特的挑战和解题思路。以下是对该竞赛中部分题目的简要介绍及解题思路概述: A题: Legs 题意: 一只鸡有2条腿,一头奶牛有...

    codeforces round 962 (div. 3) .zip

    Codeforces Round 962 (Div. 3) 是一场编程竞赛,旨在测试参赛者在算法和数据结构方面的能力。由于篇幅限制,我将对这场竞赛中的几个关键问题进行详细解析,但请注意,由于具体实现细节可能因题目而异,且无法在此...

    Codeforces Round #479 (Div. 3) E. Cyclic Components

    E. Cyclic Components 题目链接-E. Cyclic Components 题目大意 给你nnn个点和mmm条边,求所构成图中单圈环的个数 ...并查集并查集并查集 很明显单圈环每个点的度都为222,所以我们可以用数组cnt[]记录每个点的度,...

    Codeforces Round #627 (Div. 3) D. Pair of Topics(二分,思维)

    ### Codeforces Round #627 (Div. 3) D. Pair of Topics(二分,思维) #### 题目背景与概述 本题目来自Codeforces Round #627 (Div. 3),编号为D的题目“Pair of Topics”,这是一道结合了二分搜索与逻辑思维的...

    【Codeforces Round#620 (Div. 2)】B. Longest Palindrome 题解

    题目链接:B. Longest Palindrome 题目 Returning back to problem solving, Gildong is now studying about palindromes. He learned that a palindrome is a string that is the same as its reverse....

    Codeforces Round #618 (Div. 2) C. Anu Has a Function(进制,位运算,贪心)

    题目“Anu Has a Function”源自Codeforces Round #618 (Div. 2)的一道竞赛编程问题,主要涉及进制转换、位运算和贪心算法。问题要求定义一个函数f(x, y) = (x | y) - y,并对数组进行排序,以最大化最后的结果。 ...

    Codeforces Round #628 (Div. 2)

    给两两节点放一个数字(0~n-2 唯一) 给你一棵树,求所有任意两节点相连的路以外的路上的数字的最小值最小 思路 构造 若一个点连了三条边及以上,则这个点的边从最小值开始赋值。其他边从最大点开始赋值。 证明:一...

    Codeforces Round #629 (Div. 3) E – Tree Queries dfs序判祖先关系

    标题中的"Codeforces Round #629 (Div. 3) E – Tree Queries dfs序判祖先关系"指的是一场编程竞赛中的问题,涉及到树结构的查询和深度优先搜索(DFS)来判断节点间的祖先关系。这个问题的目标是设计算法来确定在...

    Codeforces Round #620 (Div. 2) Longest Palindrome

    B. Longest Palindrome time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Returning back to problem solving, Gildong is now studying about ...

    Codeforces Round #635 (Div. 2)D. Xenia and Colorful Gems

    题解:6nlogn,先sort三个数组a,b,c, 六次枚举二分查找,再每次min找最小值,例如:先固定数组a,再在数组b,c中利用lower_bound找到第一个大于等于a[i]的数, #pragma GCC optimize(2) #include #define ll long long...

Global site tag (gtag.js) - Google Analytics