[关闭]
@ZSCDumin 2018-12-14T10:26:21.000000Z 字数 15404 阅读 560

CCF计算机软件能力认证试题

c++

出现次数最多的数

  1. #include <iostream>
  2. #include<cstdio>
  3. using namespace std;
  5. int main() {
  7.     int num[10001] = { 0 };
  8.     int n;
  9.     cin >> n;
  11.     for (int i = 0; i < n; i++)
  12.     {
  13.         int t;
  14.         cin >> t;
  15.         num[t] ++;
  16.     }
  18.     int max = 0, index = 0;
  19.     for (int i = 10000; i >= 0; i--)
  20.     {
  21.         if (num[i] >= max){
  22.             max = num[i];
  23.             index = i;
  24.         }
  25.     }
  26.     cout << index << endl;
  27.     return 0;
  28. }

ISBN号码

  1. #include <iostream>
  2. #include<cstring>
  3. using namespace std;
  5. int main() {
  7.     char s[20];
  8.     int num[20] = { 0 };
  9.     int index = 0;
  10.     cin >> s;
  11.     int len = strlen(s);
  12.     for (int i = 0; i < len; i++){
  13.         if (s[i] == '-'){
  14.             continue;
  15.         }
  16.         else{
  17.             num[index++] = s[i] - '0';
  18.         }
  19.     }
  20.     int sum = 0;
  21.     for (int i = 0; i < index - 1; i++){
  22.         sum += num[i] * (i + 1);
  23.     }
  24.     sum = sum % 11;
  26.     if (sum == 10 && s[len - 1] == 'X' || sum == num[index - 1]){
  27.         cout << "Right" << endl;
  28.     }
  29.     else{
  30.         if (sum == 10)
  31.             s[len - 1] = 'X';
  32.         else
  33.             s[len - 1] = sum + '0';
  34.         cout << s << endl;
  35.     }
  36.     return 0;
  37. }

跳一跳

  1. #include <iostream>
  2. using namespace std;
  4. int main() {
  6.     int num[31];
  7.     int t,index=0;
  8.     while(1) {
  9.         cin >> t;
  10.         num[index++]=t;
  11.         if(t==0) {
  12.             break;
  13.         }
  14.     }
  15.     int sum=0;
  16.     int count =1;
  17.     for(int i=0; i<index; i++) {
  18.         if(num[i]==1) {
  19.             sum+=1;
  20.             count=1;
  21.         } else if(num[i]==2) {
  22.             sum+=count*2;
  23.             count ++;
  24.         } else {
  25.             break;
  26.         }
  27.     }
  28.     cout<<sum <<endl;
  29.     return 0;
  30. }

碰撞的小球

  1. #include <iostream>
  2. using namespace std;
  3. int num[105];
  5. int main() {
  7.     int dire[105];
  8.     int n, L, t;
  10.     cin >> n >> L >> t;
  12.     for (int i = 0; i < n; i++) {
  13.         cin >> num[i];
  14.         dire[i] = 1;
  15.     }
  17.     for (int i = 1; i <= t; i++) { //计时器
  18.         for (int j = 0; j < n; j++) {
  19.             //判断方向
  20.             if (num[j] == L && dire[j] == 1 || num[j] == 0 && dire[j] == -1){
  21.                 dire[j] *= -1;
  22.             }
  23.             else {
  24.                 for (int k = 0; k < n; k++){
  25.                     if (num[k] == num[j] && k != j){
  26.                         dire[j] *= -1;
  27.                         dire[k] *= -1;
  28.                     }
  29.                 }
  30.             }
  31.             //移动
  32.             num[j] += dire[j];
  33.         }
  34.     }
  36.     for (int j = 0; j < n; j++) {//输出结果
  37.         if (j == n - 1)
  38.             cout << num[j] << endl;
  39.         else
  40.             cout << num[j] << " ";
  41.     }
  42.     return 0;
  44. }

最小差值

  1. #include <iostream>
  2. #include <cmath>
  3. #include <algorithm>
  4. using namespace std;
  6. int num[1005];
  8. int main() {
  10.     int n;
  11.     cin >> n;
  12.     for (int i = 0; i < n; i++){
  13.         cin >> num[i];
  14.     }
  15.     sort(num, num + n);
  16.     int min = 99999;
  17.     for (int i = 0; i < n - 1; i++){
  18.         if (num[i] == num[i + 1]){
  19.             min = 0;
  20.             break;
  21.         }
  23.         if (min > abs(num[i] - num[i + 1]))
  24.         {
  25.             min = abs(num[i] - num[i + 1]);
  26.         }
  27.     }
  28.     cout << min << endl;
  29.     return 0;
  31. }

