Educational Codeforces Round 117

D. For Gamers. By Gamers.

题意：玩家有 $C$ 块钱，可以从酒馆中招募随从，每个随从有攻击力 $d_i$，生命 $h_i$，花费 $c_i$ 块钱。接下来有若干轮战斗，每轮战斗有一个敌人，攻击力 $D_j$，生命 $H_j$。每轮相互独立（钱也独立），玩家可以招募若干个相同随从来和怪物战斗，但要求己方没有随从会死亡。问每一轮战斗需要花费至少多少金币

战斗不是回合制的，双方连续攻击。

解：因为是双方连续攻击，所以两个怪物战斗，我放胜利的条件即 $H/d\lt h/D$，换算一下即：$H\times D\lt h\times d$

那么每个怪物的战斗力都可以直接用其攻击乘上生命来衡量。

如果购买多个随从同时作战，因为要求不能死任何一个，所以相当于攻击力可叠加，但生命值不能叠加。其实战斗力是完全等比例增长的。

那么就变成了一个背包问题，但数据范围显然不允许 $n^2$，这时发现题目又有一个条件：只能购买相同随从。

那么在背包转移时，只需要枚举每个随从花费金币的倍数去更新即可。复杂度是经典调和级数 $O(nlogn)$

最后每轮询问二分找一下大于这个怪物战斗力的最小花费（

ll n, m;
ll mxc[maxn], f[maxn];
 
void solve(){
    ll C;
    cin >> n >> C;
    for(ll i=1;i<=n;i++){
        ll c, x, y;
        cin >> c >> x >> y;
        f[c] = max(f[c], x * y);
    }
    for(ll i=1;i<=C;i++){
        f[i] = max(f[i], f[i-1]);
        for(ll j=2;j*i<=C;j++){
            f[j*i] = max(f[j*i], f[i] * j);
        }
    }
 
    cin >> m;
    for(ll i=1;i<=m;i++){
        ll x, y;
        cin >> x >> y;
        if(f[C] <= x * y){
            cout << "-1" << " \n"[i == m];
            continue;
        }
        ll p = lower_bound(f+1, f+C+1, x * y + 1) - f;
        cout << p << " \n"[i == m];
    }
}

E. Star MST

题意：对于 $n$ 个节点的完全图，每条边不超过 $m$，如果所有和1相连的边能构成最小生成树，那么这个完全图是好的。请问一共有多少种好的完全图？

从kruskal角度考虑：在我们依次将边插入时，除了1以外不能存在其他联通块，否则即不是最小生成树。

设 $dp[i][j]$ 为已经将小于等于 $j$ 的所有边插入，此时1的联通块大小为 $i$ 的答案。

转移时，插入所有长度为 $j+1$ 的边，枚举有多少个点因此并入联通块了（假设有 $k$ 个），那么一共有 $C_{n-i}^{k}$ 种取法，并入后新增的边数为 $k\times(k-1)/2+i\times k$，其中 $k$ 条确定长度为 $j+1$ 了，另外的边长度可以在 $[j+1，m]$ 之间任选。

转移：$dp[i+k][j+1]+=dp[i][k]\times C_{n-i}^k\times(m-j)^{k\times (k-1)/2+(i-1)\times k}$

ll n, m;
ll f[300][300];
 
ll qpow(ll x, ll p){
    ll r = 1;
    while(p > 0){
        if(p & 1) r = r * x % mode;
        x = x * x % mode;
        p /= 2;
    }
    return r;
}
 
ll inv(ll x){ return qpow(x, mode-2);}
ll jc[maxn];
ll C(ll n, ll m){
    return jc[n] * inv(jc[m] * jc[n-m] % mode) % mode;
}
 
void solve(){
    jc[0] = 1;
    for(int i=1;i<=1000;i++) jc[i] = jc[i-1] * i % mode;
 
    cin >> n >> m;
    f[1][0] = 1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<m;j++){
            for(int k=0;i+k<=n;k++){
                (f[i+k][j+1] += f[i][j] * C(n-i, k) % mode * qpow(m-j, k*(k-1)/2 + (i-1)*k) % mode) %= mode;
            }
        }
    }
    cout << f[n][m] << '\n';
}

F. Words on Tree

写的稀碎，看看思路就好，代码别看了（

题意：现在有一棵树，每个点上有一个字符，给定了若干个限制条件，形如 $x,y,s$，表示树上 $x$ 到 $y$ 的路径上的字符连起来必须是 $s$ 或者 $s$ 的反串。你需要填写树上的字符使得所有限制条件都被满足。

既然有限制条件，并且这个限制条件显然是二选一，我们肯定要往2-SAT方向去想

对每个限制条件建两个点，一个表示字符正着放，另一个表示反着放。问题是怎么连边，似乎怎么连都得 $n^2$ 条边

这里的关键在于：并不需要把所有约束条件都表示出来，只要一个约束条件已经被已有约束包含，就可以忽略它

