HHTC

HHTC_学校集训编程题目（9）（个人赛_3）

C - Character Recognition?G - Good TeacherJ - Joking with Fermat's Last TheoremL - Last BloodA - 电子锁F - 自动驾驶系统H - 三色抽卡游戏I - 质数串 由于很菜，这几天的比赛也没做出来几个题，，，，， 这里就记录一下这几天做的几道编程题目吧 同样有些题目是听了别人的解题思路解决的~~

C - Character Recognition?

挺简单的一道题目！！！ 直接进行判断就好了！！ AC代码：

#include <stdio.h> #include <iostream> #include <stdlib.h> #include <string.h> #include <string> #include <map> #include <set> #include <math.h> #include <vector> #include <algorithm> using namespace std; char a[5][50]; int main(){ int n; cin>>n; for(int i=0;i<5;i++){ getchar(); for(int j=0;j<4*n;j++){ cin>>a[i][j]; } } for(int j=0;j<n;j++){ if(a[0][4*j] == '.'){ cout<<"1"; }else if(a[3][4*j] == '*'){ cout<<"2"; }else{ cout<<"3"; } } cout<<endl; return 0; }

G - Good Teacher

一道模拟题目，就是判断所处的位置在何处~ 一开始left和right没有初始化好，wa了几次！！ AC代码：

#include <stdio.h> #include <iostream> #include <stdlib.h> #include <string.h> #include <string> #include <map> #include <set> #include <math.h> #include <vector> #include <algorithm> using namespace std; string s[105]; int main(){ int n,m; cin>>n; for(int i=1;i<=n;i++) cin>>s[i]; cin>>m; while(m--){ int x; cin>>x; int left = 0,right = 0; if(s[x] == "?"){ left = right = x; while(left >= 1 || right <= n){ if(left > 1){ left--; } if(right < n){ right++; } //cout<<left<<" "<<right<<endl; if(s[left] != "?" && s[right] != "?" && (abs(right - x) == abs(left - x))){ cout<<"middle of "<<s[left]<<" and "<<s[right]<<endl; break; }else if(s[left] != "?"){ for(int i=0;i<abs(left-x);i++){ cout<<"right of "; } cout<<s[left]<<endl; break; }else if(s[right] != "?"){ for(int i=0;i<abs(right-x);i++){ cout<<"left of "; } cout<<s[right]<<endl; break; } } }else{ cout<<s[x]<<endl; } } return 0; }

J - Joking with Fermat’s Last Theorem

就是给出两个数XY，求这个范围内满足a^3+b^3 = c*10+3的等式数目，x<a,b,c<y 可以经过化简缩小范围，不然会超时！！！ AC代码：

#include <stdio.h> #include <iostream> #include <stdlib.h> #include <string.h> #include <string> #include <map> #include <set> #include <math.h> #include <vector> #include <algorithm> using namespace std; int main() { int n,m,k=1; while(scanf("%d %d",&n,&m) != EOF){ cout<<"Case "<<k++<<": "; int sum = 0; int num = pow(m*10+3,1.0/3); for(int i=n;i<=num;i++){ for(int j=n;j<=num;j++){ if((i*i*i + j*j*j) % 10 == 3 && i*i*i + j*j*j <= m*10 + 3) sum++; } } cout<<sum<<endl; } return 0; }

L - Last Blood

大意就是求每一个题目最后一个提交正确的队伍，和时间 直接模拟即可，我用map进行操作结果错误n次！！！ 改用结构体，正确~~ AC代码：

#include<string.h> #include<stdio.h> #include<string> #include<math.h> #include<iostream> #include<algorithm> #include<map> using namespace std; struct node { int t; int a; string n; } ss[100]; int b[1001][13]; main() { int n,m,t,i; int ti,dw; char a; string tm,z; cin>>n>>m>>t; for(i=0; i<n; i++) { ss[i].t=-1; ss[i].n=""; a=i+'A'; ss[i].n+=a; } while(t--) { cin>>ti>>dw>>tm>>z; for(i=0; i<n; i++) { if(ss[i].n==tm) { if(ss[i].t<=ti&&z=="Yes"&&b[dw][i]==0) { ss[i].t=ti; ss[i].a=dw; } break; } } if(z=="Yes") b[dw][i]=1; } for(i=0; i<n; i++) { if(ss[i].t!=-1) cout<<ss[i].n<<" "<<ss[i].t<<" "<<ss[i].a<<endl; else cout<<ss[i].n<<" - -\n"; } }

A - 电子锁