游戏

  1. #include <iostream>
  2. #include <cmath>
  3. #include <queue>
  4. #include <algorithm>
  5. using namespace std;
  7. int num[1005];
  9. int main() {
  11.     int N, K, num = 1;
  12.     queue<int> list;
  13.     cin >> N >> K;
  15.     for (int i = 1; i <= N; i++){
  16.         list.push(i);
  17.     }
  19.     while (list.size() > 1){
  20.         int top = list.front(); //取第一个元素
  21.         list.pop();  //删除第一个元素
  22.         if (num % K != 0 && (num % 10) != K){
  23.             list.push(top);
  24.         }
  25.         num++;
  26.     }
  28.     cout << list.front();
  29.     return 0;
  30. }

版本二(有点瑕疵,样例: 3 1通不过)

  1. #include <iostream>
  2. #include <cmath>
  3. #include <algorithm>
  4. using namespace std;
  6. int num[1005];
  8. int main() {
  10.     int n, k;
  11.     cin >> n >> k;
  12.     int resNum = n;
  13.     for (int i = 0; i < n; i++){
  14.         num[i] = i + 1;
  15.     }
  16.     int count = 0;
  17.     while (resNum > 1){
  18.         for (int i = 0; i < n; i++){
  19.             if (num[i] != -1){
  20.                 count++;
  21.                 if (count % k == 0 || count % 10 == k)
  22.                 {
  24.                     resNum--;
  25.                     num[i] = -1;
  26.                 }
  27.             }
  28.         }
  29.     }
  30.     for (int i = 0; i < n; i++){
  31.         if (num[i] != -1){
  32.             cout << num[i];
  33.             break;
  34.         }
  35.     }
  36.     return 0;
  38. }

修订版

  1. #include <iostream>
  2. #include <cmath>
  3. #include <algorithm>
  4. using namespace std;
  6. int num[1005];
  8. int main() {
  10.     int n, k;
  11.     cin >> n >> k;
  12.     int resNum = n;
  13.     for (int i = 0; i < n; i++){
  14.         num[i] = i + 1;
  15.     }
  16.     int count = 0;
  17.     for (int i = 0;; i++){
  18.         if (resNum <= 1){
  19.             break;
  20.         }
  21.         if (num[i%n] != -1){
  22.             count++;
  23.             if (count % k == 0 || count % 10 == k)
  24.             {
  25.                 resNum--;
  26.                 num[i%n] = -1;
  27.             }
  28.         }
  29.     }
  31.     for (int i = 0; i < n; i++){
  32.         if (num[i] != -1){
  33.             cout << num[i];
  34.             break;
  35.         }
  36.     }
  37.     return 0;
  39. }

分蛋糕

  1. #include <iostream>
  2. #include <cmath>
  3. #include <queue>
  4. #include <algorithm>
  5. using namespace std;
  6. int num[1005];
  7. int main() {
  8.     int n, k;
  9.     int count = 0;
  10.     cin >> n >> k;
  11.     for (int i = 0; i < n; i++){
  12.         cin >> num[i];
  13.     }
  14.     int sum = 0;
  15.     for (int i = 0; i < n; i++){
  16.         if (i == n - 1 && sum + num[i] < k){
  17.             count++;
  18.         }
  19.         else
  20.         {
  21.             sum += num[i];
  22.             if (sum >= k){
  23.                 count++;
  24.                 sum = 0;
  25.             }
  26.         }
  27.     }
  28.     cout << count << endl;
  29.     return 0;
  30. }

中间数

  1. #include <iostream>
  2. #include <cmath>
  3. #include <queue>
  4. #include <algorithm>
  5. using namespace std;
  6. int num[1005];
  7. int main() {
  8.     int n;
  9.     int flag = 0;
  10.     cin >> n;
  11.     for (int i = 0; i < n; i++){
  12.         cin >> num[i];
  13.     }
  14.     for (int i = 0; i < n; i++){
  15.         int re1 = 0, re2 = 0;
  16.         for (int j = 0; j < n; j++){
  17.             if (i != j){
  18.                 if (num[i] < num[j])
  19.                     re1++;
  20.                 if (num[i] > num[j])
  21.                     re2++;
  22.             }
  23.         }
  24.         if (re1 == re2)
  25.         {
  26.             flag = 1;
  27.             cout << num[i] << endl;
  28.             break;
  29.         }
  30.     }
  31.     if (flag == 0)
  32.         cout << "-1" << endl;
  33.     return 0;
  34. }

最大波动

  1. #include <iostream>
  2. #include <cmath>
  3. #include <queue>
  4. #include <algorithm>
  5. using namespace std;
  6. int num[1005];
  7. int main() {
  8.     int n;
  9.     int flag = 0;
  10.     cin >> n;
  11.     for (int i = 0; i < n; i++){
  12.         cin >> num[i];
  13.     }
  14.     int max = -1;
  15.     for (int i = 0; i < n-1; i++){
  16.         if (max < abs(num[i] - num[i + 1])){
  17.             max = abs(num[i] - num[i + 1]);
  18.         }
  19.     }
  20.     cout << max << endl;
  21.     return 0;
  22. }

