Codeforces|Codeforces Round #530 (Div. 2) Solution CodeforcesRound#530(Div.2)Solution

A. Snowball
签。

文章图片

文章图片

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

View Code

B. Squares and Segments
签.

Codeforces|Codeforces Round #530 (Div. 2) Solution

文章图片

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

View Code

C. Postcard
Solved.
题意：
一个不定字符串，
如果有一位上有糖果，那么它前面那一个字符可以选择留下获得丢失
如果有一位上有雪花，那么它前面那一个字符可以选择留下、丢失或者重复x次,x自定
问能否由一种合法的选择，使得确定后的字符串的长度为n
思路：
先排除两种情况，
第一种是去掉所有可以去掉的字符后，长度都大于n
第二种是保留所有的不定字符，并且没有雪花，此时长度小于n
那么其他情况都是可以构造的
考虑两种情况
第一种没有雪花，那么只需要删掉一些字符使得满足题意，不合法情况在之前已经排除
第二种有雪花，保留一个雪花字符，删掉其他字符，用雪花字符的重复来填充长度

文章图片

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

View Code
D. Sum in the tree
Solved.
题意：
有一棵树，有点权，知道奇数层所有点的到根的前缀点权和，偶数层的不知道
求如何分配点权使得满足限制条件并且所有点权和最小
思路：
尽量将点权分配给深度低的，因为这样它产生的贡献肯定比分给深度大的要高
那么一个偶数层点u最多可以分配的点权就是
$Min(s[v] - s[fa[u]])\ v为它的儿子$
判-1也很好判，上面这个Min值如果是负的就不行，因为点权大于等于0
对于奇数层点的话直接算它点权

文章图片

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

View Code
【Codeforces|Codeforces Round #530 (Div. 2) Solution】
F. Cookies
Upsolved.
题意：
刚开始有一个砝码在根节点，两个玩家，
先手玩家可以选择将它移向它的某个儿子，
后手玩家可以选择移除掉通向它某个儿子的边，当然也可以选择跳过这个操作
先手玩家可以选择在什么时候停下来，并且回到根节点，回去的过程可以吃饼干
每个结点有饼干数量，以及吃掉该节点上的一块饼干需要的时间
吃饼干需要时间，在边上走也需要时间，总时间T的情况下吃到的最多的饼干
求双方都在最优操作下，先手玩家吃到的饼干的最多的数量
思路：
先处理出每个结点回去的答案，再二分答案，十分显然
怎么处理答案，
对于点u, 首先吃饼干的时间是$T - 2 * dist(root, u)$
那么用权值BIT维护时间，以及饼干数量，二分查找在剩余时间的可以吃的最大饼干数量
注意处理尾部的部分

再二分答案，dp验证
考虑什么样的情况是合理的，我们假定某一个点是必胜态，那么这个点的深度如果<=1，
那么先手必胜，因为先手先移动
再考虑哪些点是必胜态，如果该点的处理出的饼干数量$ > limit$ 那么就是必胜态
又或者该点有2个儿子以上的点是必胜态，该点也是必胜态，因为后手玩家每次只能删去一条边
递归判断即可

文章图片

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

View Code
转载于:https://www.cnblogs.com/Dup4/p/10227106.html