这是杭州电子科技大学第九十届程序设计竞赛。以往每个选手在解锁电脑时都需要将信封里的密码条拿出来，将上面的密码输入到电脑中。这回不太一样，学校刚安装了一批电子锁，选手只需要将密码条放在电脑的摄像头前，电脑就会自动识别出上面的密码。 每个选手的密码都是一个仅由大小写英文字母和数字’0’到’9’组成的字符串。 你是这场比赛的技术人员，就在比赛即将开始前的几分钟，你发现打印的密码条上数字’0’和大写字母’O’，以及小写字母’l’和大写字母’I’过于相似。你对学校新引进的电子锁不太放心，于是决定修改识别部分的逻辑，使得’0’和’O’、'l’和’I’也算匹配。 比赛马上就要开始了，抓紧时间吧！

Input

第一行包含一个正整数$T(1\le T\le 100)$，表示测试数据的组数。 每组数据第一行包含一个正整数$n(1\le n\le 20)$，表示密码的长度。 第二行包含一个长度为$n$的字符串$A$，表示密码条上的密码。 第三行包含一个长度为$n$的字符串$B$，表示电子锁的识别结果。

Output

对于每组数据输出一行，如果$A$和$B$匹配，输出OK，否则输出NO。

Sample Input

2 3 aO2 a02 3 I45 l46

Sample Output

OK NO

就是字符串匹配的问题，我把l看成了1，wa了好几次，噗！！！ AC代码：

#include <stdio.h> #include <iostream> #include <stdlib.h> #include <string.h> #include <string> #include <map> #include <set> #include <math.h> #include <vector> #include <algorithm> using namespace std; char a[50],b[50]; int main(){ int T,n; cin>>T; while(T--){ cin>>n; cin>>a; cin>>b; if(strlen(a) != strlen(b)){ cout<<"NO"<<endl; continue; } for(int i=0;i<strlen(a);i++){ if(a[i] == 'O') a[i] = '0'; if(a[i] == 'l') a[i] = 'I'; if(b[i] == 'O') b[i] = '0'; if(b[i] == 'l') b[i] = 'I'; } if(strcmp(a,b)) cout<<"NO"<<endl; else cout<<"OK"<<endl; } return 0; }

F - 自动驾驶系统

一家科技公司有一块试验地用于测试自动驾驶系统。试验地由n×m个格子组成，从上到下依次编号为第1到n行，从左到右依次编号为第1到m列。试验车位于其中的某个格子上，每次自动驾驶系统可以控制汽车往上下左右移动一格。汽车不能走出边界，也不能碰到障碍格。 你需要编写自动驾驶系统中的导航部分。在测试的一开始，试验地里没有任何障碍。你的程序会依次收到q条信息，它们的格式是以下两种之一： ? x y，表示询问从第1行第1列的格子出发，到达第x行第y列的格子最少需要移动多少次。 * x y，表示第x行第y列的格子变成了障碍格。

Input

第一行包含一个正整数T(1≤T≤5)，表示测试数据的组数。 每组数据第一行包含三个正整数n,m,q(1≤n,m≤50,1≤q≤100000)，表示试验地的尺寸以及信息的数量。 接下来m行，每行描述一条信息。其中1≤x,y≤n，保证每个格子不会被重复变成障碍格多次，且(1,1)不会变成障碍格。

Output

对于每个询问输出一行一个整数，即最少移动次数，若无法到达请输出−1。

Sample Input

1 3 4 5 ? 2 2 * 1 2 ? 2 2 * 2 1 ? 2 2

Sample Output

2 2 -1

题意很简单，就是让你求0，0到x，y的最小步数，？表示询问，*表示添加障碍物 DFS肯定超时，所以采用bfs，貌似模板题吧 AC代码：

#include <stdio.h> #include <iostream> #include <stdlib.h> #include <string.h> #include <string> #include <map> #include <set> #include <queue> #include <vector> #include <algorithm> using namespace std; int T,n,m,k; int a[55][55]; int vis[55][55]; int d[4][2] = {1,0,0,1,-1,0,0,-1}; struct node{ int x,y; }; void bfs(){ memset(vis,-1,sizeof(vis)); vis[1][1] = 0; node dd,ff; dd.x = 1; dd.y = 1; queue<node> q; q.push(dd); while(!q.empty()){ dd = q.front(); q.pop(); for(int i=0;i<4;i++){ node ff = dd; ff.x += d[i][0]; ff.y += d[i][1]; if(vis[ff.x][ff.y] != -1) continue; if(a[ff.x][ff.y] == 1) continue; if(ff.x < 1 || ff.x > n || ff.y < 1 || ff.y > m) continue; vis[ff.x][ff.y] = vis[dd.x][dd.y] + 1; q.push(ff); } } } int main(){ scanf("%d",&T); while(T--){ memset(a,0,sizeof(a)); scanf("%d %d %d",&n,&m,&k); bfs(); while(k--){ char z[5]; int x,y; scanf("%s %d %d",z,&x,&y); if(z[0] == '?'){ printf("%d\n",vis[x][y]); } if(z[0] == '*'){ a[x][y] = 1; bfs(); } } } return 0; }

