和dkw组队 敲开心!

明天早自习请假了但是还要七点半起床 好痛苦QAQ

大概上午要睡过去

A. Protect Sheep

送分(ming)构造题(?)

把羊四周全围上狗就行

别像我一样没判羊挨着羊的情况然后连WA两发QAQ

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<cstdlib>
#include<map>
#include<vector>
using namespace std;

int mapx[1010][1010]={0},sx,sy;
char ch=0;
int wayx[4]={-1,0,1,0},wayy[4]={0,1,0,-1};

inline void readx(int& x)
{
	int k=1; x=0; register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

int main()
{
	readx(sx); readx(sy);
	for (int i=1;i<=sx;i++)
	{
		for (int j=1;j<=sy;j++)
		{
			ch=0; while (ch!='S' && ch!='W' && ch!='.') ch=getchar();
			if (ch=='S') mapx[i][j]=1;
			else if (ch=='W') mapx[i][j]=3;
		}
	}
	
//	for (int i=1;i<=sx;i++)
//	{
//		for (int j=1;j<=sy;j++) printf("%d",mapx[i][j]);
//		printf("\n");
//	}
	
	for (int i=1;i<=sx;i++)
	{
		for (int j=1;j<=sy;j++)
		{
			if (mapx[i][j]==1)
			{
				for (int w=0;w<=3;w++)
				{
					if (mapx[i+wayx[w]][j+wayy[w]]==3) { printf("No\n");return 0; }
					else if (mapx[i+wayx[w]][j+wayy[w]]==0) mapx[i+wayx[w]][j+wayy[w]]=2;
				}
			}
		}
	}
	
	printf("Yes\n");
	for (int i=1;i<=sx;i++)
	{
		for (int j=1;j<=sy;j++)
		{
			if (mapx[i][j]==1) printf("S");
			else if (mapx[i][j]==0) printf(".");
			else if (mapx[i][j]==2) printf("D");
			else printf("W");
		}
		printf("\n");
	}
	return 0;
}

B. Primal Sport

留坑

C. Producing Snow

对于每个雪堆二分哪一天最早化到负数

对温度做个前缀和,每次二分,假设cac天化到负数,当前是第i天

差分答案,化的=温度的区间,也就是i~cac-1差分一下,最后可以得知每天化了多少雪

加上化的小于温度的那一天,这个单独统计

最后加起来就ok

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<cstdlib>
#include<map>
#include<vector>
using namespace std;

long long n,seq[100010]={0};
long long tem[100010]={0};

long long st[100010]={0};

long long ans[100010]={0},ansk[100010]={0};

inline void readx(long long & x)
{
	long long  k=1; x=0; register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

int main()
{
	readx(n);
	for (int i=1;i<=n;i++) readx(seq[i]);
	for (int i=1;i<=n;i++) 
	{
		readx(tem[i]);
		st[i]=st[i-1]+tem[i];
	}
	st[n+1]=1e18;
	
	for (int i=1;i<=n;i++)
	{
		int lx=i,rx=n+1,mid,cac=i;
		while (lx<=rx)
		{
			mid=(lx+rx)>>1;
			if (st[mid]-st[i-1]>seq[i]) 
			{
				rx=mid-1;
				cac=mid;
			}
			else lx=mid+1;
		}

		ansk[i]+=1; ansk[cac]+=-1;
		ans[cac]+=seq[i]-(st[cac-1]-st[i-1]);		
	}
	
	for (int i=1;i<=n;i++) ansk[i]=ansk[i-1]+ansk[i];
	for (int i=1;i<=n;i++) ans[i]+=ansk[i]*tem[i];
	for (int i=1;i<=n;i++) printf("%lld ",ans[i]);
	printf("\n");
	return 0;
}

D. Perfect Security

一颗Trie树题,挺好玩的

带删除Trie树,每个结点记录有多少个数在这上面

递归删除并且贪心就行了

如果还不明白:

尽量让密钥和文本不匹配的那几位在低位上,这样才能字典序小,

也就是把数看成一个二进制字符串,带权匹配。

对于询问Trie树,如果能走同0或同1的当然好,那就贪心的走就是了,递归回来删除

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<cstdlib>
#include<map>
#include<vector>
using namespace std;

int n,cache1,upd,noden=2,cache2;
bool a[300010][33]={0};
bool seq[300010][33]={0};

struct trie_tree
{
	int hasnum,val,lc,rc;
}trie[300010*31]={0};

inline void readx(int& x)
{
	int k=1; x=0; register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

inline void update(int steps,int inx)
{
	if (steps==31) { trie[inx].hasnum++; return; }
	trie[inx].hasnum++;
	if (a[upd][steps])
	{
		if (trie[inx].rc!=-1) update(steps+1,trie[inx].rc);
		else
		{
			noden++;
			trie[inx].rc=noden; trie[noden].val=1;
			update(steps+1,noden);
		}
	}
	else
	{
		if (trie[inx].lc!=-1) update(steps+1,trie[inx].lc);
		else
		{
			noden++;
			trie[inx].lc=noden; trie[noden].val=0;
			update(steps+1,noden);
		}
	}
	return;
}

inline void matchx(int steps,int inx)
{
	if (steps==31)
	{
		trie[inx].hasnum--; 
		cache2+=(trie[inx].val^seq[upd][30]);
		return;
	}
	cache2+=(trie[inx].val^seq[upd][steps-1])*(1<<(30-steps+1));
	
	if (seq[upd][steps])
	{
		if (trie[inx].rc==-1 || trie[trie[inx].rc].hasnum==0) matchx(steps+1,trie[inx].lc);
		else matchx(steps+1,trie[inx].rc);
	}
	else
	{
		if (trie[inx].lc==-1 || trie[trie[inx].lc].hasnum==0) matchx(steps+1,trie[inx].rc);
		else matchx(steps+1,trie[inx].lc);
	}
	
	trie[inx].hasnum--;
	return;
}

int main()
{
	readx(n);
	for (int i=1;i<=n;i++)
	{
		readx(cache1);
		for (int j=0;j<=30;j++) seq[i][j]=(cache1&(1<<(30-j)));
	}
	for (int i=1;i<=n;i++) 
	{
		readx(cache1);
		for (int j=0;j<=30;j++) a[i][j]=(cache1&(1<<(30-j)));
	}
	
	trie[0].lc=1; trie[1].val=0; trie[0].rc=2; trie[2].val=1;
	for (int i=1;i<=300010*31-2;i++) trie[i].lc=trie[i].rc=-1;
	
//	for (int i=1;i<=n;i++)
//	{
//		for (int j=0;j<=30;j++) printf("%d",seq[i][j]);
//		printf("\n");
//	}
	
	for (int i=1;i<=n;i++)
	{
		upd=i;
		if (a[i][0]) update(1,2);
		else update(1,1);
	}
	
	for (int i=1;i<=n;i++)
	{
		cache2=0; upd=i;
		if (seq[i][0])
		{
			if (!trie[2].hasnum) matchx(1,1);
			else matchx(1,2);
		}
		else
		{
			if (!trie[1].hasnum) matchx(1,2);
			else matchx(1,1);
		}
		printf("%d ",cache2);
	}
	return 0;
}

E. Picking Strings

留坑

分类: Codeforces

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.