具体而言，我们在每一个节点处随便选取一个涉及这个节点的约束条件，那么可以确定这个节点一定是两种字符之一，我们称这个被选择的约束条件为哨兵。

对于任意两个有重复部分的约束条件，它们都去和哨兵建立联系，它们两个之间的约束关系也就通过哨兵建立了。

int n, m;
vector<int> vp[maxn], vp2[maxn];
int dep[maxn], fa[maxn], bin[maxn];
char chr[maxn][2];
 
void dfs(int p, int f){
    fa[p] = f;
    dep[p] = dep[f] + 1;
    for(int v: vp[p]){
        if(v != f) dfs(v, p);
    }
}
 
vector<int> getPath(int u, int v){
    vector<int> r1, r2;
    while(u != v){
        if(dep[u] > dep[v]) r1.push_back(u), u = fa[u];
        else r2.push_back(v), v = fa[v];
    }
    r1.push_back(u);
    for(int i=(int)r2.size()-1;i>=0;i--) r1.push_back(r2[i]);
    return r1;
}
 
int dfn[maxn], low[maxn], bel[maxn], dfcnt = 0;
stack<int> stk;
int belid = 0;
 
void tarjian(int p){
    dfn[p] = low[p] = ++dfcnt;
    stk.push(p);
    for(int v: vp2[p]){
        if(!dfn[v]) tarjian(v);
        if(!bel[v]) low[p] = min(low[p], low[v]);
    }
    if(dfn[p] == low[p]){
        bel[p] = ++belid;
        while(stk.top() != p){
            bel[stk.top()] = belid;
            stk.pop();
        }
        stk.pop();
    }
}
 
void solve(){
    cin >> n >> m;
    for(int i=1;i<n;i++){
        int x, y;
        cin >> x >> y;
        vp[x].push_back(y);
        vp[y].push_back(x);
    }
    dfs(1, 0);
    struct query{
        int x, y;
        string s;
    };
    vector<query> qr(m + 1);
    for(int i=1;i<=m;i++){
        int x, y;
        string s;
        cin >> x >> y >> s;
        qr[i] = {x, y, s};
        auto l = getPath(x, y);
        for(int j=0;j<l.size();j++){
            if(!bin[l[j]]){
                chr[l[j]][0] = s[j];
                chr[l[j]][1] = s[s.size()-1-j];
                bin[l[j]] = i;
            }
        }
    }
    for(int i=1;i<=m;i++){
        string s = qr[i].s;
        auto l = getPath(qr[i].x, qr[i].y);
        for(int j=0;j<l.size();j++){
            char mc[2] = {s[j], s[s.size()-1-j]};
            char *yc = chr[l[j]];
            int yj = bin[l[j]];
            if(yj == i) continue;
            if(yc[0] == yc[1] && mc[0] == mc[1] && yc[0] == mc[0]) continue;
            if(yc[0] == yc[1]){
                if(mc[0] != yc[0] && mc[1] != yc[0]){
                    cout << "NO\n";
                    return;
                }else{
                    if(mc[0] == yc[0]) vp2[m+i].push_back(i);
                    else vp2[i].push_back(m+i);
                }
            }else if(mc[0] == mc[1]){
                if(mc[0] != yc[0] && mc[0] != yc[1]){
                    cout << "NO\n";
                    return;
                }else{
                    if(mc[0] == yc[0]) vp2[yj+m].push_back(yj);
                    else vp2[yj].push_back(yj+m);
                }
            }else{
                bool fd = false;
 
                for(int u=0;u<2;u++){
                    if(mc[u] != yc[0] && mc[u] != yc[1]){
                        vp2[i+m*u].push_back(i+m*(u^1));
                    }
                }
                for(int u=0;u<2;u++){
                    if(yc[u] != mc[0] && yc[u] != mc[1]){
                        vp2[yj+m*u].push_back(yj+m*(u^1));
                    }
                }
 
                for(int u=0;u<2;u++){
                    for(int v=0;v<2;v++){
                        if(mc[u] == yc[v]){
                            fd = true;
                            vp2[i+m*u].push_back(yj+m*v);
                            vp2[yj+m*v].push_back(i+m*u);
                        }
                    }
                }
                if(!fd){
                    cout << "NO\n";
                    return;
                }
            }
        }
    }
    for(int i=1;i<=2*m;i++) if(!dfn[i]) tarjian(i);
    for(int i=1;i<=m;i++){
        if(bel[i] == bel[i+m]){
            cout << "NO\n";
            return;
        }
    }
    vector<int> cs(m+1);
    for(int i=1;i<=m;i++){
        if(bel[i] < bel[i+m]) cs[i] = 0;
        else cs[i] = 1;
    }
    cout << "YES\n";
    for(int i=1;i<=n;i++){
        if(!bin[i]) cout << 'a';
        else cout << chr[i][cs[bin[i]]];
    }
    cout << '\n';
}