UVA 11462 Age Sort

题意

排序,25MB大数据,都是整数,最大100最小0,内存极其紧张。

思路

面对这种数据范围很小,量很大的情况,考虑计数排序,原理非常简单就是开个数组统计一下不同值有多少个数字就搞定了,时间O(n)。

能做到O(n)的排序算法还有Sleep Sort,不过因为利用多线程睡眠差异太难控制所以也没啥实际意义。

被卡常数的时候,也可以考虑用计数排序进行没什么卵用的优化(结果可能就真卡过了)。

代码

CodeForces 236A Boy or Girl

题意

判断字符串长度是奇数还是偶数。

思路

代码

 

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)的完全剩余系里标记一下就搞定了。

代码

暴力:

数学:

 

UVA 12946 Peanoland contacting Gaussland

题意

给出了一个从整数到复数的映射,你要求出给你的整数映射成的复数的实部和虚部。

思路

STL complex裸题。

直接模拟就好,当然自己写一个complex结构体也不是难事。

代码

 

CodeForces 583A Asphalting Roads

题意

修路,一次选定一个横排一个竖排,如果横排竖排都没修,就把横排和竖排都修好,否则不用管。给出你若干修路尝试,问你哪些尝试最终执行了。

思路

照着题意简单模拟一下就好了。

代码

 

URAL 2066 Simple Expression

题意

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

思路

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

代码

 

SGU 123 The sum

题意

打出斐波那契数列前41项。

思路

没啥好说的,入门经典题。对于新手来说,容易跪在直接求斐波那契的题的原因一般是没有采用记忆化的方法(存住之前的每一个值),而是每一次都重新推一遍,这样就超时了。要么就是没有注意到int范围弄爆了,或者把longlong弄爆了(这个时候应该是java大法好)。

代码

 

HDU 1157 Who's in the Middle

我先给水过去,然后加难度。。。

HDU 1702 ACboy needs your help again!

STL小练习

其实手写应该会很带感

Codeforces 501 B Misha and Changing Handles

STL小练习系列

Scroll to top