Codeforces Round #533 (Div. 2) Solution

A. Salem and Sticks

签.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 1010
 5 int n, a[N];
 6 
 7 int work(int x)
 8 {
 9     int res = 0;
10     for (int i = 1; i <= n; ++i)
11         res += max(0, abs(x - a[i]) - 1);
12     return res;
13 }
14 
15 int main()
16 {
17     while (scanf("%d", &n) != EOF)
18     {
19         for (int i = 1; i <= n; ++i) scanf("%d", a + i);
20         int Min = (int)1e9, pos = -1;
21         for (int i = 1; i <= 100; ++i) 
22         {
23             int tmp = work(i);
24             if (tmp < Min)
25             {
26                 Min = tmp;
27                 pos = i;
28             }
29         }    
30         printf("%d %d
", pos, Min);
31     }
32     return 0;
33 }

View Code

B. Zuhair and Strings

签.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 200010
 5 int n, k;
 6 char s[N];
 7 
 8 int work(char c)
 9 {
10     int res = 0;
11     int tmp = 0;
12     for (int i = 1; i <= n; ++i)
13     {
14         if (s[i] != c) tmp = 0;
15         else
16         {
17             ++tmp;
18             if (tmp == k)
19             {
20                 ++res;
21                 tmp = 0;
22             }
23         }
24     }
25     return res;
26 }
27 
28 int main()
29 {
30     while (scanf("%d%d", &n, &k) != EOF)
31     {
32         scanf("%s", s + 1);
33         int res = 0;
34         for (int i = 'a'; i <= 'z'; ++i) 
35             res = max(res, work(i));
36         printf("%d
", res);
37     }
38     return 0;
39 }

View Code

C. Ayoub and Lost Array

签.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 #define N 200010
 6 const ll MOD = (ll)1e9 + 7;
 7 int n, l, r;
 8 ll a[3], f[N][3]; 
 9 
10 int main()
11 {
12     while (scanf("%d%d%d", &n, &l, &r) != EOF)
13     {
14         memset(a, 0, sizeof a);
15         while (l % 3 && l <= r)
16         {
17             a[l % 3]++;
18             ++l;
19         }
20         while (r % 3 && l <= r)
21         {
22             a[r % 3]++;
23             --r;
24         }
25         if (l <= r)
26         {
27             ++a[0];
28             int tmp = (r - l) / 3;
29             a[0] += tmp;
30             a[1] += tmp;
31             a[2] += tmp;
32         }
33         memset(f, 0, sizeof f);
34         f[0][0] = 1;
35         for (int i = 1; i <= n; ++i) 
36         {
37             f[i][0] = (f[i - 1][0] * a[0] % MOD + f[i - 1][1] * a[2] % MOD + f[i - 1][2] * a[1] % MOD) % MOD;
38             f[i][1] = (f[i - 1][0] * a[1] % MOD + f[i - 1][1] * a[0] % MOD + f[i - 1][2] * a[2] % MOD) % MOD;
39             f[i][2] = (f[i - 1][0] * a[2] % MOD + f[i - 1][1] * a[1] % MOD + f[i - 1][2] * a[0] % MOD) % MOD;
40         }
41         printf("%lld
", f[n][0]);
42     }        
43     return 0;
44 }

View Code

D. Kilani and the Game

签.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 1010
 5 int n, m, p;
 6 char G[N][N];
 7 int s[10];
 8 struct node
 9 {
10     int x, y, step;
11     node () {}
12     node (int x, int y, int step) : x(x), y(y), step(step) {}
13 };
14 queue <node> q[10];
15 bool stop()
16 {
17     for (int i = 1; i <= p; ++i) if (!q[i].empty())
18         return false;
19     return true;
20 }
21 
22 int Move[][2] = 
23 {
24     -1, 0,
25      1, 0,
26      0,-1,
27      0, 1,
28 };
29 bool ok(int x, int y)
30 {
31     if (x < 1 || x > n || y < 1 || y > m || G[x][y] != '.') return false;
32     return true;
33 }
34 
35 void BFS(int id, int cnt)
36 {
37     while (!q[id].empty())
38     {
39         int x = q[id].front().x;
40         int y = q[id].front().y;
41         int step = q[id].front().step;
42         //printf("%d %d %d %d
", x, y, id, step);
43         if (step / s[id] >= cnt) return;
44         q[id].pop();
45         for (int i = 0; i < 4; ++i) 
46         {
47             int nx = x + Move[i][0];
48             int ny = y + Move[i][1];
49             if (ok(nx, ny))
50             {
51                 G[nx][ny] = id + '0';
52                 q[id].push(node(nx, ny, step + 1));
53             }
54         }
55     }
56 }    
57 
58 int main()
59 {
60     while (scanf("%d%d%d", &n, &m, &p) != EOF)
61     {
62         for (int i = 1; i <= p; ++i) scanf("%d", s + i); 
63         for (int i = 1; i <= n; ++i) scanf("%s", G[i] + 1);
64         for (int i = 1; i <= p; ++i) while (!q[i].empty()) q[i].pop();
65         for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) if (isdigit(G[i][j]))
66             q[G[i][j] - '0'].push(node(i, j, 0));
67         int cnt = 1;
68         while (1)
69         {
70             for (int i = 1; i <= p; ++i) BFS(i, cnt);
71             ++cnt;
72             if (stop()) break;
73         }
74         int ans[10];
75         memset(ans, 0, sizeof ans);
76         for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) if (isdigit(G[i][j]))
77             ++ans[G[i][j] - '0'];
78         //for (int i = 1; i <= n; ++i) printf("%s
", G[i] + 1);
79         for (int i = 1; i <= p; ++i) printf("%d%c", ans[i], " 
"[i == p]);
80     }
81     return 0;
82 }

View Code

E. Helping Hiasat

Upsolved.

题意：

两种操作

更改自己的handle
伙伴查询handle

如果一个伙伴在每次查询时显示的都是自己名字，那么他就会开心

问最多可以让多少人开心

思路：

法一：

一张图的最大独立集是选出一个点集，使得任意两点不相邻

一张图的最大团是选出一个点集，使得任意两点之间有边相连

一张无向图的补图的最大图就是原图的最大独立集

我们发现这道题两个1之间的所有点都是不能一起happy的，那我们给他们两两之间连上边

然后求补图的最大团即可

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 110
 5 int n, m, t;
 6 int g[N][N];
 7 int dp[N];
 8 int stk[N][N];
 9 int mx;
10 
11 map <string, int> mp;
12 int get(string s)
13 {
14     if (mp.find(s) != mp.end()) return mp[s];
15     else mp[s] = t++;
16     return mp[s];
17 }
18 
19 int DFS(int n, int ns, int dep)
20 {
21     if (ns == 0)
22     {
23         mx = max(mx, dep);
24         return 1;
25     }
26     int i, j, k, p, cnt;
27     for (i = 0; i < ns; ++i)
28     {
29         k = stk[dep][i];
30         cnt = 0;
31         if (dep + n - k <= mx)
32             return 0;
33         if (dep + dp[k] <= mx)
34             return 0;
35         for (j = i + 1; j < ns; ++j)
36         {
37             p = stk[dep][j];
38             if (g[k][p])
39                 stk[dep + 1][cnt++] = p;
40         }
41         DFS(n, cnt, dep + 1);
42     }
43     return 1;
44 }
45 
46 int clique(int n)
47 {
48     int i, j, ns;
49     for (mx = 0, i = n - 1; i >= 0; --i) 
50     {
51         for (ns = 0, j = i + 1; j < n; ++j)
52         {
53             if (g[i][j])
54                 stk[1][ns++] = j;
55         }
56         DFS(n, ns, 1);
57         dp[i] = mx;
58     }
59     return mx;
60 }
61 
62 vector <int> vec;
63 void add()
64 {
65     vec.erase(unique(vec.begin(), vec.end()), vec.end());
66     for (auto u : vec) for (auto v : vec)
67         g[u][v] = g[v][u] = 0;
68     vec.clear();
69 }
70 
71 int main()
72 {
73     while (scanf("%d%d", &n, &m) != EOF)
74     {
75         t = 0;
76         mp.clear();
77         for (int i = 0; i < m; ++i) for (int j = 0; j < m; ++j) g[i][j] = 1; 
78         []()
79         {
80             int op; char s[50];
81             for (int nn = 1; nn <= n; ++nn)
82             {
83                 scanf("%d", &op);
84                 if (op == 1)
85                     add();
86                 else 
87                 {
88                     scanf("%s", s + 1);
89                     vec.push_back(get(s + 1));
90                 } 
91             }
92         }();
93         add();
94         for (int i = 0; i < m; ++i) g[i][i] = 1;
95         //for (int i = 1; i <= m; ++i) for (int j = 1; j <= m; ++j) printf("%d %d %d
", i, j, g[i][j]);
96         printf("%d
", clique(m));
97     }
98     return 0;
99 }

View Code

法二：

$m = 40, 可以折半状压，再合起来$

考虑妆压的时候要从子集转移到超集，可以通过$dp上去$

$vp的时候想到折半状压，但是当时是枚举子集来转移，复杂度大大增加..$

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 50
 5 #define M 1100010
 6 int n, m, t;
 7 int G[N][N];
 8 
 9 map <string, int> mp; 
10 int get(string s)
11 {
12     if (mp.find(s) != mp.end()) return mp[s];
13     else mp[s] = ++t;
14     return mp[s];
15 }
16 
17 vector <int> vec;
18 void add()
19 {
20     vec.erase(unique(vec.begin(), vec.end()), vec.end());
21     for (auto u : vec) for (auto v : vec)
22         G[u][v] = 1;
23     vec.clear();
24 }
25 
26 int f[M], g[M];
27 int main()
28 {
29     while (scanf("%d%d", &n, &m) != EOF)
30     {
31         t = 0; mp.clear();
32         memset(G, 0, sizeof G);
33         int op; char s[N];
34         for (int nn = 1; nn <= n; ++nn)
35         {
36             scanf("%d", &op);
37             if (op == 1) add(); 
38             else
39             {
40                 scanf("%s", s + 1);
41                 vec.push_back(get(s + 1)); 
42             }
43         }  
44         add();
45         for (int i = 1; i <= m; ++i) 
46             G[i][i] = 0;
47         int s1 = m / 2, s2 = m - s1;
48         for (int i = 1; i < (1 << s1); i <<= 1) f[i] = 1;
49         for (int i = 1; i < (1 << s2); i <<= 1) g[i] = 1;
50         f[0] = g[0] = 0;
51         for (int i = 1; i < (1 << s1); ++i) 
52         {
53             for (int j = 0; j < s1; ++j) if (!((i >> j) & 1))
54             {
55                 int flag = 1;
56                 for (int k = 0; k < s1; ++k) if (((i >> k) & 1) && G[k + 1][j + 1])
57                 {
58                     flag = 0;
59                     break;  
60                 }
61                 f[i | (1 << j)] = max(f[i | (1 << j)], f[i] + flag);  
62             }    
63         }
64         for (int i = 1; i < (1 << s2); ++i)
65         {
66             for (int j = 0; j < s2; ++j) if (!((i >> j) & 1)) 
67             {
68                 int flag = 1;
69                 for (int k = 0; k < s2; ++k) if (((i >> k) & 1) && G[s1 + k + 1][s1 + j + 1])
70                 {
71                     flag = 0;
72                     break;
73                 }
74                 g[i | (1 << j)] = max(g[i | (1 << j)], g[i] + flag);
75             }
76         }
77         int res = 0;
78         for (int i = 0; i < (1 << s1); ++i)
79         {
80             int s3 = (1 << s2) - 1;
81             for (int j = 0; j < s1; ++j) if ((i >> j) & 1)
82             {
83                 for (int k = 0; k < s2; ++k) if (G[j + 1][s1 + k + 1] && ((s3 >> k) & 1))
84                     s3 ^= (1 << k);
85             }
86             res = max(res, f[i] + g[s3]);
87         }
88         printf("%d
", res);
89     }
90     return 0;
91 }

View Code

法三：

为什么随机也行啊，能不能证明啊，喵喵喵..

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 #define N 50
 6 int n, m, t;
 7 int G[N][N], a[N];
 8 ll f[N];
 9 
10 map <string, int> mp; 
11 int get(string s)
12 {
13     if (mp.find(s) != mp.end()) return mp[s];
14     else mp[s] = ++t;
15     return mp[s];
16 }
17 
18 vector <int> vec;
19 void add()
20 {
21     vec.erase(unique(vec.begin(), vec.end()), vec.end());
22     for (auto u : vec) for (auto v : vec)
23         G[u][v] = 1;
24     vec.clear();  
25 }
26 
27 int main()
28 {
29     while (scanf("%d%d", &n, &m) != EOF)
30     {
31         t = 0; mp.clear();
32         memset(G, 0, sizeof G);
33         int op; char s[N];
34         for (int nn = 1; nn <= n; ++nn)
35         {
36             scanf("%d", &op);
37             if (op == 1) add(); 
38             else
39             {
40                 scanf("%s", s + 1);
41                 vec.push_back(get(s + 1));  
42             }
43         }  
44         add();
45         for (int i = 1; i <= m; ++i) 
46             G[i][i] = 0;
47         int res = 0;
48         for (int i = 1; i <= m; ++i) a[i] = i;
49         for (int i = 1; i <= m; ++i)
50         {
51             f[i] = 0;
52             for (int j = 1; j <= m; ++j) if (G[i][j])
53                 f[i] |= (1ll << (j - 1));
54         }    
55         for (int t = 1; t <= 500; ++t)
56         {
57             random_shuffle(a + 1, a + 1 + m);
58             ll g = 0; int tmp = 0;
59             for (int i = 1; i <= m; ++i) if (((g >> (a[i] - 1)) & 1ll) == 0) 
60             {
61                 g |= f[a[i]];
62                 ++tmp;
63             }
64             res = max(res, tmp);
65         }
66         printf("%d
", res);
67     }
68     return 0;
69 }

View Code