H - 三色抽卡游戏

你的对手太坏了！在每年的年度三色抽卡游戏锦标赛上，你的对手总是能打败你，他的秘诀是什么？ 在每局三色抽卡游戏中，有n个卡组，每个卡组里所有卡片的颜色都相同，且颜色只会是红®、绿(G)、蓝(B)中的一种。第i个卡组有vi张卡片。 对决双方每次只能选择一个还未抽完卡的卡组，从中拿走若干张卡片，可以全拿走，但不能一张都不拿。你只能选择颜色为红或者绿的卡组，而对手只能选择颜色为蓝或者绿的卡组。 你是先手，你和对手轮流行动，谁不能操作了就输了。 因为你的对手每次总是能打败你，你决定写一个程序来帮助你做出决策。 给定游戏刚开始时的卡组情况，你的程序需要判断假设双方都按照最优策略操作，那么你是否会赢？

Input

第一行包含一个正整数T(1≤T≤100)，表示测试数据的组数。 每组数据第一行包含一个正整数n(1≤n≤1000)，表示卡组的数量。 接下来n行，每行一个字符ci(ci∈{′R′,′G′,′B′})和一个正整数vi(1≤vi≤1000)，分别表示第i个卡组的颜色以及卡片数量。

Output

对于每组数据输出一行，若你能赢，输出YES，否则输出NO。

Sample Input

3 2 R 2 B 3 2 B 2 R 3 3 R 5 B 6 G 1

Sample Output

NO YES NO

尼姆博弈论，，，， 当异或和为0时表示必败~ 先不用管红色和蓝色，处理好绿色的胜负 当自己绿色能够胜利时，并且红色数>=蓝色数，这是必胜 当自己绿色不能获得胜利时，红色数>蓝色数，这是必胜 AC代码：

#include <stdio.h> #include <iostream> #include <stdlib.h> #include <string.h> #include <string> #include <map> #include <set> #include <queue> #include <vector> #include <algorithm> using namespace std; int t,n,x,a,b,c; char ch; int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); a=b=c=0; for(int i=1; i<=n; i++) { cin >> ch >> x; if(ch=='R') a+=x; else if(ch=='B') b+=x; else if(ch=='G') c ^= x; } if(c) a++; if(a>b) puts("YES"); else puts("NO"); } return 0; }

I - 质数串

一个正整数x是质数，当且仅当x≥2且x不是任何一个[2,x−1]的数的倍数。 一个数字串是’‘质数串’’，当且仅当它的每个非空连续子串表示的数字都是质数。 例子1：“373"是质数串，它的子串有"3”、“37”、“373”、“7”、“73”、“3”，这些串表示的数字都是质数。 例子2："55"不是质数串，因为"55"这个子串表示的数字不是质数。 相信聪明的你一定已经发现了一个事实，那就是质数串的限制很紧，所以质数串的数量其实非常稀少。 给定一个长度为n的数字串S，请统计它有多少个非空连续子串是质数串。注意两个子串如果位置不同也算不同，比如"373373"中，"373"要算入答案两次。

Input

第一行包含一个正整数T(1≤T≤30)，表示测试数据的组数。 每组数据第一行包含一个正整数n(1≤n≤100000)，表示数字串的长度。 第二行包含一个长度为n的仅由字符’1’到’9’组成的字符串S。

Output

对于每组数据输出一行一个整数，即是质数串的非空连续子串数量。

Sample Input

3 6 373373 5 37373 3 313

Sample Output

12 11 2

不多说，题目意思也不难理解，找出所有的质数串发现只有几个，直接枚举就好了 AC代码：

#include <stdio.h> #include <iostream> #include <stdlib.h> #include <string.h> #include <string> #include <map> #include <set> #include <queue> #include <vector> #include <algorithm> using namespace std; int main() { string s; int T; cin>>T; while(T--) { int sum=0; int n; cin>>n; cin>>s; for(int i=0; i<n; i++) { if(s[i]=='2') sum++; if(s[i]=='3') sum++; if(s[i]=='5') sum++; if(s[i]=='7') sum++; if(s[i]=='2'&&s[i+1]=='3') sum++; if(s[i]=='3'&&s[i+1]=='7') sum++; if(s[i]=='5'&&s[i+1]=='3') sum++; if(s[i]=='7'&&s[i+1]=='3') sum++; if(s[i]=='3'&&s[i+1]=='7'&&s[i+2]=='3') sum++; } cout<<sum<<endl; } return 0; } /* 2 3 5 7 23 37 53 73 373 */