提示:题解正文前超长啰嗦部分

我活到现在,还没这么惨过,NOIp都没有。

比赛开始4min的时候,切掉A

 

 

 

嗯没有什么毛病

最后

 

 

用实力告诉你什么叫没带脑子比赛


开始切B

下面两段程序只有这里不一样

for (int i=1;i<=len;i++)
	{
		while (mapx[i]=='*') i++;
		if (i>len) break;
		int j=i;
		while (mapx[j+1]=='.') j++;
		
		if (a<b) swap(a,b); 
		bool flag=0;
		for (int k=i;k<=j;k++)
		{
			if (!flag && a) a--;
			else if (b) b--;
			flag^=1;
		}
		i=j+1;
	}
for (int i=1;i<=len;i++)
	{
		while (mapx[i]=='*') i++;
		if (i>len) break;
		int j=i;
		while (mapx[j+1]=='.') j++;
		
		if (a<b) swap(a,b); bool flag=0;
		if (!a) break;
		for (int k=i;k<=j;k++)
		{
			if (!flag) 
			{
				a--;
				if (!b) break;
			}
			else 
			{
				b--;
				if (!a) break;
			}
			flag^=1;
		}
		i=j+1;
	}

为啥第二个会WA?????


C 35min找错

尝试cout某些变量,发现去掉cout和不去掉,结果不一样

你猜哪错了?

for (int i=i;i<=n;i++)

35min找这一个字母 我怕不是学文化课学傻了写出i=i来??

然后 忘记判前导零 WA一发

最后,最后还fst了!!

for (int i=0;i<=8;i++)

10^9是10位数,我***……

我持盾,持盾。。


D 手速打完

seq[100010] -> WA 一发

改对,交上,Ac。

最后还是fst了!!!!

map<int,int>

我***……

我持盾,持盾。。


然后我们愉悦的比赛就结束了。

我都不知道我的脑子飞哪去了……找到和我说一声‘

细节决定Rating啊!

凉凉。


我们还是来扯题解吧

A. Equator

这题巨没意思,加一遍扫一遍完事

注意sum/2还要上取整,也就是+sum%2

B. Students in Railway Carriage

我们貌似其实好像大概一定可以说明贪心是对的

这样,如果有一些空段,它们\geq 2且是一个偶数,

那你无论什么顺序安排反正都一样,填满的格子不能变多。(二元组证一下……)

对于奇数那些,……呃, \geq 3的拆成一段偶数空位和一个空位这样两个空段

这就变成了若干由一个空位,2N个空位组成的空段。

对于一个的那些你怎么放也是固定结果的。

(注意其实\geq 3的,拆出的一个空位,你放黑或白都可以,并不受后面偶数段的影响)

然后你每次挑大的放进那一个就行。挨着放就行,反正次序安排与解的优劣无关

对于一个B这样好像很啰嗦了……

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

int a,b,len;
char mapx[200010]={0};

int main()
{
	scanf("%d%d%d",&len,&a,&b);
	scanf("%s",mapx+1);
	int ansx=a+b;
	
	for (int i=1;i<=len;i++)
	{
		while (mapx[i]=='*') i++;
		if (i>len) break;
		int j=i;
		while (mapx[j+1]=='.') j++;
		
		if (a<b) swap(a,b); 
		bool flag=0;
		for (int k=i;k<=j;k++)
		{
			if (!flag && a) a--;
			else if (b) b--;
			flag^=1;
		}
		i=j+1;
	}
	
	printf("%d\n",ansx-a-b);
	return 0;
}

C. Make a Square

解法1,枚举最终状态,每次判断可行并更新答案

解法2,从0到9枚举步数,DFS出终态并判断合法与否

特别注意判终态不含前导零(终态不含即可,非终态?含也行。为什么呢?)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<iterator>
#include<algorithm>
#include<cstdlib>
#include<queue>
#include<vector>
#define eps 1e-8
#define ll long long
using namespace std;

ll seq[20]={0},n,len=0;
ll seq2[20]={0},ans=0;

inline void readx(ll& x)
{
	x=0; ll k=1; 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 bool judgex()
{
	ll q=0,quq=0;
	for (int i=1;i<=15;i++) if (seq2[i]!=-1)
	{
		if ((!q) && (!seq2[i])) return false; 
		q*=10LL; q+=seq2[i];
	}
	quq=floor(sqrt(q));
	if (!q) return false;
	if (quq*quq==q) return true;
	return false;
}

inline void DFS(ll posx,ll stepx)
{
	if (posx>len+1) return;
	if (!stepx)
	{
		if (judgex()) ans=1LL;
		return;
	}
	
	ll qwq=seq2[posx];
	seq2[posx]=-1LL;
	DFS(posx+1LL,stepx-1LL);
	seq2[posx]=qwq;
	DFS(posx+1LL,stepx);
	return;
}

int main()
{
	for (int i=0;i<=19;i++) seq[i]=-1;
	readx(n);
	while (n)
	{
		seq[++len]=n%10;
		n/=10;
	}
	for (int i=1;i<=len/2;i++) swap(seq[i],seq[len+1-i]);
	
	
	for (int i=0;i<=9;i++)
	{
		memcpy(seq2,seq,sizeof(seq));
		for (int j=1;j<=len;j++)
		{
			DFS(j,i);
			if (ans==1LL)
			{
				printf("%d\n",i);
				return 0;
			}
		}
	}
	printf("-1\n");
	return 0;
}

D. Merge Equals

从左向右扫一遍然后开map记录位置,找到一个二元组,递归地消除即可。

特别注意long long

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

ll n,seq[170010]={0};
map<ll,int> maps;

inline void readx(ll& x)
{
	x=0; ll k=1; 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 go(int pos)
{
	int tor=maps[seq[pos]];
	maps[seq[pos]]=0;
	
	seq[pos]*=2LL; seq[tor]=-1; 
	if (maps[seq[pos]]) go(pos);
	else maps[seq[pos]]=pos;
}

int main()
{
	fill(seq,seq+170004,-1);
	readx(n);
	for (int i=1;i<=n;i++) readx(seq[i]);
	for (int i=1;i<=n;i++)
	{
		if (maps[seq[i]]!=0) go(i);
		else maps[seq[i]]=i;
	}
	int ansx=0;
	for (int i=1;i<=n;i++) if (seq[i]!=-1) ansx++;
	printf("%d\n",ansx);
	for (int i=1;i<=n;i++) if (seq[i]!=-1) printf("%lld ",seq[i]);
	printf("\n");
	return 0;
}

E. Byteland, Berland and Disputed Cities

交了几发,WA了。

所以思路是错的,并不会,留坑了。

F. Simple Cycles Edges

并没来得及看,留坑了。

G. Visible Black Areas

瞅了一眼图好像是个计算几何?并没细看题面,咕咕咕。


发表评论

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

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