Asusetic
0%

2021.10.13模拟赛

发表于 分类于 Valine：
本文字数： 881 阅读时长 ≈ 1 分钟

I thought I were no more than a bystander Till I felt a touch so real

2021.10.13模拟赛

傻逼了

A. 单词表

单词表

谢谢出题人的大样例，不然我可能就把错的二分交上去了

然后焦虑了一会没啥好想法只能暴力枚举，然后测了下跑得飞快

突然想到复杂度其实就是调和级数 O(nlog⁡n)O(n\log n) 的…

然而还是被卡常了

B. 序列与改写

序列与改写

考虑这个约束条件是 d∣n∧dor⁡n=nd|n \land d \operatorname{or} n=n ,发现这个改写的关系能变成一个 DAG

那我们 EGF 合并标号即可，因为 n≤2000n \le 2000 暴力卷积合并就行

复杂度上考虑这个限制其实很强，打表发现最大的改写深度不超过 44 ，所以卷积的时候枚举四项即可，复杂度 O(16n2)O(16n^2)

C. 拉丁方阵

拉丁方阵

先通过奥妙重重的找规律发现每个点操作次数就是 A−BA-B 每一位的数的绝对值，正数 ++ 负数 −- 即可

因为出题人给了大样例，所以大样例必然是std跑的，只是random_shuffle了一下，所以sort一遍就能找到规律

证明就是 记C=A−BC=A-B ，则 Ai,j+Ci,j+∑x≠iCx,j+∑y≠jCi,y=Ai,j−Ci,j+∑Cx,j+∑Ci,yA_{i,j}+C_{i,j}+\sum\limits_{x\neq i}C_{x,j}+\sum\limits_{y\neq j}C_{i,y}=A_{i,j}-C_{i,j}+\sum C_{x,j}+\sum C_{i,y}

考虑每行每列都是排列，所以 ∑Cx,j\sum C_{x,j} 和 ∑Ci,y\sum C_{i,y} 都是 00 所以就是这样

D.寻路游戏

寻路游戏

障碍点很少，考虑能影响到最短路的点除了同一行列就是构成单调升/降内的一段

排序统计即可，感觉细节挺多的…