Codeforces Round 1404考试总结

考试总结

Codeforces Round #668 (Div. 1)考试总结：

2021年7月29日进行vp，ABDE四题，rk33，倒序开题yyds！

CF1404A Balanced Bitstring

题意：给定一个长为$n$存在$0/1/?$的字符串，你可以使$?$任意变为$0/1$，求是否存在方案使得所有长度为$k$的子串中$0/1$数量相等。（$1\leqslant n\leqslant 3\times 10^5$）

分析：

简单结论题。

考虑长度为$k$的区间的移动，发现满足条件的串一定满足$s_i=s_{i+k}$。

先判一手，然后把前$k$个位置能确定就确定，最后算一算又没有$0/1$超过$\frac{k}{2}$就好了。

代码：

#include<stdio.h>
#include<iostream>
using namespace std;
const int maxn=300005;
int T,n,m;
int cnt[maxn][2];
string s;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m),cin>>s,s=" "+s;
        int flg=0;
        for(int i=1;i<=n;i++){
            if(s[i]=='0')
                cnt[(i-1)%m+1][0]++;
            if(s[i]=='1')
                cnt[(i-1)%m+1][1]++;
        }
        int tot0=0,tot1=0;
        for(int i=1;i<=m;i++){
            if(cnt[i][0]&&cnt[i][1]){
                flg=1;
                break;
            }
            if(cnt[i][0])
                tot0++;
            if(cnt[i][1])
                tot1++;
        }
        if(m%2||tot0>m/2||tot1>m/2)
            flg=1;
        puts(flg==0? "YES":"NO");
        for(int i=1;i<=m;i++)
            cnt[i][0]=cnt[i][1]=0;
    }
    return 0;
}

CF1404B Tree Tag

题意：给定一个$n$个点的树，Alice和Bob初始在点$a,b$，移动速度为$da,db$，Alice、Bob轮流在树上移动不超过自己速度的距离，Alice先手，求存不存在一个时刻使得Alice必定与Bob同时处于一个节点过。（注意，移动是跳跃性的，也就是说不会经过路径上除端点的节点）（$1\leqslant n\leqslant 10^5$）

分析：

由于Alice先手，先判一次行动是否可以直接到达。

发现如果Alice抓不到Bob，最后一定是Bob在Alice四周反复横跳，所以只要Alice速度的两倍不比Bob慢，那么Alice就可以抓到Bob。

显然，Alice如果站在直径的中点，那么她离点的最远距离是最小的，所以再判一手Alice速度是否大于等于直径的一半。

如果不满足条件，那么Bob一定存在一种方案使得Alice无法抓到他。

代码：

#include<stdio.h>
#include<vector>
using namespace std;
const int maxn=100005;
int T,n,a,b,da,db,pos;
int dis[maxn];
vector<int>v[maxn];
void dfs(int x,int last){
    if(dis[x]>dis[pos])
        pos=x;
    for(int i=0;i<v[x].size();i++){
        int y=v[x][i];
        if(y==last)
            continue;
        dis[y]=dis[x]+1,dfs(y,x);
    }
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d%d%d",&n,&a,&b,&da,&db);
        for(int i=1;i<n;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            v[x].push_back(y),v[y].push_back(x);
        }
        if(2*da>=db)
            puts("Alice");
        else{
            pos=0,dis[a]=0,dfs(a,0);
            if(dis[b]<=da)
                puts("Alice");
            else{
                int tmp=pos;
                pos=0,dis[tmp]=0,dfs(tmp,0);
                if(2*da>=dis[pos])
                    puts("Alice");
                else puts("Bob");
            }
        }
        for(int i=1;i<=n;i++)
            v[i].clear();
    }
    return 0;
}

CF1404C Fixed Point Removal

题意：给定长为$n$的序列$a$，一次操作可以删除一个满足$a_i=i$的位置$i$，同时之后的数向前移动一位。$q$次询问，每次给定$x,y$，求不能删去前$x$个，后$y$个的情况下最多能删除多少元素。（$1\leqslant n\leqslant 3\times 10^5$）

分析：

套路题。

观察数据范围可知算法复杂度差不多是单$\log$，根据套路，我们将询问挂在右端点上，并从左往右扫，用数据结构维护左端点为$i$时的答案。

具体地，我们记$v_i$为可以删除的区间左端点为$i$时，有多少个点无法删除，可以发现加入一个点后我们只需要计算其对一段后缀的贡献。

扫描到$i$时，若$i<a_i$，不难发现其一定无法删除，于是直接全局加一。否则，我们二分一个位置使得其前面已经有$a_i$个无法删除的位置，将这个位置对应的后缀与$i+1$对应的后缀取并并直接更新。

这种操作用树状数组可以轻松维护，二分的时候在树状数组上二分就可以了，时间复杂度$O(n\log n)$。

代码：

#include<stdio.h>
#include<vector>
#define lowbit(x) x&-x
using namespace std;
const int maxn=300005;
int n,m;
int a[maxn],ans[maxn],t[maxn];
vector< pair<int,int> >v[maxn];
void update(int x,int v){
    for(int i=x;i<=n;i+=lowbit(i))
        t[i]+=v;
}
int query(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i))
        res+=t[i];
    return res;
}
int getkth(int k){
    int res=0;
    for(int i=18;i>=0;i--)
        if(res+(1<<i)<=n&&k>t[res+(1<<i)])
            k-=t[res+(1<<i)],res+=(1<<i);
    return res+1;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        x++,y=n-y;
        if(x<=y)
            v[y].push_back(make_pair(x,i));
    }
    for(int i=1,tot=0;i<=n;i++){
        if(i-a[i]>=0){
            tot++;
            int pos=getkth(a[i]);
            if(pos<=i)
                update(pos,1);
            else update(i+1,1);
        }
        for(int j=0;j<v[i].size();j++)
            ans[v[i][j].second]=tot-query(v[i][j].first);
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}

