2021 ICPC Southeastern Europe Regional Contest (SEERC 2021) 补题记录（12 / 14）

发表于 更新于 分类于 本文字数： 27k 阅读时长 ≈ 25 分钟

SEERC 2021 补题记录

这场后短时间内应该专注于结课考试不能继续 vp 了

A. King of String Comparison

tag

  • 双指针

题意

两个串 s,ts, t ，求 s[l,r]s[l, r] 字典序比 t[l,r]t[l, r] 小的数对 (l,r)(l, r) 个数。
其中 1≤∣s∣=∣t∣,≤2⋅1051 \leq |s| = |t|, \leq 2 \cdot 10^5 。

思路

枚举左端点，维护最长满足 s[l,r]=t[l,r]s[l, r] = t[l, r] 的长度即可，长度有单调性，可以双指针维护。
复杂度 O(n)O(n) 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*
    Author: Cupids_Bow
    Time: 2022-10-16 10:13:14
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n;
    cin>>n;

    string s,t;
    cin>>s>>t;

    int r=-1;
    i64 ans=0;
    for(int i=0;i<n;i++){
        r=max(i-1,r);
        while(r+1<n&&s[r+1]==t[r+1]) r++;
        if(r+1<n&&s[r+1]<t[r+1]) ans+=n-r-1;
    }

    cout<<ans;

    return true&&false;
}

B. New Queries On Segment Deluxe

tag

  • 主席树

题意

给定 k⋅nk \cdot n 的矩阵 aa 与长为 nn 的数列 bb ，定义 bj=∑i=1kai,jb_j = \sum\limits_{i = 1}^{k} a_{i,j} ，实现三种操作：

  • 1 t p l r x1 \ t \ p \ l \ r \ x 将 ap,i(t)a^{(t)}_{p,i} 加上 xx ，并生成一个新版本。
  • 2 t p l r y2 \ t \ p \ l \ r \ y 将 ap,i(t)a^{(t)}_{p,i} 赋值 xx ，并生成一个新版本。
  • 3 t l r3 \ t \ l \ r 求 min⁡i=lrbi(t)\min\limits_{i = l}^{r} b^{(t)}_i 。

其中 (t)(t) 表示第 tt 个版本，输入的 aa 和 bb 为第 00 个版本。
其中 1≤k≤4,1≤n≤250000,1≤q≤20000,∣ai∣≤1081 \leq k \leq 4, 1 \leq n \leq 250000, 1 \leq q \leq 20000, |a_i| \leq 10^8 。

思路

