- 浏览: 316106 次
- 性别:
- 来自: 珠海
文章分类
最新评论
-
xialluyouyue:
Ubuntu下搭建nodejs+express+mongodb环境简单教程 -
k317544294:
Good 陈迪峰
(开源游戏) DOTA音效版 俄罗斯方块 -
基德KID.1412:
su1216 写道竖线代表或者,不代表替换
对哦~ 谢谢你的提 ...
正则表达式中特殊字符的用法(收藏) -
su1216:
竖线代表或者,不代表替换
正则表达式中特殊字符的用法(收藏) -
qiqijianglu:
基德KID.1412 写道qiqijianglu 写道基德KI ...
【高斯消元 求期望】HDU 4418 Time travel
KIDx 的解题报告
题目链接:http://codeforces.com/contest/133
以下省略头文件,前三题是水题,不解释
A题
B题
C题
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)次
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 表示正在向后走
题目链接: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; }
发表评论
-
《挑战编程》第11章-动态规划
2013-02-02 12:46 1524UVa 题号: 10131 Is Bigger Smart ... -
UVA 10201 Adventures in Moving - Part IV
2013-02-01 17:40 1718// [解题方法] // dp[i][j]表示到达第 ... -
UVA 10271 Chopsticks
2013-02-01 11:47 2256// [解题方法] // 将筷子按长度从大到小排序 ... -
UVA 10261 Ferry Loading
2013-01-31 16:34 3167// [题意] // n辆车按顺序安排在一个渡口的左 ... -
UVA 10003 Cutting Sticks
2013-01-31 15:35 1973// [解题方法] // 记忆化搜索(递归,子问题的 ... -
UVA 116 Unidirectional TSP
2013-01-30 09:53 1757// [解题方法] // 记忆化搜索(递归,子问题的 ... -
UVA 10154 Weights and Measures
2013-01-30 09:40 2034// 乌龟塔问题:每个乌龟有力量和重量,求最多能堆多少乌 ... -
UVA 10069 Distinct Subsequences
2013-01-29 16:23 1501// [解题方法] // dp[i][j]表示Z串的 ... -
UVA 10131 Is Bigger Smarter?
2013-01-29 16:01 1872// [解题方法] // 对大象增加编号属性i,以免 ... -
hdu 4170 Supply Mission
2012-09-22 10:03 1271KIDx的解题报告 ... -
UVA 10202 + HDU 1270 小希的数表
2012-09-15 20:01 2755KIDx的解题报告 题目链接:http://ac ... -
HDU 1979 Fill the blanks
2012-08-20 12:40 1124KIDx的解题报告 题目链接:http://ac ... -
【拓扑+DP】HDU 4109 Instrction Arrangement
2012-03-25 23:34 1434KIDx的解题报告 题目链接:http://acm ... -
【DP最大公共子序列】HDU 1159/1080/1503
2012-03-11 18:04 3152KIDx的解题报告 第一题(比较简单,不详细解): ... -
【最大不连续子序列和】HDU 2845 Beans
2012-03-08 22:09 3595KIDx的解题报告 题目链接:http://acm.h ... -
【数学】HDU 1719 Friend
2012-03-02 16:44 1202KIDx的解题报告 好久没写博客了,来题数学提提神 ... -
【BKDR_hash】HDU 2648 Shopping
2011-12-10 19:35 1821KIDx 的解题报告 题目链接:http://acm. ... -
Codeforces Beta Round #97 (Div. 2) 【完整题解】
2011-12-10 14:23 1529KIDx 的解题报告 题目链接:http://codeforc ... -
2011 ACM/ICPC 北京赛区现场赛 B题(hdu 4082)
2011-11-12 14:15 2111KIDx 的解题报告 题目链接:http://acm.hdu. ... -
Codeforces Beta Round #4 (Div. 2 Only) 【完整题解】
2011-11-08 00:33 1422KIDx 的解题报告 http://codeforces.c ...
相关推荐
Codeforces Round #723 (Div. 2).md
### Codeforces Round 961 (Div. 2):深度解析与实战技巧 #### 引言 Codeforces 是一个国际知名的在线编程竞赛平台,它汇聚了来自世界各地的编程爱好者和专业人士。每一轮比赛都旨在测试参赛者的算法思维、编程...
codeforces round 961 (div. 2)
传送门 题意: 开始位置在0,问能否跳到n+1位置 每步只能跳d 在1——n每个位置有方向,L,R,求d的最小值 思路: 只用找相邻两个R之间的最大值即可 代码: #include #include ...typedef long long l
就是把所有相等的数放到一个vector里,如果他出现大于2次,看最远的间距是否大于2即可,找到一个就可以 代码: #include #include #include #include #include #include #include #include #include #include #...
### Codeforces Round 961 (Div. 2) A题解析 #### 题目背景 Codeforces Round 961 (Div. 2) 是一场针对中级水平程序员的编程竞赛,通常会包含几个不同难度级别的题目。A题作为入门级题目,旨在测试参赛者的基础算法...
codeforces round 962 (div. 3)tion-ma笔记
Codeforces Round #629 (Div. 3) E.Tree Queries (DFS) 思路:若ai 在路径上 ,则ai的父结点一定在路径上,若ai是路径上某个结点的子结点,则ai的父结点一定在路径上,综上只需考虑ai的父节点就行了。对每个ai判断...
Codeforces Round 962 (Div. 3) 是一场编程竞赛,其中包含了多个编程题目,每个题目都有其独特的挑战和解题思路。以下是对该竞赛中部分题目的简要介绍及解题思路概述: A题: Legs 题意: 一只鸡有2条腿,一头奶牛有...
Codeforces Round 962 (Div. 3) 是一场编程竞赛,旨在测试参赛者在算法和数据结构方面的能力。由于篇幅限制,我将对这场竞赛中的几个关键问题进行详细解析,但请注意,由于具体实现细节可能因题目而异,且无法在此...
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”,这是一道结合了二分搜索与逻辑思维的...
题目链接: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....
题目“Anu Has a Function”源自Codeforces Round #618 (Div. 2)的一道竞赛编程问题,主要涉及进制转换、位运算和贪心算法。问题要求定义一个函数f(x, y) = (x | y) - y,并对数组进行排序,以最大化最后的结果。 ...
给两两节点放一个数字(0~n-2 唯一) 给你一棵树,求所有任意两节点相连的路以外的路上的数字的最小值最小 思路 构造 若一个点连了三条边及以上,则这个点的边从最小值开始赋值。其他边从最大点开始赋值。 证明:一...
标题中的"Codeforces Round #629 (Div. 3) E – Tree Queries dfs序判祖先关系"指的是一场编程竞赛中的问题,涉及到树结构的查询和深度优先搜索(DFS)来判断节点间的祖先关系。这个问题的目标是设计算法来确定在...
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 ...
题解:6nlogn,先sort三个数组a,b,c, 六次枚举二分查找,再每次min找最小值,例如:先固定数组a,再在数组b,c中利用lower_bound找到第一个大于等于a[i]的数, #pragma GCC optimize(2) #include #define ll long long...