黑书::练手


因为繁重的假期作业好久没更博客了……真是尴尬QwQ

好不容易有点时间了决定看会黑书……实话说黑书有些题确实不适合人做……明显的傻题却近乎打表的模式轻松上100+行……

不过想找找感觉,毕竟长时间接触有点手生……于是就开始写咯~


黑书::枚举法

练习题1.2.3:奇怪的问题

这些问题是这样的:

⑴ 第一个答案是b 的问题是哪一个?
(a)2 (b) 3 (c) 4 (d) 5 (e) 6
⑵ 恰好有两个连续问题的答案是一样的,它们是:
(a) 2,3 (b) 3,4 (c) 4,5 (d) 5,6 (e) 6,7
⑶ 本问题答案和哪一个问题的答案相同?
(a) 1 (b) 2 (c) 4 (d) 7 (e) 6
⑷ 答案是a 的问题的个数是:
(a) 0 (b) 1 (c) 2 (d) 3 (e) 4
⑸ 本问题答案和哪一个问题的答案相同?
(a) 10 (b) 9 (c) 8 (d) 7 (e) 6
⑹ 答案是a 的问题的个数和答案是什么的问题的个数相同?
(a) b (b) c (c) d (d) e (e) 以上都不是
⑺ 按照字母顺序,本问题的答案和下一个问题的答案相差几个字母?
(a) 4 (b) 3 (c) 2 (d) 1 (e) 0(注: a和b相差一个字母)
⑻ 答案是元音字母的问题的个数是:
(a) 2 (b) 3 (c) 4 (d) 5 (e)6(注:A和E是元音字母)
⑼ 答案是辅音字母的问题的个数是:
(a)一个质数 (b)一个阶乘数 (c)一个平方数 (d)一个立方数 (e)5的倍数
⑽ 本问题的答案是:
(a) a (b) b (c) c (d) d (e) e

那么,这道题该如何解决呢?

由于只有10个,我们可以考虑直接判断。

那么,我们先枚举第一题答案,答案生效之后枚举第二题答案,以此类推……

“等等……这里面的某些题需要知道全局的某些数据才能解出来啊……”切(打)了1/4题(表)的我惊讶地说道。

于是,全盘删掉,又仔细看了看……原来需要枚举得出所有可能的答案(生成全排列),然后对答案进行判断,这是一种将求解类问题转化为判断类问题的方法。

于是,我们便可以得出所有可能的答案了~

所使用的“奇技淫巧”:

1.bool tmp=ca()&&cb()&&cc()&&cd()&&ce()&&cf()&&cg()&&ch()&&ci();

这里巧妙地运用了"&&"短路运算符,使得程序在进行后续判断没有意义时会提前结束。减少测评(Judgement夹击妹抖)所需时间。

2.生成答案序列时使用了DFS......因为层数不多不少比较适合DFS虽然可能会花掉更多时间但是代码实现上更加简单易懂。

不过这道题的判断没有办法简化,所以写的比较丑……有好的建议请留言~

#include <cstdio>

int ans[11],ansa,ansb,ansc,ansd,anse;

bool ca()
{
	if(ans[1]==1) return ans[2]==2;
	if(ans[1]==2) return ans[3]==2;
	if(ans[1]==3) return ans[4]==2;
	if(ans[1]==4) return ans[5]==2;
	if(ans[1]==5) return ans[6]==2;
	return false;
}

bool cb()
{
	if(ans[2]==1) return ans[2]==ans[3];
	if(ans[2]==2) return ans[3]==ans[4];
	if(ans[2]==3) return ans[4]==ans[5];
	if(ans[2]==4) return ans[5]==ans[6];
	if(ans[2]==5) return ans[6]==ans[7];
	return false;
}

bool cc()
{
	if(ans[3]==1) return ans[3]==ans[1];
	if(ans[3]==2) return ans[3]==ans[2];
	if(ans[3]==3) return ans[3]==ans[4];
	if(ans[3]==4) return ans[3]==ans[7];
	if(ans[3]==5) return ans[3]==ans[6];
	return false;
}

bool cd()
{
	if(ans[4]==1) return ansa==0;
	if(ans[4]==2) return ansa==1;
	if(ans[4]==3) return ansa==2;
	if(ans[4]==4) return ansa==3;
	if(ans[4]==5) return ansa==4;
	return false;
}

bool ce()
{
	if(ans[5]==1) return ans[5]==ans[10];
	if(ans[5]==2) return ans[5]==ans[9];
	if(ans[5]==3) return ans[5]==ans[8];
	if(ans[5]==4) return ans[5]==ans[7];
	if(ans[5]==5) return ans[5]==ans[6];
	return false;
}

bool cf()
{
	if(ans[6]==1) return ansa==ansb;
	if(ans[6]==2) return ansa==ansc;
	if(ans[6]==3) return ansa==ansd;
	if(ans[6]==4) return ansa==anse;
	if(ans[6]==5) return ansa!=ansb&&ansa!=ansc&&ansa!=ansd&&ansa!=anse;
	return false;
}

bool cg()
{
	if(ans[7]==1) return ans[8]==ans[7]+4||ans[8]==ans[7]-4;
	if(ans[7]==2) return ans[8]==ans[7]+3||ans[8]==ans[7]-3;
	if(ans[7]==3) return ans[8]==ans[7]+2||ans[8]==ans[7]-2;
	if(ans[7]==4) return ans[8]==ans[7]+1||ans[8]==ans[7]-1;
	if(ans[7]==5) return ans[8]==ans[7];
	return false;
}

bool ch()
{
	if(ans[8]==1) return ansa+anse==2;
	if(ans[8]==2) return ansa+anse==3;
	if(ans[8]==3) return ansa+anse==4;
	if(ans[8]==4) return ansa+anse==5;
	if(ans[8]==5) return ansa+anse==6;
	return false;
}

bool ci()
{
	int tmp=10-ansa-anse;
	if(ans[9]==1) return tmp==1||tmp==3||tmp==5||tmp==7;
	if(ans[9]==2) return tmp==1||tmp==2||tmp==6;
	if(ans[9]==3) return tmp==1||tmp==4||tmp==9;
	if(ans[9]==4) return tmp==1||tmp==8;
	if(ans[9]==5) return tmp==5;
	return false;
}

void check()
{
	ansa=0,ansb=0,ansc=0,ansd=0,anse=0;
	for(int i=1;i<=10;++i)
	{
		if(ans[i]==1) ansa++;
		if(ans[i]==2) ansb++;
		if(ans[i]==3) ansc++;
		if(ans[i]==4) ansd++;
		if(ans[i]==5) anse++;
	}
	bool tmp=ca()&&cb()&&cc()&&cd()&&ce()&&cf()&&cg()&&ch()&&ci();
	if(tmp)
	{
		for(int i=1;i<=10;++i) printf("%c ",'A'-1+ans[i]);
		printf("\n");
	}
	return;
}

void gen(int target)
{
	if(target==11)
	{
		check();
		return;
	}
	for(int i=1;i<=5;++i)
	{
		ans[target]=i;
		gen(target+1);
	}
	return;
}

int main()
{
	gen(1);
	return 0;
}

最终的答案为:

A B C C E E A E C E
A B C C E E E E C A
C D E B E E D C B A

这只是一道练手的水题QwQ未来还会写更多东西哒~

还得写作业……闹心QwQ


(微小的)总结

黑书是个好东西……里面有很多有用的“算法之外的”东西值得我们去深入理解。

碎叫啦~

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

转载:转载请注明原文链接 - 黑书::练手


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