Codeforces Round #634 (Div. 3)

比赛链接：https://codeforces.com/contest/1335

这场比赛打起来还行，除了数组开太小的蜜汁操作WA了几发（不是第一次了，习惯了）。

A - Candies and Two Sisters

给定n，把n拆成a,b俩个数，满足a + b = n && a > b的方案数，（1， n - 1）, (2, n - 2)....., 就是（n - 1）/2。

 1 #include <bits/stdc++.h>
 2  
 3 using namespace std;
 4  
 5 const int N = 1e5  + 10;
 6  
 7 int T;
 8 int n; 
 9  
10 int main()
11 {
12     cin >> T;
13     while(T --)
14     {
15         cin >> n;
16             cout << (n - 1) / 2 << '
';
17     }
18 }

View Code

B - Construct the String

给定n, a, b， b = min(a, 26), 构造一个长度为n并且每a个长度中就会有b个不要的字符串。那么我们之间让字符串的循环节为b一定满足要求。

 1 #include <bits/stdc++.h>
 2  
 3 using namespace std;
 4  
 5 const int N = 1e5  + 10;
 6  
 7 int T;
 8 int n, a, b; 
 9  
10 int main()
11 {
12     scanf("%d", &T);
13     while(T --)
14     {
15         scanf("%d%d%d", &n, &a, &b);
16         for (int i = 0; i < n; i ++)
17         {
18             printf("%c", i % b + 'a'); 
19         }
20         cout << '
';
21     }
22 }

View Code

C - Two Teams Composing

给定一个长度为n的数组a，1<=a[i]<= n，把n个数分成俩组，满足第一组内每个数都不相同，第二组内每个数都相同，并且俩组大小要相同。

那么我们先求出出现次数最多的数的次数x，求出除了这个数以外的不重复数的个数y。肯定是输出x,y中小的那个数，再讨论下x - 1>=y + 1的情况。

 1 #include <bits/stdc++.h>
 2  
 3 using namespace std;
 4  
 5 const int N = 2e5  + 10;
 6  
 7 int T;
 8 int n, a[N];
 9 int sum[N];
10 int b[N];
11 int cnt;
12  
13 int main()
14 {
15     scanf("%d", &T);
16     while(T --)
17     {
18         memset(sum, 0, sizeof(sum));
19         scanf("%d", &n);
20         for (int i = 1; i <= n; i ++)
21             scanf("%d", &a[i]), sum[a[i]] ++, b[i] = a[i];
22         if(n == 1)
23         {
24             puts("0");
25             continue;
26         }
27          int mx = 0;
28          for (int i = 1; i <= n; i ++)
29              mx = max(mx, sum[a[i]]);
30         sort(b + 1, b + n + 1);
31         cnt = unique(b + 1, b + n + 1) - (b + 1);
32         cnt --;
33         if(cnt + 1 <= mx - 1)
34         {
35             cout << cnt + 1 << endl;
36             continue;
37         }
38         else
39         cout << min(mx, cnt) << endl; 
40     }
41 }

View Code

D - Anti-Sudoku

给定9 * 9的数独矩阵，改变9个位置使每行每列每9宫格中至少有一个数出现俩次，那么改变某一个数会改变所在的行，所在的列，所在的9宫格。那么只要找到9个数，占据每行每列9个9宫格。

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 2e5  + 10;
 
int T;
int n, a[N];
int sum[N];
int b[N];
int cnt;
char s[60][60];
 
void fun(int x, int y)
{
    s[x][y]     = (s[x][y] - '0' + 1) % 9 + '0';
    if(s[x][y] == '0')
    s[x][y] = '9';
 
}
 
