省队集训-0424模拟赛

A.图上的游戏

题意：

有一张图，

n

个点，每个点有颜色

\in\set{0,1,2}

，随机产生

m

条有向边（可重可自环）。然后

A,B

两个人博弈，轮流操作，一次可以将一个颜色为

2

的点染成

1

或

2

，直到不存在颜色为

2

的点。最终分数为：所有两端颜色不同的边中，

0\rightarrow1

的边的个数，减去

1\rightarrow0

的边的个数。

A

想要最大化得分，

B

想要最小化得分。

给定

N,M

，以及

N

个点的颜色。

\forall i \le N,j\le M

，求当只保留

[1,i]

的点（即

n=i

），且

m=j

时，对于所有的

n^{2m}

种情况，博弈分数的总和为多少。

N,M\le50

。

Sol：

设

v_i

表示一个点的出度减入度，则分数为

\frac{1}{2}(\sum\limits_{c_i=0}v_i-\sum\limits_{c_i=1}v_i)

。图定下来后

v_i

就确定了，于是两人会按照

|v_i|

降序把所有

c_i=2

的点排序，然后贪心选择。

考虑如何计算分数总和。
首先，

c_i\ne2

的点本身不影响总和，只影响方案数，因为把所有边都反转它就要做负贡献，抵消掉。
然后我们可以按

|v_i|

降序，枚举所有的点可能的出度入度个数的对，总共有

O(n^2)

种，然后做一个背包（因为总出度、入读都是

m

），维护方案数和总和。

我们可以把

m

条有向边，看成两个独立的长为

m

的出点、入点序列，于是贡献系数就可以

O(1)

计算：
设出度入度分别为

a,b

，已经用了

i

个

col=2

的点，

j

的入度，

k

的出度，维护方案数、总和。枚举

(a,b)

个数

c

，有

ca,cb\le m

，乘上

\frac{1}{k!(a!b!)^c}

的系数，转移到

(i+c,j+ac,k+bc)

，总和加上

(c\mod 2)|a-b|

。

然后是统计答案：
注意我们只对

col=2

的点做了背包。设

e

为

col=2

的点的个数。首先要乘上

e!m!m!

（划分多组的组合数系数）。考虑剩下的点的出、入度，先乘上

\frac{1}{(m-j)!(m-k)!}

，表示把剩下的点当成特殊的一组，然后乘上

(n-e)^{m-j+m-k}

的方案数。

由于转移时有

ca,cb\le m

，所以总复杂度

O(\frac{n^6}{\log^2})

。

Code：

CPP

#include <bits/stdc++.h>
#define pii pair <int,int>
#define fi first
#define se second
#define mkp make_pair
using namespace std;
const int N = 55,mod = 1e9 + 7;
int n,m,cnt,f[N][N][N],g[N][N][N],inv[N],fac[N],ifac[N],mi[N << 1],col[N];
pii p[N * N];
bool cmp(pii x,pii y){return abs(x.fi - x.se) > abs(y.fi - y.se);}
int main()
{
    inv[1] = fac[0] = ifac[0] = 1;
    for(int i = 2;i < N;i++) inv[i] = mod - 1LL * (mod / i) * inv[mod % i] % mod;
    for(int i = 1;i < N;i++) fac[i] = 1LL * fac[i - 1] * i % mod;
    for(int i = 1;i < N;i++) ifac[i] = 1LL * ifac[i - 1] * inv[i] % mod;
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 0;i <= m;i++)
        for(int j = 0;j <= m;j++)
            p[++cnt] = mkp(i,j);
    sort(p + 1,p + cnt + 1,cmp);
    f[0][0][0] = 1;
    for(int i = 1;i <= cnt;i++)
    {
        int a = p[i].fi,b = p[i].se,c = abs(a - b);
        for(int j = n;j >= 0;j--)
            for(int k = 1,s = 1;k <= j && k * a <= m && k * b <= m;k++)
            {
                s = 1LL * s * inv[k] % mod * ifac[a] % mod * ifac[b] % mod;
                for(int x = k * a;x <= m;x++)
                    for(int y = k * b;y <= m;y++)
                    {
                        int v = 1LL * f[j - k][x - k * a][y - k * b] * s % mod;
                        f[j][x][y] = (f[j][x][y] + v) % mod;
                        g[j][x][y] = (g[j][x][y] + 1LL * g[j - k][x - k * a][y - k * b] * s % mod) % mod;
                        if(k & 1)
                            if(j & 1) g[j][x][y] = (g[j][x][y] + 1LL * v * c % mod) % mod;
                            else g[j][x][y] = (g[j][x][y] - 1LL * v * c % mod + mod) % mod;
                    }
            }
    }
    for(int i = 1;i <= n;i++) scanf("%d",&col[i]);
    for(int i = 1,e = 0;i <= n;i++)
    {
        e += (col[i] == 2),mi[0] = 1;
        for(int j = 1;j <= 2 * m;j++) mi[j] = 1LL * mi[j - 1] * (i - e) % mod;
        for(int j = 1;j <= m;j++)
        {
            int ans = 0;
            for(int x = 0;x <= j;x++)
                for(int y = 0;y <= j;y++)
                    ans = (ans + 1LL * g[e][x][y] * fac[e] % mod * fac[j] % mod * fac[j] % mod * mi[j - x + j - y] % mod * ifac[j - x] % mod * ifac[j - y] % mod) % mod;
            ans = 1LL * ans * (mod / 2 + 1) % mod;
            printf("%d ",ans);
        }
        puts("");
    }
    return 0;
}

