Codeforces Round 1404 简要题解

A. Balanced Bitstring

略

B. Tree Tag

略

C. Fixed Point Removal

先考虑对固定的数组$a$如何求解。显然如果某个初始的$i<a_i$一定不可移除，否则我们为了移除它，需要某个时刻在$[1,i?1]$之间移除恰好$i?a_i$个。那么我们从左到右扫描，记录当前可移除的最大个数$sum$，若$i\ge a_i$且$sum\ge i?a_i$就意味着可以移除$a_i$，将$sum$增加$1$。最后构造方案是容易的，只需每次移除可移除的最后一个数即可。
现在还要将一个前缀和后缀变为不可移除。我们考虑对$x$从大到小扫描，每次将某个$a_i$变为可以移除的话，会引起连锁反应，将后面一些$a_i$变为可以移除。用一个线段树维护当前后缀中还未能移除且$i?a_i>0$的数分别还需要前面移除多少个数，那么每次即为后缀减$1$，查询权值$\le 0$的最小位置。而$y$的影响仅是一个求前缀和，用树状数组维护当前可以移除的位置集合即可。
时间复杂度为$\mathcal{O}((n+q)\log n)$。

#include <bits/stdc++.h>
#define lowbit(x) (x&-x)
#define inf 0x3f3f3f3fusing namespace std;typedef long long ll;namespace BIT {
    int sumv[300005];void add(int x,int n) {
    for(;x<=n;x+=lowbit(x)) sumv[x]++;
}int sum(int x) {
    int s=0;for(;x;x-=lowbit(x)) s+=sumv[x];return s;
}}namespace SGT {
    int addv[1200000],minn[1200000];inline void pushdown(int o) {
    if (addv[o]) {
    addv[o*2]+=addv[o];addv[o*2+1]+=addv[o];minn[o*2]-=addv[o];minn[o*2+1]-=addv[o];addv[o]=0;}
}inline void pushup(int o) {
    minn[o]=min(minn[o*2],minn[o*2+1]);
}void init() {
    memset(minn,0x3f,sizeof(minn));
}void update1(int l,int r,int o,int p,int q) {
    if (l==r) minn[o]=q;else {
    pushdown(o);int m=((l+r)>>1);if (m>=p) update1(l,m,o*2,p,q);else update1(m+1,r,o*2+1,p,q);pushup(o);}
}void update2(int l,int r,int o,int p) {
    if (l==r) {
    addv[o]++;minn[o]--;}else {
    pushdown(o);int m=((l+r)>>1);if (m>=p) {
    addv[o*2+1]++;minn[o*2+1]--;update2(l,m,o*2,p);}else update2(m+1,r,o*2+1,p);pushup(o);}
}int query(int l,int r,int o) {
    if (l==r) return l;else {
    pushdown(o);int m=((l+r)>>1);if (minn[o*2]<=0) return query(l,m,o*2);else return query(m+1,r,o*2+1);}
}}struct Query {
    int l,r,id;Query() {
    }Query(int a,int b,int c):l(a),r(b),id(c) {
    }bool operator < (const Query & b) const {
    return l>b.l;}
};Query q[300005];
int num[300005],ans[300005];int main() {
    int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&num[i]);for(int i=1;i<=m;i++) {
    int x,y;scanf("%d%d",&x,&y);q[i]=Query(x+1,n-y,i);}sort(q+1,q+m+1);SGT::init();int r=1;for(int i=n;i>0;i--) {
    if (i>=num[i]) {
    SGT::update1(1,n,1,i,i-num[i]);while (SGT::minn[1]<=0) {
    int x=SGT::query(1,n,1);BIT::add(x,n);SGT::update1(1,n,1,x,inf);SGT::update2(1,n,1,x);}}while (r<=m&&q[r].l>=i) {
    ans[q[r].id]=BIT::sum(q[r].r);r++;}}for(int i=1;i<=m;i++) printf("%d\n",ans[i]);return 0;
}

D. Game of Pairs

首先考虑$n$为偶数的情况。注意到若我们选择先手并配对$(i,n+i)$，那么后手不管如何取，总和一定满足$\equiv {\sum }_{i=1}^{n}i?\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}n)$，因此先手必胜。
再考虑$n$为偶数的情况。此时我们选择后手。对于先手的一个匹配方案，我们可以将每个数在$\mathrm{m}\mathrm{o}\mathrm{d}n$意义下看待，那么我们对于一个匹配$(u,v)$将$u\mathrm{m}\mathrm{o}\mathrm{d}n$与$v\mathrm{m}\mathrm{o}\mathrm{d}n$连一条边。这样一定会得到若干个环，因此我们容易得到一个方案，使得每个$\mathrm{m}\mathrm{o}\mathrm{d}n$意义下的数恰好被选了一次。此时这个方案中的数字和$\equiv {\sum }_{i=1}^{n}i\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}n)$，但有可能$?\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}2n)$。不过由于${\sum }_{i=1}^{2n}i\equiv n(\mathrm{m}\mathrm{o}\mathrm{d}2n)$，因此取它的补集即可。
时间复杂度为$\mathcal{O}(n)$。

