GDOI Day2解题报告

· · 个人记录

赛后大体总结：

Day2 的预估分可能要比 Day1 高一些吧，毕竟 Day1 考的真的很烂（T3 为啥 CE 我都不知道，文件读写我加了啊）

结果 Day2 比 Day1 考的还烂！

为啥 T1 暴了我也不知道。。。

还是觉得自己的思维深度不够，也可能是算法的不熟悉和不熟练导致的吧

下次比赛再加油吧

解题报告：

T1 点指兵兵

题意

问有多少个 m ，能使得 m 个物品围成一圈，从第一个物品开始数，数 n 下，最终的物品不是初始物品也不与初始物品相邻

数据范围

对于所有测试点，3 \leq n \leq 2 \times 10^9,1 \leq T \leq 5 。

思路：

法一： 30\ pts

枚举 m ，然后模拟数物品的过程

时间复杂度 O(n^2)

法二： 80\ pts

观察发现，最终的物品编号为 (n-1) \mod \ m+1

因此枚举 m 就可以 O(1) 判断

特殊限制： n 与 n-2 都是质数

如果用模式来表达这题，就会变成：

求有多少个 m ，使得：

(n-1) \mod\ m \notin\left\{0,1,-1\right\} \because\ a \mod\ b = c\quad \Rightarrow \quad b|(a-c)

所以 m 不能是 n,n-1,n-2 的因子

由于 n,n-2 ，都是质数，所以只需要对 n-1 进行因数分解，从 3 到 n 中去掉这些因数，那么其他都是合法的 m

法三： 100\ pts

要求 m 不能是 n,n-1,n-2 的因数，所以我们要去掉这三个数在 3 到 n 范围内的因数

而我们对这三个数进行因数分解时，是不会有某个数 d 重复的

因为 3 \leq d ，它的倍数间隔至少为 3 ，所以不会在 n,n-1,n-2 中重复出现

所以只需要对 n,n-1,n-2 这三个数进行因数分解就好啦

T2 网页浏览

题意

给定网页形成的树，从父节点到子节点可以替换打开或新标签页打开，退出的时候可以返回标签页或关闭标签页。根节点只能点击打开。问最少要多少次操作能浏览完整棵树上的节点

数据范围

对于所有测试点，1 \leq n \leq 10^5 。

思路

法一： 30\ pts

暴力枚举浏览顺序以及每个网页的打开和关闭的操作

枚举量不超过 4^n \times n! \leq 9 \times 10^7

测试点 4 ：

总次数为 $n+1

测试点 5 ：

总次数为 $1+2 \times (n-2) + 2 = 2n-1

法三：（子节点不超过 5 个）

可以通过枚举子节点 + 树形 DP 的思想获得这一部分分

法四： 100\ pts

每个网页都一定要有“打开”和“关闭”两个步骤，而关闭网页或许可以同时执行多个网页的退出步骤

先考虑一下返回上一个标签页的意义，设现在要从 A 替换打开 B ，然后再从 B 回到 A 后删除，那和新建 B 然后返回 A ，再关闭 B 实际上没有什么区别

所以根据贪心的思想，在每一个非最后一个的叶子结点使用“替换打开”就可以使操作数量减少

所以最后的操作次数应该是： \quad n+ 叶子结点个数

T3 教室的电子钟

题意

电子钟共有年月日时分秒共 98 个灯管，求起始时间到终止时间共有多少次明暗变化

数据范围：

对于所有测试点:

0 \leq X_1,X_2 \leq 9998;1 \leq Y_1, Y_2 \leq 12;1 \leq Z_1,Z_2 \leq 31;0 \leq A_1,A_2 \leq 23;0 \leq B_1,B_2 \leq 59;0 \leq C_1,C_2 \leq 59

保证起始时间不晚于结束时间。

思路：

对于部分分：

  1. 一秒一秒跳，只处理秒 （ 10\ pts ）

  2. 加上分的处理（ 20\ pts ）

  3. 加上时的处理（ 30\ pts ）

  4. 加上日的处理（ 40\ pts ）

  5. 加上月和年的处理 （ 50\ pts ）

法一：

一秒一秒跳到第一个完整日的开始，一日一日跳到最后一个完整日的结束，最后一秒一秒跳到结束时间

法二：

起始时间和终止时间都往某一个方向跳到一个完整年的开始，然后一年一年地跳到终止时间

法三：

可以使用前缀和思想：

设 000000 为一开始的时间，a[i] 为从 000000 跳到 i 的明暗变化次数，那么从 l 到 r 所经历的明暗次数变化应该就是 a[r]-a[l]

法四：

对平年和闰年的每一秒算出前缀和，然后输入的两个时间直接转化成秒相减， 240MB 的空间，查询能做到 O(1)

T4 机器人

题意

给定一个由障碍物，空地和机器人（有且仅有一个）组成的地图和命令序列，机器人可以选择命令序列中的任意一个子序列执行，问机器人能否走出地图

数据范围

令 |S| 表示指令序列长度

对于所有测试点，1 \leq T \leq 10 ，1 \leq |S| \leq 10^5 ，1 \leq n,m \leq 500 。

思路

法一： 20\ pts

枚举每一个子序列，判断机器人会不会走出地图

时间复杂度 O(2^{|S|})

法二： 30\ pts

设 $dp[x][y][k]$ 表示已经走到了 $(x,y)$ 的位置指令序列已经到了第 $k$ 位 转移即是枚举下一个指令 时间复杂度 $O(nm|S|^2)

法三： 50\ pts

设 dp[x][y][k] 表示已经走到了 (x,y) 的位置指令序列已经到了第 k 位，是否可能出界

转移只考虑下一条指令 k+1 执不执行

时间复杂度 O(nm|S|)

法四： 70\ pts

上一档部分分的 DP 其实 k 没有必要

其实我们希望用到的指令越少越好，可以给后面的步骤制造出更大的出界机会

所以这样就变成了一个最短路问题：从指定起点出发，求到达每个位置所需要的最少指令数

预处理对于指令序列的每一个位置，它的下一个位置（上下左右）在哪

用 dij 求最短路即可

时间复杂度 O((nm)^2+|S|)

最后的正解还没推出来

如果有知道的同学可以评论提出来，我会及时更正