B.修理：

题意：

有一个序列

a

，和一个初始为

0

的变量

x

，可以进行一下两种操作：

1. $x\leftarrow x+1$
2. $a_i\leftarrow a_i\oplus x$

定义这个序列的代价，为最小的操作次数使得

a_i

全零。

给定一个长为

n

的序列，每次询问一个子区间

[l,r]

的代价，强制在线。

Sol：

x

一定要大于等于

\max highbit(a_i)

，然后

\le x

的

a_i

有

1

的贡献，

>x

的有

2

的贡献。
设

H

为

\max highbit(a_i)

，则

\le H

的

a_i

贡献一定为

1

，可以只考虑 $>H$ 的点。

扫描

r

，对每个

l

维护答案，用可持久化数据结构存答案，然后在线回答。考虑

r+1

时对答案的影响。
贡献其实可以写成

2len+x-\sum[a_i\le x](x\ge H)

，设

d(x)=x-H-\sum[a_i\le x]

，则要最小化

d(x)

，答案为

2len+H+\min d(x)

。

设最优

x

为使得

d(x)

最小时最小的

x

。不难发现随着区间扩展，

\min d(x)

不增而且最多减少

1

，因为后面一个求和式最多加一，而且取得最优的

x

不降。
同时，我们一定可以找出一个分界点

m

，使得

l\le m

的区间

d_(x)-1

，

l>m

的区间

d(x)

不变，证明如下：

设

l_1<l_2

，且

d_{l_2}

更新。设

x_1=x_{[l_1,r]},x_2=x_{[l_2,r]},t=x_{[l_2,r+1]}

，显然有

x_1\ge x_2,t\ge a_{r+1}

，因此

d_{[l_2,r+1]}(t)=d_{[l_2,r]}(t)-1=d_{[l_2,r]}(x_2)-1

。
若

a_{r+1}\le x_1

则

\min d_{l_1}

一定更新；考虑

x_1<a_{r+1}

。注意到新加入一个数会让

d(x)

的一个后缀减一，所以较小位置与较大位置的

d(x)

之差只会扩大。
所以

d_{[l_1,r]}(x_1)-d_{[l_1,r]}(t)\ge d_{[l_1,r]}(x_2)-d_{[l_1,r]}(t)\ge d_{[l_2,r]}(x_2)-d_{[l_2,r]}(t)=-1

，因此

d_{l_1}

也会更新。

考虑求出

m

。
可以证明

a_m

在后续是没有影响的。首先有

x_{[m,r+1]}\ge a_m

，否则

d_{[m,r+1]}(x_{[m,r+1]})=d_{[m+1,r+1]}(x_{[m,r+1]})

，

m+1

也会更新。
又因为

x

递增，所以

L\le m,R\ge r+1

一定有

x_{[L,R]}\ge x_{[m,r+1]}

，所以

a_m

后面只有

1

的贡献，可以打上答案永久 $-1$ 的标记然后把

a_m

删掉。

设受删除影响后的

d(x)

为

d'(x)

。假设加入

a_{r+1}

后，

d'_{[1,r+1]}(x)

最小的一个小于

0

的位置为

v

。
如果不存在这样的

v

，则

\min d(x)

不改变（

m=0

）；否则，

m

为

