投稿
  1. 职涯宝首页
  2. 后端开发
  3. Python开发

Codeforces Round #668 (Div. 1)

鲁小强 • • Python开发

正题

      A. Balanced Bitstring

      这样来考虑:当前区间k合法,那么要往右移一位依然合法,那么必须要保证加进来的位置=弹出去的位置,也就是说对于i,我们判断一下输入的式子是否满足这样的性质就可以了,如果一个相等集合内只有问号,那么我们就待定它,最后看一下01个数是否都没有超过k/2即可．

#include
using namespace std;

const int N=300010;
char s[N];
int T,n,k;

int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d %d",&n,&k);
		scanf("%s",s+1);
		bool tf=true;
		for(int i=1;i

      B. Tree Tag　　　　　

      比赛的时候想的并不是很清楚,以Alice为根建树,首先如果da*2>=db,那么肯定是Alice赢,因为它可以走到一个刚好距离Bob db的位置,然后Bob往外跳一定是输.考虑da*22*da,如果没有这样的直径,那么输出Alice,因为只要Alice站在直径的中心点,下一步肯定可以抓到Bob.如果有这样的直径,而且Alice第一步抓不到Bob,那么我们先让Bob往子树里最深的点跳,知道跳不动,如果Alice下一步可以抓到Bob,那么Bob就往外跳,可以分类讨论Bob初始点是否为直径端点,来证明Bob一定可以跳到一个Alice抓不到的地方,然后让bob反复横跳就可以了.

#include
using namespace std;

const int N=100010;
struct edge{
	int y,nex;
}s[Nmx) mx=dep,p=x;
	if(x==b) op=dep;
	for(int i=first[x];i!=0;i=s[i].nex) if(s[i].y!=fa) dfs(s[i].y,x,dep+1);
}

void ga(int x,int fa,int dep){
	if(dep>mx) mx=dep,q=x;
	for(int i=first[x];i!=0;i=s[i].nex) if(s[i].y!=fa) ga(s[i].y,x,dep+1);
}

int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d %d %d %d %d",&n,&a,&b,&da,&db);
		for(int i=1;i=db){printf("Alicen");continue;}
		dfs(a,0,0);
		if(op2*da?"Bobn":"Alicen");
	}
}

      C. Fixed Point Removal

      考虑一次怎么做,d[i]表示[1,i]被删除的个数,如果i,否则Codeforces Round #668 (Div. 1).可以发现,考虑y=0的情况,我们发现对于i,可以使i产生贡献的是一个前缀,那么我们要找到这个前缀最右是多少,定义ans[i]为当x=mid的个数>=b[i],那么mid就是可行的ans,将二分放到线段树上即可.

      发现询问只要满足x

#include
using namespace std;

const int N=300010;
int n,q;
int a[N],rt[N],ans[N];
vector V[N];
int t[N

      D. Game of Pairs

      首先n为偶数很simple.前n个中间划一刀,后n个中间划一刀,两两连边就可以,可以证明无论怎么取%n!=0

      其次是n为奇数,首先要证明一个东西,如果选出一些数mod 2n=n,那么可以转化为mod 2n=0,因为总和mod2n = n,所以每个pair选另外一个就可以满足.

      我们考虑构造一种方案使得%n下选出的是1到n,一个pair两个中只能选一个,%n同余的两个数只能选一个,那么就有2n个点2n条边,且每个点度数为2,两条边的种类不同,所以必定形成了多个简单偶数环,在这些偶数环中,我们只要隔一个选一个出来就可以/

#include
using namespace std;

const int N=1000010;
int n;
int b[N];
pair a[N];
struct edge{
	int y,nex;
}s[N0){
		printf("Firstn");fflush(stdout);
		for(int i=1;i

      E. Bricks

      赛后看到就识别原题了.

      直接考虑网络流,S连到i表示割掉这条边 i选横着,i连到T表示割掉这条边 i选竖着,流量为o,o是一个足够大的数,对于两个横着相邻的点,我们先加上他们的贡献(也就是-1),然后在网络流里面新建一个点,将两个点连向它流量为inf,这个点连向汇点,表示如果有一个点选了竖着,那么这两点的贡献就不算数,要减去他们的贡献,也就是加上1,最后答案就是dinic()-点数*o+贡献.

      实验证明不连o也是可以的,因为连o主要是为了保证两边不会同时被割,但是一个点要么属于S集要么属于T集,两边不可能同时被割,然后这个本质上就是其他题解的最大独立集?

#include
using namespace std;

const int N=120010;
int n,m;
struct edge{
	int y,nex,c;
}s[N*8];
char ch[210][210];
bool tf[210][210];
int first[N],head[N],len=1,tot,bg,ed,op,d[N],o;
int fx[4]={-1,1,0,0};
int fy[4]={0,0,-1,1};
queue q;

void ins(int x,int y,int c){
	s[++len]=(edge){y,first[x],c};first[x]=len;
	s[++len]=(edge){x,first[y],0};first[y]=len;
}

int pos(int x,int y){
	return (x-1)*m+y;
}

bool bfs(){
	memset(d,0,sizeof(d));d[bg]=1;
	q.push(bg);
	for(int i=1;i

      总结

      这次比赛只做了前三题,因为第三题想到一半,后面都想错了,最后5分钟才发现可以直接看前面ans[i]来二分,所以后面两题看都没看,以后要吸取经验,想清楚点,t4赛后一个半小时莽出来了,t5也是赛后才看到题发现是原题,但网络流最小割的思想也有待复习.

本文由 @鲁小强 发布于 职涯宝 ，未经作者许可，禁止转载，欢迎您分享文章

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
鲁小强鲁小强认证作者
0 0
上一篇 2020年11月21日 11:15:04
下一篇 2020年11月21日 11:26:30

相关推荐

发表评论

登录后才能评论
小程序
小程序
微信客服
微信客服
QQ客服 建站服务
分享本页
返回顶部
icon 首页
icon 快讯
icon 专题
icon 问答
icon 教程
icon 我的