devbox
天景科技苑
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Codeforces Round 956 (Div. 2) 部分题解A~C_codeforces 956

作者：天景科技苑 | 2024-08-19 22:19:11

赞

踩

codeforces 956

A. Array Divisibility

题目大意

构造长度为n的数组，满足：

  • 所有j的aj之和可以被k整除，其中j是k的倍数，k的取值为1~n。

思路

构造序列1->n即可满足条件。

代码实现
  1. void solve() {
  2.     ll n; cin >> n;
  3.     for (int i = 1; i <= n; i++)cout << i << " ";
  4.     cout << "\n";
  5. }

B. Corner Twist

题目大意

给定a和b两个网格，网格中只存在0、1、2三种值。

给定操作，可以选择一个矩形的一条对角线上的两个端点，让他们加1/2；另一条对角线的端点值加2/1，然后对这些值取模3。问是否存在操作可以让a和b两个网格一致。

思路

考虑网格的边上的值，边上的值的变化会受到其他的影响，所以我们优先去找如何让边上的值相等即可。

正扫一遍，反扫一遍，然后比较数组即可。

代码实现
  1. void solve() {
  2.     ll n, m; cin >> n >> m;
  3.     vector<vector<char>>a(n + 1, vector<char>(m + 1));
  4.     vector<vector<char>>b(n + 1, vector<char>(m + 1));
  5.     for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> a[i][j];
  6.     for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> b[i][j];
  7.     for (int i = 1; i < n; i++) {
  8.         for (int j = 1; j < m; j++) {
  9.             if (a[i][j] != b[i][j]) {
  10.                 if (a[i][j] == '0') {
  11.                     if (b[i][j] == '1') {
  12.                         a[i][j] += 1;
  13.                         if (a[i][j] == '3')a[i][j] = '0';
  14.                         if (a[i][j] == '4')a[i][j] = '1';
  15.  
  16.                         a[i + 1][j + 1] += 1;
  17.                         if (a[i + 1][j + 1] == '3')a[i + 1][j + 1] = '0';
  18.                         if (a[i + 1][j + 1] == '4')a[i + 1][j + 1] = '1';
  19.  
  20.                         a[i + 1][j] += 2;
  21.                         if (a[i + 1][j] == '3')a[i + 1][j] = '0';
  22.                         if (a[i + 1][j] == '4')a[i + 1][j] = '1';
  23.  
  24.                         a[i][j + 1] += 2;
  25.                         if (a[i][j + 1] == '3')a[i][j + 1] = '0';
  26.                         if (a[i][j + 1] == '4')a[i][j + 1] = '1';
  27.                     }else if(b[i][j]=='2') {
  28.                         a[i][j] += 2;
  29.                         if (a[i][j] == '3')a[i][j] = '0';
  30.                         if (a[i][j] == '4')a[i][j] = '1';
  31.  
  32.                         a[i + 1][j + 1] += 2;
  33.                         if (a[i + 1][j + 1] == '3')a[i + 1][j + 1] = '0';
  34.                         if (a[i + 1][j + 1] == '4')a[i + 1][j + 1] = '1';
  35.  
  36.                         a[i + 1][j] += 1;
  37.                         if (a[i + 1][j] == '3')a[i + 1][j] = '0';
  38.                         if (a[i + 1][j] == '4')a[i + 1][j] = '1';
  39.  
  40.                         a[i][j + 1] += 1;
  41.                         if (a[i][j + 1] == '3')a[i][j + 1] = '0';
  42.                         if (a[i][j + 1] == '4')a[i][j + 1] = '1';
  43.                     }
  44.                 }
  45.                 else if (a[i][j] == '1') {
  46.                     if (b[i][j] == '2') {
  47.                         a[i][j] += 1;
  48.                         if (a[i][j] == '3')a[i][j] = '0';
  49.                         if (a[i][j] == '4')a[i][j] = '1';
  50.  
  51.                         a[i + 1][j + 1] += 1;
  52.                         if (a[i + 1][j + 1] == '3')a[i + 1][j + 1] = '0';
  53.                         if (a[i + 1][j + 1] == '4')a[i + 1][j + 1] = '1';
  54.  
  55.                         a[i + 1][j] += 2;
  56.                         if (a[i + 1][j] == '3')a[i + 1][j] = '0';
  57.                         if (a[i + 1][j] == '4')a[i + 1][j] = '1';
  58.  
  59.                         a[i][j + 1] += 2;
  60.                         if (a[i][j + 1] == '3')a[i][j + 1] = '0';
  61.                         if (a[i][j + 1] == '4')a[i][j + 1] = '1';
  62.                     }
  63.                     else if (b[i][j] == '0') {
  64.                         a[i][j] += 2;
  65.                         if (a[i][j] == '3')a[i][j] = '0';
  66.                         if (a[i][j] == '4')a[i][j] = '1';
  67.  
  68.                         a[i + 1][j + 1] += 2;
  69.                         if (a[i + 1][j + 1] == '3')a[i + 1][j + 1] = '0';
  70.                         if (a[i + 1][j + 1] == '4')a[i + 1][j + 1] = '1';
  71.  
  72.                         a[i + 1][j] += 1;
  73.                         if (a[i + 1][j] == '3')a[i + 1][j] = '0';
  74.                         if (a[i + 1][j] == '4')a[i + 1][j] = '1';
  75.  
  76.                         a[i][j + 1] += 1;
  77.                         if (a[i][j + 1] == '3')a[i][j + 1] = '0';
  78.                         if (a[i][j + 1] == '4')a[i][j + 1] = '1';
  79.                     }
  80.                 }
  81.                 else {
  82.                     if (b[i][j] == '0') {
  83.                         a[i][j] += 1;
  84.                         if (a[i][j] == '3')a[i][j] = '0';
  85.                         if (a[i][j] == '4')a[i][j] = '1';
  86.  
  87.                         a[i + 1][j + 1] += 1;
  88.                         if (a[i + 1][j + 1] == '3')a[i + 1][j + 1] = '0';
  89.                         if (a[i + 1][j + 1] == '4')a[i + 1][j + 1] = '1';
  90.  
  91.                         a[i + 1][j] += 2;
  92.                         if (a[i + 1][j] == '3')a[i + 1][j] = '0';
  93.                         if (a[i + 1][j] == '4')a[i + 1][j] = '1';
  94.  
  95.                         a[i][j + 1] += 2;
  96.                         if (a[i][j + 1] == '3')a[i][j + 1] = '0';
  97.                         if (a[i][j + 1] == '4')a[i][j+1] = '1';
  98.                     }
  99.                     else if (b[i][j] == '1') {
  100.                         a[i][j] += 2;
  101.                         if (a[i][j] == '3')a[i][j] = '0';
  102.                         if (a[i][j] == '4')a[i][j] = '1';
  103.  
  104.                         a[i + 1][j + 1] += 2;
  105.                         if (a[i + 1][j + 1] == '3')a[i + 1][j + 1] = '0';
  106.                         if (a[i + 1][j + 1] == '4')a[i + 1][j + 1] = '1';
  107.  
  108.                         a[i + 1][j] += 1;
  109.                         if (a[i + 1][j] == '3')a[i + 1][j] = '0';
  110.                         if (a[i + 1][j] == '4')a[i + 1][j] = '1';
  111.  
  112.                         a[i][j + 1] += 1;
  113.                         if (a[i][j + 1] == '3')a[i][j + 1] = '0';
  114.                         if (a[i][j + 1] == '4')a[i][j + 1] = '1';
  115.                     }
  116.                 }
  117.             }
  118.         }
  119.     }
  120.     for (int i = n; i > 1; i--) {
  121.         for (int j = m; j > 1; j--) {
  122.             if (a[i][j] != b[i][j]) {
  123.                 if (a[i][j] == '0') {
  124.                     if (b[i][j] == '1') {
  125.                         a[i][j] += 1;
  126.                         if (a[i][j] == '3')a[i][j] = '0';
  127.                         if (a[i][j] == '4')a[i][j] = '1';
  128.  
  129.                         a[i - 1][j - 1] += 1;
  130.                         if (a[i - 1][j - 1] == '3')a[i - 1][j - 1] = '0';
  131.                         if (a[i - 1][j - 1] == '4')a[i - 1][j - 1] = '1';
  132.  
  133.                         a[i - 1][j] += 2;
  134.                         if (a[i - 1][j] == '3')a[i - 1][j] = '0';
  135.                         if (a[i - 1][j] == '4')a[i - 1][j] = '1';
  136.  
  137.                         a[i][j - 1] += 2;
  138.                         if (a[i][j - 1] == '3')a[i][j - 1] = '0';
  139.                         if (a[i][j - 1] == '4')a[i][j - 1] = '1';
  140.                     }
  141.                     else if (b[i][j] == '2') {
  142.                         a[i][j] += 2;
  143.                         if (a[i][j] == '3')a[i][j] = '0';
  144.                         if (a[i][j] == '4')a[i][j] = '1';
  145.  
  146.                         a[i - 1][j - 1] += 2;
  147.                         if (a[i - 1][j - 1] == '3')a[i - 1][j - 1] = '0';
  148.                         if (a[i - 1][j - 1] == '4')a[i - 1][j -1] = '1';
  149.  
  150.                         a[i - 1][j] += 1;
  151.                         if (a[i - 1][j] == '3')a[i - 1][j] = '0';
  152.                         if (a[i - 1][j] == '4')a[i - 1][j] = '1';
  153.  
  154.                         a[i][j - 1] += 1;
  155.                         if (a[i][j - 1] == '3')a[i][j - 1] = '0';
  156.                         if (a[i][j - 1] == '4')a[i][j - 1] = '1';
  157.                     }
  158.                 }
  159.                 else if (a[i][j] == '1') {
  160.                     if (b[i][j] == '2') {
  161.                         a[i][j] += 1;
  162.                         if (a[i][j] == '3')a[i][j] = '0';
  163.                         if (a[i][j] == '4')a[i][j] = '1';
  164.  
  165.                         a[i - 1][j - 1] += 1;
  166.                         if (a[i - 1][j - 1] == '3')a[i - 1][j - 1] = '0';
  167.                         if (a[i - 1][j - 1] == '4')a[i - 1][j - 1] = '1';
  168.  
  169.                         a[i - 1][j] += 2;
  170.                         if (a[i - 1][j] == '3')a[i - 1][j] = '0';
  171.                         if (a[i - 1][j] == '4')a[i - 1][j] = '1';
  172.  
  173.                         a[i][j - 1] += 2;
  174.                         if (a[i][j - 1] == '3')a[i - 1][j] = '0';
  175.                         if (a[i][j - 1] == '4')a[i - 1][j] = '1';
  176.                     }
  177.                     else if (b[i][j] == '0') {
  178.                         a[i][j] += 2;
  179.                         if (a[i][j] == '3')a[i][j] = '0';
  180.                         if (a[i][j] == '4')a[i][j] = '1';
  181.  
  182.                         a[i - 1][j - 1] += 2;
  183.                         if (a[i - 1][j - 1] == '3')a[i - 1][j - 1] = '0';
  184.                         if (a[i - 1][j - 1] == '4')a[i - 1][j - 1] = '1';
  185.  
  186.                         a[i - 1][j] += 1;
  187.                         if (a[i - 1][j] == '3')a[i - 1][j] = '0';
  188.                         if (a[i - 1][j] == '4')a[i - 1][j] = '1';
  189.  
  190.                         a[i][j - 1] += 1;
  191.                         if (a[i][j - 1] == '3')a[i][j - 1] = '0';
  192.                         if (a[i][j - 1] == '4')a[i][j - 1] = '1';
  193.                     }
  194.                 }
  195.                 else {
  196.                     if (b[i][j] == '0') {
  197.                         a[i][j] += 1;
  198.                         if (a[i][j] == '3')a[i][j] = '0';
  199.                         if (a[i][j] == '4')a[i][j] = '1';
  200.  
  201.                         a[i - 1][j - 1] += 1;
  202.                         if (a[i - 1][j - 1] == '3')a[i - 1][j - 1] = '0';
  203.                         if (a[i - 1][j - 1] == '4')a[i - 1][j - 1] = '1';
  204.  
  205.                         a[i - 1][j] += 2;
  206.                         if (a[i - 1][j] == '3')a[i - 1][j] = '0';
  207.                         if (a[i - 1][j] == '4')a[i - 1][j] = '1';
  208.  
  209.                         a[i][j - 1] += 2;
  210.                         if (a[i][j - 1] == '3')a[i][j - 1] = '0';
  211.                         if (a[i][j - 1] == '4')a[i][j-1] = '1';
  212.                     }
  213.                     else if (b[i][j] == '1') {
  214.                         a[i][j] += 2;
  215.                         if (a[i][j] == '3')a[i][j] = '0';
  216.                         if (a[i][j] == '4')a[i][j] = '1';
  217.  
  218.                         a[i - 1][j - 1] += 2;
  219.                         if (a[i - 1][j - 1] == '3')a[i - 1][j - 1] = '0';
  220.                         if (a[i - 1][j - 1] == '4')a[i - 1][j-1] = '1';
  221.  
  222.                         a[i - 1][j] += 1;
  223.                         if (a[i - 1][j] == '3')a[i - 1][j] = '0';
  224.                         if (a[i - 1][j] == '4')a[i - 1][j] = '1';
  225.  
  226.                         a[i][j - 1] += 1;
  227.                         if (a[i][j - 1] == '3')a[i][j - 1] = '0';
  228.                         if (a[i][j - 1] == '4')a[i][j-1] = '1';
  229.                     }
  230.                 }
  231.             }
  232.         }
  233.     }
  234.     for (int i = 1; i <= n; i++) {
  235.         for (int j = 1; j <= m; j++) {
  236.             if (a[i][j] != b[i][j]) {
  237.                 cout << "NO\n"; return;
  238.             }
  239.         }
  240.     }
  241.     cout << "YES\n";
  242. }