咋一看感觉寄了，什么都不会。考虑 k=4k = 4 可能是一个突破点。
如果只是维护一个序列 bb ，显然可以直接主席树维护三种操作，对于区间加可以直接标记永久化，每个版本增加 log2nlog^2n 个节点，对于区间赋值可以直接将对应子树扔掉再转换成区间加，区间 minmin 直接查询即可，注意加上永久化标记。
如果加上 kk 维的 aa 数组，对于区间加和取 minmin 操作是没有影响的，对于赋值操作仍然是将其转换为删子树再区间加，关键在于删去子树的贡献。由于 kk 最大只有 44 ，可以考虑维护 2k2^k 棵主席树，每棵维护一个 aa 数组的子集对应的 bb 数组，删子树的时候可以直接查询对应集合的值。
复杂度 O(q⋅log2n⋅2k)O(q \cdot log^2n \cdot 2^k) 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
/*
    Author: Cupids_Bow
    Time: 2022-10-19 22:11:04
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

const int INF=0x3f3f3f3f;
const int N=250000+5;

int k,n,q;
int a[4][N];

struct tree{
    int tot;
    int rt[N][1<<4];
    int lc[N<<6];
    int rc[N<<6];
    int minn[N<<6];
    int lz[N<<6];
    void cpy(int x,int y){
        lc[x]=lc[y];
        rc[x]=rc[y];
        minn[x]=minn[y];
        lz[x]=lz[y];
    }
    void pushup(int x){
        minn[x]=min(minn[lc[x]],minn[rc[x]])+lz[x];
    }
    void build(int &x,int l,int r,int mask){
        if(!x) x=++tot;
        if(l==r){
            for(int i=0;i<k;i++) if((mask>>i)&1) minn[x]+=a[i][l];
            return;
        }
        int mid=l+r>>1;
        build(lc[x],l,mid,mask);
        build(rc[x],mid+1,r,mask);
        pushup(x);
        return;
    }
    void add(int &x,int pre,int l,int r,int ql,int qr,int val){
        tot++;
        cpy(tot,pre);
        x=tot;
        if(l>=ql&&r<=qr){
            minn[x]+=val;
            lz[x]+=val;
            return;
        }
        int mid=l+r>>1;
        if(mid>=ql) add(lc[x],lc[pre],l,mid,ql,qr,val);
        if(mid+1<=qr) add(rc[x],rc[pre],mid+1,r,ql,qr,val);
        pushup(x);
        return;
    }
    void change(int &x,int y,int z,int l,int r,int ql,int qr,int val,int tmp=0){
        if(l>=ql&&r<=qr){
            tot++;
            cpy(tot,z);
            x=tot;
            minn[x]+=val-tmp;
            lz[x]+=val-tmp;
            return;
        }
        tmp+=lz[y]-lz[z];
        tot++;
        cpy(tot,y);
        x=tot;
        int mid=l+r>>1;
        if(mid>=ql) change(lc[x],lc[y],lc[z],l,mid,ql,qr,val,tmp);
        if(mid+1<=qr) change(rc[x],rc[y],rc[z],mid+1,r,ql,qr,val,tmp);
        pushup(x);
        return;
    }
    int search(int x,int l,int r,int ql,int qr){
        if(l>=ql&&r<=qr) return minn[x];
        int res=INF;
        int mid=l+r>>1;
        if(mid>=ql) res=min(res,search(lc[x],l,mid,ql,qr));
        if(mid+1<=qr) res=min(res,search(rc[x],mid+1,r,ql,qr));
        return res+lz[x];
    }
}tr;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>k>>n>>q;

    for(int i=0;i<k;i++)
        for(int j=1;j<=n;j++) cin>>a[i][j];

    for(int mask=1;mask<(1<<k);mask++) tr.build(tr.rt[0][mask],1,n,mask);

    for(int i=1;i<=q;i++){
        int op;
        cin>>op;

        if(op==1){
            int t,p,l,r,x;
            cin>>t>>p>>l>>r>>x;
            p--;
            for(int mask=1;mask<(1<<k);mask++){
                if((mask>>p)&1) tr.add(tr.rt[i][mask],tr.rt[t][mask],1,n,l,r,x);
                else tr.rt[i][mask]=tr.rt[t][mask];
            }
        }
        else if(op==2){
            int t,p,l,r,y;
            cin>>t>>p>>l>>r>>y;
            p--;
            for(int mask=1;mask<(1<<k);mask++){
                if((mask>>p)&1) tr.change(tr.rt[i][mask],tr.rt[t][mask],tr.rt[t][mask^(1<<p)],1,n,l,r,y);
                else tr.rt[i][mask]=tr.rt[t][mask];
            }
        }
        else{
            int t,l,r;
            cin>>t>>l>>r;
            cout<<tr.search(tr.rt[t][(1<<k)-1],1,n,l,r)<<"\n";
        }
    }

    return true&&false;
}

C. Werewolves

tag

  • 树 dp

题意

nn 个节点的树，求有多少个连通块使得其中所有点的点权存在绝对众数。
其中 1≤n≤30001 \leq n \leq 3000 。

思路

枚举作为绝对众数的权值 colcol ，将权值等于 colcol 的点标记为 11 ，其余点标记为 −1-1 ，则问题转变为有多少个和大于 00 的连通块，跑树背包即可，所有情况下 11 的总数加起来为 nn ，所以总复杂度为一般树背包的复杂度。
复杂度 O(n2)O(n^2) 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/*
    Author: Cupids_Bow
    Time: 2022-10-17 16:59:29
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

const int mod=998244353;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n;
    cin>>n;

    vector<int> c(n+5,0),cnt(n+5,0);
    for(int i=1;i<=n;i++) cin>>c[i],cnt[c[i]]++;

    vector<vector<int>> e(n+5,vector<int>(0));
    for(int i=1,x,y;i<n;i++){
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }

    int ans=0;
    vector<int> sz(n+5,0);
    vector<vector<int>> dp(n+5,vector<int>(n*2+5,0));
    vector<int> g(n*2+5,0);
    function<void(int,int,int)> dfs=[&](int x,int fa,int col){
        sz[x]=1;
        for(int i=-cnt[col];i<=cnt[col];i++) dp[x][i+n]=0;
        dp[x][((c[x]==col)?1:-1)+n]=1;
        for(auto v:e[x]){
            if(v==fa) continue;
            dfs(v,x,col);
            for(int i=-cnt[col];i<=cnt[col];i++) g[i+n]=0;
            for(int i=-sz[x];i<=sz[x];i++)
                for(int j=-sz[v];j<=sz[v];j++) if(abs(i+j)<=cnt[col]) g[i+j+n]=(g[i+j+n]+1ll*dp[x][i+n]*dp[v][j+n]%mod)%mod;
            for(int i=-cnt[col];i<=cnt[col];i++) dp[x][i+n]=(dp[x][i+n]+g[i+n])%mod;
            sz[x]+=sz[v];
            sz[x]=min(sz[x],cnt[col]);
        }
        for(int i=1;i<=sz[x];i++) ans=(ans+dp[x][i+n])%mod;
    };

    for(int i=1;i<=n;i++) if(cnt[i]) dfs(1,1,i);

    cout<<ans;

    return true&&false;
}

E. Replace Sort

tag

  • dp
  • jls 线段树

题意

给定长为 nn 的序列 aa 和大小为 mm 的集合 bb ，单次操作可以将 aa 中若干个数字替换成 bb 中的数字， bb 中每个数字只能替换一次，求最小的操作次数使得 aa 递增，无解输出 −1-1 。
其中 1≤n,m≤5⋅1051 \leq n, m \leq 5 \cdot 10^5 。

思路

先将 bb 序列升序排序，容易有朴素的 dpdp ：

  • f[i]f[i] 表示 aa 数组前 ii 个都递增，且最后一个数为 aia_i 时的最小操作次数。
  • g[i][j]g[i][j] 表示 aa 数组前 ii 个都递增，且最后一个数为 bjb_j 时的最小操作次数。
  • f[i]={f[i−1] (ai−1<ai)g[i−1][j] (bj<ai)f[i] = \begin{cases} f[i - 1]\ (a_{i - 1} < a_i)\\ g[i - 1][j]\ (b_j < a_i) \end{cases}
  • g[i][j]={g[i−1][j−1]+1f[i−1]+1 (ai−1<bj)g[i][j] = \begin{cases} g[i - 1][j - 1] + 1 \\ f[i - 1] + 1\ (a_{i - 1} < b_j) \end{cases}

复杂度为 O(n2)O(n^2) 。
考虑优化， f[i]f[i] 的第一步转移可以直接更新，第二步转移相当于一个区间求 minmin ， g[i]g[i] 的第一步转移相当于区间整体平移后加 11 ，第二步转移相当于区间取 minmin 。
考虑用线段树优化转移，将 g[i]g[i] 的第二维表示在线段树上， f[i]f[i] 和 g[i]g[i] 的第二步转移相当于区间求 minmin 和区间取 minmin ，关键在于 g[i]g[i] 的第一步转移，可以考虑维护一个当前转移区间的起点 stst ，区间平移时将 st−−st -- 即可，剩余的操作套 jlsjls 线段树即可。
复杂度 O(n⋅logn)O(n \cdot logn) 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/*
    Author: Cupids_Bow
    Time: 2022-10-18 10:08:01
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

const int INF=0x3f3f3f3f;
const int N=1e6+5;

struct tree{
    int l[N<<2];
    int r[N<<2];
    int minn[N<<2];
    int maxn1[N<<2];
    int maxn2[N<<2];
    int lzp1[N<<2];
    int lzp2[N<<2];
    void pushup(int x){
        minn[x]=min(minn[x<<1],minn[x<<1|1]);
        maxn1[x]=max(maxn1[x<<1],maxn1[x<<1|1]);
        if(maxn1[x]==maxn1[x<<1]&&maxn1[x]==maxn1[x<<1|1]) maxn2[x]=max(maxn2[x<<1],maxn2[x<<1|1]);
        else if(maxn1[x]==maxn1[x<<1]) maxn2[x]=max(maxn2[x<<1],maxn1[x<<1|1]);
        else if(maxn1[x]==maxn1[x<<1|1]) maxn2[x]=max(maxn1[x<<1],maxn2[x<<1|1]);
    }
    void build(int x,int L,int R){
        l[x]=L;
        r[x]=R;
        lzp1[x]=lzp2[x]=0;
        if(l[x]==r[x]){
            minn[x]=INF;
            maxn1[x]=INF;
            maxn2[x]=-INF;
            return;
        }
        int mid=L+R>>1;
        build(x<<1,L,mid);
        build(x<<1|1,mid+1,R);
        pushup(x);
        return;
    }
    void pushdown(int x){
        int mx=max(maxn1[x<<1],maxn1[x<<1|1]);
        if(mx==maxn1[x<<1]) update(x<<1,lzp1[x],lzp2[x]);
        else update(x<<1,lzp1[x],lzp1[x]);
        if(mx==maxn1[x<<1|1]) update(x<<1|1,lzp1[x],lzp2[x]);
        else update(x<<1|1,lzp1[x],lzp1[x]);
        lzp1[x]=lzp2[x]=0;
    }
    void update(int x,int k1,int k2){
        if(minn[x]==maxn1[x]){
            k1=k2;
            minn[x]+=k1,maxn1[x]+=k2;
        }
        else minn[x]+=k1,maxn2[x]+=k1,maxn1[x]+=k2;
        lzp1[x]+=k1,lzp2[x]+=k2;
    }
    void add(int x,int ql,int qr,int k){
        if(ql>qr) return;
        if(l[x]>=ql&&r[x]<=qr){
            update(x,k,k);
            return;
        }
        pushdown(x);
        if(r[x<<1]>=ql) add(x<<1,ql,qr,k);
        if(l[x<<1|1]<=qr) add(x<<1|1,ql,qr,k);
        pushup(x);
        return;
    }
    void ckmin(int x,int ql,int qr,int k){
        if(ql>qr) return;
        if(l[x]>=ql&&r[x]<=qr){
            if(maxn1[x]<=k) return;
            else if(maxn2[x]<k){
                update(x,0,k-maxn1[x]);
                return;
            }
        }
        pushdown(x);
        if(r[x<<1]>=ql) ckmin(x<<1,ql,qr,k);
        if(l[x<<1|1]<=qr) ckmin(x<<1|1,ql,qr,k);
        pushup(x);
        return;
    }
    int search(int x,int ql,int qr){
        if(ql>qr) return INF;
        if(l[x]>=ql&&r[x]<=qr) return minn[x];
        pushdown(x);
        int res=INF;
        if(r[x<<1]>=ql) res=min(res,search(x<<1,ql,qr));
        if(l[x<<1|1]<=qr) res=min(res,search(x<<1|1,ql,qr));
        return res;
    }
}tr;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n,m;
    cin>>n>>m;

    vector<int> a(n+5,0),b(m+5,0);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];

    sort(b.begin()+1,b.begin()+1+m);

    tr.build(1,0,n+m+5);
    int st=n+1;

    vector<int> dp(n+5,INF);
    dp[0]=0;
    for(int i=1;i<=n;i++){
        if(a[i]>a[i-1]) dp[i]=min(dp[i],dp[i-1]);
        int pos=lower_bound(b.begin()+1,b.begin()+1+m,a[i])-b.begin();
        pos--;
        dp[i]=min(dp[i],tr.search(1,st+1,st+pos));
        st--;
        tr.add(1,st+1,st+m,1);
        pos=lower_bound(b.begin()+1,b.begin()+1+m,a[i-1])-b.begin();
        tr.ckmin(1,st+pos,st+m,dp[i-1]+1);
    }

    int ans=dp[n];
    ans=min(ans,tr.search(1,st+1,st+m));
    if(ans==INF) ans=-1;

    cout<<ans;

    return true&&false;
}

F. to Pay Respects

tag

  • 贪心

题意

一个人和恶龙对决，共 nn 回合，每回合依次进行如下操作：

  • 恶龙吟唱治疗魔法，叠上一层治疗效果
  • 人吟唱伤害魔法，叠上一层伤害效果，若存在治疗效果则减少一层治疗效果
  • 人进行一次物理攻击
  • 所有魔法效果生效

人一次物理攻击造成 XX 的伤害，假设第 ii 回合魔法生效前共有 pp 层伤害效果和 rr 层治疗效果，则第 ii 回合造成的伤害为 X+P⋅p−R⋅rX + P \cdot p - R \cdot r ，人最多吟唱 KK 次伤害魔法，给定长为 nn 的 0101 串 ss ， si=1s_i = 1 表示龙第 ii 回合吟唱了治疗魔法。
最大化最后人能造成的伤害值。
其中 1≤n,X,P,R,≤106,0≤K≤N1 \leq n, X, P, R, \leq 10^6, 0 \leq K \leq N 。

思路

可以将治疗的伤害值等价为人造成的伤害值，初始时先将所有的治疗值加上。之后人在第 ii 回合吟唱魔法造成的总伤害可以等价地表示为 (n−i+1)⋅(P+[si=1]⋅r)(n - i + 1) \cdot (P + [s_i = 1] \cdot r) 。
计算出每回合的伤害值，取前 KK 大的即可，物理攻击和治疗返回值单独计算。
复杂度 O(n⋅logn)O(n \cdot logn) 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
    Author: Cupids_Bow
    Time: 2022-10-16 16:35:06
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n,x,r,p,k;
    cin>>n>>x>>r>>p>>k;

    string s;
    cin>>s;

    vector<i64> res(n,0);
    i64 ans=1ll*n*x;
    for(int i=0;i<n;i++){
        if(s[i]=='1'){
            res[i]=1ll*(p+r)*(n-i);
            ans-=1ll*r*(n-i);
        }
        else res[i]=1ll*p*(n-i);
    }

    sort(res.begin(),res.end(),greater<i64>());

    for(int i=0;i<k;i++) ans+=res[i];

    cout<<ans;

    return true&&false;
}

G. Max Pair Matching

tag

  • 思维
  • 贪心

题意

n⋅2n \cdot 2 个点的完全图，点 i,ji, j 匹配的权值为 max(∣ai−aj∣,∣ai−bj∣,∣bi−aj∣,∣bi−bj∣)max(|a_i - a_j|, |a_i - b_j|, |b_i - a_j|, |b_i - b_j|) ，求图的最大权匹配。
其中 1≤n≤105,0≤ai,bi≤1091 \leq n \leq 10^5, 0 \leq a_i, b_i \leq 10^9 。

思路

点 i,ji, j 的权值 max(∣ai−aj∣,∣ai−bj∣,∣bi−aj∣,∣bi−bj∣)max(|a_i - a_j|, |a_i - b_j|, |b_i - a_j|, |b_i - b_j|) 可以等价为 max(max(ai,bi)−min(aj,bj),max(aj,bj)−min(ai,bi))max(max(a_i, b_i) - min(a_j, b_j), max(a_j, b_j) - min(a_i, b_i)) 。所以原图中匹配的总权值可以等价地表示成选取 nn 个点加上 max(a,b)max(a, b) ，剩下 nn 个点减去 min(a,b)min(a, b) 。
假定 ai≥bia_i \geq b_i ，在数轴上比较一下可以发现 ∣ai−aj∣,∣bi−bj∣|a_i - a_j|, |b_i - b_j| 是没有作用的，假设 ii 与 jj 匹配，取 max(ai,bi)max(a_i, b_i) 与 min(aj,bj)min(a_j, b_j) 的条件为 ai−bj≥aj−bia_i - b_j \geq a_j - b_i 或 bi−aj≥bj−aib_i - a_j \geq b_j - a_i ，移项得 ai+bi≥aj+bja_i + b_i \geq a_j + b_j 。所以将点按 a+ba + b 降序排序后取前 nn 项加上 max(a,b)max(a, b) ，剩下的减去 min(a,b)min(a, b) 即为答案。
复杂度 O(n⋅logn)O(n \cdot logn) 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*
    Author: Cupids_Bow
    Time: 2022-10-17 16:01:46
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n;
    cin>>n;

    vector<array<int,2>> a(n*2,{0,0});
    for(auto &[x,y]:a) cin>>x>>y;

    sort(a.begin(),a.end(),[&](const array<int,2> &x,const array<int,2> &y){
        return x[0]+x[1]>y[0]+y[1];
    });

    i64 ans=0;
    for(int i=0;i<n;i++) ans+=max(a[i][0],a[i][1]);
    for(int i=n;i<n*2;i++) ans-=min(a[i][0],a[i][1]);

    cout<<ans;

    return true&&false;
}

I. Flood Fill

tag

  • 网络流

题意

给定 n,mn, m 的网格 aa 和 bb ，每一格为黑色或白色，单次操作可以选择 aa 中一个同色连通块将其反色，求最后 a,ba, b 中对应格子颜色不同的最小个数。
其中 1≤n,m≤1001 \leq n, m \leq 100 。

思路

考虑所有同色的连通块，相邻的两个连通快不可能同时被反色，因为其中一个反色后就与另一个合并为同一个连通块了。
所以操作等价为：选取若干个互不相邻的连通块将其反色，求最后 a,ba, b 中对应格子颜色不同的最小个数。
由于相邻的两个连通块颜色一定不同，所以所有连通块形成的图一定是二分图，即求一个二分图最大带权独立集，跑最大流即可。
复杂度 O(能过)O(能过) 。

代码

写的奇丑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
/*
    Author: Cupids_Bow
    Time: 2022-10-18 20:13:53
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

constexpr int INF=0x3f3f3f3f;
constexpr int N=1e4+5;
constexpr int M=4e4+5;

int st,en;
int dep[N],maxflow;
int first[N],cur[N],inque[N],tot=-1,vis;
struct Edge{
    int u;
    int v;
    int val;
    int nex;
}e[M<<1];

void add(int x,int y,int flow){
    tot++;
    e[tot]={x,y,flow,first[x]};
    first[x]=tot;
}

int bfs(){
    for(int i=0;i<=en;i++) cur[i]=first[i],dep[i]=INF,inque[i]=0;
    dep[st]=0;
    queue<int> q;
    q.push(st);
    inque[st]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        inque[u]=0;
        for(int k=first[u];k!=-1;k=e[k].nex){
            int v=e[k].v;
            if(dep[v]>dep[u]+1&&e[k].val){
                dep[v]=dep[u]+1;
                if(!inque[v]){
                    q.push(v);
                    inque[v]=1;
                }
            }
        }
    }
    if(dep[en]!=INF) return 1;
    return 0;
}

int dfs(int u,int flow){
    int rlow=0;
    if(u==en){
        vis=1;
        maxflow+=flow;
        return flow;
    }
    int used=0;
    for(int k=cur[u];k!=-1;k=e[k].nex){
        cur[u]=k;
        int v=e[k].v;
        if(e[k].val&&dep[v]==dep[u]+1){
            if(rlow=dfs(v,min(flow-used,e[k].val))){
                used+=rlow;
                e[k].val-=rlow;
                e[k^1].val+=rlow;
                if(used==flow) break;
            }
        }
    }
    return used;
}

int dinic(){
    while(bfs()){
        vis=1;
        while(vis){
            vis=0;
            dfs(st,INF);
        }
    }
    return maxflow;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    memset(first,-1,sizeof(first));

    int n,m;
    cin>>n>>m;

    vector<string> a(n+5,""),b(n+5,"");
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];

    int dx[]={1,-1,0,0},
        dy[]={0,0,1,-1};

    int ans=0;
    vector<vector<int>> viss(n+5,vector<int>(m+5,0)),id(n+5,vector<int>(m+5,0));
    vector<vector<int>> p(2,vector<int>(0));
    vector<int> w(n*m+5,0);
    int cnt=0;
    auto bfs=[&](int xs,int ys){
        queue<array<int,2>> q;
        array<int,2> val={0,0};
        val[a[xs][ys]==b[xs][ys]]++;
        q.push({xs,ys});
        viss[xs][ys]=1;
        cnt++;
        id[xs][ys]=cnt;
        while(!q.empty()){
            auto [x,y]=q.front();
            q.pop();
            for(int i=0;i<4;i++){
                int xe=x+dx[i],
                    ye=y+dy[i];
                if(xe<1||xe>n||ye<0||ye>=m||a[xe][ye]!=a[xs][ys]||viss[xe][ye]) continue;
                q.push({xe,ye});
                val[a[xe][ye]==b[xe][ye]]++;
                viss[xe][ye]=1;
                id[xe][ye]=cnt;
            }
        }
        w[cnt]=val[0]-val[1];
        ans+=val[1];
        p[a[xs][ys]-'0'].push_back(cnt);
    };

    for(int i=1;i<=n;i++)
        for(int j=0;j<m;j++) if(!viss[i][j]) bfs(i,j);

    st=0,en=cnt+1;
    for(auto x:p[0]){
        if(w[x]<0) continue;
        add(st,x,w[x]);
        add(x,st,0);
        ans+=w[x];
    }
    for(auto y:p[1]){
        if(w[y]<0) continue;
        add(y,en,w[y]);
        add(en,y,0);
        ans+=w[y];
    }

    map<array<int,2>,int> mp;
    for(int i=1;i<=n;i++)
        for(int j=0;j<m;j++){
            if(i+1<=n&&id[i][j]!=id[i+1][j]&&!mp.count({id[i][j],id[i+1][j]})){
                if(a[i][j]=='0'){
                    add(id[i][j],id[i+1][j],INF);
                    add(id[i+1][j],id[i][j],0);
                }
                else{
                    add(id[i+1][j],id[i][j],INF);
                    add(id[i][j],id[i+1][j],0);
                }
                mp[{id[i][j],id[i+1][j]}]=mp[{id[i+1][j],id[i][j]}]=1;
            }
            if(j+1<m&&id[i][j]!=id[i][j+1]&&!mp.count({id[i][j],id[i][j+1]})){
                if(a[i][j]=='0'){
                    add(id[i][j],id[i][j+1],INF);
                    add(id[i][j+1],id[i][j],0);
                }
                else{
                    add(id[i][j+1],id[i][j],INF);
                    add(id[i][j],id[i][j+1],0);
                }
                mp[{id[i][j],id[i][j+1]}]=mp[{id[i][j+1],id[i][j]}]=1;
            }
        }

    dinic();

    cout<<n*m-(ans-maxflow);

    return true&&false;
}

J. ABC Legacy

tag

  • 贪心

题意

给定长为 n⋅2n \cdot 2 的只含 A,B,CA, B, C 的串 ss ，判断能否将 ss 分割成若干个 AB,AC,BCAB, AC, BC 子序列，给出分割方式。
其中 1≤n≤1051 \leq n \leq 10^5 。

思路

将取子序列看成是括号匹配的过程， AA 和 CC 只能当作左括号和右括号，且确定了 A,CA, C 的数量后 BB 中有多少个需要作为左括号匹配，有多少个需要作为右括号匹配是确定的。假设有 xx 个 BB 需要作为左括号，将最靠左的 xx 个 BB 强制当成左括号，剩下的当成右括号匹配即可，可以证明这样一定最优，若不能全部匹配则无解。
复杂度 O(n)O(n) 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/*
    Author: Cupids_Bow
    Time: 2022-10-16 10:46:54
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n;
    cin>>n;

    string s;
    cin>>s;

    vector<array<int,2>> ans;
    int cnt=0,cntb=0;
    for(int i=0;i<n*2;i++){
        if(s[i]=='A') cnt++;
        if(s[i]=='B') cntb++;
        if(s[i]=='C') cnt--;
    }

    if((cntb-cnt)%2==1){
        cout<<"NO";
        return true&&false;
    }

    cntb=(cntb-cnt)/2;
    vector<int> staa,stab;
    for(int i=0;i<n*2;i++){
        if(s[i]=='A') staa.push_back(i);
        if(s[i]=='B'){
            if(cntb){
                stab.push_back(i);
                cntb--;
            }
            else{
                if(staa.size()){
                    ans.push_back({staa.back(),i});
                    staa.pop_back();
                }
                else{
                    cout<<"NO";
                    return true&&false;
                }
            }
        }
        if(s[i]=='C'){
            if(stab.size()){
                ans.push_back({stab.back(),i});
                stab.pop_back();
            }
            else if(staa.size()){
                ans.push_back({staa.back(),i});
                staa.pop_back();
            }
            else{
                cout<<"NO";
                return true&&false;
            }
        }
    }

    if(staa.size()||stab.size()){
        cout<<"NO";
        return true&&false;
    }

    cout<<"YES\n";
    for(auto [x,y]:ans) cout<<x+1<<" "<<y+1<<"\n";

    return true&&false;
}

K. Amazing Tree

tag

  • 贪心

题意

给定 nn 个节点的无根树，编号为 [1,n][1, n] ，选定一个点为根，构造字典序最小的后序遍历序列。
其中 1≤n≤2⋅1051 \leq n \leq 2 \cdot 10^5 。

思路

想一下可以发现序列起点一定是某个度数为 11 的节点。
以编号最小的度数为 11 的节点为根，先预处理出每棵子树中叶子的最小权值，记为 minnminn 。
假设编号最小度数为 11 的节点为 stst ，从 stst 开始 dfsdfs ，假设 dfsdfs 中在不断地往父节点跳。每到达一个节点 xx ，先检查所有子树的 minnminn 值，若 maxn(minn(v))(v∈son(x))maxn(minn(v))(v \in son(x)) 小于 xx ，则按 minn(v)minn(v) 从小到大排序后直接后序遍历每棵子树 vv ，最后再遍历 xx 即可，若不是，则按 minn(v)minn(v) 从小到大排序后先后序遍历除了 minn(v)minn(v) 最大的子树 ，再遍历 xx ，最后再继续从剩下的一个节点开始跳父亲。
可能代码更直观。
复杂度 O(n)O(n) 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/*
    Author: Cupids_Bow
    Time: 2022-10-17 17:37:57
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

void work(){
    int n;
    cin>>n;

    vector<vector<int>> e(n+5,vector<int>(0));
    for(int i=1,x,y;i<n;i++){
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }

    vector<int> minn(n+5,0);
    function<void(int,int)> dfs=[&](int x,int fa){
        if(e[x].size()==1) minn[x]=x;
        else minn[x]=n+1;
        for(auto v:e[x]){
            if(v==fa) continue;
            dfs(v,x);
            minn[x]=min(minn[x],minn[v]);
        }
    };

    vector<int> ans;
    function<void(int,int)> calc=[&](int x,int fa){
        vector<array<int,2>> vec;
        for(auto v:e[x]){
            if(v==fa) continue;
            vec.push_back({minn[v],v});
        }
        sort(vec.begin(),vec.end());
        for(auto [val,v]:vec) calc(v,x);
        ans.push_back(x);
    };

    function<void(int,int)> dp=[&](int x,int fa){
        vector<array<int,2>> vec;
        for(auto v:e[x]){
            if(v==fa) continue;
            vec.push_back({minn[v],v});
        }
        sort(vec.begin(),vec.end(),greater<array<int,2>>());
        while(vec.size()>1){
            calc(vec.back()[1],x);
            vec.pop_back();
        }
        if(vec.size()==0) ans.push_back(x);
        else{
            if(vec[0][0]>x){
                ans.push_back(x);
                dp(vec[0][1],x);
            }
            else{
                calc(vec[0][1],x);
                ans.push_back(x);
            }
        }
    };

    int st=1;
    for(int i=1;i<=n;i++) if(e[i].size()==1){
        st=i;
        break;
    }
    dfs(st,st);
    dp(st,st);

    for(auto x:ans) cout<<x<<" ";
    cout<<"\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int _=1;
    cin>>_;
    while(_--){
        work();
    }

    return true&&false;
}

L. Jason ABC

tag

  • 思维
  • 构造

题意

长为 n⋅3n \cdot 3 的只含 A,B,CA, B, C 的串 ss ，单次操作可以将 s[l,r]s[l, r] 全替换为 c∈{A,B,C}c \in \{A, B, C\} ，求最少操作次数使得 ss 中恰好有 nn 个 A,B,CA, B, C 。
其中 1≤n≤3⋅1051 \leq n \leq 3 \cdot 10^5 。

思路

若 ss 一开始就满足条件，则操作次数为 00 。
否则首先判断能否一次操作完成，即是否存在区间 [l,r][l, r] 使得 [1,l−1]∪[r+1,n⋅3][1, l - 1] \cup [r + 1, n \cdot 3] 中存在两个字母满足条件，双指针查找即可。
若都不满足，则一定可以在两次操作内完成先找一段前缀 [1,p][1, p] 使得 [1,p][1, p] 中恰好有 nn 个某一种字母，再往后修改 22 次，每次补全剩下的一个字母即可。
复杂度 O(n)O(n) 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/*
    Author: Cupids_Bow
    Time: 2022-10-17 20:48:27
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n;
    cin>>n;

    string s;
    cin>>s;

    vector<array<int,3>> cnt(n*3+5,{0,0,0});
    for(int i=1;i<=n*3;i++){
        if(s[i-1]=='A') cnt[i][0]++;
        if(s[i-1]=='B') cnt[i][1]++;
        if(s[i-1]=='C') cnt[i][2]++;
        cnt[i][0]+=cnt[i-1][0];
        cnt[i][1]+=cnt[i-1][1];
        cnt[i][2]+=cnt[i-1][2];
    }

    if(cnt[n*3][0]==n&&cnt[n*3][1]==n&&cnt[n*3][2]==n){
        cout<<"0";
        return true&&false;
    }

    auto check1=[&](char c){
        int w=c-'A';
        int w1=(w+1)%3,w2=(w+2)%3;
        for(int l=1,r=1;l<=n*3;l++){
            if(r<l) r=l;
            while(r+1<=n*3&&(cnt[r][w1]-cnt[l-1][w1]<cnt[n*3][w1]-n||cnt[r][w2]-cnt[l-1][w2]<cnt[n*3][w2]-n)) r++;
            if(cnt[r][w1]-cnt[l-1][w1]==cnt[n*3][w1]-n&&cnt[r][w2]-cnt[l-1][w2]==cnt[n*3][w2]-n){
                cout<<"1\n"<<l<<" "<<r<<" "<<c;
                return 1;
            }
        }
        return 0;
    };

    if(check1('A')||check1('B')||check1('C')) return true&&false;

    auto check2=[&](){
        for(int i=1;i<=n*3;i++){
            if(cnt[i][0]==n){
                cout<<"2\n";
                cout<<i+1<<" "<<i+n-cnt[i][1]<<" "<<"B\n";
                cout<<i+n-cnt[i][1]+1<<" "<<n*3<<" "<<"C\n";
                return;
            }
            if(cnt[i][1]==n){
                cout<<"2\n";
                cout<<i+1<<" "<<i+n-cnt[i][2]<<" "<<"C\n";
                cout<<i+n-cnt[i][2]+1<<" "<<n*3<<" "<<"A\n";
                return;
            }
            if(cnt[i][2]==n){
                cout<<"2\n";
                cout<<i+1<<" "<<i+n-cnt[i][0]<<" "<<"A\n";
                cout<<i+n-cnt[i][0]+1<<" "<<n*3<<" "<<"B\n";
                return;
            }
        }
    };

    check2();

    return true&&false;
}

M. Counting Phenomenal Arrays

tag

  • dfs
  • 计数

题意

给定 nn 和 modmod ，求长度为 k∈[2,n]k \in[2, n] ，元素和等于乘积的长为 kk 的数组个数，结果模 modmod 。
其中 2≤n≤2⋅105,108≤mod≤1092 \leq n \leq 2 \cdot 10^5, 10^8 \leq mod \leq 10^9 保证 modmod 为素数。

思路

假设当前数组的和与乘积均为 resres ，反证可以发现数组中的最大元素不会超过 ⌊res2⌋\lfloor \frac{res}{2} \rfloor ，且对于长为 kk 的数组， resres 不会超过 k⋅2k \cdot 2 。
假设我们生成的结果数组递增。可以从小到大枚举往当前数组中插入的数 x(x≥2)x(x \geq 2) ，同时记录当前数组的乘积 mulmul ，和 addadd ，已填数个数 szsz 与当前的方案数。转移时枚举插入多少个当前的 xx ，由于 x≥2x \geq 2 ， szsz 的值最多不会超过 lognlogn ，因此暴力 dfsdfs 即可，计算答案时剩下不足的位置全部填 11 。最后结果需要乘上阶乘表示全排列。
复杂度 O(n⋅logn)O(n \cdot logn) 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/*
    Author: Cupids_Bow
    Time: 2022-10-19 19:58:13
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n,mod;
    cin>>n>>mod;

    auto power=[&](int a,int b){
        int res=1;
        while(b){
            if(b&1) res=1ll*res*a%mod;
            a=1ll*a*a%mod;
            b>>=1;
        }
        return res;
    };

    vector<int> fac(n*2+5,0),ifac(n*2+5,0);
    fac[0]=ifac[0]=1;
    for(int i=1;i<n*2+5;i++) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[n*2+4]=power(fac[n*2+4],mod-2);
    for(int i=n*2+3;i>=1;i--) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;

    vector<int> ans(n*2+5,0);
    function<void(int,int,int,int,int)> dfs=[&](int x,int add,int mul,int sz,int val){
        if(x>n||1ll*x*mul-add-x+sz>n){
            ans[mul-add+sz]=(ans[mul-add+sz]+1ll*val*ifac[mul-add]%mod)%mod;
            return;
        }
        dfs(x+1,add,mul,sz,val);
        for(int i=1;;i++){
            if(1ll*x*mul-add-x+sz>n) break;
            mul*=x;
            add+=x;
            sz++;
            dfs(x+1,add,mul,sz,1ll*val*ifac[i]%mod);
        }
    };

    dfs(2,0,1,0,1);

    for(int i=2;i<=n;i++) cout<<1ll*ans[i]*fac[i]%mod<<" ";

    return true&&false;
}

N. A-series

tag

  • 贪心

题意

n+1n + 1 种纸，第 ii 张的大小 AiA_i 是 Ai+1A_{i + 1} 的两倍，开始 AiA_i 有 aia_i 张， AiA_i 需要 bib_i 张，可以将一张 AiA_i 大小的纸切割成两张 Ai+1A_{i + 1}大小的纸，求最小的满足 bb 数组的切割次数。
其中 1≤n≤2⋅105,0≤ai,bi≤1091 \leq n \leq 2 \cdot 10^5, 0 \leq a_i, b_i \leq 10^9 。

思路

从 AnA_n 往前贪心地借位即可。
复杂度 O(n)O(n) 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*
    Author: Cupids_Bow
    Time: 2022-10-16 10:36:31
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n;
    cin>>n;

    vector<int> a(n+1,0),b(n+1,0);
    for(int i=0;i<=n;i++) cin>>a[i];
    for(int i=0;i<=n;i++) cin>>b[i];

    i64 ans=0;
    for(int i=n;i>=1;i--) if(a[i]<b[i]){
        int cnt=(b[i]-a[i])/2+(b[i]-a[i])%2;
        a[i-1]-=cnt;
        ans+=cnt;
    }
    if(a[0]<b[0]) ans=-1;

    cout<<ans;

    return true&&false;
}