Codeforces Round #303 (Div. 2)


这几天停课老师留的任务……

感觉自己好菜OvO


T1 模拟

没啥可说的,给出许多车和他们的碰撞结果,询问碰撞中从未损坏的有哪些车。

用个cnt计数器搞一下就可以了。

#include <cstdio>

int n,cnt[110],ans,in;

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
		{
			scanf("%d",&in);
			switch(in)
			{
				case 1:++cnt[i];break;
				case 2:++cnt[j];break;
				case 3:++cnt[i],++cnt[j];break;
			}
		}
	for(int i=1;i<=n;++i)
		if(!cnt[i]) ++ans;
	printf("%d\n",ans);
	for(int i=1;i<=n;++i)
		if(!cnt[i]) printf("%d ",i);
	return 0;
}

T2 贪心

给出两个长度相同的01串,求出一个与他俩长度相同的新串使得这个新串和他们的差相同。

这道题贪心策略是:如果这两个串差异为偶数个,则遵循a串1/2,遵循b串1/2,相同的直接输出。如果差异为奇数个则无法完成进入特判。

注意这里是遵循a,b串而不是1/2输出'0'1/2输出'1',这里我debug了好久……

#include <cstdio>

int top,cnt;
bool a[1000100],b[1000100],ok;

void read()
{
	char tmp=getchar();
	while(tmp!='0'&&tmp!='1') tmp=getchar();
	while(tmp=='0'||tmp=='1')
	{
		a[++top]=tmp-'0';
		tmp=getchar();
	}
	top=0;
	while(tmp!='0'&&tmp!='1') tmp=getchar();
	while(tmp=='0'||tmp=='1')
	{
		b[++top]=tmp-'0';
		tmp=getchar();
	}
	return;
}

int main()
{
	read();
	for(int i=1;i<=top;++i)
		if(a[i]!=b[i]) cnt++;
	int haf=cnt/2,now=0;
	if(cnt%2) printf("impossible");
	else
	{
		for(int i=1;i<=top;++i)
		{
			if(a[i]==b[i]) printf("%d",a[i]);
			else
			{
				++now;
				if(now>haf) printf("%d",a[i]);
				else printf("%d",b[i]);
			}
		}
	}
}

Lijin的T3 背包

n个人,m行代码,每个人写一行代码会出现a[i]个bug,问最终一共出现bug数量少于b的情况数量。

这道题直接上背包就可以了,debug注意首先不需要四重循环直接三重就可以了,四重会重复遍历从而超时;其次初始化一定要写!对!了!滚动数组无论如何不要写错。

#include <bits/stdc++.h>

using namespace std;

int n,m,b,mo,a[510],ans,now,f[2][510][510];
void fucking_debug()
{
	for(int i=1;i<=m;++i)
	{
		for(int j=0;j<=b;++j)
			printf("%d ",f[now][i][j]);
		printf("\n");
	}
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&b,&mo);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	f[0][0][0]=f[1][0][0]=1;
	for(int i=1;i<=n;++i)//PeopleNow
	{
		now^=1;
		for(int j=0;j<=m;++j)
			for(int k=0;k<=b;++k)
			{
				f[now][j][k]=f[now^1][j][k];
				if(j>0&&k-a[i]>=0)
					f[now][j][k]=(f[now][j][k]+f[now][j-1][k-a[i]])%mo;
			}
	}
	for(int i=0;i<=b;++i)
		ans=(ans+f[now][m][i])%mo;
	printf("%d",ans);
	return 0;
}

T3 T4 T5 没时间写完了……

T3是DP无疑,但是没时间想明白如何10^5即不到n^2就完成的DP.

T4贪心策略未知。

暂时就是这样吧。

声明:TonyZhao's Home|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - Codeforces Round #303 (Div. 2)


不骗了,不骗了。
A Simple OIer fighting tooth and nail.