折点计算

  1. #include <iostream>
  2. #include <cmath>
  3. #include <queue>
  4. #include <algorithm>
  5. using namespace std;
  6. int num[1005];
  7. int main() {
  8.     int n;
  9.     cin >> n;
  10.     for (int i = 0; i < n; i++){
  11.         cin >> num[i];
  12.     }
  13.     int count = 0;
  14.     int before = num[0] > num[1] ? 0 : 1;
  15.     int after = 0;
  16.     for (int i = 1; i < n - 1; i++){
  17.         if (num[i] > num[i + 1]){
  18.             after = 0;
  19.         }
  20.         else
  21.         {
  22.             after = 1;
  23.         }
  24.         if (before != after){
  25.             count++;
  26.         }
  27.         before = after;
  28.     }
  29.     cout << count << endl;
  30.     return 0;
  31. }

整数之和

  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4. int main() {
  5.     char n[30];
  6.     cin >> n;
  7.     int sum = 0;
  8.     for (int i = 0; i < strlen(n); i++){
  9.         sum += n[i] - '0';
  10.     }
  11.     cout << sum << endl;
  12.     return 0;
  13. }

数列分段

  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4. int num[1005];
  6. int main() {
  7.     int n;
  8.     cin >> n;
  9.     for (int i = 0; i < n; i++){
  10.         cin >> num[i];
  11.     }
  12.     int sum = 1;
  13.     for (int i = 0; i < n-1; i++){
  14.         if (num[i] != num[i + 1]){
  15.             sum++;
  16.         }
  17.     }
  18.     cout << sum << endl;
  19.     return 0;
  20. }

图像旋转

  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  5. int num[1005][1005];
  7. int main() {
  8.     int n, m;
  9.     cin >> n >> m;
  10.     for (int i = 0; i < n; i++){
  11.         for (int j = 0; j < m; j++){
  12.             cin >> num[i][j];
  13.         }
  14.     }
  15.     int sum = 1;
  16.     for (int i = 0; i < n - 1; i++){
  17.         if (num[i] != num[i + 1]){
  18.             sum++;
  19.         }
  20.     }
  21.     for (int i = m - 1; i >= 0; i--){
  22.         for (int j = 0; j < n; j++){
  23.             cout << num[j][i] << " ";
  24.         }
  25.         cout << endl;
  26.     }
  27.     return 0;
  28. }

门禁系统

  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  5. int num[1005];
  6. int res[1005];
  8. int main() {
  9.     int n;
  10.     cin >> n;
  11.     for (int i = 0; i < n; i++){
  12.         cin >> num[i];
  13.         res[i] = 1;
  14.     }
  15.     for (int i = 1; i < n; i++){
  16.         for (int j = 0; j < i; j++){
  17.             if (num[i] == num[j])
  18.                 res[i]++;
  19.         }
  20.     }
  21.     for(int i = 0; i < n; i++){
  22.         cout << res[i] << " ";
  23.     }
  24.     return 0;
  25. }

相邻数对

  1. #include <iostream>
  2. #include <cmath>
  3. using namespace std;
  5. int num[1005];
  7. int main() {
  8.     int n;
  9.     cin >> n;
  10.     for (int i = 0; i < n; i++){
  11.         cin >> num[i];
  12.     }
  13.     int count = 0;
  14.     for (int i = 0; i < n; i++){
  15.         for (int j = 0; j < n; j++){
  16.             if (i != j)
  17.             {
  18.                 if (abs(num[i] - num[j]) == 1)
  19.                 {
  20.                     count++;
  21.                 }
  22.             }
  23.         }
  24.     }
  25.     cout << count / 2 << endl;
  26.     return 0;
  27. }

相反数

  1. #include <iostream>
  2. #include <cmath>
  3. using namespace std;
  5. int num[1005];
  7. int main() {
  8.     int n;
  9.     cin >> n;
  10.     for (int i = 0; i < n; i++){
  11.         cin >> num[i];
  12.     }
  13.     int count = 0;
  14.     for (int i = 0; i < n; i++){
  15.         for (int j = 0; j < n; j++){
  16.             if (i != j)
  17.             {
  18.                 if (num[i] + num[j] == 0)
  19.                 {
  20.                     count++;
  21.                 }
  22.             }
  23.         }
  24.     }
  25.     cout << count / 2 << endl;
  26.     return 0;
  27. }

