Codeforces Round #530 (Div. 2) Solution

A. Snowball

签。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int w, h, u[2], d[2];
 5 
 6 int main()
 7 {
 8     while (scanf("%d%d", &w, &h) != EOF)
 9     {    
10         for (int i = 0; i < 2; ++i) scanf("%d%d", u + i, d + i);
11         for (int i = h; i >= 0; --i)
12         {
13             w += i;
14             for (int j = 0; j < 2; ++j) if (i == d[j])
15             {
16                 w -= u[j];
17                 w = max(w, 0);
18             }
19         }
20         printf("%d
", w);
21     }
22     return 0;
23 }

View Code

B. Squares and Segments

签.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int n;
 5 int main()
 6 {
 7     while (scanf("%d", &n) != EOF)
 8     {
 9         int limit = sqrt(n);
10         int res = 1e9;
11         for (int i = 1; i <= limit; ++i) 
12             res = min(res, i + n / i + (n % i ? 1 : 0));
13         printf("%d
", res);
14     }
15     return 0;
16 }

View Code

C. Postcard

Solved.

题意：

一个不定字符串，

如果有一位上有糖果，那么它前面那一个字符可以选择留下获得丢失

如果有一位上有雪花，那么它前面那一个字符可以选择留下、丢失或者重复x次,x自定

问能否由一种合法的选择，使得确定后的字符串的长度为n

思路：

先排除两种情况，

第一种是去掉所有可以去掉的字符后，长度都大于n

第二种是保留所有的不定字符，并且没有雪花，此时长度小于n

那么其他情况都是可以构造的

考虑两种情况

第一种没有雪花，那么只需要删掉一些字符使得满足题意，不合法情况在之前已经排除

第二种有雪花，保留一个雪花字符，删掉其他字符，用雪花字符的重复来填充长度

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 1010
 5 char s[N];
 6 int n, len;
 7 
 8 int main()
 9 {
10     while (scanf("%s", s + 1) != EOF)
11     {
12         scanf("%d", &n);
13         len = strlen(s + 1);
14         int snow = 0, candy = 0;
15         for (int i = 1; i <= len; ++i) 
16         {
17             if (s[i] == '*') ++snow;
18             if (s[i] == '?') ++candy;
19         }
20         if (len - 2 * (snow + candy) > n) puts("Impossible");
21         else if (len - candy < n && snow == 0) puts("Impossible");
22         else 
23         {
24             string res = "";
25             if (snow == 0)
26             {
27                 int needdel = len - candy - n;
28                 for (int i = 1; i <= len; ++i) 
29                 {
30                     if (s[i] == '?') continue;
31                     if (i != len && s[i + 1] == '?') 
32                     {
33                         if (needdel) --needdel;
34                         else res += s[i];
35                     }
36                     else res += s[i];
37                 }
38             }
39             else
40             {
41                 int flag = true;
42                 int needadd = n - (len - 2 * (candy + snow));
43                 for (int i = 1; i <= len; ++i)
44                 {
45                     if (i != len && s[i + 1] == '?') continue;
46                     if (i != len && s[i + 1] == '*' && !flag) continue;
47                     if (s[i] == '?' || s[i] == '*') continue;
48                     if (i != len && s[i + 1] == '*')
49                     {
50                         flag = false;
51                         while (needadd--) res += s[i]; 
52                     } 
53                     else res += s[i];
54                 }
55             }
56             cout << res << endl;
57         }
58     }
59     return 0;
60 }

View Code

D. Sum in the tree

Solved.

题意：

有一棵树，有点权，知道奇数层所有点的到根的前缀点权和，偶数层的不知道

求如何分配点权使得满足限制条件并且所有点权和最小

思路：

尽量将点权分配给深度低的，因为这样它产生的贡献肯定比分给深度大的要高

那么一个偶数层点u最多可以分配的点权就是

$Min(s[v] - s[fa[u]]) v为它的儿子$

判-1也很好判，上面这个Min值如果是负的就不行，因为点权大于等于0

对于奇数层点的话直接算它点权

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 #define N 100010
 6 int n, s[N];
 7 vector <int> G[N];
 8 bool flag; ll res;
 9 
10 ll dist[N];
11 void DFS(int u, int fa)
12 {
13     if (s[u] == -1)
14     {
15         if (G[u].size() == 1) return;
16         ll Min = (ll)1e18;
17         for (auto v : G[u]) if (v != fa) 
18             Min = min(Min, s[v] - dist[fa]);
19         if (Min < 0)
20         {
21             flag = false;
22             return; 
23         }
24         res += Min;
25         dist[u] = dist[fa] + Min; 
26     }
27     else 
28     {
29         dist[u] = s[u];
30         res += dist[u] - dist[fa];
31     }
32     for (auto v : G[u]) if (v != fa)
33     {
34         DFS(v, u);
35         if (!flag) return;
36     }
37 }
38 
39 int main()
40 {
41     while (scanf("%d", &n) != EOF)
42     {
43         flag = true; res = 0;
44         for (int i = 1; i <= n; ++i) G[i].clear();
45         for (int i = 2, p; i <= n; ++i)
46         {
47             scanf("%d", &p);
48             G[i].push_back(p);
49             G[p].push_back(i);
50         }
51         for (int i = 1; i <= n; ++i) scanf("%d", s + i);
52         DFS(1, 0); 
53         if (!flag) res = -1;
54         printf("%lld
", res);
55     }
56     return 0;
57 }

View Code

E. Nice table

Upsolved.

题意：

构造一个$n * m的字符串矩阵，只包含'A', 'G', 'C', 'T'$

使得$任意2 cdot 2 的子矩形都包含'A', 'G', 'C', 'T'$

并且要与给出的矩阵不同的字符个数最少

思路：

要求满足$任意2 cdot 2 的子矩形都包含'A', 'G', 'C', 'T'$

的矩阵要满足每一行都是由两个字符交替组成

或者每一列都是由两个字符交替组成

枚举即可

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 #define N 150010
  5 int n, m, p;
  6 string s[N];
  7 string t[2][6] = 
  8 {
  9     {
 10         "AG",
 11         "AC",
 12         "AT",
 13         "GC",
 14         "GT",
 15         "CT",
 16     },    
 17     {
 18         "CT",
 19         "GT",
 20         "CG",
 21         "AT", 
 22         "AC",
 23         "AG",
 24     }
 25 };
 26 string res[12][N];    
 27 
 28 void work_row(string a, string b)
 29 {
 30     for (int i = 0; i < n; ++i) res[p][i].clear();
 31     string tmp[2];
 32     int cnt[2];
 33     for (int i = 0; i < n; ++i) 
 34     {
 35         tmp[0] = tmp[1] = "";
 36         cnt[0] = cnt[1] = 0;
 37         for (int j = 0; j < m; ++j) 
 38             for (int k = 0; k < 2; ++k)
 39                 tmp[k] += (i & 1) ? a[j % 2 ^ k] : b[j % 2 ^ k];    
 40         for (int j = 0; j < m; ++j)
 41             for (int k = 0; k < 2; ++k)
 42                 cnt[k] += tmp[k][j] != s[i][j]; 
 43         if (cnt[0] < cnt[1])
 44             res[p][i] = tmp[0];
 45         else 
 46             res[p][i] = tmp[1]; 
 47     }
 48     ++p;
 49 }
 50 
 51 void work_col(string a, string b)
 52 {
 53     for (int i = 0; i < n; ++i) res[p][i].clear();
 54     string tmp[2];
 55     int cnt[2];
 56     for (int j = 0; j < m; ++j)
 57     {
 58         tmp[0] = tmp[1] = "";
 59         cnt[0] = cnt[1] = 0;
 60         for (int i = 0; i < n; ++i) 
 61             for (int k = 0; k < 2; ++k)
 62                 tmp[k] += (j & 1) ? a[i % 2 ^ k] : b[i % 2 ^ k];
 63         for (int i = 0; i < n; ++i)
 64             for (int k = 0; k < 2; ++k)
 65                 cnt[k] += tmp[k][i] != s[i][j];
 66         if (cnt[0] < cnt[1])
 67             for (int i = 0; i < n; ++i)
 68                 res[p][i] += tmp[0][i];
 69         else
 70             for (int i = 0; i < n; ++i)
 71                 res[p][i] += tmp[1][i];
 72     }
 73     ++p;
 74 }
 75 
 76 int com(int x)
 77 {
 78     int tmp = 0;
 79     for (int i = 0; i < n; ++i) 
 80         for (int j = 0; j < m; ++j)
 81             tmp += res[x][i][j] != s[i][j];
 82    return tmp;    
 83 }
 84 
 85 int main()
 86 {
 87     ios::sync_with_stdio(false);
 88     cin.tie(0); cout.tie(0);
 89     while (cin >> n >> m)
 90     {
 91         p = 0;
 92         for (int i = 0; i < n; ++i) cin >> s[i];
 93         for (int i = 0; i < 6; ++i)
 94             work_row(t[0][i], t[1][i]);
 95         for (int i = 0; i < 6; ++i)
 96             work_col(t[0][i], t[1][i]);
 97         int Min = (int)1e9, pos = -1;
 98         for (int i = 0; i < 12; ++i)
 99         {
100             //puts("bug");
101             //for (int j = 0; j < n; ++j) cout << res[i][j] << "
";
102             int tmp = com(i);
103             //cout << tmp << "
";
104             if (tmp < Min)
105             {
106                 Min = tmp;
107                 pos = i;
108             }
109         }
110         for (int i = 0; i < n; ++i) cout << res[pos][i] << "
";
111     }
112     return 0;
113 }

View Code

F. Cookies

Upsolved.

题意：

刚开始有一个砝码在根节点，两个玩家，

先手玩家可以选择将它移向它的某个儿子，

后手玩家可以选择移除掉通向它某个儿子的边，当然也可以选择跳过这个操作

先手玩家可以选择在什么时候停下来，并且回到根节点，回去的过程可以吃饼干

每个结点有饼干数量，以及吃掉该节点上的一块饼干需要的时间

吃饼干需要时间，在边上走也需要时间，总时间T的情况下吃到的最多的饼干

求双方都在最优操作下，先手玩家吃到的饼干的最多的数量

思路：

先处理出每个结点回去的答案，再二分答案，十分显然

怎么处理答案，

对于点u, 首先吃饼干的时间是$T - 2 * dist(root, u)$

那么用权值BIT维护时间，以及饼干数量，二分查找在剩余时间的可以吃的最大饼干数量

注意处理尾部的部分

再二分答案，dp验证

考虑什么样的情况是合理的，我们假定某一个点是必胜态，那么这个点的深度如果<=1，

那么先手必胜，因为先手先移动

再考虑哪些点是必胜态，如果该点的处理出的饼干数量$ > limit$ 那么就是必胜态

又或者该点有2个儿子以上的点是必胜态，该点也是必胜态，因为后手玩家每次只能删去一条边

递归判断即可

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 #define ll long long
  5 #define N 100010
  6 #define M 1000010
  7 int n; ll T;
  8 int x[N], t[N], l[N];
  9 vector <int> G[N];
 10 
 11 namespace BIT
 12 {
 13     ll val[M], sum[M], a[M];
 14     void init()
 15     {
 16         memset(val, 0, sizeof val);
 17         memset(sum, 0, sizeof sum);
 18         memset(a, 0, sizeof a);
 19     }    
 20     void update(int x, ll v)
 21     {
 22         ll sumv = v * x;
 23         a[x] += v; 
 24         for (; x < M; x += x & -x)
 25         {
 26             val[x] += v;
 27             sum[x] += sumv; 
 28         }  
 29     }
 30     ll query(ll T)
 31     {
 32         int l = 0, r = M - 5;
 33         ll res = 0;
 34         while (r - l >= 0)
 35         {
 36             int mid = (l + r) >> 1;
 37             int x = mid;
 38             ll score = 0, sumt = 0;
 39             for (; x; x -= x & -x)
 40             {
 41                 score += val[x];
 42                 sumt += sum[x];
 43             } 
 44             if (sumt <= T)
 45             {
 46                 score += min(a[mid + 1], ((T - sumt) / (mid + 1)));  
 47                 res = score;
 48                 l = mid + 1;
 49             }
 50             else
 51                 r = mid - 1;
 52         }
 53         return res;
 54     }
 55 }
 56 
 57 int fa[N], deep[N];
 58 ll dist[N], score[N];
 59 void DFS(int u)
 60 {
 61     for (auto v : G[u]) if (v != fa[u])
 62     {
 63         deep[v] = deep[u] + 1;
 64         dist[v] = dist[u] + l[v];
 65         BIT::update(t[v], x[v]);
 66         score[v] = BIT::query(T - 2ll * dist[v]);
 67         DFS(v);
 68         BIT::update(t[v], -x[v]);
 69     }
 70 }
 71 
 72 bool vis[N];
 73 void dp(int u, ll x)
 74 {
 75     if (score[u] >= x)
 76     {
 77         vis[u] = 1;
 78         return;
 79     }
 80     int cnt = 0;
 81     for (auto v : G[u]) if (v != fa[u])
 82     {
 83         dp(v, x);
 84         cnt += vis[v];
 85     }
 86     if (cnt >= 2) vis[u] = 1;
 87 }
 88 
 89 bool check(ll x)
 90 {
 91     memset(vis, 0, sizeof vis);
 92     dp(1, x);
 93     for (int i = 1; i <= n; ++i) if (deep[i] <= 1 && vis[i])
 94         return 1;
 95     return 0;
 96 }
 97 
 98 void init()
 99 {
100     for (int i = 1; i <= n; ++i) G[i].clear();
101     BIT::init();
102 }
103 
104 int main()
105 {
106     while (scanf("%d%lld", &n, &T) != EOF)
107     {
108         init();
109         for (int i = 1; i <= n; ++i) scanf("%d", x + i);
110         for (int i = 1; i <= n; ++i) scanf("%d", t + i);
111         for (int i = 2; i <= n; ++i)
112         {
113             scanf("%d%d", fa + i, l + i);
114             G[i].push_back(fa[i]);
115             G[fa[i]].push_back(i);
116         }
117         BIT::update(t[1], x[1]); score[1] = BIT::query(T); dist[1] = 0; deep[1] = 0; 
118         DFS(1); 
119         ll l = 0, r = (ll)1e11 + 10, res = 0;  
120         while (r - l >= 0)
121         {
122             ll mid = (l + r) >> 1;
123             if (check(mid)) 
124             {
125                 res = mid;
126                 l = mid + 1;
127             }
128             else
129                 r = mid - 1;
130         }
131         printf("%lld
", res);
132     }    
133     return 0;
134 }

View Code