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

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 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

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 using namespace std;typedef long long ll;ll mod=1e9+7;const int N=345678;vectorg[N];vectora[N];int ans[N];int dfs(int u,int fa,set&s){ sets1; sets2; vectorvv; 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>u>>v; g[u].push_back(v); g[v].push_back(u); } sets; 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<

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,double>ans记忆一下相同询问的答案，这样我们枚举小的次数最大就只有O(n1.5)。(因为这题复杂度只跟小的有关，那么最差的情况是两个连通块是相同的时候，假设所有联通块大小均为k，那么复杂度为O(k∗min(q,(nk)2))，所以复杂度为O(n1.5)),(具体看代码~)

代码：

#include using namespace std;typedef long long ll;const int N=123456;int fa[N], sz[N];vector 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 d[N];vector 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, 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。