\min\limits_{i 未删除 \land a_i\le v}i

。下面给出证明。

首先可以归纳证明，每次删掉

a_m

后，

\forall x,d'(x)\ge 0

。
考虑加入

a_{r+1}

后一个满足

d'_{[l,r+1]}(t)<0

的位置，显然有

t\ge a_{r+1}

。
如果

x_{[l,r]}\ge a_{r+1}

，则答案一定会更新；
否则

x<t

，把

x

改成

t

一定更优。因为

d(x)=d'(x)+标记

，而由于

x

递增，所以上文中标记只与区间端点有关。

对于

d'_{[1,r+1]}(x)

中一个

<0

的位置

t

，设

minn_t

表示

\min\limits_{i 未删除 \land a_i\le t}i

，则显然

\forall i\le minn_t,d'_{[i,r+1]}(t)=d'_{[1,r+1]}(t)<0

，因为

d(x)

中后面的和式值不变。
显然

minn_t

随

t

增大而减小，而

t\le v

，所以

m=minn_v

。

考虑用一棵值域线段树维护

[1,r]

中未被删除的值，以维护

d'(x)

，

v

可以在上面线段树二分求得。再对每个

H

开一个可持久化线段树存下标记即可。
时空复杂度

O(n\log n)

。
代码里好像把

d(x)

全部取负数了、、

Code：

CPP

#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
using namespace std;
typedef long long ll;
const int N = 2e5 + 5,INF = 2e9;
int n,Q,T,c[60],s[60],id[N],nxt[N],pos[N],rt[N][60],q[N][60];
ll a[N];
struct SgT1
{
    #define ls (x << 1)
    #define rs (ls | 1)
    int minn[N << 2],maxn[N << 2],tag[N << 2];
    void upd(int x,int v){maxn[x] += v,tag[x] += v;}
    void pushdown(int x){if(tag[x]) upd(ls,tag[x]),upd(rs,tag[x]),tag[x] = 0;}
    void pushup(int x){minn[x] = min(minn[ls],minn[rs]),maxn[x] = max(maxn[ls],maxn[rs]);}
    void update1(int x,int l,int r,int p,int a,int b)
    {
        if(l == r) return (void)(minn[x] = a,maxn[x] += b);
        pushdown(x);
        if(p <= mid) update1(ls,l,mid,p,a,b);
        else update1(rs,mid + 1,r,p,a,b);
        pushup(x);
    }
    void update2(int x,int l,int r,int L,int R,int v)
    {
        if(L <= l && r <= R) return upd(x,v);
        pushdown(x);
        if(L <= mid) update2(ls,l,mid,L,R,v);
        if(R > mid) update2(rs,mid + 1,r,L,R,v);
        pushup(x);
    }
    int find(int x,int l,int r,int L,int R)
    {
        if(maxn[x] <= 0) return 0;
        if(l == r) return l;
        pushdown(x);
        if(L <= l && r <= R)
        {
            if(maxn[ls] > 0) return find(ls,l,mid,L,R);
            return find(rs,mid + 1,r,L,R);
        }
        int ret = 0;
        if(L <= mid && (ret = find(ls,l,mid,L,R))) return ret;
        if(R > mid) ret = find(rs,mid + 1,r,L,R);
        return ret;
    }
    int query(int x,int l,int r,int L,int R)
    {
        if(L <= l && r <= R) return minn[x];
        pushdown(x);
        if(R <= mid) return query(ls,l,mid,L,R);
        if(L > mid) return query(rs,mid + 1,r,L,R);
        return min(query(ls,l,mid,L,R),query(rs,mid + 1,r,L,R));
    }
    #undef ls
    #undef rs
} tr1;
struct SgT2
{
    int tot,sum[N * 20],ls[N * 20],rs[N * 20];
    int update(int o,int l,int r,int p)
    {
        int x = ++tot;
        sum[x] = sum[o] + 1; 
        if(l == r) return x;
        if(p <= mid) ls[x] = update(ls[o],l,mid,p),rs[x] = rs[o];
        else rs[x] = update(rs[o],mid + 1,r,p),ls[x] = ls[o];
        return x;
    }
    int query(int x,int l,int r,int L,int R)
    {
        if(!x) return 0;
        if(L <= l && r <= R) return sum[x];
        if(R <= mid) return query(ls[x],l,mid,L,R);
        if(L > mid) return query(rs[x],mid + 1,r,L,R);
        return query(ls[x],l,mid,L,R) + query(rs[x],mid + 1,r,L,R);
    }
} tr2;
int main()
{
    freopen("repair.in","r",stdin);
    freopen("repair.out","w",stdout);
    scanf("%d%d%d",&n,&Q,&T);
    for(int i = 1;i <= n;i++) scanf("%lld",&a[i]);
    for(int i = 1;i <= n;i++) c[__lg(a[i])]++;
    for(int i = 0;i < 60;i++) s[i] = (i ? s[i - 1] : 0) + c[i];
    for(int i = 0,id = 0;i < 60;i++) for(int j = 1;j <= c[i];j++) tr1.update1(1,1,n,++id,INF,1 - j);
    fill(pos + 1,pos + n + 1,n + 1);
    for(int i = n;i >= 1;i--)
    {
        int t = __lg(a[i]);
        ll r = a[i] - (1LL << t);
        if(r >= c[t]) continue;
        id[i] = (t ? s[t - 1] : 0) + r + 1;
        nxt[i] = pos[id[i]],pos[id[i]] = i;
    }
    memset(pos,0,sizeof(pos));
    for(int i = 1;i <= n;i++)
    {
        memcpy(rt[i],rt[i - 1],sizeof(rt[i]));
        memcpy(q[i],q[i - 1],sizeof(q[i]));
        int t = __lg(a[i]);
        ll r = a[i] - (1LL << t);
        q[i][t]++;
        if(r >= c[t]) continue;
        if(!pos[id[i]]) tr1.update1(1,1,n,id[i],i,0),pos[id[i]] = i;
        tr1.update2(1,1,n,id[i],s[t],1);
        int v = tr1.find(1,1,n,id[i],s[t]);
        if(v)
        {
            int p = tr1.query(1,1,n,(t ? s[t - 1] : 0) + 1,v);
            rt[i][t] = tr2.update(rt[i][t],1,n,p);
            if(nxt[p] <= i) tr1.update1(1,1,n,id[p],nxt[p],0),pos[id[p]] = nxt[p];
            else tr1.update1(1,1,n,id[p],INF,0),pos[id[p]] = 0;
            tr1.update2(1,1,n,id[p],s[t],-1);
        }
    }
    ll lst = 0,l,r;
    for(int i = 1,t;i <= Q;i++)
    {
        scanf("%lld%lld",&l,&r);
        if(T == 2) l ^= lst,r ^= lst;
        if(l > r) swap(l,r);
        for(t = 59;q[r][t] - q[l - 1][t] == 0;t--);
        lst = (1LL << t) + r - l + 1 + q[r][t] - q[l - 1][t] - tr2.query(rt[r][t],1,n,l,r);
        printf("%lld\n",lst);
    }
    return 0;
}

