[题解]第六届ACM/ICPC程序设计新生赛
A. 开宴「群游万象」
多样例读入的示范题,只要根据题目的格式读入数据,没有任何难点。
#include<stdio.h> #include<algorithm> int main() { int t, n, m; scanf("%d", &t); while(t --) { scanf("%d", &n); int ans = 0; for(int i = 0; i < n; ++ i) { int tmp; scanf("%d", &tmp); ans += tmp; } printf("%d\n", ans); } }
这种给定个数并读取固定数量的数据的方法非常常见,也许在课程设计就会遇到。
B. 0号字符搬运工
遇到非0的字符,直接输出就可以;遇到为0的字符,统计个数,最后循环输出。
#include<stdio.h> int main() { int n, rec0 = 0; scanf("%d", &n); for(int i=0; i<n; ++i) { int x; scanf("%d", &x); if(x == 0) ++rec0; else printf("%d ", x); } while(rec0--) printf("0 "); return 0; }
C. 还是头发重要
首先有一个知识点,即,但是不知道这个也没有关系,一般也能记住的大概值,正确的答案需要的取值至少到小数点后8位才可以。
#include <bits/stdc++.h> using namespace std; const double PI = acos(-1); #define pi 3.1415926535898 //对 //#define pi 3.1415926 错 int main() { int n; scanf("%d",&n); printf("%.3f\n",pow(n,2)/(2*PI)); return 0; }
D. 鸡哥哥的烦恼
每次所能涂色的最大块数由上一个涂色的状态所决定。那么从初始什么也没有的状态开始涂色,能涂的最多的块数必定是最外围两两错开一格的方式;而第二次涂色时,由于第一次涂色的方式为两两错开,那么第二次涂色必定可以将最外围一圈涂满,并且还可以继续向内扩展,此时问题又回到了第一次涂色如何涂最多的块数。
根据上面的规律可以发现,涂满方格的方式是类似螺旋状从外向内涂,每次可以向内推进2格,答案即为
#include<stdio.h> int main() { int n; scanf("%d", &n); printf("%d\n", n / 2 + 1); }
E. 扫地机器人
优先考虑斜向走到最靠下方的点,再横向/竖向走到终点。
#include<stdio.h> int main() { int t, x, y, res; scanf("%d", &t); while(t --) { scanf("%d %d", &x, &y); if(x > y) { int z = x; x = y; y = z; } res = x * 2; if(x < y) { res += (y - x) * 2 - 1; } printf("%d\n", res); } return 0; }
F. wjjの库存
可以发现每次需要判断的区间为一段连续的区间,因此可以将值累加起来存入数组sum[ ],需要判断区间[l, r]时,输出sum[r] - sum[l - 1]即可。这种累加通过下标相减统计的方法也称为前缀和。
#include<bits/stdc++.h> using namespace std; long long int sum[20000000]; int main(){ int n, t, z; scanf("%d", &n); sum[0]=0; for(int i = 1; i <= n; i ++){ scanf("%d", &t); sum[i] = t + sum[i-1]; } for(int i = 0; i < z; i ++){ int l, r; scanf("%d %d", &l, &r); printf("%lld\n", sum[r] - sum[l - 1]); } }
G. Adjacency Matrix
根据题目要求对二维数组中的数据进行更改即可,需要注意的是,对于每个点自身,一定是可达的,即对于在范围中的每个,需要置maze[i][i]为1。
#include<stdio.h> int main() { int a[55][55]; for(int i = 0; i < 55; ++ i) { for(int j = 0; j < 55; ++ j) { if(i!=j) a[i][j] = -1; else a[i][j] = 1; } } int n, m, x, y; scanf("%d %d", &n, &m); while(m--) { scanf("%d %d", &x, &y); a[x][y]=a[y][x]=1; } for(int i=0;i<n;++i) { for(int j=0;j<n;++j) { if(j) printf(" "); printf("%d", a[i][j]); } puts(""); } }
这种存图方法叫邻接矩阵,是一种常见的存图方式,可以方便的获取两个点之间是否可达,但若要获取对于特定点的所有边,则显得很慢,此时还有另外一种存图的方法:邻接表,可以方便的获取每个点的连边。
H. 小明卖柠檬
记录5元、10元和20元的张数,每次需要找零时,根据顾客支付的面值种类来进行判断:
- 若为5元,则不需要找零,同时增加5元面值的数量。
- 若为10元,则判断自身5元面值的数量是否为0,若为0则无法正确找零,标记flag为0,若不为0则让5元面值数量减一。
- 若为20元,优先判断10元的数量是否足够,若足够则优先支付10元(因为5元面值能够应对所有情况),再判断5元面值的数量,若10元不足,则需要判断5元面值是否有3张。
#include<stdio.h> int main() { int n, rec5 = 0, rec10 = 0, flag = 1; scanf("%d", &n); for(int i = 0; i < n && flag; ++ i) { int x; scanf("%d", &x); if(x == 5) rec5 ++; else if(x == 10) { if(rec5 == 0) flag = 0; else { ++ rec10; -- rec5; } } else if(x == 20) { if(rec10 == 0) { if(rec5 >=3 ) rec5 -= 3; } else { if(rec5 == 0) flag = 0; else { ++ rec10; -- rec5; } } } } if(flag) printf("Yes"); else printf("No"); return 0; }
I. 松果弹抖闪电鞭
类似于等差数列求和,将最大的和最小的两两匹配即为可以创造出数量最多的话化劲。
#include<stdio.h> int main() { int t, n; scanf("%d", &t); while(t --) { scanf("%d", &n); printf("%d\n", n - n / 2); } }
J. 宴散「华灯共影」
首先,m盏灯n个地点的方案数可以归结为m盏灯n-1个地点的方案数加上n个地点都已经有一盏灯即m-n盏灯和n个地点的方案数之和;不断细分,直到没有灯,或者地点数只有一个的时候,此时返回方案数1;而当地点数大于灯的数量时,必定存在地点没有灯,而由于与顺序无关,因此我们不需要关心到底哪几个地点不存在灯,只需要求m盏灯m个地点的方案。
而我们并不需要关心中间的过程,只需要推出当前状态的后续不断向下递归求的,这种方法被称为分治。
#include<stdio.h> long long f(long long m, long long n) { if(m == 0 || n == 1) return 1; if(m < n) return f(m, m); return f(m, n - 1) + f(m - n, n); } int main() { int t; long long m, n; scanf("%d", &t); for(int i = 0; i < t; ++ i) { scanf("%lld %lld", &m, &n); printf("%lld\n", f(m,n)); } }
这种方法中间存在许多次冗余的计算,可以使用dp(动态规划)算法进行优化。