ARC108

E 题意：给定长$n$排列，初始每个数未被标记，每次操作随机选一个未被标记的且标记后满足标记数单调的数标记，如果不存在这样的数结束操作，求期望操作数

考虑区间dp，$f_{l,r}$表示区间$[l,r]$左右端点标记时的期望操作数，那么假设$[l+1,r-1]$中可选点个数为$k$，如果$k=0$那么$f_{l,r}=0$，否则$f_{l,r}=1+\sum\limits_{i=1}^k (f_{l,s_i}+f_{s_i,r})/2$，可以用树状数组优化到$O(n^2\log{n})$

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3+10, P = 1e9+7;
int n, a[N], dp[N][N], inv[N];
int L[N][N],R[N][N],f[N][N];

int main() {
    scanf("%d", &n);
    inv[1] = 1;
    for (int i=2; i<=n; ++i) inv[i] = inv[P%i]*(int64_t)(-P/i)%P;
    for (int i=1; i<=n; ++i) scanf("%d", &a[i]);
    a[n+1] = n+1;
    for (int len=1; len<=n+2; ++len) {
        for (int l=0,r=len-1; r<=n+1; ++l,++r) {
            for (int t=a[r]; t<n+2; t |= t+1) ++f[l][t];
            if (len<=2||a[l]+1>a[r]-1) continue;
            int cnt = 0, w = 0;
            for (int x=a[r]-1; x>=0; x = (x&(x+1))-1) {
                w = (w+L[l][x]+(int64_t)R[r][x])%P;
                cnt += f[l][x];
            }
            for (int x=a[l]; x>=0; x = (x&(x+1))-1) {
                w = (w-L[l][x]-(int64_t)R[r][x])%P;
                cnt -= f[l][x];
            }
            if (!cnt) dp[l][r] = 0;
            else dp[l][r] = (w*(int64_t)inv[cnt]+1)%P;
            for (int t=a[r]; t<n+2; t |= t+1) L[l][t] = (L[l][t]+dp[l][r])%P;
            for (int t=a[l]; t<n+2; t |= t+1) R[r][t] = (R[r][t]+dp[l][r])%P;
        }
    }
    if (dp[0][n+1]<0) dp[0][n+1] += P;
    printf("%d\n", dp[0][n+1]);
}

View Code

F 题意：给定树，把每个点涂上$0$或$1$，假设任意两$0$点最大距离为$X$，任意两$1$点最大距离为$Y$，那么贡献为$max(X,Y)$，求$2^N$种涂色方案的贡献和

先求出树的直径$(u,v)$，假设$u$和$v$同色，那么贡献为直径长度

异色的话，假设贡献为$D$

如果点$x$满足$dis(u,x)>D\wedge dis(v,x)>D$那么一定不合法

如果点$x$满足$dis(u,x)\le D \wedge dis(v,x)\le D$那么这个点可以涂$0$或$1$

其余点都只能涂$1$种颜色