C.人员调度2

题意：

要做二分图匹配，左右各

n

个点，

i,j

匹配贡献为

a_i+b_j+(a_i\oplus b_j)

。此外有

m

个特殊边

(i,j,v)

，表示

i,j

匹配有额外

v

的贡献。

给定

K

，

\forall i\le K

，回答恰好匹配

K

对时候的最大值。

K\le 300,n\le 10^5,a_i,b_i<2^{12},v\le2\times10^5

。

Sol：

拆位看基础贡献，其实是

2(a_i|b_j)

。直接跑

K

轮增广路的话是

O(Kn^3)

的。

法一：

观察匈牙利算法的增广路，发现要么从左边直接到右边，要么中间经过一些匹配过的点。
值域比较小，直接每次

O(V)

处理出和一个点最优的为匹配点，然后

O(K^3)

floyd 跑已匹配点的最短路。

O(K^4+Kn+KV)

。

法二：

首先每个点只用保留和自己连接的所有边中前

K

大的；
其次，在上述保留的边中，只用取前

O(K^2)

条。因为用一条边会尽调与之相连的边，最多

O(K)

条。所以可以通过调整法把每一条边都变成前

O(K^2)

大的。

~~由于数据范围和时限比较逆天两个都过不了，所以把两个做法绑一起，其中法二的 $O(K^2)$ 对 $10000$ 取 $\min$ 。~~

Code：

CPP