除法

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. long long tree[101024];
  5. int n, m, a[101024];
  6. int lowbit(int x)
  7. {
  8.     return -x&x;
  9. }
  10. void update(int x, int v)
  11. {
  12.     for (int i = x; i <= n; i += lowbit(i))
  13.         tree[i] += v;
  14. }
  15. long long getsum(int x)
  16. {
  17.     long long ans = 0;
  18.     for (int i = x; i > 0; i -= lowbit(i))
  19.         ans += tree[i];
  20.     return ans;
  21. }
  22. int main()
  23. {
  24.     int op, l, r;
  25.     int v;
  26.     cin >> n >> m;
  27.     for (int i = 1; i <= n; ++i)
  28.     {
  29.         cin >> a[i];
  30.         update(i, a[i]);
  31.     }
  32.     for (int i = 0; i < m; i++)
  33.     {
  34.         cin >> op;
  35.         if (op == 1)
  36.         {
  37.             cin >> l >> r >> v;
  38.             if (v == 1)
  39.                 continue;
  40.             while (l <= r)
  41.             {
  42.                 if (a[l] >= v&&a[l] % v == 0)
  43.                 {
  44.                     update(l, -(a[l] - a[l] / v));
  45.                     a[l] /= v;
  46.                 }
  47.                 ++l;
  48.             }
  49.         }
  50.         else if (op == 2)
  51.         {
  52.             cin >> l >> r;
  53.             cout << getsum(r) - getsum(l - 1) << endl;
  54.         }
  55.     }
  56.     return 0;
  57. }

字符串匹配

  1. #include <iostream>
  2. #include <string>
  3. #include <algorithm>
  4. using namespace std;
  5. string a[105];
  6. string str;
  7. int n, m;
  8. int main()
  9. {
  10.     string::size_type idx;
  11.     getline(cin, str);
  12.     cin >> n;
  13.     cin >> m;
  14.     getchar();
  15.     for (int i = 0; i < m; i++){
  16.         getline(cin, a[i]);
  17.     }
  18.     if (n == 0){
  19.         transform(str.begin(), str.end(), str.begin(), ::tolower);
  20.         for (int i = 0; i < m; i++){
  21.             string t = a[i];
  22.             transform(a[i].begin(), a[i].end(), a[i].begin(), ::tolower);
  23.             idx = a[i].find(str);
  24.             if (idx != string::npos){
  25.                 cout << t << endl;
  26.             }
  27.         }
  28.     }
  29.     else
  30.     {
  31.         for (int i = 0; i < m; i++){
  32.             idx = a[i].find(str);
  33.             if (idx != string::npos){
  34.                 cout << a[i] << endl;
  35.             }
  36.         }
  37.     }
  38.     return 0;
  39. }

数字排序

  1. #include <iostream>
  2. #include <string>
  3. #include <algorithm>
  4. using namespace std;
  5. int n;
  7. struct my{
  8.     int num;
  9.     int count;
  10. }nums[1005];
  12. int compare(my s1, my s2){
  13.     if (s1.count == s2.count)
  14.         return s1.num < s2.num;
  15.     else
  16.         return s1.count > s2.count;
  17. }
  18. int main()
  19. {
  20.     int num[1005] = { 0 };
  21.     cin >> n;
  23.     for (int i = 0; i < n; i++){
  24.         int t;
  25.         cin >> t;
  26.         num[t]++;
  27.     }
  29.     int k = 0;
  30.     for (int i = 0; i < 1001; i++){
  31.         if (num[i] >= 1){
  32.             nums[k].num = i;
  33.             nums[k].count = num[i];
  34.             k++;
  35.         }
  36.     }
  38.     sort(nums, nums + k, compare);
  40.     for (int i = 0; i < k; i++){
  41.         cout << nums[i].num << " " << nums[i].count << endl;
  42.     }
  44.     return 0;
  45. }

