UVa 11464 Even Parity

题意

请参考LRJ白书第一章例题7.

思路

大概是个带有机智成分的枚举。

为什么这么说,因为这道题的关键思路点就是发现只要知道第一行,就可以构造出整个数表,这样我们只要枚举第一行就可以解决问题,复杂度直接降低了一次幂。

代码

 

 

Codeforces 515B Drazil and His Happy Friends

题意

Translated by paryerhgq

Drazil有很多朋友,他们中有些人是快乐的,有些人是不快乐的。 Drazil想让他的朋友变得快乐。于是,他发明了以下的计划。
在他的朋友中,有n个男孩和m个女孩。我们把男孩从0到n-1编号,女孩从0到m-1编号。在第i天,Drazil邀请第i mod n个男孩和第i mod m个女孩一起吃饭(注意i从0开始)。如果两个人之中有一个是快乐的,那么另外一个也会变得快乐,否则,这两个人的心情状态不会改变。一个人一旦成为快乐的人(或者他原本就是快乐的),他能保持永远快乐。
Drazil想知道他是否可以使用该计划,使得他所有的朋友都变得快乐。

思路

注意到问题规模比较小,所以我们直接模拟就好了但是我们要至少操作2*nm次才可以。

有一种不暴力的解法,我们发现我们最后能够变快乐的人的编号x一定满足x = a (mod gcd(boy,girl)),其中boy是男生人数,girl是女生人数,a是某个一开始就快乐的人的编号,这样我们只要扫一遍所有快乐的人,在模gcd(boy,girl)的完全剩余系里标记一下就搞定了。

代码

暴力:

数学:

 

URAL 2066 Simple Expression

题意

给出三个数,要你求出用这三个数进行加减乘运算可以得到的最小值是多少。

思路

问题规模相当小,可以枚举每一种算术组合。也可以使用一些贪心策略少枚举一些情况,详情请参考下面的代码。

代码

 

CodeForces 244B Undoubtedly Lucky Numbers

把那些lucky numbers预先生成出来打进一个表里(预处理),接收到输入的时候然后只要查表就可以了。

HDU 1015 Safecracker

用STL,next_permutation把所有可能性搞出来注意检验就可以爆过去了。

CodeForces 96B Lucky Numbers (easy)

打个表就行,因为数据范围小。

Scroll to top