2024天梯赛校内选拔赛-民间题解
Silencer76 2024-03-16
比赛地址：2024天梯赛校内选拔赛 。
------------------------------------
直接输出即可。
------------------------------------
在头文件 <cmath> 里面有一个函数 hypot ，给定两个直角边长，返回斜边长。
------------------------------------
把九宫格视为一个一维数组，然后使用 min_element 函数得到最小值所在的地址，减去数组首地址就是下标。
最后输出下标对应的字符串。
------------------------------------
分类讨论，先判断是不是三角形，然后判断是不是等腰三角形，最后判断是不是等边三角形。
------------------------------------
开一个同等长度的 int 数组，遍历该字符串。
第一位默认是 1 。
如果前一位的字符和当前位置的字符相同，那么当前位置继承前一位的数字，并 +1 ，前一位清零。
如果不同，当前位置设为 1 。
最后再次遍历该数组，如果某个位置的数字不为 0 ，则输出位置对应的字符，以及数字。
------------------------------------
由题意有 r-l+1<n ，则可以贪心的选择 r-l+1 = n-1 。
所以排序的区间是 [1,n-1] 或者 [2,n] 。
那么，只要保证 a[n] 是数组中的最大值，或者 a[1] 是数组中的最小值，即可输出 YES。
否则，输出 NO 。
------------------------------------
首先通过埃氏筛选法，把 [0,99999] 中的素数筛出来。
然后进行 bfs ，过程较为繁琐。
------------------------------------
使用两个 map ，一个正着枚举，一个反着枚举，对次数进行预处理。
枚举的时候，使用一个变量来维护次数的最大值，然后填入数组里。
相当于维护了一个前缀最大数组和一个后缀最大数组。
最后 o(n) 遍历，只要相邻两个元素值都小于等于 k 即可输出 YES 。
否则，输出 NO 。
------------------------------------
个人认为这是本场最难的题目。
将 小时 统一转化为等价的 分钟，将会使代码构建更加方便。
首先，对所有的限制时间段进行排序，然后 o(n) 预处理。
预处理中，我们需要把能合并的区间进行合并。
当且仅当 区间的左边界 小于等于 上一个区间的右边界+1 时，可以合并。
注意到合并后，右边界可能发生变化（区间相交），也可能不发生变化（区间包含）。
预处理结束后，将所有合并后的区间存进 map 中。
map 的每个 key 代表左边界，value 代表右边界。
对于每次查询，我们在 map 上找严格大于此时间点的左边界（upper_bound）。
如果这个左边界是 map 的第一个元素，说明巨魔在敌人开展任意限制之前就已偷塔成功。
否则，对这个迭代器-1，即找到上一个限制的区间。
如果查询的时间点比区间的右边界大，说明时间点在两段限制区间的缝隙里面，可以偷塔。
否则，巨魔无法完成任务。
------------------------------------
为了方便输出，使用两个 vector 来模拟 栈 。
首先 o(n) 遍历，找到光标位置，光标左边的字符存进第一个 vector 里面，右边的存进另一个里面。
预处理结束后，将存储右边字符的 vector 进行倒置，保证两个 vector 的尾部都是光标相邻的位置。
然后进行操作，< 就是把左边 vector 尾部字符扔掉右边，> 同理。
DELETE 和 BACKSPACE 除了删除字符，还需要判断对应的另一个 vector 是否有匹配字符。
如果有，就同步删除。
以上操作都需要判断 vector 里面是否有字符可以操作，非法访问会造成 runtime error 。
最后输出之前，把存储右边字符的 vector 倒回来。
------------------------------------
先 o(n) 预处理每个数字跟相邻的关系，然后进行模拟。
如果两边都能走，那么贪心地选择最小的那个值，这样能拉低平均值。
否则，选择能走的那边。
考虑到单调性，每个数字仅可能被访问 3 次。
所以模拟的时间复杂度仍是 o(n) 。
------------------------------------
开两个数组 a 和 b ，表示点的状态。
数组 a 标记点的最终走向，默认值为 0 ，死胡同为 1 ，环为 2 。
数组 b 标记点的访问情况，默认值为 false ，访问过为 true 。
对每个点进行 dfs ，如果被访问过，直接返回最终走向。
否则，递归访问子节点，直到没有子节点，或者访问到曾经访问过的节点。
如果某节点出度为 0 ，返回 1 。
如果子节点中有环，返回 2 。
如果上述都不满足，返回 1 。
那么，如何判环呢？
假设对于某节点 now 而言，其中的一个子节点是 x ，那么成环的必然条件是：
1. b[x]=true
2. a[x]!=1
a[x]=0 时，代表本轮 dfs 中， x 从另一条路径走到了 now ，并且即将走回 x 。
a[x]=2 时，代表 x 在前面几轮 dfs 已经走向了环。
如果节点 now 的其中一个子节点 x ，有 a[x]=2 ，则子节点会感染父节点 a[now]=2 。
每次递归将 a[now] 返回，如有感染，也会感染回去。
最终判断有多少个 a[now]=1 ，输出数量。
Akanecco 2024-03-16
佬
易向晚来适 2024-03-17
佬