http://xcacm.hfut.edu.cn/contest.php?cid=1009
打了一下午，最后一道题2333，前面比较基础。
问题 A: 求成绩最大值和最小值
题目描述
GX是宣城校区A班的一名同学，如果GX在B班的话，那么这两个班的平均成绩都会提高.现在给出A班与B班的人数以及成绩，求GX成绩可能的最大值和最小值。
输入
第一行有两个正整数n（2 <= n <= 50) 和m（1 <= m <= 50)，分表代表A班与B的人数
第二行有n-1个数，表示A班中除了GX，其他n-1人的成绩（每个人的成绩都为正整数，且小于100）
第三行有m个数，表示B班m个人的成绩
输出
对于每组数据，输出一行，包含两个数，分别为GX成绩可能的最小值和最大值，不存在输出-1 -1
样例输入
4 3
5 5 5
4 4 3
6 5
5 5 4 5 3
1 3 2 2 1
样例输出
4 4
2 4
各种判断即可
#include<iostream> #include<cstdio> using namespace std; int d[100]; int c[100]; int main() { int a,b,i,j,n,m,sum=0,num=0,max=0,min=0; while(~scanf("%d%d",&n,&m)) { min=0;max=0;a=0;b=0;j=0;sum=0;num=0; for(i=1;i<n;i++) {scanf("%d",&d[i]);sum+=d[i];} for(i=1;i<=m;i++){scanf("%d",&c[i]);num+=c[i];} a=sum/(n-1); j=sum%(n-1); b=num/m; if(a==b||a<b){cout<<"-1"<<" "<<"-1"<<endl;continue;} if(j>0){max=a;} else if(j==0){max=a-1;} min=b+1; if(min>max){cout<<"-1"<<" "<<"-1"<<endl;continue;} cout<<min<<" "<<max<<endl; } return 0; }
问题 B: 打扫房间
题目描述
某天，老师派GX去打扫一间神秘的空房间，这间房间的地面有n*n块地砖，每块砖用0表示未打扫，1表示已打扫。GX有一个奇怪的习惯，他喜欢每次只打扫一整列地砖，每当他打扫完一整列之后，这间房间会出现一个神秘的现象，未打扫的地砖会变为已打扫，已打扫的地砖会变为未打扫（也就是1会变成0，而0会变成1）。按照GX的打扫方法，请输出最多能产生多少行全都是已打扫的地砖。
输入
第一行输入n（2<= n <= 100）
接下来输入一个n*n的矩阵
输出
对于每组数据，输出一个数，表示最多能产生多少行全都是已打扫的地砖
样例输入
4
0101
1000
1111
0101
3
111
111
111
样例输出
2
3
杰神说20行的代码，用map果然。
#include<iostream> #include<cstdio> #include<string> #include<map> using namespace std; int main() { int n; while(~scanf("%d",&n)) { int mun=0; map<string,int>donser; for(int i=1;i<=n;i++) { char sb[105]; scanf("%s",sb); mun=max(mun,++donser[sb]); } cout<<mun<<endl; } return 0; }
问题 C: 扑鼠
题目描述
GX养的一只仓鼠最近跑进了一个神秘的城堡里，他准备在这个有n个房间的城堡中抓捕他的仓鼠，他在房间0放了一块食物，根据抓鼠攻略，这块食物可以吸引距离它D的仓鼠，但是仓鼠还是没有出现，现在给你一张这个城堡的地图，上面标有各个房间的关系，已知每个房间都相连且距离为1，GX想知道他的仓鼠可能出现在哪些房间，请输出这些房间的总数
输入
第一行输入n(0<n<=100000)和D(0<D<n)
接下来的n-1行为房间的连接关系，每行有两个数x，y代表房间x与房间y相邻
输出
对于每组数据，输出一个数，表示仓鼠可能出现的房间的数量
样例输入
10 2
0 1
0 2
0 3
1 4
1 5
2 6
3 7
4 8
6 9
样例输出
2
其实就是HDU4707 ，DFS
#include<set> #include<cstdio> #include<vector> #include<cstring> #include<iostream> using namespace std; set<int>donser; vector<int>d[100010]; int r=0,num=0,lable=0,deep=0; void dfs(int i) { if(deep>=r||d[i].empty()){donser.insert(i);return;} while(d[i].size()>0) { deep++; donser.insert(i); lable=d[i].back(); d[i].pop_back(); dfs(lable); deep--; } } int main() { int n,b,x,y; while(~scanf("%d%d",&n,&r)) { for(b=1;b<n;b++) { scanf("%d%d",&x,&y); d[x].push_back(y); } dfs(0); cout<<n-donser.size()<<endl; r=num=lable=deep=0; donser.clear(); memset(d,0,sizeof(d)); } return 0; }
问题 D: 电梯
题目描述
实验楼有一部神秘的电梯，它只有“上”和“下”两个按钮，实验楼的每一层都标有一个值K，第i层的值为Ki，如果按了“上”按钮，会从第i层升到第i+Ki层；如果按了“下”按钮则会从第i层降到第i-Ki层，已知能到的层数为1到N层，GX想从第A层上到第B层，现在给你N,A,B和一串数K1到Kn，请求出GX从A到B，至少按下多少个按钮。
输入
第一行输入N,A,B( 1 <= N,A,B <= 300) ，表示实验楼共有N层，起点为A，终点为B
第二行输入N个数，表示K1到Kn
输出
对于每组数据，输出一个数，表示GX从A到B，至少按下多少个按钮，如果GX无法到达B，请输出-1.
样例输入
5 1 5
3 3 1 2 5
样例输出
3
BFS最短路问题，以前没好好撸过BFS也算是涨姿势了。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; int d[310],n,lable=0; bool str[310]; struct floor { int a; int b; }; void bfs(int x,int y) { floor temp; temp.a=x; temp.b=0; queue<floor>donser; donser.push(temp); lable=0; while(!donser.empty()) { floor temp_c; temp_c=donser.front(); donser.pop(); floor teemp1=temp_c; floor teemp2=temp_c; if(temp_c.a==y){lable=1;cout<<temp_c.b<<endl;break;} if(temp_c.a+d[temp_c.a]<=n&&!str[temp_c.a+d[temp_c.a]]) { teemp1.a=temp_c.a+d[temp_c.a]; teemp1.b++; donser.push(teemp1); str[teemp1.a]=true; } if(temp_c.a-d[temp_c.a]>=1&&!str[temp_c.a-d[temp_c.a]]) { teemp2.a=temp_c.a-d[temp_c.a]; teemp2.b++; donser.push(teemp2); str[teemp2.a]=true; } } if(!lable) cout<<"-1"<<endl; } int main() { int a,b,i; while(~scanf("%d%d%d",&n,&a,&b)) { for(i=1;i<=n;i++) { scanf("%d",&d[i]); } bfs(a,b); memset(str,0,sizeof(str)); } return 0; }
问题 E: 1D Maze
题目描述
1D people live in a 1D country. Everything in the country is one-dimensional, and everything is simple and clear: just a UPPER-CASE LETTER from A to Z. Even a 1D world has problems, though; for instance, finding an exit from a maze. An idea of a 1D maze might seem weird to us, but not to 1D people. Escaping from such a maze is a hard and vital task for them. They solve this task in a following way.
The maze has only 1 entrance as well as 1 exit. Once entered the maze, the 1D person could only move in ONE direction. In the other words, from the entrance to the exit. During the exploration, he might collect several UPPER-CASE LETTERS. Each letter has its unique weight, which are arranged in alphabetical order. For example, The weight of 'A' equals to 1, and 'B' equals to 2, and 'C' equals to 3, and so on. After he exits the maze, he should calculate the sum of the weight of all his letters, which will determine whether he can survive or go die. Here is the rule : suppose the sum is S, and another integer T is given either. If S mod T = 0, he will survive. Or he might be killed by the king of the country because of his misfortune.
All the 1D residents were extremely terrified of the maze. But with the help of a superability named esxgxlism, they have got the map of the maze and the integer T in advance. Now they turn to you for help, and your task is to forecast the ending of the maze.
输入
There are only 2 lines.
The first line contains a string , which describes the maze.
The second line contains the integer T.
It is guaranteed that the string is composed of UPPER-CASE LETTER only and T is not equals to 0.
输出
Your program should output your forecast.
If the 1D person can survive, you should print "STAY", or print "BYE" please.
Notice that the output doesn't contains quotation marks.
样例输入
HVNG
23
COMETQ
73
样例输出
BYE
STAY
神奇的题，一开始题目表意不清WA了6次，2333.念英文念了20分钟....
#include<iostream> #include<cstdio> #include<string> using namespace std; int main() { char d[100]; string sb; while(~scanf("%s",d)) { int i=0,sum=0,donser=1; while(d[i]!=' ') { sum+=d[i]-64; i++; } scanf("%d",&donser); if(!donser){cout<<"BYE";continue;} if((bool(sum%donser))){cout<<"BYE";} else cout<<"STAY"; cout<<endl; } return 0; }