首页 > 代码库 > 郑轻第六届校赛 -- 部分题解
郑轻第六届校赛 -- 部分题解
1427: 数字转换
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 379 Solved: 93
SubmitStatusWeb Board
Description
老师交给小明一个任务,有两个数字x和y(x<y),通过以下两种操作:一、将x乘以2;二、将x的值加上1。小明希望能通过尽可能少的操作来完成这个任务,但是不知道怎么做,现在请大家来帮帮他的忙吧。
Input
两个整数x,y(0<=x<y<=10^6)。
Output
一个整数n,表示最少经过多少次操作,x可以变成y。
Sample Input
Sample Output
HINT
Source
郑轻第六届校赛
闲来无事刷刷别人家的校赛题,感觉还挺水的,我都水了6个题,可能今天状态还好吧,,不过今天还有个字典树是卡住了,,下次再看吧,,唉。。。(一刷就上瘾了,都没去看大物了,,明天好好看书复习)
AC代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int main() { int x, y; while(scanf("%d %d", &x, &y) != EOF) { int cnt = 0; if(x == 0) { x = 1; cnt++; } while(x != y) { if(y/2 >= x) { cnt++; if(y&1) cnt++; y = y / 2; } else { y--; cnt++; } } printf("%d\n", cnt); } return 0; }
1428: 神秘密码
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 256 Solved: 147
SubmitStatusWeb Board
Description
小Q是一名标准的IT宅男,同时也是一名软贱攻城狮,主攻加解密算法。由于他实在是太喜欢加密解密神马的、以至于这个晚上、他在做梦的时候还在想着加解密的事情囧~。
梦中,他不慎进入了一个密码的世界,这个小世界中杂乱无序的漂浮着一些整数。他稀里糊涂的知道、闯出这个小世界的关键是找到所谓的“密码钥匙”,钥匙是一个字符串,由天上这些整数构成。同时,他也很不科学的知道这些整数的正确的顺序。也知道每个字符串中的每个字符就是对应整数的ASCII码字符。而问题的关键是,他不记得整数与字符之间的ASCII映射。
“这怎么办,难道我就困在这个这里出不去了么T_T?我是很喜欢解密,但是。。
人家还木有女盆友、
人家还没有挣到Money、
人家还没有买车、
人家还没有买房、
人家还没有。。。
人家。。哇啊儿。。。。”好吧,这厮。。哭了。。。
原谅这位整天只知道钻研技术、而不经世事的童鞋吧。那你来帮他一下肿么样?
Input
输入有T(1<=T<=100)组。
每组一个整数n(1<=n<=1000),而后有n个正整数。
保证输入合法。
Output
对于每组,请输出密码钥匙,每组占一行。
Sample Input
Sample Output
HINT
Source
郑轻第六届校赛
AC代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int a[1005]; int main() { int T, n; scanf("%d", &T); while(T--) { scanf("%d", &n); for(int i=0; i<n; i++) { scanf("%d", &a[i]); } for(int i=0; i<n; i++) printf("%c", a[i]); printf("\n"); } return 0; }
1430: 多少个0
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 213 Solved: 56
SubmitStatusWeb Board
Description
一个n*n的方格,每个格子中间有一个数字是2或者5,现在从方格的左上角走到右下角,每次只能选择向下或者向右移动一格两种移动方式,让所有经过的格子中的数字相乘,求使最后的结果中末尾处0的数字最少。
Input
第一行是一个正整数n(0<n<100)。
接下来n行是一个n*n的矩阵。
Output
一个正整数m,表示最后的结果末尾处最少有m个0。
Sample Input
Sample Output
HINT
Source
郑轻第六届校赛
思路:DP,去找2和5在一条路径(左上到右下)上数目的最大值
AC代码:
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; int n; int a[105][105]; int dp2[105][105]; int dp5[105][105]; int main() { while(scanf("%d", &n) != EOF) { for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) scanf("%d", &a[i][j]); memset(dp2, 0, sizeof(dp2)); memset(dp5, 0, sizeof(dp5)); if(a[1][1] == 2) dp2[1][1] = 1; else dp5[1][1] = 1; for(int i=2; i<=n; i++) { for(int j=1; j<=i; j++) { dp5[i][j] = max(dp5[i-1][j], dp5[i][j-1]); dp2[i][j] = max(dp2[i-1][j], dp2[i][j-1]); if(a[i][j] == 2) dp2[i][j]++; else dp5[i][j]++; dp5[j][i] = max(dp5[j][i-1], dp5[j-1][i]); dp2[j][i] = max(dp2[j][i-1], dp2[j-1][i]); if(a[j][i] == 2) dp2[j][i]++; else dp5[j][i]++; } } int ma = max(dp2[n][n], dp5[n][n]); //printf("%d %d\n", dp2[n][n], dp5[n][n]); printf("%d\n", 2 * n - 1 - ma); } return 0; }
1432: 背包again
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 193 Solved: 53
SubmitStatusWeb Board
Description
Gy最近学习了01背包问题,无聊的他又想到了一个新的问题,给定n个物品的价值,和01背包一样,每个物品只能选1次或0次,求最小不能被得到的价值。
Input
第一行一个正整数T(T <= 100),表示有T组数据。
每组数据输入格式如下:
第一行为一个正整数N(N<=100),表示物品个数。
第二行N个正整数,表示每个物品的价值vi(1<=vi<=1000000)
Output
共输出T行,即每组数据相应答案。
Sample Input
Sample Output
HINT
Source
郑轻第六届校赛
AC代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 110; int a[N]; int main() { int T; scanf("%d", &T); while(T--) { int n, m; scanf("%d", &n); for(int i=0; i<n; i++) scanf("%d", &a[i]); sort(a, a+n); m = 0; //m代表从0到m都能被得到 (DP思想) for(int i=0; i<n; i++) { if(a[i] - m > 1) //如果当前的数比m还大超过1的话,m+1就是最小不能被得到的,可以用反证证明 break; m = m + a[i]; } printf("%d\n", m + 1); //因为0到m都能被得到,所以m+1不能被得到 } return 0; }
1433: What are you doing?
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 221 Solved: 103
SubmitStatusWeb Board
Description
“Hey my friends!What are you doing?”
小伙伴们都在期待了N多年的大学中度过一段时间了,不知道大家都在忙什么呢?有咩有找到自己奋斗的目标?
据说有个叫LOL的帮派横空出世了,影响了无数大学的宅同胞。这里面有两个好斗的角色,一个叫PanSen(简称PS),一个叫JanSheng(简称JS)。这两个家伙以好斗闻名、外人称为“双雄”。不过他俩谁都不服对方,只要一见面、就必然会很“亲热”地招呼对方。(当然、用他们自己的话说是在传递爱与友谊。不过路人怎么总会觉得有点残忍类。。)
就在刚刚,这俩家伙又见面了。
“秃,那厮,洒家终于练就了无上神功。每个第 x 次攻击可释放一次大招,让这一次的攻击造成 c 倍伤害给你。你就认命吧!”PS道。
“呦~,我当时谁呢,在下不才、也刚练成了一点点小本事。每攻击 y 次后可以触发一个神状态,从下一次攻击开始、连续 z 次的攻击都可以造成双倍伤害,z次攻击过去之后、再重新开始为下一次神状态充电。让我好好‘招待你吧’!”JS回道。
“公猪母猪加油、大猪小猪加油~”路人甲喊着。
“闭嘴!”,“住口!”双雄扭头、同时发话。
“有奸情,果然、感情是打出来的,古人诚不欺我。。”,路人乙小声嘀咕。
双雄满脑黑线、殴斗继续。。。。
好了,这个战斗发生在刚刚,那么告诉你一些信息,你可以判断出最后谁胜出了么?
已知:
1、PS每次攻击可以让JS掉 a 点血,JS每次攻击可以让PS掉 b 点血;
2、PS有血量HP_p,JS有血量HP_j,血量不大于0即代表失败,战斗结束;
3、按照不成文规定,俩家伙是轮流攻击对方,JS先发动攻击。
Input
输入有T组。
每组按顺序读入多个整数:
HP_p、HP_j(0<HP_p、HP_j<=1000),表示PanSen和JanSheng的生命值;
a、b、c、x、y、z(0<a、b、c、x、y、z<=1000),意义如上。
输入保证合法。
Output
对于每组,输出获胜人的名字的简称、单独占一行。
Sample Input
Sample Output
HINT
适度LOL可练就反应迅速等无上神功,但过度LOL则有损身心健康,适度就好。
望各位小伙伴找到自己奋斗的目标、并早日成功。
Source
郑轻第六届校赛
AC代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int main() { int T; int PS, JS, a, b, c, x, y, z; scanf("%d", &T); while(T--) { scanf("%d %d %d %d %d %d %d %d", &PS, &JS, &a, &b, &c, &x, &y, &z); int cur = 1; while(1) { if(PS <= 0 || JS <= 0) break; if(cur % x == 0) JS -= c; else JS -= a; if((cur-1) % ( y + z ) <= y) PS -= b; else PS -= 2*b; cur++; } if(PS <= 0) printf("JS\n"); else printf("PS\n"); } return 0; }
1435: A+B
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 159 Solved: 114
SubmitStatusWeb Board
Description
喜闻乐见A+B。
读入两个用英文表示的A和B,计算它们的和并输出。
Input
第一行输入一个字符串,表示数字A;第二行输入一个字符串表示数字B。A和B均为正整数。
Output
输出一个正整数n,表示A+B的和(A+B<100)。
Sample Input
Sample Output
HINT
从0到9的对应的英文单词依次为:zero, one , two , three , four , five , six , seven , eight , nine 。
Source
郑轻第六届校赛
AC代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int fun(char a[]) { int len = strlen(a), ans = 0; for(int i=0; i<len; i++) { if(a[i] == 'z' && a[i+1] == 'e') { ans = ans * 10 + 0; i += 4; } else if(a[i] == 'o' && a[i+1] == 'n') { ans = ans * 10 + 1; i += 3; } else if(a[i] == 't' && a[i+1] == 'w') { ans = ans * 10 + 2; i += 3; } else if(a[i] == 't' && a[i+1] == 'h') { ans = ans * 10 + 3; i += 5; } else if(a[i] == 'f' && a[i+1] == 'o') { ans = ans * 10 + 4; i += 4; } else if(a[i] == 'f' && a[i+1] == 'i') { ans = ans * 10 + 5; i += 4; } else if(a[i] == 's' && a[i+1] == 'i') { ans = ans * 10 + 6; i += 3; } else if(a[i] == 's' && a[i+1] == 'e') { ans = ans * 10 + 7; i += 5; } else if(a[i] == 'e' && a[i+1] == 'i') { ans = ans * 10 + 8; i += 5; } else if(a[i] == 'n' && a[i+1] == 'i') { ans = ans * 10 + 9; i += 4; } } return ans; } int main() { char str1[205], str2[205]; while(gets(str1) != NULL) { gets(str2); printf("%d\n", fun(str1) + fun(str2)); } return 0; }
郑轻第六届校赛 -- 部分题解