#include <bits/stdc++.h>
#define lowbit(x) (x&-x)
#define inf 0x3f3f3f3fusing namespace std;typedef long long ll;bool vis1[500005],vis2[500005],chose[500005];
int val[500005][2],bel[1000005],id[1000005],n;void dfs(int x) {
    vis1[x]=1;if (!vis2[bel[x]]) {
    int u=bel[x];vis2[u]=1;if (val[u][0]==x) {
    chose[u]=0;if (!vis1[id[val[u][1]]]) dfs(id[val[u][1]]);}else {
    chose[u]=1;if (!vis1[id[val[u][0]]]) dfs(id[val[u][0]]);}}else {
    int u=bel[x+n];vis2[u]=1;if (val[u][0]==x+n) {
    chose[u]=0;if (!vis1[id[val[u][1]]]) dfs(id[val[u][1]]);}else {
    chose[u]=1;if (!vis1[id[val[u][0]]]) dfs(id[val[u][0]]);}}
}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=n+1;i<=2*n;i++) printf("%d ",i-n);printf("\n");fflush(stdout);return 0;}puts("Second");fflush(stdout);for(int i=1;i<=2*n;i++) {
    int x;scanf("%d",&x);if (!val[x][0]) val[x][0]=i;else val[x][1]=i;bel[i]=x;id[i]=((i>n)?i-n:i);} for(int i=1;i<=n;i++)if (!vis1[i]) dfs(i);int s=0;for(int i=1;i<=n;i++)if (!chose[i]) s=(s+val[i][0])%(2*n);else s=(s+val[i][1])%(2*n);for(int i=1;i<=n;i++) printf("%d ",val[i][chose[i]^(s>0)]);printf("\n");fflush(stdout);return 0;
}

E. Bricks

简单的二分图最大独立集。
转化一下问题，初始时我们将每个黑格都单独作为一个矩形，若两个黑格共一条边，我们可以尝试将它们合并到一个矩形内，唯一限制是一个黑格不能同时与横向和纵向的黑格合并。
因此我们可以把每条黑格间的边建成一个点，那么问题转化为取最多的点，使得不存在某条横向边与纵向边相邻，且它们对应的点同时选。这显然是一个二分图最大独立集问题。
建出来的图有$\mathcal{O}(nm)$个点，$\mathcal{O}(nm)$条边。用dinic算法时间复杂度为$\mathcal{O}(nm\sqrt{nm})$。

#include <bits/stdc++.h>
#define lowbit(x) (x&-x)
#define inf 0x3f3f3f3fusing namespace std;typedef long long ll;struct Edge {
    int t,f,next;Edge() {
    }Edge(int a,int b,int c):t(a),f(b),next(c) {
    }
};Edge e[10000000];
int head[80005],vs,vt,tot=-1;inline void addEdge(int x,int y,int z) {
    e[++tot]=Edge(y,z,head[x]);head[x]=tot;e[++tot]=Edge(x,0,head[y]);head[y]=tot;
}namespace Flow {
    int d[80005],cur[80005];
queue <int> q;bool bfs() {
    while (!q.empty()) q.pop();memset(d,255,sizeof(d));d[vs]=0;cur[vs]=head[vs];q.push(vs);while (!q.empty()) {
    int x=q.front();q.pop();for(int i=head[x];i!=-1;i=e[i].next)if (e[i].f&&d[e[i].t]==-1) {
    int u=e[i].t;d[u]=d[x]+1;cur[u]=head[u];if (u==vt) return 1;q.push(u);   }}return 0;
}int dfs(int x,int a) {
    if (x==vt||!a) return a;int ans=0;for(int &i=cur[x];i!=-1;i=e[i].next)if (e[i].f&&d[e[i].t]==d[x]+1) {
    int u=e[i].t;int f=dfs(u,min(a,e[i].f));if (f) {
    e[i].f-=f;e[i^1].f+=f;ans+=f;a-=f;if (!a) break;}}return ans;
}int maxflow() {
    int ans=0;while (bfs())ans+=dfs(vs,inf);return ans;
}} char str[205][205];
int id1[205][205],id2[205][205];int main() {
    memset(head,255,sizeof(head));int n,m;scanf("%d%d",&n,&m);int sz=0,sum=0;for(int i=1;i<=n;i++) {
    scanf("%s",str[i]+1);for(int j=1;j<=m;j++) sum+=(str[i][j]=='#');}for(int i=1;i<=n;i++)for(int j=1;j<m;j++)if (str[i][j]=='#'&&str[i][j+1]=='#') id1[i][j]=++sz;for(int i=1;i<n;i++)for(int j=1;j<=m;j++)if (str[i][j]=='#'&&str[i+1][j]=='#') id2[i][j]=++sz;vs=0;vt=sz+1;sum-=sz;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) {
    if (id1[i][j]) addEdge(vs,id1[i][j],1);if (id2[i][j]) addEdge(id2[i][j],vt,1);}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) {
    if (id1[i][j-1]&&id2[i-1][j]) addEdge(id1[i][j-1],id2[i-1][j],1);if (id1[i][j-1]&&id2[i][j]) addEdge(id1[i][j-1],id2[i][j],1);if (id1[i][j]&&id2[i-1][j]) addEdge(id1[i][j],id2[i-1][j],1);if (id1[i][j]&&id2[i][j]) addEdge(id1[i][j],id2[i][j],1);}printf("%d\n",sum+Flow::maxflow());return 0;
}