devbox
代码探险家
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Codeforces Round #668 (Div. 1) 题解_codeforces round 668

作者：代码探险家 | 2024-08-16 03:45:24

赞

踩

codeforces round 668

A

容易发现一个结论：每隔 k k k 位的字符应该是相同的。于是就可以确定这个字符串的一部分。

剩下的部分只需要保证 字符串前 k k k 个字符中 01 01 01 数量相同即可，剩下的 ? 也就确定了，代码如下：

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define maxn 300010

int T,n,k;
char s[maxn];

int main()
{
	scanf("%d",&T);while(T--)
	{
		scanf("%d %d",&n,&k);
		scanf("%s",s+1);
		int ans=1,tot=0;
		for(int i=1;i<=k;i++){
			int p=-1;
			for(int j=i;j<=n;j+=k){
				if(s[j]!='?'){
					if(p!=-1&&p!=s[j]-'0')ans=0;
					else p=s[j]-'0';
				}
			}
			if(p!=-1){
				for(int j=i;j<=n;j+=k)
				if(s[j]=='?')s[j]=p+'0';
			}
		}
		if(ans){
			int zero=0,one=0;
			for(int i=1;i<=k;i++)if(s[i]=='0')zero++;else one++;
			for(int i=1;i<=k;i++)if(s[i]=='?'){
				if(zero<k/2)s[i]='0',zero++;
				else s[i]='1',one++;
			}
			zero=0,one=0;
			for(int i=1;i<=k;i++)if(s[i]=='0')zero++;else one++;
			if(zero!=one)ans=0;
			for(int i=k+1;i<=n;i++){
				if(s[i]=='?')s[i]=s[i-k];
				if(s[i]=='0')zero++;else one++;
				if(s[i-k]=='0')zero--;else one--;
				if(zero!=one)ans=0;
			}
		}
		if(ans)printf("YES\n");else printf("NO\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

B

想象一下一开始两人会怎么走：Alice肯定往Bob那里走，Bob肯定会远离Alice，最后Bob会被赶到叶子节点，然后Alice与他的距离一定是 d a da da，因为此时Alice就可以封锁Bob尽可能多的逃跑路线。

此时，Bob只有满足 d b > 2 × d a db>2\times da db>2×da 才能逃出去，所以这就是判输赢的条件。

但是还需要满足树上存在一条长度大于 2 × d a 2\times da 2×da 的链，不然Bob没地方跑，这个判一下直径长度即可。

代码如下：

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define maxn 100010
#define pb push_back

int T,n,a,b,da,db;
vector<int>e[maxn];
int dis[maxn],fur;
void dfs(int x,int fa){
	if(dis[x]>dis[fur])fur=x;
	for(int y:e[x])if(y!=fa){
		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++)e[i].clear();
		for(int i=1,x,y;i<n;i++)scanf("%d %d",&x,&y),e[x].pb(y),e[y].pb(x);
		dis[a]=0;fur=a;dfs(a,0);
		if(dis[b]<=da){printf("Alice\n");continue;}
		dis[fur]=0;dfs(fur,0);
		if(db>da*2&&dis[fur]>da*2)printf("Bob\n");
		else printf("Alice\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

C

一个显然且有用的转化：先令每个位置与下标做差，即令 b i = i − a i b_i=i-a_i bi​=i−ai​。

那么拿了一个 0 0 0 之后，后面的 1 1 1 就能拿了，拿了一个 i i i 之后，后面的 i + 1 i+1 i+1 就都能拿了。

先考虑如何能拿最多：肯定是每次拿最右边的且能拿的位置。转化一下，一个位置 i i i 能拿当且仅当它的左边有至少 b i b_i bi​ 个能拿（赛时这一步想错了一点然后就没了，太菜了QAQ）。

对于每个 i i i，求出最大的 c i c_i ci​ 表示左边界至少到 c i c_i ci​ 位置， i i i 才能拿。然后将询问排序用树状数组维护一下 c c c 就可以了。

代码如下：

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define maxn 300010

int n,m,a[maxn];
struct TREE{
	int tr[maxn];
	void add(int x){for(;x<=n;x+=(x&-x))tr[x]++;}
	int sum(int x){int re=0;for(;x;x-=(x&-x))re+=tr[x];return re;}
}tr;
struct par{int x,pos;};
vector<par>q[maxn];
int ans[maxn];

int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i]=i-a[i];
	for(int i=1,x,y;i<=m;i++)scanf("%d %d",&x,&y),q[n-y].push_back((par){1+x,i});
	for(int i=1;i<=n;i++){
		if(a[i]>=0){
			int l=1,r=i,p=-1;
			while(l<=r){
				int mid=l+r>>1;
				if(tr.sum(i)-tr.sum(mid-1)>=a[i])p=mid,l=mid+1;
				else r=mid-1;
			}
			if(p!=-1)tr.add(p);
		}
		for(par j:q[i]){
			ans[j.pos]=tr.sum(i)-tr.sum(j.x-1);
		}
	}
	for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
}

  • 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

D

打表发现，奇数时 Second \text{Second} Second 必胜，偶数时 First \text{First} First 必胜。

先说偶数的构造方法：令 i i i 与 i + n i+n i+n 一组。先假定 Second \text{Second} Second 取每组中较小的，那么取完之后的和模 n n n 一定是 n 2 \dfrac n 2 2n​，对于任意一组，假如不取小的取大的，那么总和的变化量都是 n n n，即总和模 n n n 依然是 n 2 \dfrac n 2 2n​，也就是说，无论怎么取，模 n n n 都是 n 2 \dfrac n 2 2n​，那么模 2 n 2n 2n 就不可能为 0 0 0， Second \text{Second} Second 必败。

然后是奇数时的选取策略：此时 1 1 1 ~ 2 n 2n 2n 的和模 2 n 2n 2n 余 n n n，也就是说，如果能找到一组选取方案模 n n n 为 0 0 0，那么就一定有解。因为找到的这组选取方案模 2 n 2n 2n 要么为 0 0 0 要么为 n n n，假如是 0 0 0 那它就是解，假如是 n n n 那么每一组换成另一个，这一个方案模 2 n 2n 2n 一定为 0 0 0。

考虑如何找到一组选取方案模 n n n 为 0 0 0，此时需要满足 n n n 的剩余系中每个数都被拿了一个，即 0 + 1 + 2 + . . . + n − 1 ≡ 0 ( m o d n ) 0+1+2+...+n-1\equiv 0\pmod n 0+1+2+...+n−1≡0(modn)。

模 n n n 为 i i i 的只有 i i i 和 i + n i+n i+n 两个，两者必拿其中一个，而每一组内也是两者必拿其中一个，考虑建一张图，同组数之间连红边， i i i 与 i + 1 i+1 i+1 连蓝边，像这样（从官方题解那偷来的qwq）：
在这里插入图片描述
然后就会形成很多个环，每个点恰好连接一条红边一条蓝边，那么每个环一定都是偶环，然后就可以黑白染色，白点集和黑点集分别对应一个方案。

代码如下：

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define maxn 1000010
#define pb push_back

int n,p[maxn],last[maxn];
vector<int>e[maxn];
bool v[maxn];
vector<int>c[2];int C[2];
void dfs(int x,int col){
	v[x]=true;
	c[col].pb(x);C[col]=(C[col]+x)%(2*n);
	for(int y:e[x])if(!v[y])dfs(y,col^1);
}

int main()
{
	scanf("%d",&n);
	if(n%2==0){
		printf("First\n");fflush(stdout);
		for(int i=1;i<=2*n;i++)printf("%d ",i<=n?i:i-n);fflush(stdout);
	}else{
		printf("Second\n");fflush(stdout);
		for(int i=1;i<=2*n;i++){
			scanf("%d",&p[i]);
			if(last[p[i]])e[i].pb(last[p[i]]),e[last[p[i]]].pb(i);
			else last[p[i]]=i;
			if(i<=n)e[i].pb(i+n),e[i+n].pb(i);
		}
		for(int i=1;i<=2*n;i++)if(!v[i])dfs(i,0);
		for(int i=0;i<2;i++)if(!C[i]){
			for(int j:c[i])printf("%d ",j);
		}
		fflush(stdout);
	}
}

  • 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

E

将放砖块转化为删边，假如两个黑块之间的公共边被删了，说明两者在同一块。

由于每删一条边砖块数 − 1 -1 −1，那么问题就变成了最多能删多少条边，由于没有 L L L 形的砖，所以需要保证每一个黑块处都不能删出 L L L 形，这个问题可以转化一下：将边化点，让两个冲突的边之间连边，问题就变成了求最大独立集，由于这是二分图，用网络流解决即可。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 100010

int n,m,S,T,ans=0;
char s[210][210];
struct edge{int y,z,next;}e[maxn*6<<1];
int first[maxn],len=1;
void buildroad(int x,int y,int z){e[++len]=(edge){y,z,first[x]};first[x]=len;}
void ins(int x,int y,int z=1){buildroad(x,y,z);buildroad(y,x,0);/*printf("ins : %d %d\n",x,y);*/}
int h[maxn],q[maxn],st,ed,cur[maxn];
bool bfs(){
	memset(h,0,(T+1)<<2);
	h[q[st=ed=1]=S]=1;
	while(st<=ed){
		int x=q[st++];cur[x]=first[x];
		for(int i=first[x];i;i=e[i].next)
		if(!h[e[i].y]&&e[i].z)h[q[++ed]=e[i].y]=h[x]+1;
	}
	return h[T];
}
int dfs(int x,int flow){
	if(x==T)return flow; int tt=0;
	for(int i=cur[x];i;i=e[i].next){
		int y=e[i].y;cur[x]=i;
		if(h[y]==h[x]+1&&e[i].z){
			int p=dfs(y,min(flow-tt,e[i].z));tt+=p;
			e[i].z-=p;e[i^1].z+=p;
		}
		if(tt==flow)break;
	}
	if(!tt)h[x]=0;
	return tt;
}

int main()
{
	scanf("%d %d",&n,&m);S=n*(m-1)+m*(n-1)+1;T=S+1;
	for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
//	printf("S : %d  T : %d\n",S,T);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)if(s[i][j]=='#'){
			int L=j>1&&s[i][j-1]=='#'?(i-1)*(m-1)+j-1:0;
			int R=j<m&&s[i][j+1]=='#'?(i-1)*(m-1)+j:0;
			int U=i>1&&s[i-1][j]=='#'?(i-2)*m+j+n*(m-1):0;
			int D=i<n&&s[i+1][j]=='#'?(i-1)*m+j+n*(m-1):0;
			if(L&&U)ins(L,U);
			if(L&&D)ins(L,D);
			if(R&&U)ins(R,U);
			if(R&&D)ins(R,D);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)if(s[i][j]=='#'){
			ans++;
			if(j<m&&s[i][j+1]=='#')ins(S,(i-1)*(m-1)+j),ans--;
			if(i<n&&s[i+1][j]=='#')ins((i-1)*m+j+n*(m-1),T),ans--;
		}
	}
	while(bfs())ans+=dfs(S,n*m);
	printf("%d",ans);
}

  • 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
本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号