2020-2021 ICPC Southeastern European Regional Programming Contest (SEERC 2020) 补题记录（9 / 13）

发表于 2022-10-15 更新于 2024-07-21 分类于 gym 本文字数： 15k 阅读时长 ≈ 14 分钟

SEERC 2020 补题记录

A. Archeologists

题意

长为 $n$ 的数列 $a$ ，构造另一个深度数列 $dep(dep_0 = dep_{n + 1} = 0)$ ，使得 $|dep_i - dep_{i + 1}| \leq 1(0 \leq i \leq n)$ ，求 $\sum\limits_{i = 1}^{n} a_i \cdot dep_i$ 的最大值。
其中 $1 \leq n \leq 250000, - 10^6 \leq a_i \leq 10^6$ 。

思路

首先有 $O(n^2)$ 的 $dp$ ：

$dp_{i,j}$ 表示考虑前 $i$ 项， $dep_i = j$ 时的最大值。
转移显然。

但显然寄了。
考虑求出 $a$ 的前缀和数列 $sum$ ，题意中关于 $dep$ 的限制可以转换为在 $sum$ 数列中求若干段连续区间，最大化区间和，同时每个点只能被作为区间起点 / 终点最多一次。
若选择区间个数比较小，可以考虑一个费用流模型，类似CF280D：

源点 $st$ ，汇点 $en$ 。
$\forall i \in [0,n-1]$ ，连边 $i \rightarrow i + 1$ ，容量为 $INF$ ，费用为 $0$ 。
$\forall i \in [0,n]$ ，连边 $st \rightarrow i$ ，容量为 $1$ ，费用为 $- sum_i$ 。
$\forall i \in [0,n]$ ，连边 $i \rightarrow en$ ，容量为 $1$ ，费用为 $sum_i$ 。

在图上跑最大费用最大流即可。
但实际上可以不用真的把图建出来，上述条件可以等价地理解为， $0 - n$ 每个节点有两条边，一条往后连一条往前连， $i, j$ 之间连边等价于有一条 $j$ 到 $i$ 的流量，对应的贡献为 $sum_i - sum_j$ 。于是可以直接从前往后维护一个小根堆，每个点入队两次，每次贪心地匹配即可。
复杂度 $O(n \cdot logn)$ 。

代码

/*
    Author: Cupids_Bow
    Time: 2022-10-14 20:00:52
*/
#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<i64> a(n+5,0);
    for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];

    i64 ans=0;
    priority_queue<i64,vector<i64>,greater<i64>> q;
    q.push(0);
    for(int i=1;i<=n;i++){
        q.push(a[i]);
        ans+=a[i]-q.top();
        q.pop();
        q.push(a[i]);
    }

    cout<<ans;

    return true&&false;
}

B. Reverse Game

题意

长为 $n$ 的 $01$ 串， $Alice$ 和 $Bob$ 每次可以翻转一个等于 $10, 110, 100, 1010$ 的子串，不能操作的人输，问谁赢。
其中 $1 \leq n \leq 10^6$ 。

思路

每次翻转会减少 $1$ 或 $2$ 个逆序对，统计一下总逆序对数即可。
打个表可以发现除了逆序对数等于 $3$ 的倍数都是 $Alice$ 赢。
复杂度 $O(n)$ 。

代码