Z形扫描

  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4. int n;
  5. int num[505][505];
  6. const int RIGHT = 1; //向右走
  7. const int DOWN = 2; //向下走
  8. const int LEFTDOWN = 3; //向做下走
  9. const int RIGHTUP = 4;  //向右上走
  11. #define max 505
  13. string to_String(int n)
  14. {
  15.     int m = n;
  16.     int i = 0, j = 0;
  17.     char s[max];
  18.     char ss[max];
  19.     while (m > 0)
  20.     {
  21.         s[i++] = m % 10 + '0';
  22.         m /= 10;
  23.     }
  24.     s[i] = '\0';
  26.     i = i - 1;
  27.     while (i >= 0)
  28.     {
  29.         ss[j++] = s[i--];
  30.     }
  31.     ss[j] = '\0';
  33.     return ss;
  34. }
  35. void run(){
  37.     //从第一个位置开始，x为横坐标，y为纵坐标，注意x,y在二维数组中的位置
  38.     int x = 0;
  39.     int y = 0;
  40.     //输出要求有空格隔开
  41.     string result = to_String(num[y][x]) + " ";
  42.     //方向变量的初始值
  43.     int direction = 0;
  45.     //下面就开始出发走咯
  46.     while (!(x == n - 1 && y == n - 1)){//循环直至到达终点（最右下角的位置）
  47.         //先判断下一步往哪个方向走
  48.         if (direction == 0){   //为0说明还没走出第一步，所以接着应该往右边走一步
  49.             direction = RIGHT;
  50.         }
  51.         else if (direction == RIGHT){ //上一次方向向右，下一步应该向左下或者右上
  52.             if (x - 1 >= 0 && y + 1 < n){    //左下可走
  53.                 direction = LEFTDOWN;
  54.             }
  55.             else {  //只能走右上了
  56.                 direction = RIGHTUP;
  57.             }
  58.         }
  59.         else if (direction == DOWN){   //上一次方向向下，下一步应该向左下或者右上
  60.             if (x - 1 >= 0 && y + 1 < n){    //左下可走
  61.                 direction = LEFTDOWN;
  62.             }
  63.             else {  //只能走右上了
  64.                 direction = RIGHTUP;
  65.             }
  66.         }
  67.         else if (direction == LEFTDOWN){   //上一次向左下，如果可以，下一步应该继续向左下，否则 向右或者向下走
  68.             if (y + 1 < n && x - 1 >= 0){    //先判断能否继续向左下
  69.                 direction = LEFTDOWN;
  70.             }
  71.             else if (y + 1 < n){  //然后判断能否向下走
  72.                 direction = DOWN;
  73.             }
  74.             else {      //最后只能向右走了
  75.                 direction = RIGHT;
  76.             }
  77.         }
  78.         else if (direction == RIGHTUP){    //上一次向右上，如果可以，下一步应该继续向右上，否则向右或者下走
  79.             if (x + 1 < n && y - 1 >= 0){  //先判断能否继续向右上
  80.                 direction = RIGHTUP;
  81.             }
  82.             else if (x + 1 < n){  //然后判断能否向右走
  83.                 direction = RIGHT;
  84.             }
  85.             else{            //最后只能向下走了
  86.                 direction = DOWN;
  87.             }
  88.         }
  90.         //根据上面确定的方向来走出下一步
  91.         switch (direction){
  92.         case RIGHT: x = x + 1; break;
  93.         case DOWN: y = y + 1; break;
  94.         case LEFTDOWN: x = x - 1; y = y + 1; break;
  95.         case RIGHTUP: x = x + 1; y = y - 1; break;
  96.         }
  98.         //读取当前走到位置的数字.注意x和y的位置
  99.         result += to_String(num[y][x]) + " ";
  100.     }
  101.     cout << result << endl;
  102. }
  103. int main()
  104. {
  105.     cin >> n;
  106.     for (int i = 0; i < n; i++){
  107.         for (int j = 0; j < n; j++){
  108.             cin >> num[i][j];
  109.         }
  110.     }
  111.     run();
  112.     return 0;
  113. }

