首页 > 代码库 > 二模 (6) day2

二模 (6) day2

第一题:

题目大意:50*50的格子里玩贪吃蛇。给出N步扭头的操作,判断贪吃蛇会在第几步挂掉。(蛇初始向东)

 

解题过程:

1.一开始的方法是:为了加快速度,只保存头和尾的坐标,然后保存尾巴的方向,每次move先头运动,然后尾巴按照之前的方向运动直到需要改变方向(继续按之前的方向运动将撞到墙壁或者走到一个map[x][y]==0的地方)。。事实证明这样是错误的。有可能尾巴继续走会到一个map[x][y]==0的地方,但是还不需要改变方向。。 运气不错,竟然还拿到了60分。

2.AC算法:保存所有点的坐标,然后模拟。。   对于这种数据很小的题目,不必去追求速度,AC才是王道额。

 


 

第二题:

题目大意:平面上给定 n 个两两不同的整数点,统计以给定的点为顶点,其直角边平行于坐标轴的直角三角形的个数。 0<n≤100,000

 

解题过程:

1.首先肯定是要做个离散化,排个序。。然后想到可以枚举直角顶点,然后分别计算下面4种直角三角形:

    X    X        XXX     XXX

  XX    XX      XX         XX

XXX    XXX    X             X

那么就要用到一个点 正左方的点的个数A,正右方点的个数B,正上方点的个数C,正下方点的个数D。

那么上面4种情况 的个数 分别为  A*C,B*C,B*D,A*D,   合并一下就是 (A+B)* (C+D)。。

所以只要统计出 每条直线上有多少个点,然后对于每个点,二分找到它属于那两条直线,乘起来 累加到ans即可。

初始得分100. 感觉会有更好的处理方法,我的方法跑出来貌似有些慢了。。常数较大。

 

 


第三题:

题目描述:

阿兰是某机密部门的打字员,出于保密的需要,该部门用于输入密码的键盘是特殊设计的,键盘上没有数字键,而只有以下六个键:Swap0, Swap1, Up, Down, Left, Right。为了说明这六个键的作用,我们先定义录入区的 6 个位置的编号,从左至右依次为 1,2,3,4,5,6。下面列出每个键的作用:
Swap0:按 Swap0,光标位置不变,将光标所在位置的数字与录入区的 1 号位置的数字(左起第一个数字)交换。如果光标已经处在录入区的 1 号位置,则按 Swap0 键之后,录入区的数字不变;

Swap1:按 Swap1,光标位置不变,将光标所在位置的数字与录入区的 6 号位置的数字(左起第六个数字)交换。如果光标已经处在录入区的 6 号位置,则按 Swap1 键之后,录入区的数字不变;
Up:按 Up,光标位置不变,将光标所在位置的数字加 1(除非该数字是 9)。例如,如果光标所在位置的数字为 2,按 Up 之后,该处的数字变为 3;如果该处数字为 9,则按 Up 之后,数字不变,光标位置也不变;
Down:按 Down,光标位置不变,将光标所在位置的数字减 1(除非该数字是 0),如果该处数字为 0,则按 Down 之后,数字不变,光标位置也不变;
Left:按 Left,光标左移一个位置,如果光标已经在录入区的 1 号位置(左起第一个位置)上,
则光标不动;
Right:按 Right,光标右移一个位置,如果光标已经在录入区的 6 号位置(左起第六个位置)
上,则光标不动。
当然,为了使这样的键盘发挥作用,每次录入密码之前,录入区总会随机出现一个长度为 6 的初始密码,而且光标固定出现在 1 号位置上。当巧妙地使用上述六个特殊键之后,可以得到目标密码,这时光标允许停在任何一个位置。
现在,阿兰有一个 6 位的数字密码,请编写一个程序,求出录入一个密码需要的最少的击键次数。

 

解题过程:

1.这题貌似只能BFS爆搜了。。。用双向BFS会快一些,但是还是过不了000000 999999的极限数据。需要3s左右。。老师的测试数据有点弱了。。裸的BFS竟然最多只跑了0.8s。。 然后加了个剪枝, 就是先处理出target的最大数字和最小数字,如果当前数字不在它们之间就不需要up,down操作了。瞬间变成0.2s。。

2.还有2个错误的剪枝:如果当前某一位数字和target对应位上的数相等,就不用改变他的值。。   还有 放弃左移操作。。   当然都是错的。。 不过本人实在太弱。在POJ1184提交了N次TLE,就猥琐的加了第二个错误的剪枝,并且000000 999999 直接输出59,结果就900MS AC了说。

3.如果有什么好的剪枝欢迎大神提出。

 

二模 (6) day2