如果答案为$D$，那么对于第二类点还要满足至少$1$个染成距离为$D$的颜色，这个可以容斥求一下

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10, P = 1e9+7;
int n, fa[N], vis[N], pw[N], dep[2][N], f[N], h[N];
vector<int> g[N];
int bfs(int x, int d[]) {
    for (int i=1; i<=n; ++i) vis[i] = 0;
    queue<int> q;
    fa[x] = d[x] = 0, vis[x] = 1, q.push(x);
    while (q.size()) {
        x = q.front(); q.pop();
        for (int y:g[x]) if (!vis[y]) {
            vis[y] = 1, fa[y] = x, d[y] = d[x]+1;
            q.push(y);
        }
    }
    return x;
}
int main() {
    scanf("%d", &n);
    for (int i=1; i<n; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int u = bfs(1,dep[0]), v = bfs(u,dep[1]);
    bfs(v,dep[0]);
    pw[0] = 1;
    int ma = 0;
    for (int i=1; i<=n; ++i) { 
        pw[i] = pw[i-1]*2%P;
        if (i!=u&&i!=v) { 
            ma = max(ma, min(dep[0][i], dep[1][i]));
            ++f[max(dep[0][i], dep[1][i])];
        }
    }
    int ans = pw[n-2]*(int64_t)dep[0][u]%P, now = 0;
    for (int D=0; D<=dep[0][u]; ++D) {
        now += f[D];
        if (D<ma) continue;
        h[D] = pw[now];
        if (D) ans = (ans+(h[D]-h[D-1])*(int64_t)D)%P;
    }
    ans = ans*2%P;
    if (ans<0) ans += P;
    printf("%d\n", ans);
}

View Code

Dwango Programming Contest 6th

C 题意：$n$个小孩，$k$天，第$i$天随机选$a_i$个小孩发一块曲奇，假设最终第$i$个小孩拿了$c_i$块曲奇，求$c_1\times c_2\times ...\times c_n$的期望乘上$\binom{n}{a_1}\times\binom{n}{a_2}\times ... \times \binom{n}{a_k}$

期望乘总方案，那么也就是要求所有方案下的贡献和

先写下刚看到这个题时的一些想法

假设所有$a_i$都为$1$的话，那么很容易做，对于一个确定的序列$c$，方案数就是$\frac{k!}{\prod\limits_{i=1}^n c_i!}$

所以答案也就是$k![x^k]\prod\limits_{i=1}^n\sum\limits_{j\ge 0} \frac{j}{j!} x^{j}=k=\frac{k!n^{k-n}}{(k-n)!}$ 

那么如果$a_i$不全是$1$，那么方案数感觉很难处理，没想出来什么好办法

然后说下正解做法

考虑一个转化：$k\times n$的格子，先对于每个$k$，把第$k$行选$a_k$个格子放上棋子，然后再把每列选恰好一个棋子涂黑，求方案数

这样的话就可以简单dp了，设$f_{i,j}$表示前$i$行涂黑了$j$个棋子的方案数，枚举下一行涂黑多少列转移即可

$dp$转移是一个卷积形式，也可以$O(kn\log{n})$来做

然后还有一个问题是，如果初始每个小孩曲奇数不为$0$的话，是否可做呢？

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+10, K = 22, P = 1e9+7;
int n, k, a[N], f[K][N], C[N][N];
void add(int &a, int64_t b) {a=(a+b)%P;}
int main() {
    scanf("%d%d", &n, &k);
    for (int i=1; i<=k; ++i) scanf("%d", &a[i]);
    for (int i=0; i<=n; ++i) {
        C[i][0] = 1;
        for (int j=1; j<=i; ++j) C[i][j] = (C[i-1][j]+C[i-1][j-1])%P;
    }
    f[0][0] = 1;
    for (int i=1; i<=k; ++i) {
        for (int j=0; j<=n; ++j) {
            int &ret = f[i-1][j];
            if (!ret) continue;
            for (int x=0; x<=a[i]&&x+j<=n; ++x) {
                add(f[i][j+x], C[n-j][x]*(int64_t)C[n-x][a[i]-x]%P*ret);
            }
        }
    }
    printf("%d\n", f[k][n]);
}

View Code

gym102006K

图的最小着色问题，把每条边定向，然后求mex，由于每个点出度不超过$2$，所以答案$\le 3$

所以如果是二分图的话答案就是$2$，否则只能是$3$

gym102439L

题意：范围$[1,2n]$的数，每人分$2$个，随机分给$n$个人，求和的最大值唯一的概率

打个表可以发现和的最大值不变时，方案数是不变的

假设最大值是$i+j$，可以发现分布是$xxxxxixxjxx$的话很好计算，直接枚举最后三个数匹配，剩余数即可任意匹配

ARC107F

题意：$n$点$m$边无向图，每个点$i$有权值$(A_i,B_i)$，可以任选一些点删除，花费是删点的$A$值和，删点后对应边也删除，最终每个连通块得分为$B$值和的绝对值，求最大化得分和-花费

每个点有三种情况，取$b_i$或取$-b_i$或删除，并且要求每个连通块正负要相同。

答案先加上$\sum |b_i|$，然后构造最小割即可。

同一个连通块符号相同，可以拆点，对于边$(u,v)$连$(u,v+n,INF),(v,u+n,INF)$

对于$b_i\le 0$的连边$(S,i,0),(i,i+n,a+b),(i+n,T,2b)$，否则连$(S,i,-2b),(i,i+n,-b+a),(i+n,T,0)$

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10, S = N-2, T = N-1, INF = 0x3f3f3f3f;
int n, m, a[N], b[N];
struct edge {
    int to,w,next;
    edge(int to=0,int w=0,int next=0):to(to),w(w),next(next) {}
} e[N];
int head[N], dep[N], cur[N], cnt=1;
queue<int> Q;
int bfs() {
    for (int i=1; i<=2*n; ++i) dep[i]=INF,cur[i]=head[i];
    dep[S]=INF,cur[S]=head[S];
    dep[T]=INF,cur[T]=head[T];
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        for (int i=head[u]; i; i=e[i].next) {
            if (dep[e[i].to]>dep[u]+1&&e[i].w) {
                dep[e[i].to]=dep[u]+1;
                Q.push(e[i].to);
            }
        }
    }
    return dep[T]!=INF;
}
int dfs(int x, int w) {
    if (x==T) return w;
    int used = 0;
    for (int i=cur[x]; i; i=e[i].next) {
        cur[x] = i;
        if (dep[e[i].to]==dep[x]+1&&e[i].w) {
            int f = dfs(e[i].to,min(w-used,e[i].w));
            if (f) used+=f,e[i].w-=f,e[i^1].w+=f;
            if (used==w) break;
        }
    }
    return used;
}
int dinic() {
    int ans = 0;
    while (bfs()) ans+=dfs(S,INF);
    return ans;
}
void add(int u, int v, int w) {
    e[++cnt] = edge(v,w,head[u]);
    head[u] = cnt;
    e[++cnt] = edge(u,0,head[v]);
    head[v] = cnt;
}