C. Have Your Cake and Eat It Too

题目大意

三个人吃蛋糕，每个人对蛋糕不同位置有自己的估价。

问如何分配蛋糕，使三个人获得的蛋糕价值均高于蛋糕价值和的三分之一。

思路

分类讨论：三个人拿蛋糕的顺序

  • abc

  • acb

  • bac

  • bca

  • cab

  • cba

代码实现
  1. ll a[2100000];
  2. ll b[2100000];
  3. ll c[2100000];
  4. void solve() {
  5.     ll n; cin >> n;
  6.     ll need = 0;
  7.     a[0] = b[0] = c[0] = 0;
  8.     for (int i = 1; i <= n; i++)cin >> a[i], need += a[i];
  9.     for (int i = 1; i <= n; i++)cin >> b[i];
  10.     for (int i = 1; i <= n; i++)cin >> c[i];
  11.     need = ceil(need / 3.0);
  12.     for (int i = 1; i <= n; i++)a[i] += a[i - 1];
  13.     for (int i = 1; i <= n; i++)b[i] += b[i - 1];
  14.     for (int i = 1; i <= n; i++)c[i] += c[i - 1];
  15.     a[n + 1] = b[n + 1] = c[n + 1] = 1e22;
  16.     //abc
  17.     ll id = lower_bound(a + 1, a + 1 + n, need) - a;
  18.     ll id2 = lower_bound(b + 1, b + 1 + n, b[id] + need) - b;
  19.     if (c[n] - c[id2] >= need) {
  20.         cout << 1 << " " << id << " " << id + 1 << " " << id2 << " " << id2 + 1 << " " << n << "\n";
  21.         return;
  22.     }
  23.     //acb
  24.     id = lower_bound(a + 1, a + 1 + n, need) - a;
  25.     id2 = lower_bound(c + 1, c + 1 + n, c[id] + need) - c;
  26.     if (b[n] - b[id2] >= need) {
  27.         cout << 1 << " " << id << " " << id2 + 1 << " " << n << " " << id + 1 << " " << id2 << "\n";
  28.         return;
  29.     }
  30.     //bca
  31.     id = lower_bound(b + 1, b + 1 + n, need) - b;
  32.     id2 = lower_bound(c + 1, c + 1 + n, c[id] + need) - c;
  33.     if (a[n] - a[id2] >= need) {
  34.         cout << id2 + 1 << " " << n << " " << 1 << " " << id << " " << id + 1 << " " << id2 << "\n";
  35.         return;
  36.     }
  37.     //bac
  38.     id = lower_bound(b + 1, b + 1 + n, need) - b;
  39.     id2 = lower_bound(a + 1, a + 1 + n, a[id] + need) - a;
  40.     if (c[n] - c[id2] >= need) {
  41.         cout << id + 1 << " " << id2 << " " << 1 << " " << id << " " << id2 + 1 << " " << n << "\n";
  42.         return;
  43.     }
  44.     //cab
  45.     id = lower_bound(c + 1, c + 1 + n, need) - c;
  46.     id2 = lower_bound(a + 1, a + 1 + n, a[id] + need) - a;
  47.     if (b[n] - b[id2] >= need) {
  48.         cout << id + 1 << " " << id2 << " " << id2 + 1 << " " << n <<" " << 1 << " " << id << "\n";
  49.         return;
  50.     }
  51.     //cba
  52.     id = lower_bound(c + 1, c + 1 + n, need) - c;
  53.     id2 = lower_bound(b + 1, b + 1 + n, b[id] + need) - b;
  54.     if (a[n] - a[id2] >= need) {
  55.         cout << id2 + 1 << " " << n << " " << id + 1 << " " << id2 << " " << 1 << " " << id << "\n";
  56.         return;
  57.     }
  58.     cout << "-1\n";
  59. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/天景科技苑/article/detail/1003909
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号