#include <bits/stdc++.h>
#define pii pair <int,int>
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
#define il inline
using namespace std;
typedef long long ll;
il int read()
{
    int x = 0;
    char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) x = x * 10 + ch - '0',ch = getchar();
    return x;
}
const int N = 1e5 + 5,M = 305,V = (1 << 12),INF = 2e9;
int n,m,K;
namespace AAA
{
    int cnt,a[N],b[N],d1[N],d2[N],id1[N],id2[N],used[N],vis[N];
    int cnt1[V],cnt2[V],cur1[V],cur2[V],s1[V][M],s2[V][M];
    vector <int> t[V],w1[V],w2[V],p[N];
    struct Edge{int x,y,z;};
    vector <Edge> e,p1[N],p2[N];
    bool cmp1(Edge x,Edge y){return x.z > y.z;}
    bool cmp2(Edge x,Edge y){return x.x < y.x;}
    struct Flow
    {
        int tot = 1,S,T,head[N],to[N],val[N],cst[N],nxt[N],pre[N],dis[N],in[N];
        queue <int> q;
        il void add_(int x,int y,int z,int c){to[++tot] = y,val[tot] = z,cst[tot] = c,nxt[tot] = head[x],head[x] = tot;}
        il void add_edge(int x,int y,int z,int c){add_(x,y,z,c),add_(y,x,0,-c);}
        il void spfa()
        {
            memset(dis,-127,sizeof(int) * (cnt + 1));
            q.push(S),dis[S] = 0,in[S] = 1;
            while(!q.empty())
            {
                int x = q.front();
                q.pop(),in[x] = 0;
                for(int i = head[x],y;i;i = nxt[i])
                    if(val[i] && dis[y = to[i]] < dis[x] + cst[i])
                    {
                        dis[y] = dis[x] + cst[i],pre[y] = i;
                        if(!in[y]) q.push(y),in[y] = 1;
                    }
            }
        }
        il void ek()
        {
            int ans = 0;
            while(K--)
            {
                spfa(),ans += dis[T];
                for(int i = T;i != S;i = to[pre[i] ^ 1]) val[pre[i]]--,val[pre[i] ^ 1]++;
                printf("%d ",ans);
            }
            puts("");
        }
    } g;
    void Main()
    {
        for(int i = 1;i <= n;i++) a[i] = read();
        for(int i = 1;i <= n;i++) b[i] = read();
        for(int i = 1,x,y,z;i <= m;i++)
        {
            x = read(),y = read(),z = read() + 2 * (a[x] | b[y]);
            p1[x].pb((Edge){x,y,z}),p2[y].pb((Edge){x,y,z});
        }
        for(int i = 1;i <= n;i++) w1[a[i]].pb(i);
        for(int i = 1;i <= n;i++) w2[b[i]].pb(i);
        for(int i = 0;i < V;i++)
        {
            for(int j = 0;j < V;j++) t[j].clear();
            for(int j = 0;j < V;j++) t[i | j].pb(j);
            for(int j = V - 1;j >= 0 && cnt1[i] < K;j--)
                for(int k : t[j])
                {
                    for(int c = w2[k].size() - 1;c >= 0 && cnt1[i] < K;c--) s1[i][++cnt1[i]] = w2[k][c];
                    if(cnt1[i] == K) break;
                }
            for(int j = V - 1;j >= 0 && cnt2[i] < K;j--)
                for(int k : t[j])
                {
                    for(int c = w1[k].size() - 1;c >= 0 && cnt2[i] < K;c--) s2[i][++cnt2[i]] = w1[k][c];
                    if(cnt2[i] == K) break;
                }
        }
        for(int i = 1;i <= n;i++)
        {
            for(Edge j : p1[i]) vis[j.y] = i;
            sort(p1[i].begin(),p1[i].end(),cmp1);
            for(int j = 1,x = 1,y = 0;j <= K;j++)
            {
                while(x <= K && vis[s1[a[i]][x]] == i) x++;
                if(x <= K && (y == (int)p1[i].size() || 2 * (a[i] | b[s1[a[i]][x]]) > p1[i][y].z)) p[s1[a[i]][x++]].pb(i);
                else p[p1[i][y++].y].pb(i);
            }
        }
        memset(vis,0,sizeof(vis));
        for(int i = 0;i < V;i++)
        {
            memcpy(s1[i],s2[i],sizeof(int) * (K + 1));
            sort(s1[i] + 1,s1[i] + K + 1);
        }
        for(int i = 1;i <= n;i++)
        {
            for(Edge j : p2[i]) vis[j.x] = i;
            sort(p2[i].begin(),p2[i].end(),cmp1);
            for(int j = 1,x = 1,y = 0;j <= K;j++)
            {
                while(x <= K && vis[s2[b[i]][x]] == i) x++;
                if(x <= K && (y == (int)p2[i].size() || 2 * (a[s2[b[i]][x]] | b[i]) > p2[i][y].z)) used[s2[b[i]][x++]] = i;
                else used[p2[i][y++].x] = i;
            }
            sort(p2[i].begin(),p2[i].end(),cmp2);
            for(int j = 1,x = 1,y = 0,k,cur = 0,d;j <= K;j++)
            {
                while(x <= K && (vis[s1[b[i]][x]] == i || used[s1[b[i]][x]] != i)) x++;
                while(y < (int)p2[i].size() && used[p2[i][y].x] != i) y++;
                if(x <= K && (y == (int)p2[i].size() || s1[b[i]][x] < p2[i][y].x)) k = s1[b[i]][x++],d = -1;
                else k = p2[i][y].x,d = p2[i][y++].z;
                while(cur < (int)p[i].size() && p[i][cur] < k) cur++;
                if(cur == (int)p[i].size()) break;
                if(p[i][cur] == k) e.pb((Edge){k,i,d == -1 ? 2 * (a[k] | b[i]) : d});
            }
        }
        int up = min(min((int)e.size(),2 * K * K),10000);
        if(up < (int)e.size())
        {
            nth_element(e.begin(),e.begin() + up,e.end(),cmp1);
            e.resize(up);
        }
        for(Edge i : e)
        {
            if(!id1[i.x]) id1[i.x] = ++cnt;
            if(!id2[i.y]) id2[i.y] = ++cnt;
            g.add_edge(id1[i.x],id2[i.y],1,i.z);
        }
        g.T = ++cnt;
        for(int i = 1;i <= n;i++) if(id1[i]) g.add_edge(0,id1[i],1,0);
        for(int i = 1;i <= n;i++) if(id2[i]) g.add_edge(id2[i],cnt,1,0);
        g.ek();
    }
}
namespace BBB
{
    int tot,a[N],b[N],f[M][M],opt[M][M],id1[N],id2[N],p1[M],p2[M],mch1[M],mch2[M],val1[M],val2[M],c1[M],c2[M],p[M];
    int head1[N],to1[N * 5],v1[N * 5],nxt1[N * 5],head2[N],to2[N * 5],v2[N * 5],nxt2[N * 5],cnt1[V],cnt2[V],cur1[V],cur2[V],s1[V][M],s2[V][M];
    vector <int> t[V],w1[V],w2[V];
    map <int,int> mp[N];
    void get_rt(int s,int t)
    {
        int mid = opt[s][t];
        if(!mid) return ;
        get_rt(s,mid),p[++tot] = mid,get_rt(mid,t);
    }
    il int get_val(int x,int y)
    {
        int ret = 2 * (a[x] | b[y]);
        if(mp[x].find(y) != mp[x].end()) ret += mp[x][y];
        return ret;
    }
    void Main()
    {
        for(int i = 1;i <= n;i++) a[i] = read();
        for(int i = 1;i <= n;i++) b[i] = read();
        for(int i = 1;i <= n;i++) w1[a[i]].pb(i);
        for(int i = 1;i <= n;i++) w2[b[i]].pb(i);
        for(int i = 0;i < V;i++)
        {
            for(int j = 0;j < V;j++) t[j].clear();
            for(int j = 0;j < V;j++) t[i | j].pb(j);
            for(int j = V - 1;j >= 0;j--)
                for(int k : t[j])
                {
                    for(int c = w2[k].size() - 1;c >= 0 && cnt1[i] < K;c--) s1[i][cnt1[i]++] = w2[k][c];
                    for(int c = w1[k].size() - 1;c >= 0 && cnt2[i] < K;c--) s2[i][cnt2[i]++] = w1[k][c];
                }
        }
        for(int i = 1,x,y,z;i <= m;i++)
        {
            x = read(),y = read(),z = read();
            to1[i] = y,v1[i] = z,nxt1[i] = head1[x],head1[x] = i;
            to2[i] = x,v2[i] = z,nxt2[i] = head2[y],head2[y] = i;
            mp[x][y] = z;
        }
        for(int T = 1,sum = 0;;T++)
        {
            int max1 = -1,max2 = -1,s,t,u,v,tmp;
            for(int i = 1;i <= n;i++)
                if(!id1[i])
                    for(int c = head1[i],j,v;c;c = nxt1[c])
                        if(!id2[j = to1[c]] && max1 < (v = 2 * (a[i] | b[j]) + v1[c]))
                            max1 = v,s = i,t = j;
            for(int i = 1,v,p;i <= n;i++)
            {
                if(id1[i]) continue;
                v = a[i];
                while(id2[p = s1[v][cur1[v]]]) cur1[v]++;
                if(max1 < (tmp = 2 * (v | b[p])))
                    max1 = tmp,s = i,t = p;
            }
            for(int i = 1;i < T;i++)
                for(int j = 1,d;j < T;j++)
                    if(max2 < (d = f[i][j] + val1[mch2[j]] + val2[i] - get_val(p1[mch2[j]],p2[j])))
                        max2 = d,u = i,v = j;
            sum += max(max1,max2);
            printf("%d ",sum);
            if(T == K) break;
            if(max1 >= max2)
            {
                id1[s] = id2[t] = T,p1[T] = s,p2[T] = t;
                mch1[T] = mch2[T] = T;
            }
            else
            {
                p[tot = 1] = u,get_rt(u,v),p[++tot] = v,v = mch2[v];
                for(int i = tot - 1,t;i >= 1;i--)
                {
                    t = mch2[p[i]];
                    mch1[t] = p[i + 1],mch2[p[i + 1]] = t;
                }
                id1[c2[u]] = id2[c1[v]] = T,p1[T] = c2[u],p2[T] = c1[v];
                mch1[T] = u,mch2[u] = T;
                mch2[T] = v,mch1[v] = T;
            }
            for(int i = 1;i <= T;i++)
                for(int j = 1;j <= T;j++)
                    if(i != j) f[i][j] = get_val(p1[mch2[i]],p2[j]) - get_val(p1[mch2[i]],p2[i]);
                    else f[i][j] = 0;
            for(int i = 1;i <= T;i++)
                for(int j = 1;j <= T;j++)
                    opt[i][j] = 0;
            for(int k = 1,v;k <= T;k++)
                for(int i = 1;i <= T;i++)
                    for(int j = 1;j <= T;j++)
                        if((v = f[i][k] + f[k][j]) > f[i][j])
                            f[i][j] = v,opt[i][j] = k;
            for(int i = 1;i <= T;i++) val1[i] = val2[i] = -1;
            for(int i = 1,maxn,p;i <= T;i++)
            {
                maxn = -1;
                for(int c = head1[p1[i]],j,v;c;c = nxt1[c])
                    if(!id2[j = to1[c]] && maxn < (v = 2 * (a[p1[i]] | b[j]) + v1[c]))
                        maxn = v,p = j;
                if(maxn > val1[i]) val1[i] = maxn,c1[i] = p;
            }
            for(int i = 1,v,p;i <= T;i++)
            {
                v = a[p1[i]];
                while(id2[p = s1[v][cur1[v]]]) cur1[v]++;
                if(val1[i] < (tmp = 2 * (v | b[p]))) val1[i] = tmp,c1[i] = p;
            }
            for(int i = 1,maxn,p;i <= T;i++)
            {
                maxn = -1;
                for(int c = head2[p2[i]],j,v;c;c = nxt2[c])
                    if(!id1[j = to2[c]] && maxn < (v = 2 * (a[j] | b[p2[i]]) + v2[c]))
                        maxn = v,p = j;
                if(maxn > val2[i]) val2[i] = maxn,c2[i] = p;
            }
            for(int i = 1,v,p;i <= T;i++)
            {
                v = b[p2[i]];
                while(id1[p = s2[v][cur2[v]]]) cur2[v]++;
                if(val2[i] < (tmp = 2 * (v | a[p]))) val2[i] = tmp,c2[i] = p;
            }
        }
        puts("");
    }
}
int main()
{
    freopen("transfer.in","r",stdin);
    freopen("transfer.out","w",stdout);
    n = read(),m = read(),K = read();
    if(n <= 300 && m <= 10000 && K <= 300) BBB :: Main();
    else AAA :: Main();
    return 0;
}

省队集训-0424模拟赛

文章操作

A.图上的游戏

题意：

Sol：

Code：

B.修理：

题意：

Sol：

Code：

C.人员调度2

题意：

Sol：

法一：

法二：

Code：

相关推荐

评论

省队集训-0424模拟赛