int main() {
    scanf("%d%d", &n, &m);
    int tot = 0;
    for (int i=1; i<=n; ++i) scanf("%d", &a[i]);
    for (int i=1; i<=n; ++i) scanf("%d", &b[i]), tot += abs(b[i]);
    for (int i=1; i<=m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u+n,v,INF);
        add(v+n,u,INF);
    }
    for (int i=1; i<=n; ++i) {
        if (b[i]>=0) add(i,i+n,b[i]+a[i]),add(i+n,T,2*b[i]);
        else add(S,i,-2*b[i]),add(i,i+n,-b[i]+a[i]);
    }
    printf("%d\n", tot-dinic());
}

View Code

gym101982I

题意：给定序列，每个元素范围$[1,k]$，有些位置为$0$表示不确定的数，要求填上$[1,k]$使得逆序对最大

首先可以发现填数一定是非降的，那么就可以得到一个dp做法

设${dp}_{i,j}$表示前$i$个位置，最后一个位置填的数是$j$的最大值

先除去已有的数之间的逆序对贡献，那么每次枚举填数的数和填的长度来转移

那么有${dp}_{i,j}=\max\limits_{0\le x<i,j<y\le k+1} {dp}_{x,y}+calc(x+1,i,j)$

$calc(l,r,j)$表示$[l,r]$中填$j$时对已经填好的数的贡献

这个$dp$方程化简一下发现可以斜率优化到$O(nk)$

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int n, k, cur, a[N], sum[N], cnt[N][105];
int64_t dp[N][2],f[N];
deque<int> q;
int64_t dy(int a, int b) {
    return sum[a]*(int64_t)sum[a]+f[a]-dp[a][cur^1]-sum[b]*(int64_t)sum[b]-f[b]+dp[b][cur^1];
}
int64_t dx(int a, int b) {
    return sum[a]-sum[b];
}
int chk(int a, int b, int c) {
    return dy(a,b)*dx(b,c)<=dy(b,c)*dx(a,b);
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i=1; i<=n; ++i) { 
        scanf("%d", &a[i]);
        memcpy(cnt[i],cnt[i-1],sizeof cnt[0]);
        sum[i] = sum[i-1]+!a[i];
        if (a[i]) {
            for (int j=a[i]; j<=k; ++j) ++cnt[i][j];
        }
    }
    int64_t ans = 0;
    for (int i=1; i<=n; ++i) if (a[i]) ans += cnt[i-1][k]-cnt[i-1][a[i]];
    if (!sum[n]) return printf("%lld\n", ans),0;
    for (int i=1; i<=n; ++i) dp[i][0] = -1e12;
    for (int j=k; j; --j) {
        for (int i=1; i<=n; ++i) {
            f[i] = f[i-1];
            if (!a[i]) f[i] += cnt[i-1][k]-cnt[i-1][j]+cnt[n][j-1]-cnt[i][j-1];
        }
        q.clear();
        q.push_back(0);
        cur ^= 1;
        for (int i=1; i<=n; ++i) dp[i][cur] = -1e12;
        for (int i=1; i<=n; ++i) {
            if (a[i]) {
                dp[i][cur] = dp[i-1][cur];
                continue;
            }
            while (q.size()>1&&dy(q[1],q[0])<=dx(q[1],q[0])*sum[i]) q.pop_front();
            dp[i][cur] = dp[q[0]][cur^1]+f[i]-f[q[0]]+sum[q[0]]*(sum[i]-(int64_t)sum[q[0]]);
            dp[i][cur] = max(dp[i][cur], dp[i][cur^1]);
            while (q.size()>1&&chk(i,q.back(),q[q.size()-2])) q.pop_back();
            q.push_back(i);
        }
    }
    printf("%lld\n", dp[n][cur]+ans);
}

View Code