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元的张数，每次需要找零时，根据顾客支付的面值种类来进行判断：

  1. 若为5元，则不需要找零，同时增加5元面值的数量。
  2. 若为10元，则判断自身5元面值的数量是否为0，若为0则无法正确找零，标记flag为0，若不为0则让5元面值数量减一。
  3. 若为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(动态规划)算法进行优化。