I thought I were no more than a bystander Till I felt a touch so real
2021.10.13模拟赛
傻逼了
A. 单词表
谢谢出题人的大样例,不然我可能就把错的二分交上去了
然后焦虑了一会没啥好想法只能暴力枚举,然后测了下跑得飞快
突然想到复杂度其实就是调和级数 的…
然而还是被卡常了
B. 序列与改写
考虑这个约束条件是 ,发现这个改写的关系能变成一个 DAG
那我们 EGF 合并标号即可,因为 暴力卷积合并就行
复杂度上考虑这个限制其实很强,打表发现最大的改写深度不超过 ,所以卷积的时候枚举四项即可,复杂度
C. 拉丁方阵
先通过奥妙重重的找规律发现每个点操作次数就是 每一位的数的绝对值,正数 负数 即可
因为出题人给了大样例,所以大样例必然是std跑的,只是random_shuffle了一下,所以sort一遍就能找到规律
证明就是 记 ,则
考虑每行每列都是排列,所以 和 都是 所以就是这样
D.寻路游戏
障碍点很少,考虑能影响到最短路的点除了同一行列就是构成单调升/降内的一段
排序统计即可,感觉细节挺多的…