2017新春模拟赛


新年过去了寒假也过去了作业君也阵亡了……我的作业啊555

作为新年第一次比赛,整体难度不是很大,但是因为手生(补作业的缘故QwQ)还是考的不是很好……


2017新春模拟赛

T1:模拟

题目大意:在一个 N*N 的矩阵中,填满了正整数和一个零,零的位置表示一个空位置,问这个位置填多少才能 满足每行的和与每列的和都是一个定值。注意:数据保证一定会有且只有一个空位置。

不愧是模拟赛和NOIP一样第一题都是大水题……直接计算每行每列的值判断一下是否相等,如果相等算出差值即可。

可是,我在写的时候比较混乱,初始化啥的写得比较诡异,忘记初始化成-1了,前面写完后面改,没衔接上QwQ

最终丢掉了几个点……附更改后代码:

#include <cstdio>

int n,a[550][550],targetx,targety;
long long ans=-1,res,rescmp;
bool flg,first;

void check()
{
	if(!first)
	{
		first=true;
		rescmp=res;
		return;
	}
	if(res!=rescmp)
	{
		flg=true;
		return;
	}
}

int main()
{
	freopen("happiness.in","r",stdin);
	freopen("happiness.out","w",stdout);
	scanf("%d",&n);
	if(n==1)
	{
		printf("-1");
		return 0;
	}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
		{
			scanf("%d",&a[i][j]);
			if(!a[i][j])
			{
				targetx=i;
				targety=j;
			}
		}
	for(int i=1;i<=n;++i)
	{
		if(flg) break;
		if(i==targetx) continue;
		res=0;
		for(int j=1;j<=n;++j) res+=a[i][j];
		check();
	}
	for(int j=1;j<=n;++j)
	{
		if(flg) break;
		if(j==targety) continue;
		res=0;
		for(int i=1;i<=n;++i) res+=a[i][j];
		check();
	}
	if(!flg)
	{
		res=0;
		long long tmp=0;
		for(int i=1;i<=n;++i) res+=a[i][targety];
		for(int i=1;i<=n;++i) tmp+=a[targetx][i];
		if(res==tmp) ans=rescmp-tmp;
		if(ans<=0) ans=-1;
	}
	printf("%lld",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}

T2:DFS判环(弱

奇葩的国度中有 N 座城市,城市编号为 1 到 N,有 N 条单向的道路,不存在某个城市通向自己的道路。现可以任意修改任意道路的通行方向。 如果原来通行方向为 A 到 B,那么修改后的方向就是 B 到 A。问有多少种改变道路通行方 向的方案,使得这 N 座城市间的道路不产生环。注意:这 N 个数恰好是 1 到 N 的一个全排列。

这道题看到理解错了,当场懵*并认为需要用Tarjan......比赛结束才看到红字,发现其实这就是道极其简单的DFS判环,是判环的方法里面最简单的一种……

然后就愉快的爆零

这道题还有一个难点就是计算式为tmpans=2^tmpval-2,即数量级为2^n-2,需要注意。

附改后代码。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

long long ans=1,pf[110000],n,r[110000],tmpval;
bool use[110000],usetmp[110000];

bool dfs(int target)
{
	if(use[target]) return true;
	use[target]=true;
	if(dfs(r[target]))
	{
		tmpval++;
		return true;
	}
	return false;
}

int main()
{
	freopen("travel.in","r",stdin);
	freopen("travel.out","w",stdout);
	scanf("%lld",&n);
	pf[0]=1;
	for(int i=1;i<=n;i++) pf[i]=(pf[i-1]*2)%1000000007;
	for(int i=1;i<=n;++i) scanf("%lld",&r[i]);
	for(int i=1;i<=n;++i)
		if(!use[i])
		{
			tmpval=0;
			dfs(i);
			ans*=pf[tmpval]-2;
			ans=ans%1000000007;
		}
	printf("%lld",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}

T3:DP

这个DP很有意思哦……三维DP加上枚举时间复杂度o(n^4)......

f[i][j][k]表示第i盏灯修复染上j颜色达到k满意度的最小代价,可以得到一个很长的转移方程。

  • 如果第i盏灯不需要维修:f[i][color[i]][k]=std::min(f[i][color[i]][k],f[i-1][j][color[i]==j?k:k-1]);
  • 如果第i盏灯需要维修:f[i][j][k]=std::min(f[i][j][k],f[i-1][l][l==j?k:k-1]+p[i][j]);

需要讨论i与i-1的灯颜色一样和不一样两种情况。不一样时需要j-1.
首先需要枚举第i盏灯的M种颜色,在每次枚举第i盏灯时需要讨论是否与上一盏灯的颜色是否一致。

if else语句在使用的时候一定要注意'{}'匹配性。在切这道题的时候我发现调试不过,经检验发现是因为我在语句直接嵌套的时候喜欢不用'{}'直接写在一行上,但是如果多个if嵌套而又有else的话就会出现嵌套不对的情况导致程序完全不向指定方向前进的情况。

一定要注意!还有,如果要求最小值那么就要去初始化所有的数为最大值,我习惯性使用了一个不可能达到的数——‘-1’,但是这在实际应用中严重影响到了代码架构的可读性和规范性,俗话叫“自己挖坑自己往里跳”,于是就十分尴尬得WA了一个点……

附改后代码:

#include <cstdio>
#include <cstring>
#include <algorithm>

int color[110],f[110][110][110],n,m,ktot,ans=0x7fffffff,p[110][110];

int main()
{
	freopen("lantern.in","r",stdin);
	freopen("lantern.out","w",stdout);
	scanf("%d%d%d",&n,&m,&ktot);
	for(int i=1;i<=n;++i) scanf("%d",&color[i]);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j) scanf("%d",&p[i][j]);
	memset(f,-1,sizeof f);
	if(color[1]!=0) f[1][color[1]][1]=0;
	else for(int i=1;i<=m;++i) f[1][i][1]=p[1][i];
	for(int i=2;i<=n;++i)
		for(int k=1;k<=i;++k) //Confirm the light U want to consider and the satisfy point you want.
		{
			if(color[i]!=0) //Confirm whether this light needs to be repaired
			{
				if(color[i-1]!=0) //The light before it can't be repaired too.
					f[i][color[i]][k]=f[i-1][color[i-1]][color[i]==color[i-1]?k:k-1];
				else//The light before it can be repaired.
				{
					f[i][color[i]][k]=0x7fffffff;
					for(int j=1;j<=m;++j)
						if(f[i-1][j][color[i]==j?k:k-1]!=-1)
							f[i][color[i]][k]=std::min(f[i][color[i]][k],f[i-1][j][color[i]==j?k:k-1]);
					if(f[i][color[i]][k]==0x7fffffff) f[i][color[i]][k]=-1;
				}
			}
			else //The light needs to be repaired.
			{
				if(color[i-1]!=0)//The light before it can't be repaired.
				{
					for(int j=1;j<=m;++j)
						if(f[i-1][color[i-1]][color[i-1]==j?k:k-1]!=-1)
							f[i][j][k]=f[i-1][color[i-1]][color[i-1]==j?k:k-1]+p[i][j];
				}
				else
					for(int j=1;j<=m;++j)
					{
						f[i][j][k]=0x7fffffff;
						for(int l=1;l<=m;++l)
							if(f[i-1][l][l==j?k:k-1]!=-1)
								f[i][j][k]=std::min(f[i][j][k],f[i-1][l][l==j?k:k-1]+p[i][j]);
						if(f[i][j][k]==0x7fffffff) f[i][j][k]=-1;
					}
						
			}
		}
		for(int i=1;i<=m;++i)
				if(f[n][i][ktot]!=-1) ans=std::min(ans,f[n][i][ktot]);
		if(ans==0x7fffffff) ans=-1;
		printf("%d",ans);
		fclose(stdin);
		fclose(stdout);
		return 0;
}

小结

还需要总结,完善自己的代码逻辑,再就是看题的时候不要漏看什么,也不要“顿时一脸懵*”,否则会导致杯具的发生(还记得OI之星Po姐姐曾经就这样错过QwQ

最后的最后,再给我的作业君上一支香……又要熬夜抢救作业君QwQ

 

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

转载:转载请注明原文链接 - 2017新春模拟赛


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