- 浏览: 308736 次
- 性别:
- 来自: 珠海
文章分类
最新评论
-
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 1468UVa 题号: 10131 Is Bigger Smart ... -
UVA 10201 Adventures in Moving - Part IV
2013-02-01 17:40 1660// [解题方法] // dp[i][j]表示到达第 ... -
UVA 10271 Chopsticks
2013-02-01 11:47 2199// [解题方法] // 将筷子按长度从大到小排序 ... -
UVA 10261 Ferry Loading
2013-01-31 16:34 3094// [题意] // n辆车按顺序安排在一个渡口的左 ... -
UVA 10003 Cutting Sticks
2013-01-31 15:35 1914// [解题方法] // 记忆化搜索(递归,子问题的 ... -
UVA 116 Unidirectional TSP
2013-01-30 09:53 1652// [解题方法] // 记忆化搜索(递归,子问题的 ... -
UVA 10154 Weights and Measures
2013-01-30 09:40 1959// 乌龟塔问题:每个乌龟有力量和重量,求最多能堆多少乌 ... -
UVA 10069 Distinct Subsequences
2013-01-29 16:23 1422// [解题方法] // dp[i][j]表示Z串的 ... -
UVA 10131 Is Bigger Smarter?
2013-01-29 16:01 1812// [解题方法] // 对大象增加编号属性i,以免 ... -
hdu 4170 Supply Mission
2012-09-22 10:03 1206KIDx的解题报告 ... -
UVA 10202 + HDU 1270 小希的数表
2012-09-15 20:01 2696KIDx的解题报告 题目链接:http://ac ... -
HDU 1979 Fill the blanks
2012-08-20 12:40 1077KIDx的解题报告 题目链接:http://ac ... -
【拓扑+DP】HDU 4109 Instrction Arrangement
2012-03-25 23:34 1376KIDx的解题报告 题目链接:http://acm ... -
【DP最大公共子序列】HDU 1159/1080/1503
2012-03-11 18:04 3116KIDx的解题报告 第一题(比较简单,不详细解): ... -
【最大不连续子序列和】HDU 2845 Beans
2012-03-08 22:09 3565KIDx的解题报告 题目链接:http://acm.h ... -
【数学】HDU 1719 Friend
2012-03-02 16:44 1163KIDx的解题报告 好久没写博客了,来题数学提提神 ... -
【BKDR_hash】HDU 2648 Shopping
2011-12-10 19:35 1780KIDx 的解题报告 题目链接:http://acm. ... -
Codeforces Beta Round #97 (Div. 2) 【完整题解】
2011-12-10 14:23 1500KIDx 的解题报告 题目链接:http://codeforc ... -
2011 ACM/ICPC 北京赛区现场赛 B题(hdu 4082)
2011-11-12 14:15 2065KIDx 的解题报告 题目链接:http://acm.hdu. ... -
Codeforces Beta Round #4 (Div. 2 Only) 【完整题解】
2011-11-08 00:33 1366KIDx 的解题报告 http://codeforces.c ...
相关推荐
Codeforces Round #723 (Div. 2).md
上面代码跑出来的dp[n][m]是0,然后从(1,1)(1,2)(2,2)(2,3)这样的相与值是k (看懂ans+k是啥应该就懂了) 代码: int main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int ans=(1&...
传送门 题意: 开始位置在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 #...
长度为n的字符串包含n−2n−2n−2个aaa和222个bbb,求按照字典序排列输出第kkk个字符串 解题思路 第一个bbb在倒数第二位有1个字符串,在倒数第三位有2个字符串…在倒数第nnn位时有n−1n-1n−1个字符串 可以根据第一...
Codeforces Round #629 (Div. 3) E.Tree Queries (DFS) 思路:若ai 在路径上 ,则ai的父结点一定在路径上,若ai是路径上某个结点的子结点,则ai的父结点一定在路径上,综上只需考虑ai的父节点就行了。对每个ai判断...
E. Cyclic Components 题目链接-E. Cyclic Components 题目大意 给你nnn个点和mmm条边,求所构成图中单圈环的个数 ...并查集并查集并查集 很明显单圈环每个点的度都为222,所以我们可以用数组cnt[]记录每个点的度,...
题目链接: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....
给两两节点放一个数字(0~n-2 唯一) 给你一棵树,求所有任意两节点相连的路以外的路上的数字的最小值最小 思路 构造 若一个点连了三条边及以上,则这个点的边从最小值开始赋值。其他边从最大点开始赋值。 证明:一...
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...
输入一个正整数x,找出这样的2个正整数a和b,使得gcd(a,b)+lcm(a,b)=x 解题思路 找最特殊的情况a=1,b=x-1即可 这样a,b两个数最大公因数为1,最小公倍数x-1,满足题意√ 附上代码 #include #define int long long #...
A #include using namespace std; typedef long long ll; int main(){ int t; cin>>t; while(t--){ ll x; cin>>x; cout<<1>>t; while(t--){ st.clear(); ll n; cin >>n;... ll re
传送门 A. EhAb AnD gCd 直接输出1,n-1即可 #include #include #include #include #include #include #include #include #include #include #define pb push_back #define lb lower_bound ...con
传送门 题意: 找规律,题意就是有多少种方式填充该图形 画两个就发现,输出n即可 代码: #include #include #include #include #include #include #include #include ...#define SZ(x) ((int)(x)
给一个长度为n的数组,两种操作,一个是把任意一个ai变成ai+2a_i变成a_i+2ai变成ai+2,另一个是如果所有数都大于0,可以把所有数减1,问通过这些操作能否把所有数变为0 思路: 如果任意两个数之差为奇数,那么就...
-2,4,5,5,6,8 要输出的序列应该是每次从前面选一个,然后从后面选一个 -2,8,4,6,5,5 然后把该序列倒着输出即可 代码: #include #include #include #include #include #include #include #include #...
将所有数字看成2进制,从最高位看起,如果第i位上为1的数只有一个的话,那么这个数必然对答案有贡献,就把它排在第一个,后面任意排。 例:11,6,4,0 二进制表示为:1011,110,100,0 右起第四位为1的只有1011,...