int main()
{
    scanf("%d", &T);
    while(T --)
    {
        for (int i = 1; i <= 9; i ++)
            scanf("%s", s[i] + 1);
        fun(1, 1);
        fun(2, 4);
        fun(3, 7);
        fun(4, 2);
        fun(5, 5);
        fun(6, 8);
        fun(7, 3);
        fun(8, 6);
        fun(9, 9);
        for (int i = 1; i <= 9; i ++)
            printf("%s
", s[i] + 1);
            
    }
}

View Code

E - Three Blocks Palindrome

给定一个n(1 <= n <= 2e5)长的数组a(a[i] >= 1 && a[i] <= 200)，构成一个数组满足x个a, y个b，x个a，求max（x + y + x），其中x,y可以为0。

那么我们可以枚举值域y（1到200）,设l，r为下标，考虑l前面出现了x个y 那么r以后也应该出现x个y，然后只要求出l到r中出现次数最多的数，因为a[i]最多只有200，直接暴力。

复杂度为o（200 * n）。

 1 #include <bits/stdc++.h>
 2  
 3 using namespace std;
 4  
 5 const int N = 2e5  + 10;
 6  
 7 int T;
 8 int n, a[N];
 9 int sum[N];
10 int b[N];
11 int cnt;
12 vector<int>x[210];
13 vector<int>y[210];
14  
15  
16  
17 int fun()
18 {
19     int res = 0;
20     int id = 0;
21     for (int i = 1; i <= 200; i ++)
22     {
23         if(res < sum[i])
24         {
25             res = sum[i];
26             id = i;
27         }
28     }
29     return res;
30 }
31  
32 int main()
33 {
34     scanf("%d", &T);
35     while(T --)
36     {
37         memset(sum, 0, sizeof(sum));
38         for (int i = 0; i < 210; i ++)
39             x[i].clear(), y[i].clear();
40         scanf("%d", &n);
41         for (int i = 1; i <= n; i ++)
42             scanf("%d", &a[i]), sum[a[i]] ++;
43  
44         for (int i = 1; i <= n; i ++)
45         {
46             x[a[i]].push_back(i);
47         }
48         for (int i = n; i >= 1; i --)
49         {
50             y[a[i]].push_back(i);
51         }
52         int ans = 1;
53         for (int i = 1; i <= 200; i ++)
54         {
55             int t = x[i].size();
56             if(!t) continue;
57             int l = 1, r = n;
58             for (int j = 0; j < t; j ++)
59             {
60                 if(x[i][j] >= y[i][j]) break;
61                 while(l <= x[i][j]) sum[a[l ++]] --;
62                 while(r >= y[i][j]) sum[a[r --]] --;
63             //    cout << l << " " << r << " " <<j << " " << fun()<< endl;
64                 ans = max(ans, 2 * (j + 1) + fun()); 
65             }
66             while(l > 1) sum[a[ --l]]++;
67             while(r < n) sum[a[ ++ r]] ++;
68     //        cout << l << " " << r << endl;
69         }
70         cout << ans << endl;
71     }
72 }

View Code

F - Robots on a Grid

给一个n * m的图，每个格子上面有标有一个方向“上下左右”其中之一，不会越界，并且代表黑色或者白色。求在这些格子上最多能放多少个机器人，以及最多放多少个机器人在黑色格子。机器人要求一直在运动。

首先看到机器人一直在运动，肯定要满足环才可以，那么这题的第一问就变成求所有环的环长，拓扑排序求环即可。第二问的话，不仅要考虑环中的黑色点，还要考虑从环外进入环里的黑色格子，那么就在环中的某个点，反图bfs，求出每个能到点相对于这个点的距离。这个点在换上相对于这个点的距离肯定是dist % len，其中len为环长。第二问就迎刃而解。

  1 #include <bits/stdc++.h>
  2  
  3 using namespace std;
  4  
  5 typedef pair<int, int> PII;
  6  
  7 int dx[4] = {1, 0, -1, 0};
  8 int dy[4] = {0, 1, 0, -1};
  9  
 10 int main()
 11 {
 12     ios::sync_with_stdio(false);
 13     cin.tie(0);
 14     cout.tie(0);
 15     int T;
 16     cin >> T;
 17     while(T --)
 18     {
 19         int h, w;
 20         cin >> h >> w;
 21         vector<string>c(h);
 22         for (int i = 0; i < h; i ++)
 23             cin >> c[i];
 24         vector<string>s(h);
 25         for (int i = 0; i < h; i ++)
 26             cin >> s[i];
 27         vector<vector<int>> deg(h, vector<int>(w, 0));
 28         for (int i = 0; i < h; i ++)
 29             for (int j = 0; j < w; j ++)
 30             {
 31                 if(s[i][j] == 'U') deg[i - 1][j] ++;
 32                 if(s[i][j] == 'D') deg[i + 1][j] ++;
 33                 if(s[i][j] == 'L') deg[i][j - 1] ++;
 34                 if(s[i][j] == 'R') deg[i][j + 1] ++;
 35             }
 36         vector<PII>que;
 37         for (int i = 0; i < h; i ++)
 38             for (int j = 0; j < w; j ++)
 39                 if(deg[i][j] == 0)
 40                 que.push_back({i, j});
 41         for (int i = 0; i < (int) que.size(); i ++)
 42         {
 43             int nx = que[i].first;
 44             int ny = que[i].second;
 45             int tx = nx;
 46             int ty = ny;
 47             if(s[nx][ny] == 'U') tx --;
 48             if(s[nx][ny] == 'D') tx ++;
 49             if(s[nx][ny] == 'L') ty --;
 50             if(s[nx][ny] == 'R') ty ++;
 51             if(-- deg[tx][ty] == 0)
 52             {
 53                 que.push_back({tx, ty});
 54             }
 55         }
 56         vector< vector<int>> dist(h, vector<int>(w, -1));
 57         vector<int> cnt (h * w);
 58         int A = 0, B = 0;
 59         for (int i = 0; i < h; i ++)
 60             for (int j = 0; j < w; j ++)
 61             {
 62                 if(deg[i][j] != 0 && dist[i][j] == -1)
 63                 {
 64                     que.clear();
 65                     que.push_back({i, j});
 66                     dist[i][j] = 0;
 67                     int len = 0;
 68                     for (int t = 0; t < (int)que.size(); t ++)
 69                     {
 70                         int nx = que[t].first;
 71                         int ny = que[t].second;
 72                         if(deg[nx][ny] != 0)
 73                             len ++;
 74                         for (int k = 0; k < 4; k ++)
 75                         {
 76                             int tx = dx[k] + nx;
 77                             int ty = dy[k] + ny;
 78                             if(tx < 0 || tx >= h || ty < 0 || ty >= w || dist[tx][ty] != -1) continue;
 79                             int x = tx, y = ty;
 80                             if(s[tx][ty] == 'U') x --;
 81                             if(s[tx][ty] == 'D') x ++;
 82                             if(s[tx][ty] == 'L') y --;
 83                             if(s[tx][ty] == 'R') y ++;
 84                             if(x == nx && y == ny)
 85                             {
 86                                 que.push_back({tx, ty});
 87                                 dist[tx][ty] = dist[nx][ny] + 1;
 88                             }
 89                         }
 90                     }
 91                     for (int i = 0; i < len; i ++)
 92                         cnt[i] = 0;
 93             //        cout << que.size() << endl;
 94                     for (int i = 0; i < (int)que.size(); i ++)
 95                     {
 96                         int nx = que[i].first;
 97                         int ny = que[i].second;
 98                         if(c[nx][ny] == '0')
 99                         {
100                             cnt [dist[nx][ny] % len] = 1;
101                         }
102                     }
103                     A += len;
104                     B += accumulate(cnt.begin(), cnt.begin() + len, 0);
105                 }
106             }
107         cout << A << " " << B << '
';
108     }
109 }

View Code