CF1404D Game of Pairs

题意：给定$2n$个数，A与B分别进行一次操作。A将元素划分成$n$对，B从每一对选择一个元素，如果权值和是$2n$的倍数则B胜利，否则A胜利。你需要扮演其中一方并取得胜利。（$1\leqslant n\leqslant 5\times 10^5$）

分析：

考虑观察样例，发现$n=2$时选择A，此时B不存在任何方案，根据套路我们猜测$n$为偶数时A必胜，否则B必胜。

$n$为偶数时，我们根据直觉将$(i,n+i)$划分为第$i$对，不难发现最后和一定是$kn+\sum_{i=1}^n i=\frac{n}{2}\times(n+1)+kn$，前一个一定不是$n$的倍数，所以B必败。

$n$为奇数时，我们设A给出的划分第$i$组为$(a_i,b_i)$。我们重新计算上面式子的值，发现和为$\frac{n+1}{2}\times n+kn$，是$n$的倍数，这启发我们在$i$与$n+i$中仅选一个。

将$(a_i,b_i)$以及$(i,n+i)$之间连边，两个完美匹配并起来一定是二分图，我们对其黑白染色，那么我们把黑点取出来，其和一定是$n$的倍数。若其为$n$的奇数倍，由于所有值之和为$\frac{2n(2n+1)}{2}=(2n+1)n$也是$n$的奇数倍，所以白点的和一定满足条件。

时间复杂度：$O(n)$。

代码：

#include<stdio.h>
#include<vector>
using namespace std;
const int maxn=500005;
int n;
long long sum;
int col[maxn<<1],lst[maxn<<1],a[maxn<<1];
vector<int>v[maxn<<1];
void dfs(int x,int c){
    col[x]=c;
    for(int i=0;i<v[x].size();i++){
        int y=v[x][i];
        if(col[y]==0)
            dfs(y,3-c);
    }
}
int main(){
    scanf("%d",&n);
    if(n%2==0){
        puts("First");
        fflush(stdout);
        for(int i=1;i<=n;i++)
            printf("%d ",i);
        for(int i=1;i<=n;i++)
            printf("%d ",i);
        puts("");
        return 0;
    }
    puts("Second");
    fflush(stdout);
    for(int i=1;i<=(n<<1);i++){
        scanf("%d",&a[i]);
        if(lst[a[i]]==0)
            lst[a[i]]=i;
        else v[i].push_back(lst[a[i]]),v[lst[a[i]]].push_back(i);
    }
    for(int i=1;i<=n;i++) 
        v[i].push_back(n+i),v[n+i].push_back(i); 
    for(int i=1;i<=(n<<1);i++){
        if(col[i]==0)
            dfs(i,1);
        if(col[i]==1)
            sum+=i;
    }
    int ok=sum%(2*n)==0? 1:2;
    for(int i=1;i<=(n<<1);i++)
        if(col[i]==ok)
            printf("%d ",i);
    puts("");
    return 0;
}

CF1404E Bricks

题意：给定一个$n\times m$的网格，格子有黑白两种颜色。你要用若干$1\times k$或$k\times 1$的长方形覆盖网格（不能超出边界），使得所有黑格子恰好被覆盖所有白格子恰好不被覆盖且长方形不重叠，求覆盖完黑格子最少用多少长方形。（$1\leqslant n,m\leqslant 200$）

分析：

如果长方形可以重叠，那么就是原题P6062 [USACO05JAN]Muddy Fields G。

正难则反，考虑先每个位置放一个长方形，然后将长方形一个个合并。

我们可以选择若干条边，让这些边两端的长方形合并，那么我们的任务被转化成在边满足条件的情况下取出最多的边。

容易发现一个点上下左右四条边相邻的边一定不能同时选，所以我们将边当成点，相邻的边连边，跑一个二分图最大点独立集就好了。

时间复杂度：$O(n^4)$。

代码：

#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
const int maxn=205;
int n,m,stp,ans,vtot,etot;
int vid[maxn][maxn],eid[maxn][maxn][2],vis[maxn*maxn*2],match[maxn*maxn*2];
string s[maxn];
vector<int>v[maxn*maxn*2];
inline void add(int x,int y){
    if(x&&y)
        v[x].push_back(y);
}
int Hungry(int x){
    for(int i=0;i<v[x].size();i++){
        int y=v[x][i];
        if(vis[y]==stp)
            continue;
        vis[y]=stp;
        if(match[y]==0||Hungry(match[y])){
            match[y]=x;
            return 1;
        }
    }
    return 0;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        cin>>s[i];
        for(int j=1;j<=m;j++){
            if(s[i][j-1]=='#')
                vid[i][j]=++vtot;
            if(j>1&&s[i][j-1]=='#'&&s[i][j-2]=='#')//(i,j) left
                eid[i][j][0]=++etot;
            if(i>1&&s[i][j-1]=='#'&&s[i-1][j-1]=='#')//(i,j) up
                eid[i][j][1]=++etot;
        }
    }
    for(int i=2;i<=n;i++)
        for(int j=2;j<=m;j++){//eid[i][j][0] eid[i][j][1] eid[i-1][j][0] eid[i][j-1][1]
            add(eid[i][j][0],eid[i][j][1]),add(eid[i-1][j][0],eid[i][j][1]);
            add(eid[i][j][0],eid[i][j-1][1]),add(eid[i-1][j][0],eid[i][j-1][1]);
        }
    for(int i=1;i<=etot;i++)
        stp++,ans+=Hungry(i);
    printf("%d\n",vtot-(etot-ans));
    return 0;
}