一模 (1) day1

时间:2023-03-08 17:24:12

第一题:(水题)

题目大意:求出n个  X% (X是小于等于2位的整数) 的乘积,去掉末尾的0;

解题过程:

1.直接 把整数乘好,然后确定小数点的位置,去掉多余的0 输出即可。

第二题:(搜索题)

题目大意:给出5*5的矩阵,矩阵由J 和 H 组成。 求出 规模为7 且 J的个数多于H的四连通块的个数。

解题过程:

1.一开始 直接 爆搜+hash 判重,但是样例过不去,然后才发现 深搜 的路径是一直走到底的,也就是不可能出现十字的情况。

2.然后想到可以先深搜5个,然后剩下2个用枚举的方法加上去。。(这样是错的,见反例B,应该深搜4个,枚举3个)枚举比较费时间,为了节省时间,我保存了上次枚举时方块的横坐标,然后这次枚举的横坐标就从上次的开始。但是这样是错的。(见反例A)应该从上次枚举时方块的横坐标-1开始。

反例A:

0 0 0 0 0
0 1 0 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0

反例B:

0 0 0 0 0
0 0 0 0 0
0 0 1 0 1
0 1 1 1 1
0 0 0 1 0

坑爹啊!!!!!!

第三题:

题目大意:经典约瑟夫问题,求出队顺序;

解题过程:

1.写了个链表暴力模拟竟然也能过。。

2.题解是排序二叉树,本来一直以为约瑟夫只能暴力模拟的。。找了好多资料,终于搞懂了。算法大致如下:

每次找到一个元素,删掉之后,剩下的编号大于它的重新编个号,比如 N=5 M=3,1 2 3 4 5,删去3,那么 变成 1 2 3(4) 4(5),可以发现重新编号后现在还是指着3,再往后数3个,那么指向1,也就是剩余的人中编号第1个小的。也就是 把删掉的元素拿掉后形成的队列中,再去数m个,找到队列中的元素i,那么这里的元素i的真实编号是 当前还没被删掉的编号第i个小的人的编号。  用排序二叉树来维护即可。