日期计算

  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4. int n, m;
  6. int month1[12] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
  7. int month2[12] = { 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
  8. bool isLeapYear(int year){
  9.     if (year % 4 == 0 && year % 100 != 0 || year % 400 == 0){
  10.         return true;
  11.     }
  12.     else{
  13.         return false;
  14.     }
  15. }
  16. void printMonthAndDay(int flag, int m){
  17.     int days = m;
  18.     int month = 1;
  19.     int day = 0;
  20.     int i = 0;
  21.     if (flag == 0){
  22.         while (days - month1[i] > 0)
  23.         {
  24.             days -= month1[i++];
  25.             month++;
  26.         }
  27.         cout << month << "\n" << days << endl;
  28.     }
  29.     else{
  30.         while (days - month2[i] > 0)
  31.         {
  32.             days -= month2[i++];
  33.             month++;
  34.         }
  35.         cout << month << "\n" << days << endl;
  36.     }
  37. }
  38. int main()
  39. {
  40.     cin >> n >> m;
  41.     int flag = isLeapYear(n);
  42.     printMonthAndDay(flag, m);
  43.     return 0;
  44. }

火车票

  1. #include <iostream>
  2. using namespace std;
  3. int n;
  4. int num[105];
  5. int seat[20][5];
  7. int main()
  8. {
  9.     cin >> n;
  10.     for (int i = 0; i < n; i++)
  11.     {
  12.         cin >> num[i];
  13.     }
  14.     for (int i = 0; i < n; i++){
  15.         int res = num[i];
  16.         int t[100];
  17.         int flag = 0;
  18.         for (int j = 0; j < 20; j++){
  19.             int count = 0;
  20.             int backup[20][5] = { 0 };
  21.             for (int k = 0; k < 5; k++){
  22.                 if (seat[j][k] == 0){
  23.                     backup[j][k] = 1;
  24.                     t[count++] = j * 5 + k + 1;
  25.                     for (int l = 1; l < res; l++){
  26.                         k++;
  27.                         if (seat[j][k] == 1 || k >= 5 || count >= res)
  28.                         {
  29.                             break;
  30.                         }
  31.                         else
  32.                         {
  33.                             t[count++] = j * 5 + k + 1;
  34.                             backup[j][k] = 1;
  35.                         }
  36.                     }
  37.                     if (count == res){ //座位够分
  38.                         for (int s = 0; s < count; s++){
  39.                             cout << t[s] << " ";
  40.                         }
  41.                         cout << endl;
  42.                         for (int x = 0; x < 20; x++){
  43.                             for (int y = 0; y < 5; y++){
  44.                                 if (backup[x][y] == 1)
  45.                                 {
  46.                                     seat[x][y] = 1;
  47.                                 }
  48.                             }
  49.                         }
  50.                         flag = 1;
  51.                         break;
  52.                     }
  53.                     else{ //座位不够分
  54.                         break;
  55.                     }
  56.                 }
  57.             }
  58.             if (flag == 1)
  59.                 break;
  60.         }
  61.         if (flag == 0){
  62.             for (int j = 0; j < 20; j++){
  63.                 for (int k = 0; k < 5; k++){
  64.                     if (seat[j][k] == 0 && res>0){
  65.                         seat[j][k] = 1;
  66.                         res--;
  67.                         cout << j * 5 + k + 1 << " ";
  68.                     }
  69.                 }
  70.             }
  71.             cout << endl;
  72.         }
  73.     }
  74.     return 0;
  75. }

俄罗斯方块

  1. #include <iostream>
  3. const int ROW = 15;
  4. const int COL = 10;
  5. const int N = 4;
  7. int board[ROW + 1][COL];
  8. int block[N][N];
  9. struct {
  10.     int row, col;
  11. } coords[N];
  13. using namespace std;
  15. int main()
  16. {
  17.     int row, col;
  19.     // 输入数据
  20.     for (int i = 0; i < ROW; i++)
  21.     for (int j = 0; j < COL; j++)
  22.         cin >> board[i][j];
  23.     for (int i = 0; i < N; i++)
  24.     for (int j = 0; j < N; j++)
  25.         cin >> block[i][j];
  26.     cin >> col;
  28.     // 底边全放1
  29.     for (int j = 0; j < COL; j++)
  30.         board[ROW][j] = 1;
  32.     // 提取小方块坐标
  33.     int k = 0;
  34.     for (int i = N - 1; i >= 0; i--)
  35.     for (int j = 0; j < N; j++)
  36.     if (block[i][j] == 1) {
  37.         coords[k].row = i;
  38.         coords[k].col = j;
  39.         k++;
  40.     }
  42.     // 模拟小方块落下过程（选取参考点原点进行搜索，从当前坐标点开始加上小矩阵元素为1的坐标，
  43.     //判断其位置是否为1 ，位置上为1则停止）
  44.     row = 1;
  45.     col--;
  46.     bool checkflag;
  47.     for (;;) {
  48.         checkflag = false;
  50.         for (int i = 0; i < N; i++)
  51.         if (board[row + coords[i].row][col + coords[i].col] == 1) {
  52.             checkflag = true;
  53.             break;
  54.         }
  56.         if (checkflag)
  57.             break;
  59.         row++;
  60.     }
  61.     row--;
  63.     // 合并小方块到方格
  64.     for (int i = 0; i < N; i++)
  65.         board[row + coords[i].row][col + coords[i].col] = 1;
  67.     // 输出结果
  68.     for (int i = 0; i < ROW; i++) {
  69.         for (int j = 0; j < COL; j++) {
  70.             if (j != 0)
  71.                 cout << " ";
  72.             cout << board[i][j];
  73.         }
  74.         cout << endl;
  75.     }
  76.     return 0;
  77. }

消除类游戏

  1. #include <iostream>
  2. using namespace std;
  3. int num[50][50];
  4. int backup[50][50];
  5. int n, m;
  6. int main()
  7. {
  8.     cin >> n >> m;
  9.     for (int i = 0; i < n; i++){
  10.         for (int j = 0; j < m; j++){
  11.             cin >> num[i][j];
  12.             backup[i][j] = num[i][j];
  13.         }
  14.     }
  16.     // 行扫描
  17.     for (int i = 0; i < n; i++){
  18.         for (int j = 0; j < m - 1; j++){
  19.             int t = num[i][j];
  20.             int count = 1;
  21.             for (int k = j + 1; k < m; k++){
  22.                 if (num[i][k] != t)
  23.                     break;
  24.                 else
  25.                     count++;
  26.             }
  27.             if (count >= 3){
  28.                 for (int k = j; k < j + count; k++){
  29.                     backup[i][k] = 0;
  30.                 }
  31.             }
  32.         }
  33.     }
  35.     // 列扫描
  36.     for (int i = 0; i < m; i++){
  37.         for (int j = 0; j < n - 1; j++){
  38.             int t = num[j][i];
  39.             int count = 1;
  40.             for (int k = j + 1; k < n; k++){
  41.                 if (num[k][i] != t)
  42.                     break;
  43.                 else
  44.                     count++;
  45.             }
  46.             if (count >= 3){
  47.                 for (int k = j; k < j + count; k++){
  48.                     backup[k][i] = 0;
  49.                 }
  50.             }
  51.         }
  52.     }
  54.     // 输出
  55.     for (int i = 0; i < n; i++){
  56.         for (int j = 0; j < m; j++){
  57.             if (j == m - 1)
  58.                 cout << backup[i][j];
  59.             else
  60.                 cout << backup[i][j] << " ";
  61.         }
  62.         cout << endl;
  63.     }
  64.     return 0;
  65. }

学生排队

  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. int n, m;
  6. vector<int> v;
  7. int find(int num){
  8.     for (int i = 0; i < v.size(); i++){
  9.         if (num == v[i])
  10.             return i+1;
  11.     }
  12.     return -1;
  13. }
  14. int main()
  15. {
  16.     cin >> n;
  17.     cin >> m;
  19.     for (int i = 0; i < n; i++){
  20.         v.push_back(i + 1);
  21.     }
  22.     for (int i = 0; i < m; i++){
  23.         int p, q;
  24.         cin >> p >> q;
  25.         int pos = find(p);
  26.         //cout << pos << endl;
  27.         if (q >= 0){
  28.             //cout << *v.begin() << endl;
  29.             v.insert(v.begin() + pos + q, p);
  30.             v.erase(v.begin() + pos - 1);
  31.         }
  32.         else{
  33.             //cout << *v.begin() << endl;
  34.             v.insert(v.begin() + pos - 1 + q, p);
  35.             v.erase(v.begin() + pos);
  36.         }
  37.     }
  38.     for (int i = 0; i < v.size(); i++){
  39.         cout << v[i] << " ";
  40.     }
  41. }

地铁修建

  1. # include <iostream>
  2. # include <queue>
  3. # include <functional>
  4. using namespace std;
  6. typedef pair<int, int> pii;
  7. const int maxn = 100000 + 100;
  8. const int INF = INT_MAX;
  9. struct node
  10. {
  11.     int from, to, dist;
  12.     node(int from, int to, int dist) :from(from), to(to), dist(dist){}
  13. };
  14. int n, m;
  15. vector<node> edges;
  16. vector<int> g[maxn];
  17. bool visited[maxn];
  18. int d[maxn];
  19. void AddEdge(int from, int to, int dist)
  20. {
  21.     edges.push_back(node(from, to, dist));
  22.     g[from].push_back(edges.size() - 1);
  23. }
  24. void dij(int start)
  25. {
  26.     priority_queue<pii, vector<pii>, greater<pii> >q;//d和from
  27.     for (int i = 0; i<n; i++) d[i] = INF;
  28.     d[start] = 0;
  29.     memset(visited, 0, sizeof(visited));
  30.     q.push(make_pair(0, start));
  31.     while (!q.empty()){
  32.         pii x = q.top(); q.pop();
  33.         int u = x.second;
  34.         if (visited[u]) continue;
  35.         visited[u] = true;
  36.         for (int i = 0; i<g[u].size(); i++){
  37.             node &e = edges[g[u][i]];
  38.             //if (d[e.to]>max(d[u], e.dist)){//改变松弛策略
  39.             //  d[e.to] = max(d[u], e.dist);
  40.             //  q.push(make_pair(d[e.to], e.to));
  41.             //}
  42.             if (d[e.to]> d[u] + e.dist){//改变松弛策略
  43.                 d[e.to] = d[u] + e.dist;
  44.                 q.push(make_pair(d[e.to], e.to));
  45.             }
  46.         }
  47.     }
  48. }
  49. int main()
  50. {
  51.     cin >> n >> m;
  52.     for (int i = 0; i<m; i++){
  53.         int a, b, c;
  54.         cin >> a >> b >> c;
  55.         AddEdge(a - 1, b - 1, c);// 只写一个代表：有向图
  56.         //AddEdge(b - 1, a - 1, c); //两个同时写代表：无向图
  57.     }
  59.     dij(0);
  60.     cout << d[n - 1] << endl;
  61.     return 0;
  62. }

棋局评估

  1. #include <iostream>
  2. #include <cstring>
  3. #include <map>
  4. using namespace std;
  5. int a[9];
  6. map<int, int> mymap;
  8. int isover(){
  9.     for (int i = 0; i < 3; i++){    //检测列，仔细计算下，容易出错
  10.         if (a[i] == a[i + 3] && a[i] == a[i + 6] && a[i])
  11.             return a[i];
  12.     }
  13.     for (int i = 0; i < 9; i += 3){//检测行
  14.         if (a[i] == a[i + 1] && a[i] == a[i + 2] && a[i])
  15.             return a[i];
  16.     }
  17.     if (a[0] == a[4] && a[0] == a[8] && a[0])//检测对角
  18.         return a[0];
  19.     if (a[2] == a[4] && a[2] == a[6] && a[2])
  20.         return a[2];
  21.     return 0;
  22. }
  24. int dp(){
  25.     int aa = 0; //状态
  26.     for (int i = 0; i < 9; i++){
  27.         aa = aa * 10 + a[i];
  28.     }
  29.     if (mymap.find(aa) != mymap.end()){ //记忆化搜索，若当前状态出现过，则不再重新计算。
  30.         return mymap[aa];
  31.     }
  33.     int ct = 0;
  34.     for (int i = 0; i < 9; i++) //找空余的0
  35.     if (a[i])
  36.         ct++;
  37.     int rt = isover();
  38.     if (rt == 1) //Alice赢
  39.         return 10 - ct;    
  40.     if (rt == 2) // Bob赢
  41.         return -(10 - ct); 
  42.     if (ct == 9 && rt == 0) //下满了，并且未分出胜负，则平局
  43.         return 0;
  44.     int an = 0;
  45.     if (ct % 2 == 0){ //轮到Alice
  46.         an = -100;
  47.         for (int i = 0; i < 9; i++){
  48.             if (a[i] == 0){    //遍历所有空格
  49.                 a[i] = 1;
  51.                 int s = dp();
  52.                 if (an < s){  //找到得分最高的
  53.                     an = s;
  54.                 }
  55.                 a[i] = 0;
  56.             }
  57.         }
  58.     }
  59.     else{   //轮到Bob
  60.         an = 100;
  61.         for (int i = 0; i < 9; i++){
  62.             if (a[i] == 0){
  63.                 a[i] = 2;
  65.                 int s = dp();
  66.                 if (an > s){//找到得分最低的
  67.                     an = s;
  68.                 }
  69.                 a[i] = 0;
  70.             }
  71.         }
  72.     }
  73.     return mymap[aa] = an;
  74. }
  76. int main(){
  77.     int t;
  78.     cin >> t;
  79.     while (t--){
  80.         mymap.erase(mymap.begin(), mymap.end());
  81.         for (int i = 0; i < 9; i++)   {
  82.             cin >> a[i];
  83.         }
  84.         cout << dp() << endl;
  85.     }
  87.     return 0;
  88. }

最大的矩形

  1. #include<iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. int n;
  6. int num[1005];
  8. int find_min(int i, int j){
  9.     int min = 99999999;
  10.     for (int k = i; k <= j; k++){
  11.         if (num[k] < min){
  12.             min = num[k];
  13.         }
  14.     }
  15.     return min;
  16. }
  17. int main(){
  18.     cin >> n;
  19.     for (int i = 0; i < n; i++){
  20.         cin >> num[i];
  21.     }
  22.     int max = -99999;
  23.     for (int i = 0; i < n-1; i++){
  24.         for (int j = i+1; j < n; j++){
  25.             int res = find_min(i, j) * (j-i+1);
  26.             if (res > max){
  27.                 max = res;
  28.             }
  30.         }
  31.     }
  32.     cout << max << endl;
  33.     return 0;
  34. }

有趣的数

  1. #include <iostream>
  3. using namespace std;
  5. /* 状态分析： states[i][0]表示第i位状态为0的情况
  6. 0－－用了2，剩0，1，3
  7. 1－－用了0，2，剩1，3
  8. 2－－用了2，3，剩0，1
  9. 3－－用了0，1，2，剩3
  10. 4－－用了0，2，3，剩1
  11. 5－－全部用了
  12. */
  14. long long states[1005][6];
  16. int main(){
  18.     long mod = 1000000007;
  19.     int n;
  20.     cin >> n;
  22.     for (int i = 0; i<6; i++)
  23.         states[0][i] = 0;
  25.     for (int i = 1; i <= n; i++)
  26.     {
  27.         int j = i - 1;
  29.         //只能以2开头，所以只存在一种情况
  30.         states[i][0] = 1;
  32.         //1、可以由第i-1步状态为0到达状态第i步的状态1
  33.         //2、可以由第i-1步状态为1到达状态第i步的状态1，此时第i位只能填2或0。
  34.         states[i][1] = (states[j][0] + states[j][1] * 2) % mod;
  36.         //1、可以由第i-1步状态为0到达状态第i步的状态2
  37.         //2、可以由第i-1步状态为2到达状态第i步的状态2，此时第i位只能填3。
  38.         states[i][2] = (states[j][0] + states[j][2]) % mod;
  40.         //1、可以由第i-1步状态为1到达状态第i步的状态3。
  41.         //2、可以由第i-1步状态为3到达状态第i步的状态3，此时第i位只能填3或1。
  42.         states[i][3] = (states[j][1] + states[j][3] * 2) % mod;
  44.         //1、可以由第i-1步状态为1或者2到达状态第i步的状态4。
  45.         //2、可以由第i-1步状态为4到达状态第i步的状态4，此时第i位只能填3或1。
  46.         states[i][4] = (states[j][1] + states[j][2] + states[j][4] * 2) % mod;
  48.         //1、第i-1步只剩一个数字到达第i步的状态,此时第i位只能填1或3。    
  49.         //2、第i-1步不剩任何数字到达第i步的状态，此时此时第i位只能填3或1。
  50.         states[i][5] = (states[j][3] + states[j][4] + states[j][5] * 2) % mod;
  51.     }
  52.     cout << states[n][5] << endl;
  53.     return 0;
  54. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注