/*
    Author: Cupids_Bow
    Time: 2022-10-12 19:00:38
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

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

    string s;
    cin>>s;

    int res=0,cnt=0;
    for(auto c:s){
        if(c=='1') cnt=(cnt+1)%3;
        else res=(res+cnt)%3;
    }

    if(res%3==0) cout<<"Bob";
    else cout<<"Alice";

    return true&&false;
}

D. Disk Sort

题意

$n + 1$ 个柱子，共 $3 \cdot n$ 颗珠子， $n$ 种颜色每种各 $3$ 颗，初始都放在 $1 - n$ 号柱子上，用最多 $6 \cdot n$ 次操作将它们按颜色分类排列在 $1 - n$ 号柱子上，各个时刻每个柱子上最多放 $3$ 颗珠子。
其中 $1 \leq n \leq 10^3$ 。

思路

转换思路即用最多 $6$ 次操作排好一种颜色的珠子，大力分类讨论即可。
复杂度 $O(n^2)$ 。

代码

略

E. Divisible by 3

题意

长为 $n$ 的序列 $a$ ，求 $nb$ 子串的个数。
数列 $a$ 的一个子串 $a[l, r]$ 是 $nb$ 当且仅当它的权值是 $3$ 的倍数。
一个数列 $b[1, 2, ..., m]$ 的权值为 $\sum\limits_{i = 1}^{n}\sum\limits_{j = i + 1}^{n} b_i \cdot b_j$ 。
其中 $1 \leq n \leq 5 \cdot 10^5, 0 \leq a_i \leq 10^9$ 。

思路

将 $a$ 每一项模 $3$ 后为一个 $012$ 数列。
$0$ 没有影响，只要计算 $1, 2$ 对总权值的贡献即可，记 $c_1, c_2$ 为子串中 $1, 2$ 出现的次数，则子串总权值为 $\frac{c_1 \cdot (c_1 - 1)}{2} + 4 \cdot \frac{c_2 \cdot (c_2 - 1)}{2} + 2 \cdot c_1 \cdot c_2$ 。
枚举右端点与左端点对应的 $c_1, c_2$ 值并计算即可。
复杂度 $O(n \cdot 3^2)$ 。

代码


/*
    Author: Cupids_Bow
    Time: 2022-10-12 19:17:05
*/
#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+5,0);
    for(int i=1;i<=n;i++) cin>>a[i],a[i]%=3;

    vector<int> cnt1(n+5,0),cnt2(n+5,0);
    for(int i=1;i<=n;i++){
        cnt1[i]=(cnt1[i-1]+(a[i]==1))%3;
        cnt2[i]=(cnt2[i-1]+(a[i]==2))%3;
    }

    i64 ans=0;
    vector<vector<int>> res(3,vector<int>(3,0));
    res[0][0]++;
    for(int i=1;i<=n;i++){
        for(int c1=0;c1<=2;c1++)
            for(int c2=0;c2<=2;c2++){
                int val=(cnt1[i]+3-c1)*(cnt1[i]+3-c1)-(cnt1[i]+3-c1)+(cnt1[i]+3-c1)*(cnt2[i]+3-c2)+(cnt2[i]+3-c2)*(cnt2[i]+3-c2)-(cnt2[i]+3-c2);
                val%=3;
                if(val==0) ans+=res[c1][c2];
            }
        res[cnt1[i]][cnt2[i]]++;
    }

    cout<<ans;

    return true&&false;
}

F. Fence Job

题意

长为 $n$ 的排列 $a$ ，单次操作可以将 $a_i(l \leq i \leq r)$ 赋值成 $min(a_l, a_{l + 1}, ..., a_r)$ ，求能得到的不同的数列个数，模 $10^9 + 7$ 。
其中 $1 \leq n \leq 3000$ 。

思路

双倍经验AGC058 B - Adjacent Chmax，只不过取 $min$ 变成取 $max$ 。
考虑如下的 $dp$ ：

记 $dp[i][j]$ 为考虑了前 $i$ 个数， $a_i = j$ 的数列个数。
$pos$ 为 $i$ 往前第一个小于 $a_i$ 的位置，不存在则为 $0$ ，用单调栈维护。
则有 $dp[i][j] += \sum\limits_{j = pos}^{i - 1}\sum\limits_{k = 1}^{n} dp[j][k]$ （用 $a_i$ 往前扩展）。
$dp[i][a[x]] += \sum\limits_{j = 1}^{a[x]} dp[i - 1][j]$ （ $a_i$ 被前面比它小的数覆盖， $x$ 为当前状态下单调栈内存的下标）。
当更新 $dp[i]$ 后，对 $j \in [pos + 1, i - 1]$ 这一段的 $dp[j][a[i]]$ 的值也要对应地更新，因为在加入 $a_i$ 之前是不存在情况使得 $a_j = a_i$ 的，加入 $a_i$ 后 $a_i$ 可以往前延伸，会多出这一种情况。
边界条件为 $dp[0][0] = 1$ ，最后答案为 $\sum\limits_{j = 1}^{n} dp[n][j]$ 。

朴素转移为 $O(n^3)$ ，套一个树状数组辅助，复杂度 $O(n^2 \cdot logn)$ 。

代码

