Codeforces Round 774 div.2 DEF

D. Weight the Tree

题意：给定一棵树，每个节点有一权重 $w_i$，若一个节点的权值等于其相邻点的权值之和，则这个节点是好的。现在你可以为每个，使得好的点数量最多，在这基础上，还要使得总权值最小，输出赋值方案。

首先想到，除了 $n=2$ 的情况，相邻两个点不可能都是好的

对于不好的点，肯定让它为1（$w_i\ge1$），那么好的点的权值一定等于其度数，我们要选上一些不相邻的点使得它好。

考虑树上dp，$dp[i,0/1]$ 表示以 $i$ 为根节点的子树，选/不选根节点时的最优解。这里比较难想的一点在于，解居然包括了两个信息：好节点数量和总权值。似乎和通常的dp不太一样，但仔细想想是没问题的，因为两个解仍然可以排序：先按照好节点数，再按照总权值。

当前节点选，则其子节点都不能选，当前节点不选，则其子节点任意。

最后要输出方案，从上往下跑一遍就可以了：每个节点的 $dp[i,1]$ 和 $dp[i, 0]$ 比较一下，确定当前点是否选，如果其父节点选了，则强制这个点不选，这样往下搜下去就能确定方案了，

int n, du[maxn];
vector<int> vp[maxn];
int f[maxn][2], g[maxn][2];

bool chose(int x){
    if(f[x][1] == f[x][0]) return g[x][1] < g[x][0];
    return f[x][1] > f[x][0];
}

void dfs(int p, int fa = -1){
    f[p][0] = 0, f[p][1] = 1;
    g[p][0] = 1, g[p][1] = du[p];
    for(int v: vp[p]){
        if(v != fa){
            dfs(v, p);
            f[p][1] += f[v][0];
            g[p][1] += g[v][0];
            int cs = chose(v);
            f[p][0] += f[v][cs];
            g[p][0] += g[v][cs];
        }
    }
}

int ans[maxn];
void getans(int p, int fa, int cs){
    ans[p] = cs ? du[p] : 1;
    for(int v: vp[p]){
        if(v != fa){
            if(cs) getans(v, p, 0);
            else getans(v, p, chose(v));
        }
    }
}

void solve(){
    cin >> n;
    if(n == 2){
        cout << "2 2\n1 1\n";
        return;
    }
    for(int i=1;i<n;i++){
        int x, y;
        cin >> x >> y;
        du[x]++, du[y]++;
        vp[x].emplace_back(y);
        vp[y].emplace_back(x);
    }
    dfs(1);
    int cs = chose(1);
    getans(1, -1, cs);
    cout << f[1][cs] << ' ' << g[1][cs] << '\n';
    for(int i=1;i<=n;i++) cout << ans[i] << " \n"[i == n];
}

E. Power Board

题意：给出一个 $n\times m$ 的图，$(i,j)$ 点上的数字为 $i^j$ ，请问这个图里有多少个不同的数字？

没法比题解写的更清楚了（摆

int n, m;
bool vis[maxn << 5];
int cnt[32];
void solve(){
    cin >> n >> m;
    int tot = 0;
    for(int i=1;i<=23;i++){
        for(int j=1;j<=m;j++){
            if(!vis[i * j]){
                vis[i * j] = true;
                tot++;
            }
        }
        cnt[i] = tot;
    }
    fill(vis, vis+n+1, false);
    ll ans = 1;
    for(int i=2;i<=n;i++){
        if(!vis[i]){
            int k = 0;
            for(ll j=i;j<=n;j*=i){
                vis[j] = true;
                k++;
            }
            ans += cnt[k];
        }
    }
    cout << ans << '\n';
}

F. Playing Around the Table

题意：有 $n$ 名玩家坐成一个环，一共有 $n^2$ 张卡牌，$1-n$ 每种卡牌各 $n$ 张，开局每名玩家持有其中 $n$ 张，接下来进行游戏：每轮中，每名玩家交给下一名玩家一张卡牌（所有人同时进行），如果玩家 $i$ 的所有卡牌都为 $i$，则其“牢固”。现要你构造一种游戏方案，至多 $n^2-n$ 轮，使得每名玩家都“牢固”。

一开始有个暴力的想法，每轮每个人都直接找一个不属于自己的卡牌传出去，然而这样显然会遇到死循环的情况。

全变成一样的不好搞，能不能先全变成不一样的呢？也就是让每个人都拥有1到n的所有卡牌。

这个比较好搞，每次每人都找一张自己有重复的卡牌交出去，如果自己没有重复的，就把上一个人传过来的交出去，这样最终一定能满足。

第一步能在可接受的步数内完成吗？对于每一种卡牌，考虑其最坏的情况：初始所有这张牌都在一个人手上，那么根据上述传递方案，这张牌一共会被传递 $1+2+…+n-1$ 次，即 $\frac{n\times(n-1)}{2}$ 次，那么一共 $n$ 张牌，一轮能传递 $n$ 次，总轮次不会超过 $\frac{n\times(n-1)}{2}$。

现在所有人的牌都是 $1..n$ 了，下一步怎么搞都行

int n;
int cnt[103][103];
void solve(){
    cin >> n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int x; cin >> x;
            cnt[i][x]++;
        }
    }
    vector<int> pass(n+1, 0);
    vector<vector<int>> ans;
    while(true){
        for(int i=1;i<=n;i++){
            pass[i] = 0;
            for(int j=1;j<=n;j++){
                if(cnt[i][j] > 1){
                    pass[i] = j;
                    break;
                }
            }
        }
        for(int i=1;i<=n;i++) if(pass[i] == 0) pass[i] = pass[(i-1+n-1)%n+1];
        for(int i=1;i<=n;i++) if(pass[i] == 0) pass[i] = pass[(i-1+n-1)%n+1];
        if(pass[1] == 0) break;
        for(int i=1;i<=n;i++){
            cnt[i][pass[i]]--;
            cnt[i%n+1][pass[i]]++;
        }
        ans.push_back(pass);
    }

    for(int k=1;k<n;k++){
        for(int d=k;d>=1;d--){
            for(int i=1;i<=n;i++){
                pass[i] = (i + d - 1) % n + 1;
            }
            ans.push_back(pass);
        }
    }
    cout << ans.size() << '\n';
    for(auto ps: ans){
        for(int i=1;i<ps.size();i++) cout << ps[i] << " \n"[i == ps.size()-1];
    }
}