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

￡神魔★判官ぃ 2022-06-16 04:55 135阅读 0赞

#### 题目链接： ####

#### [\#411 (Div. 1)][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;
    }

[411 _Div. 1]: http://codeforces.com/contest/804