Codeforces Round #354 (Div. 2)

5/5

水了场CF，写个水水地题解~~

题A CodeForces 676A

题意：给你一个排列，问你交换一次，最大最小位置最远是多少？

题解：暴力交换，暴力算，反正数据小.偷懒被hack更惨！！

 1 /*zhen hao*/
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 
 5 #define lson l, m, rt*2
 6 #define rson m + 1, r, rt*2+1
 7 #define xx first
 8 #define yy second
 9 
10 typedef pair<int,int> pii;
11 typedef long long ll;
12 typedef unsigned long long ull;
13 
14 int s[110], n;
15 
16 int cal() {
17   int p1, m1 = 110, p2, m2 = -110;
18   for (int i = 1; i <= n; i++) {
19     if (m1 > s[i]) m1 = s[i], p1 = i;
20     if (m2 < s[i]) m2 = s[i], p2 = i;
21   }
22   int ret = abs(p1 - p2);
23   return ret;
24 }
25 
26 int main() {
27 //  freopen("case.in", "r", stdin);
28   cin >> n;
29   for (int i = 1; i <= n; i++) cin >> s[i];
30   int ans = 0;
31   for (int i = 1; i <= n; i++)
32     for (int j = i + 1; j <= n; j++) {
33       swap(s[i], s[j]);
34       ans = max(ans, cal());
35       swap(s[i], s[j]);
36     }
37   printf("%d
", ans);
38   return 0;
39 }

代码君

题B CodeForces 676B

题意：给你n层杯子叠起来，然后往上面开始倒水，1s满一个杯子，问你最后又多少个杯子是满的？

题解：数据小，直接模拟，写个dfs即可。

 1 /*zhen hao*/
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 
 5 #define lson l, m, rt*2
 6 #define rson m + 1, r, rt*2+1
 7 #define xx first
 8 #define yy second
 9 
10 typedef pair<int,int> pii;
11 typedef long long ll;
12 typedef unsigned long long ull;
13 
14 int n, t;
15 int v[110][2];
16 double cnt[1100];
17 
18 void init() {
19   int cur = 1;
20   for (int i = 1; i < 11; i++) {
21     for (int j = 0; j < i; j++) {
22       v[cur][0] = cur + i;
23       v[cur][1] = cur + i + 1;
24 //      cout << cur << ' ' << v[cur][0] << ' ' << v[cur][1] << endl;
25       cur++;
26     }
27   }
28 }
29 
30 void dfs(int d, int cur, double add) {
31   cnt[cur] += add;
32   if (d >= n) return;
33   if (cnt[cur] > 1.0) {
34     double flow = cnt[cur] - 1.0;
35     cnt[cur] = 1.0;
36     dfs(d + 1, v[cur][0], flow / 2);
37     dfs(d + 1, v[cur][1], flow / 2);
38   }
39 }
40 
41 int main() {
42 //  freopen("case.in", "r", stdin);
43   init();
44   cin >> n >> t;
45   for (int i = 0; i < t; i++) {
46     dfs(0, 1, 1.0);
47   }
48   int ans = 0;
49   for (int i = 1; i <= n * (n + 1) / 2; i++) if (cnt[i] >= 1.0) ans++;
50   cout << ans << endl;
51   return 0;
52 }

代码君

题C CodeForces 676C

题意：给你个字符串，只有a和b，然后可以改k个，问你最长连续是多少？

题解：好像可以用单调队列搞，我没想这么多，就用了个二分答案。

 1 /*zhen hao*/
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 
 5 #define lson l, m, rt*2
 6 #define rson m + 1, r, rt*2+1
 7 #define xx first
 8 #define yy second
 9 
10 typedef pair<int,int> pii;
11 typedef long long ll;
12 typedef unsigned long long ull;
13 
14 const int maxn = 1e5 + 100;
15 char s[maxn];
16 int n, k, len;
17 int cnta[maxn], cntb[maxn];
18 
19 bool check(int m) {
20   int best = min(cnta[m - 1], cntb[m - 1]);
21   for (int i = 1; i + m <= len; i++) {
22     int tmp = min(cnta[i + m - 1] - cnta[i - 1], cntb[i + m - 1] - cntb[i - 1]);
23     best = min(best, tmp);
24   }
25   return best <= k;
26 }
27 
28 int main() {
29 //  freopen("case.in", "r", stdin);
30   cin >> n >> k;
31   scanf("%s", s);
32   len = strlen(s);
33   int a = 0, b = 0, L = 0, R = len + 1;
34   for (int i = 0; i < len; i++) {
35     if (s[i] == 'a') a++; else b++;
36     cnta[i] = a; cntb[i] = b;
37 //    cout << a << ' ' << b << endl;
38   }
39   while (R - L > 1) {
40     int M = (R + L) / 2;
41     if (check(M)) L = M;
42     else R = M;
43   }
44   printf("%d
", L);
45   return 0;
46 }

代码君

题D CodeForces 676D

题意：给你一个地图，除了‘*’是没有门的其他字符都有相应的门，每次操作可以到对应的门，也可以翻转这个点，然后代价是所有点也同时向顺时针翻转，然后给你起点和终点，问你最小花多少时间。

题解：没看到所有点都翻转，然后码了个最短路，GG。如果所有都可以翻转的话，显然可以用bfs。具体做法是，先用一个can[i][j][k][l]表示当前翻转的面是i面，然后j表示方向，k和l表示位置，先得到第0面，然后可以用一个for循环得到1、2、 3面的情况，然后就是很普通的bfs了。

 1 /*zhen hao*/
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 
 5 #define lson l, m, rt*2
 6 #define rson m + 1, r, rt*2+1
 7 #define xx first
 8 #define yy second
 9 
10 typedef pair<int,int> pii;
11 typedef long long ll;
12 typedef unsigned long long ull;
13 
14 const int maxn = 1e3 + 10, dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
15 char maze[maxn][maxn];
16 int vis[4][maxn][maxn], can[5][5][maxn][maxn];
17 int n, m, xt, yt, xm, ym;
18 
19 struct Node {
20   int x, y, c, d;
21   Node(int x=0, int y=0, int c=0, int d=0) : x(x), y(y), c(c), d(d) {}
22 };
23 
24 void init_graph() {
25   memset(can, 0, sizeof can);
26     for (int i = 0; i < n; i++)
27       for (int j = 0; j < m; j++) {
28         if(maze[i][j] == '+') can[0][0][i][j] = can[0][1][i][j] = can[0][2][i][j] = can[0][3][i][j] = 1;
29         if(maze[i][j] == 'U') can[0][1][i][j] = can[0][2][i][j] = can[0][3][i][j] = 1;
30         if(maze[i][j] == 'R') can[0][0][i][j] = can[0][2][i][j] = can[0][3][i][j] = 1;
31         if(maze[i][j] == 'D') can[0][0][i][j] = can[0][1][i][j] = can[0][3][i][j] = 1;
32         if(maze[i][j] == 'L') can[0][0][i][j] = can[0][1][i][j] = can[0][2][i][j] = 1;
33         if(maze[i][j] == '-') can[0][1][i][j] = can[0][3][i][j] = 1;
34         if(maze[i][j] == '|') can[0][0][i][j] = can[0][2][i][j] = 1;
35         if(maze[i][j] == '^') can[0][0][i][j] = 1;
36         if(maze[i][j] == '>') can[0][1][i][j] = 1;
37         if(maze[i][j] == 'v') can[0][2][i][j] = 1;
38         if(maze[i][j] == '<') can[0][3][i][j] = 1;
39       }
40     for (int x = 1; x < 4; x++)
41       for (int i = 0; i < n; i++)
42         for (int j = 0; j < m; j++)
43           for (int k = 0; k < 4; k++)
44             can[x][(k + 1) % 4][i][j] = can[x - 1][k][i][j];
45 }
46 
47 int bfs() {
48   queue<Node> q;
49   q.push(Node(xt, yt, 0, 0));
50   memset(vis, false, sizeof vis);
51   vis[0][xt][yt] = 1;
52   while (!q.empty()) {
53     Node r = q.front(); q.pop();
54     if (r.x == xm && r.y == ym) return r.d;
55 
56     for (int i = 0; i < 4; i++) if (can[r.c][i][r.x][r.y]) {
57       int nx = r.x + dx[i], ny = r.y + dy[i];
58       if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
59       if (vis[r.c][nx][ny] || !can[r.c][(i + 2) % 4][nx][ny]) continue;
60       vis[r.c][nx][ny] = 1;
61       q.push(Node(nx, ny, r.c, r.d + 1));
62     }
63 
64     int nc = (r.c + 1) % 4;
65     if (vis[nc][r.x][r.y]) continue;
66     vis[nc][r.x][r.y] = 1;
67     q.push(Node(r.x, r.y, nc, r.d + 1));
68   }
69   return -1;
70 }
71 
72 int main() {
73 //  freopen("case.in", "r", stdin);
74   cin >> n >> m;
75   for (int i = 0; i < n; i++) {
76     scanf("%s", maze[i]);
77   }
78   scanf("%d%d%d%d", &xt, &yt, &xm, &ym);
79   xt--; yt--; xm--; ym--;
80 //  cout << xt << ' ' << yt << endl;
81   init_graph();
82   printf("%d
", bfs());
83   return 0;
84 }

代码君

题E CodeForces 676E

题意：给你一个多项式：

P(x) = anxⁿ + an - 1x^n - 1 + ... + a1x + a0

然后另Q(x) = x - k，两个人轮流填系数使得Q（x）|P（x），也就是存在B(x)使得P(x) = B(x)Q(x)成立，现在可能已经进行了一部分，问你继续玩能不能够获胜？

题解：完全没思路，弃疗了。百度了多项式除法也不会做，然后即参照这位老兄的题解。

主要突破点是找做完除法后的余数，既然是余数，那么P（x）减去余数必然能够被Q（x）整除，那么设这个余数是J，然后满足Q（x）|（P（x）-J），怎么得到这个J呢？从P（x）出发，要每一项都得到一个（x-k）的公因子，那不就可以被Q（x）整除了吗？所以另

J = ankⁿ + an - 1k^n - 1 + ... + a1k + a0

因为P（x） - J = an（x - k）（...） + an - 1(x - k) (...) + a1(x - k)，所以只要让这个J = 0，就说明可以整除了，之后的情况就像上述博客说的那样了。最后提醒一点是：用这个博客的随机数的方法可以过，将数设为数据没有考虑的一个数也可以过。

 1 /*zhen hao*/
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 
 5 typedef long long ll;
 6 const int maxn = 1e5 + 10, mod = 100003619;
 7 int a[maxn], t[maxn], n, k;
 8 char s[110];
 9 
10 int main() {
11 //  freopen("case.in", "r", stdin);
12   cin >> n >> k;
13   int ok = 0, c = 0;
14   for (int i = 0; i <= n; i++) {
15     scanf("%s", s);
16     if (s[0] == '?') ok = 1;
17     else {
18       t[i] = 1;
19       sscanf(s, "%d", a + i);
20       c ^= 1;
21     }
22   }
23   if (k == 0) {
24     if (t[0]) puts(a[0] == 0 ? "Yes" : "No");
25     else puts(c & 1 ? "Yes" : "No");
26   } else {
27     if (ok) puts(n & 1 ? "Yes" : "No");
28     else {
29       ll res = 0;
30       for (int i = n; i >= 0; i--) {
31         res = res * k + a[i];
32         res %= mod;
33       }
34       puts(res == 0 ? "Yes" : "No");
35     }
36   }
37   return 0;
38 }

代码君