UVa 11520 Fill the Square

题意

填充一个NxN网格,使得每个格子的字母与其相邻的字母均不相同。输出字典序最小的填充方案。

思路

注意到解的空间非常大,因此只要每一次从’a’~’z’枚举并检查当前格子就可以了。这样也可以保证字典序最小,因为每一次的填充是从最小的字母开始尝试的。

代码

 

Codeforces 589A Email Aliases

题意

给出了一堆电子邮件地址,要你按照一定的规则分类,然后一类一类地输出。

思路

模拟。

只要正确地理解了题意基本不会有问题,在实现方面,可以考虑使用map的迭代器轻松地完成分类操作,令map的key为邮件地址的Hash(其实就是按照题目规则把等价但不同的邮件地址处理成同一个字符串),value为set<string>用来当作不同形态的邮件地址的容器。

代码

 

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

题意

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

思路

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

代码

 

POJ 3087 Shuffle'm Up

题意

你需要模拟一个洗牌过程,每一次把左右两个牌堆交叉叠放在一起,然后把整个叠放好的大牌堆再分成上下两半作为左右牌堆。现在给出你初始的左右牌堆,和一个要达到的目标大牌堆,问你至少要经过多少次洗牌,才能使左右牌堆直接叠放在一起等于大牌堆。

思路

这个题的数据还是比较小的,不妨尝试模拟洗牌过程,然后设定一个洗牌次数上界,只要在上界规定之内的次数没有洗出符合要求的牌堆,就视为无解。

代码

 

POJ 3083 Children of the Candy Corn

题意

对于一个入口和出口都在边界的迷宫,有两种一定能保证走出迷宫的方案,想象你自己站在迷宫的入口,你可以一直让左手扶着墙,贴着墙走,这样最后一定会走到终点。你也可以一直让右手扶着墙,贴着墙走,最终也一定会到达终点。现在要你模拟这两种策略,分别输出这样走要经历的步数,同时再算出不限于上述策略的走出迷宫的最短路方案。

思路

对于最短路,只要使用常规的BFS就可以解决。难点在于如何模拟左手扶墙和右手扶墙。如果是以左手扶墙来遍历迷宫的话,其实是相当于每一次都先尝试去走当前面朝方向的左边,若无法走,尝试直行,还不行的话,再尝试右行和上行。每一次行走,你要想想自己身处迷宫之中,并且根据你的行走动作来改变自己的朝向,模拟这个过程就是本题的难点。

有一种比较聪明的实现方式,就是把原来的行进向量(dir),也当成朝向向量来用,往左行走相当于朝向向量左转,直行相当于无旋转,右行相当于向右旋转,下行相当于两次右旋。每一次前进时把旋转完的朝向向量当行进向量用就可以了,下一次还是按照上面所述的循环操作。

本题还有一个技巧,你只需要实现扶一边墙行走,因为从起点扶一边墙走到终点相当于从终点扶另一边墙走到起点,所以你在第一次行走完之后,只要交换起点终点的’S’和’E’,然后再执行一次从”原终点”到”原起点”的行走,就可以了。

代码

 

FZU 2043 Social Network

题意

能拿出勇气挑战这种题,首先给你致敬。首先请确保你已经读懂了题面,我不会在这里翻译。我会说一些你可能没注意到的地方或者是这个题没有说明白的地方。

注意点

  • 数据是以空行分割的(也就是说保证没有多余空行),并且保证一行一命令,每个case的开头和结尾分别是启动和关机命令。但是,数据并没有保证没有多余空格,所以建议处理命令的时候过滤空格。
  • 关于消息机制,要知道当用户登录的时候显示的消息是未读消息,这一点题面说的很隐晦,而且还有一点,每次登陆和刷新之后,所有消息都会被读掉,也就是说上次显示过的消息,下次就不会显示。更为坑人的一点是,当两个人加为好友之后,一个人说话,系统会向另外一个人发通知,在加好友之前说过的话并不会推送到另外一个人那里。所以这里我们应该才用stack来实现这个消息系统,给每一个用户带一个stack,相当于收件箱,显示完就弹出,完全符合这个题的意图。
  • 关于个人界面的输出,这几乎是本题最大的坑点,首先你要注意排版,强烈建议跑完sample之后使用diff完全比较以防悲剧,同时,你很可能处理错了收件箱为空时的情况。
    你可能以为当收件箱为空时,输出应该是这样的:

    然而答案他却长这样:

    我想你应该知道咋改了。
  • 然后还有一个比较那啥的错误,就是你忘了实现refresh功能,你也没发现,因为sample没有。
  • 常规错误也要查一下,就是执行命令的判断不到位(你应该判断系统开机与否,用户注册情况,用户登录情况,用户重名情况)。

额外测试数据

不妨试一下这个数据。时间戳是我随便写的(因为没影响),如果你用了时间戳排序(虽然并没有需要),可能会有差异。

接下来上代码

模拟题的话注意点到位就不会错,其实代码本体的意义不大。

POJ 3488 Arne Saknussemm

题意

这个题的目的是练习读题,所以请努力理解这个题的题意,这里故意不翻译,it’s good for you~。

思路

操作时需要注意,string对象的结束位置并不是像char数组那样用’\0‘标记的,除非string对象被重做,否则这个对象的size值不会改变,即使你把一个string对象的每个字符全都弄成’\0’,你输出的也不是空串,而是一堆不可见的’\0’。

如果这个题很神秘的WA到死,请检查一下是不是跪在了不可见字符上。

代码

 

CodeForces 3C Tic-tac-toe

模拟题,这个题我WA了一下的原因是忘记了X的数量始终比O多一个,即使是赢了,也要是在棋盘合法的前提下。

Scroll to top