Codeforces Round #411 (Div. 1)（A~D）题解

题目链接：

#411 (Div. 1)

差点翻船。

题解：

A. 这个推导一下，找一下规律就可以了。答案是： ans=(n+1)2−1 。

B. 容易发现，无论我们要对字符串操作几遍，我们最后都是要把字符串变成 bbbb...aaaa 这种形式的。发现每个 a 能把它后边的b变成 2 个b，而 a 要变的次数一定是后面b的个数，所以从后面开始遍历，统计 b 的数量就可以了。

代码：

#include <bits/stdc .h> using namespace std; typedef long long ll; ll mod=1e9 7; int main() { string s; cin>>s; reverse(s.begin(),s.end()); ll ans =0; int b=0; for(int i=0;i<s.length();i ) { if (s[i] == 'b') { b ; } else { ans = (ans b) % mod; b = b * 2 % mod; } } cout<<ans<<endl; return 0; }

C. 这题花了我挺久时间的…还不如先做 D 题啊…

这题题意: 给你n个节点，这 n 个节点构成一棵树。每个节点有si个类型的 ice−cream ，同一个节点的 ice−cream 互相连边构成完全图。对于有相同 ice−cream 的节点 u,v, 在树上一定相邻。求将 ice−cream 构成的图染色，相邻点不能同色的最小颜色数以及方案。

题解：首先 dfs 一遍，将首个节点对应的 ice−cream 赋给不同的数字，同时记录一下 ice−cream 对应的颜色，再 dfs 到下一个树节点，将已经染过色的 ice−cream 保存一下，然后再遍历一遍没被染过色的 ice−cream ，并赋给它一个符合条件的最小值。

我这个跑了1980ms，如果卡了，请加ios::sync_with_stdio(false);

代码：

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll mod=1e9+7; const int N=345678; vector<int>g[N]; vector<int>a[N]; int ans[N]; int dfs(int u,int fa,set<int>&s) { set<int>s1; set<int>s2; vector<int>vv; for(auto x:a[u]) { s1.insert(x); if(s.count(x)) { s2.insert(ans[x]); } else { vv.push_back(x); } } int now=1; for(auto x:vv) { s1.insert(x); while(s2.count(now)) { now++; } ans[x]=now++; } for(auto v:g[u]) { if(v!=fa) { dfs(v,u,s1); } } } int main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++){ int k; cin>>k; while(k--) { int t; cin>>t; a[i].push_back(t); } } for(int i=1;i<n;i++) { int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } set<int>s; dfs(1,-1,s); for(int i=1;i<=m;i++) { if(ans[i]==0){ ans[i]=1; } } int res=0; for(int i=1;i<=m;i++) { res=max(res,ans[i]); } cout<<res<<endl; for(int i=1;i<=m;i++){ cout<<ans[i]<<" "; } return 0; }

D. :

题意：

给你一个森林，每次询问给出 u,v ，问你从 u 所在连通块中随机选出一个点与v所在连通块中随机选出一个点相连，问你此时相连出的树的直径期望是多少？（不是树就输出-1）。

题解:首先，先预处理出各连通块的直径和各点到连通块内一点的最远距离d[x]，通过树形dp+换根可以解决，询问时若在同一连通块内输出-1（并查集），否则若随机选出两点x,y，直径为 max(d[x]+d[y]+1， x 所在连通块的直径， y 所在连通块的直径) ，我们把同一连通块内的 d 从小到大排序一下，枚举小的连通块中的d，到大的连通块中(lower_bound)二分 d[x]+d[y]+1<= max( x 所在连通块的直径，y所在连通块的直径) ， 通过map<pair<int,int>,double>ans记忆一下相同询问的答案，这样我们枚举小的次数最大就只有 O(n1.5) 。(因为这题复杂度只跟小的有关，那么最差的情况是两个连通块是相同的时候，假设所有联通块大小均为 k ，那么复杂度为O(k∗min(q,(nk)2))，所以复杂度为 O(n1.5) ),(具体看代码~)

代码：

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=123456; int fa[N], sz[N]; vector<int> g[N]; int n, m, q; int find(int x) { return fa[x]=x?fa[x]:fa[x]=find(fa[x]); } int dp[N][3], G[N], mx[N]; vector<int> d[N]; vector<ll> sum[N]; bool cmp(int i, int j) { return i > j; } void dfs(int u, int p) { for(auto v: g[u]) { if(v == p) continue; dfs(v, u); dp[u][2] = dp[v][0] + 1; sort(dp[u], dp[u] + 3, cmp); } } void dfs2(int u, int p) { for(auto v: g[u]) { if(v == p) continue; int t; if(dp[u][0] == dp[v][0] + 1) t = dp[u][1]; else t = dp[u][0]; G[v] = max(G[u] + 1, t + 1); dfs2(v, u); } } int main() { cin>>n>>m>>q; for(int i = 1; i <= n; i++) { fa[i] = i; sz[i] = 1; } for(int i = 1; i <= m; i++) { int u, v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); sz[find(v)] += sz[find(u)]; fa[find(u)] = find(v); } for(int i = 1; i <= n; i++) { if(fa[i] == i) { dfs(i, 0); } } for(int i = 1; i <= n; i++) { if(fa[i] == i){ dfs2(i, 0); } } for(int i = 1; i <= n; i++) { d[i].push_back(0); sum[i].push_back(0); } for(int i = 1; i <= n; i++) { int x = find(i); mx[x] = max(mx[x], max(dp[i][0], G[i])); int t = max(dp[i][0], G[i]); d[x].push_back(t); sum[x].push_back(0); } for(int i = 1; i <= n; i++) { sort(d[i].begin(), d[i].end()); if(fa[i] == i) { for(int j = 1; j < sum[i].size(); j++) { sum[i][j] = sum[i][j - 1] + d[i][j]; } } } map<pair<int,int>, double> ans; while(q--) { int x, y; cin>>x>>y; x = find(x); y = find(y); if(x == y) //同一连通块 { puts("-1"); continue; } if(sz[x] > sz[y]) swap(x, y); if(ans.count(make_pair(x, y))) { printf("%.10lf\n", ans[make_pair(x, y)]); continue; } ll res = 0; int k = max(mx[x], mx[y]); bool fst = 1; for(auto v: d[x]) { if(fst) { fst = 0; continue; } int p = lower_bound(d[y].begin(), d[y].end(), k - 1 - v) - d[y].begin(); p = max(p, 1); res += sum[y][sum[y].size() - 1] - sum[y][p - 1] + 1LL * (v + 1) * (sum[y].size() - p); res += 1LL * (p - 1) * k; } double res2 = res * 1.0 / sz[x] / sz[y]; ans[make_pair(x, y)] = res2; printf("%.12lf\n", res2); } return 0; }