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,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;
}