/*
    Author: Cupids_Bow
    Time: 2022-10-13 20:52:04
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

const int mod=1e9+7;
const int N=3e3+5;

vector<vector<int>> dp;

void add(int x,int y,i64 k){
    x++,y++;
    for(int i=y;i<N;i+=(i&-i)) dp[x][i]=(dp[x][i]+k)%mod;
}
 
i64 sum(int x,int y){
    x++,y++;
    i64 res=0;
    for(int i=y;i;i-=(i&-i)) res=(res+dp[x][i])%mod;
    return res;
}

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

    int n;
    cin>>n;

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

    dp.resize(N,vector<int>(N,0));
    vector<int> sta;
    sta.push_back(0);
    add(0,0,1);
    for(int i=1;i<=n;i++){
        while(sta.size()&&p[sta.back()]>p[i]) sta.pop_back();
        for(int j=i;j>=sta.back()+1;j--) add(i,p[i],sum(j-1,n));
        for(auto x:sta) if(x) add(i,p[x],sum(i-1,p[x]));
        for(int j=sta.back()+1;j<=i-1;j++) add(j,p[i],sum(j-1,n));
        sta.push_back(i);
    }

    cout<<sum(n,n);

    return true&&false;
}

H. AND = OR

题意

长为 $n$ 的数列 $a$ ， $q$ 次询问，每次询问能否将 $(a_l, a_{l + 1}, ..., a_r)$ 分为两个非空集合使得一个集合内元素的或等于另一个集合内元素的与。
其中 $1 \leq n, q \leq 10^5, 0 \leq a_i \leq 2^{30} - 1$ 。

思路

首先特判 $l = r$ 。
假设分成的两个集合 $S, T$ ， $S$ 中元素的或等于 $T$ 中元素的与，最后得到的结果为 $val$ ，记 $popcount(val)$ 表示 $val$ 二进制表示下 $1$ 的个数 $k$ ，假设 $popcount(val) = k$ ，容易发现 $S$ 集合内所有数的 $popcount$ 都需要小于等于 $k$ ， $T$ 集合内所有数的 $popcount$ 都需要大于等于 $k$ 。
于是可以考虑枚举 $k$ ，分三类讨论：

区间内 $popcount = k$ 的数个数为 $0$ ，直接判断两边的结果是否相同。
区间内 $popcount = k$ 的数个数为 $1$ ，枚举这个数放在哪个个集合中。
区间内 $popcount = k$ 的数个数为 $2$ ，首先判断是否所有 $popcount = k$ 的数都相等，若不相等则无论怎么放都不能满足要求，可以反证，再枚举这些数放在哪个集合中或者都放。

于是可以 $31$ 棵线段树维护 $popcount = k$ 的所有数的或 / 与值和个数。
复杂度 $O(n \cdot log^2n)$ 。

代码

/*
    Author: Cupids_Bow
    Time: 2022-10-14 22:07:29
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

const int N=1e5+5;

struct tree{
    int l[N<<2];
    int r[N<<2];
    array<int,3> val[N<<2][31];
    void pushup(int x){
        for(int k=0;k<=30;k++){
            if(val[x<<1][k][2]!=0&&val[x<<1|1][k][2]!=0){
                if(val[x<<1][k][0]==val[x<<1][k][1]&&val[x<<1|1][k][0]==val[x<<1|1][k][1]&&val[x<<1][k][0]==val[x<<1|1][k][0]){
                    val[x][k]=val[x<<1][k];
                    val[x][k][2]+=val[x<<1|1][k][2];
                }
                else{
                    val[x][k][0]=(val[x<<1][k][0]|val[x<<1|1][k][0]);
                    val[x][k][1]=(val[x<<1][k][1]&val[x<<1|1][k][1]);
                    val[x][k][2]=(val[x<<1][k][2]+val[x<<1|1][k][2]);
                }
            }
            if(val[x<<1][k][2]!=0&&val[x<<1|1][k][2]==0) val[x][k]=val[x<<1][k];
            if(val[x<<1][k][2]==0&&val[x<<1|1][k][2]!=0) val[x][k]=val[x<<1|1][k];
            if(val[x<<1][k][2]==0&&val[x<<1|1][k][2]==0) val[x][k]={-1,-1,0};
        }
    }
    void build(int x,int L,int R,vector<int> &a){
        l[x]=L;
        r[x]=R;
        if(L==R){
            int bit=__builtin_popcount(a[L]);
            for(int k=0;k<=30;k++) val[x][k]={-1,-1,0};
            val[x][bit]={a[L],a[L],1};
            return;
        }
        int mid=L+R>>1;
        build(x<<1,L,mid,a);
        build(x<<1|1,mid+1,R,a);
        pushup(x);
        return;
    }
    array<int,3> merge(array<int,3> a,array<int,3> b){
        array<int,3> res={-1,-1,0};
        if(a[2]!=0&&b[2]!=0){
            if(a[0]==a[1]&&b[0]==b[1]&&a[0]==b[0]){
                res=a;
                res[2]+=b[2];
            }
            else{
                res[0]=(a[0]|b[0]);
                res[1]=(a[1]&b[1]);
                res[2]=(a[2]+b[2]);
            }
        }
        if(a[2]!=0&&b[2]==0) res=a;
        if(a[2]==0&&b[2]!=0) res=b;
        if(a[2]==0&&b[2]==0) res={-1,-1,0};
        return res;
    }
    array<int,3> search(int x,int ql,int qr,int k){
        if(l[x]>=ql&&r[x]<=qr) return val[x][k];
        if(r[x<<1]>=ql&&l[x<<1|1]<=qr) return merge(search(x<<1,ql,qr,k),search(x<<1|1,ql,qr,k));
        else if(r[x<<1]>=ql) return search(x<<1,ql,qr,k);
        else return search(x<<1|1,ql,qr,k);
    }
}tr;

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

    int n,q;
    cin>>n>>q;

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

    tr.build(1,1,n,a);

    while(q--){
        int l,r;
        cin>>l>>r;

        auto check=[&](){
            if(l==r) return 0;
            vector<array<int,3>> res(31,{-1,-1,0});
            for(int k=0;k<=30;k++) res[k]=tr.search(1,l,r,k);
            vector<int> pre(31,-1),suf(31,-1);
            for(int k=0;k<=30;k++) if(res[k][2]!=0){
                pre[k]=res[k][0];
                suf[k]=res[k][1];
            }
            for(int k=1;k<=30;k++){
                if(pre[k]==-1) pre[k]=pre[k-1];
                else if(pre[k-1]!=-1) pre[k]|=pre[k-1];
            }
            for(int k=29;k>=0;k--){
                if(suf[k]==-1) suf[k]=suf[k+1];
                else if(suf[k+1]!=-1) suf[k]&=suf[k+1];
            }
            for(int k=0;k<=30;k++) if(res[k][0]==res[k][1]){
                int res1=(k-1>=0?pre[k-1]:-1);
                int res2=(k+1<=30?suf[k+1]:-1);
                if(res[k][2]==0){
                    if(res1==res2) return 1;
                }
                else if(res[k][2]==1){
                    if(res1!=-1&&res2!=-1&&((res1|res[k][0])==res2)||(res1==(res2&res[k][0]))) return 1;
                    if(res1!=-1&&res2==-1&&res1==res[k][0]) return 1;
                    if(res1==-1&&res2!=-1&&res[k][0]==res2) return 1;
                }
                else{
                    if(res1==-1) res1=res[k][0];
                    if(res2==-1) res2=res[k][0];
                    if(((res1|res[k][0])==res2)||(res1==(res2&res[k][0]))) return 1;
                    if((res1|res[k][0])==(res2&res[k][0])) return 1;
                }
            }
            return 0;
        };

        cout<<(check()?"YES\n":"NO\n");
    }

    return true&&false;
}

I. Modulo Permutations

题意

计算满足如下条件的长为 $n$ 的排列个数，模 $10^9 + 7$ ：

$\forall i \in [1, n], p_i \ mod \ p_{i+1} \leq 2, (p_{n + 1} = p_1)$ 。

其中 $1 \leq n \leq 10^6$ 。

思路

若 $n$ 小于等于 $3$ ，则可以随便排，若 $n$ 大于 $3$ ，则所有大于等于 $3$ 的数后面只能放比它小的数字，所以最后的结果一定可以表示成两段递减的序列拼接起来的结果，且两段的结尾一定是 $1$ 或 $2$ ，即 $(..., 1) + (..., 2)$ 。
于是可以考虑 $dp_{x, y}(x < y)$ 表示两段结尾值分别为 $x, y$ 的分配方案数，有两种转移：

$dp[x][y] \rightarrow dp[x - 1][y]$ ， $x \ mod \ x - 1$ 一定满足条件，这一步相当于数组整体平移一个单位。
$dp[x][y] \rightarrow dp[x][x - 1]$ ， $y \ mod \ x - 1$ 需要小于等于 $2$ ，可以枚举 $x - 1$ 的倍数进行转移，复杂度为调和级数。

第一步转移一定满足条件且相当于数组整体平移一个单位，因此可以省略，记 $dp_{x, x - 1}$ 为两段结尾值分别为 $x, x - 1$ 的分配方案数，转移时枚举 $x - 1$ 的倍数即可。
复杂度 $O(n \cdot logn)$ 。

代码

/*
    Author: Cupids_Bow
    Time: 2022-10-12 22:35:53
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

const int mod=1e9+7;

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

    int n;
    cin>>n;

    vector<int> dp(n+5,0);
    dp[n+1]=1;
    for(int i=n;i>=2;i--){
        dp[i]=1;
        if(i>3){
            for(int j=i-1;j<=n;j+=i-1){
                if(j>i&&j<=n) dp[i]=(dp[i]+dp[j])%mod;
                if(j+1>i&&j+1<=n) dp[i]=(dp[i]+dp[j+1])%mod;
                if(j+2<=n) dp[i]=(dp[i]+dp[j+2])%mod;
            }
        }
        else{
            for(int j=i+1;j<=n;j++) dp[i]=(dp[i]+dp[j])%mod;
        }
    }

    cout<<1ll*dp[2]*n%mod;

    return true&&false;
}

L. Neo-Robin Hood

题意

总共 $n$ 个二元组 $(m_i, p_i)$ ，选择恰好 $2 \cdot k$ 个二元组使得其中 $k$ 个的 $\sum m$ 大于等于另 $k$ 个的 $\sum p$ 。
其中 $1 \leq n \leq 10^5, 1 \leq m_i, p_i \leq 10^9$ 。

思路

考虑同时选了两个人 $i, j$ 作为匹配，则他们的贡献为 $m_i - p_j$ 或 $m_j - p_i$ ，若 $m_i - p_j \geq m_j - p_i$ 则移项得 $m_i + p_i \geq m_j + p_j$ ，可以得到总是 $m + p$ 大的人取 $m$ 值，另一个人取 $p$ 值。
于是可以先对 $m + p$ 降序排序，所取的人一定来自于前后两段不相交的区间中，二分取的个数 $k$ ，堆维护一个前缀 / 后缀的 $k$ 大值 / 小值的和即可。
复杂度 $O(n \cdot log^2n)$ 。

代码

/*
    Author: Cupids_Bow
    Time: 2022-10-12 23:49:34
*/
#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+5,{0,0});
    for(int i=1;i<=n;i++) cin>>a[i][0];
    for(int i=1;i<=n;i++) cin>>a[i][1];

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

    int l=1,r=n/2,res=0;
    while(l<=r){
        int mid=l+r>>1;

        auto check=[&](int mid){
            vector<i64> pre(n+5,0),suf(n+5,0);
            priority_queue<int,vector<int>,greater<int>> q1;
            priority_queue<int,vector<int>,less<int>> q2;
            i64 sum=0;
            for(int i=1;i<=n;i++){
                q1.push(a[i][0]);
                sum+=a[i][0];
                if(q1.size()>mid){
                    sum-=q1.top();
                    q1.pop();
                }
                pre[i]=sum;
            }
            sum=0;
            for(int i=n;i>=1;i--){
                q2.push(a[i][1]);
                sum+=a[i][1];
                if(q2.size()>mid){
                    sum-=q2.top();
                    q2.pop();
                }
                suf[i]=sum;
            }
            for(int i=mid;i+1<=n-mid+1;i++) if(pre[i]-suf[i+1]>=0) return 1;
            return 0;
        };

        if(check(mid)) res=mid,l=mid+1;
        else r=mid-1;
    }

    cout<<res;

    return true&&false;
}

M. Mistake

题意

给定一张 $n$ 个 $m$ 条边的 $dag$ ，给出在图上跑 $k$ 次拓扑序的结果（多次的结果合并，但各个结果内部的顺序不变），求出每个元素属于第几次结果，多解输出任意一种。
其中 $1 \leq n \cdot k \leq 5 \cdot 10^5, 0 \leq m \leq 250000$ 。

思路

结果序列从首到尾贪心地匹配即可，每个编号的节点维护一个当前它可以属于的结果的集合。
复杂度 $O(n \cdot logn)$ 。

代码

/*
    Author: Cupids_Bow
    Time: 2022-10-12 20:09: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,k,m;
    cin>>n>>k>>m;

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

    vector<set<int>> q(n+5);
    for(int i=1;i<=n;i++) if(in[1][i]==0)
        for(int j=1;j<=k;j++) q[i].insert(j);
    for(int i=1,x;i<=n*k;i++){
        cin>>x;
        int id=(*q[x].begin());
        q[x].erase(q[x].begin());
        cout<<id<<" ";
        for(auto v:e[x]){
            in[id][v]--;
            if(in[id][v]==0) q[v].insert(id);
        }
    }

    return true&&false;
}