2022/7/15模拟赛记
ych 出的模拟赛 /bx /bx /bx
原题场 /fn /fn /fn
赛时
T1 string
发现是 NOIP 原题，然而忘记自己做过了。
想了一会发现自己做过，但是 ych 这个【】居然卡常，1e6->3e6 /oh
然而自己之前写的是 BIT，吸氧后 900+ms，感觉有点危险，写了个 $O(n\ln n+n\cdot 26)$ 的，感觉也许能过。
ych 啊 ych，既然已经加强数据范围了就不要出毒瘤数据了吧。
预估 100pts
T2 work
上午刚做过 P4158 粉刷匠，就只想着背包了。
然后就写了个背包，复杂度 $O(na^2nb^2n)$，感觉很危险，有可能能过。
预估 80pts
T3 sort
一开始瞎推推出来个 _逆序对数+递归层数_，然而这玩意居然是能过样例的。
写了个暴力对拍下，发现错了，然后白兰去看 T4 了。
最后 30min 随便想了一个结论：每个点到最后面的比它小的点的距离之和，发现能过样例，和暴力拍拍也对的 /xia
最后造了个 2000 个 1e9 的数据，发现输出 0，于是写了个特判原数组已经有序就输出 $n$。
用 BIT 实现的，复杂度 $O(n \log n)$，1e5 的数据应该轻松。
预估 100pts
T4 magic
想到 mod 不能约分，直接放弃。
预估 0pts
总分预估 100+80+100+0=280pts
赛后
T1 被卡 T 成 80pts，T2,3,4 发挥稳定
总分 80+80+100+0=260pts
发现 T2 正解实际上要二分，有单谷性质 /px
蓝 /bx
T3 居然结论猜对了
T4 矩阵乘法，维护前缀后缀积，然而 ych 卡带 log 的线段树做法 /baojin
ych 没开 O2，重测
/fn /fn /fn
吸氧后 T1 过了。
O2 /qiang
总分 100+80+100+0=280pts
以下为第二天
gzy T3 被卡后发现我的也挂了
successful hack!
gzy /bx
总分 100+80+90+0=270pts
T1 被 sanwei 卡成 96 分。
反正本来也过不了的。
总分 96+80+90+0=266pts
sanwei /bx
Links
贴下原题链接吧
- T1 string NOIP2020 字符串匹配
- T2 work WC2001 高性能计算机
- T3 sort USACO18OPEN Out of Sorts P
- T4 magic 「LibreOJ NOI Round #2」单枪匹马
打的太差就不贴代码了
另附 ych 写的题解，如果像我一样觉得出题人很可爱的可以不看
# 题解
A.string
题意
给定字符串 $S$，求把 $S$ 拆分为 $ABAB…ABC$ 这样的形式的方案数。
做法
考虑枚举 $AB$ 的长度，用 $Z$ 函数求出最多连续 $AB$ 作为前缀的数量。
考虑 $C$ 中出现奇数次的字母的个数，发现对于 $AB$ 长度固定时只有两种取值，和选的 $AB$ 个数有关。
其中一种取值是固定的，另一种在枚举长度时可以递推求得。
然后在 $AB$ 中选择一个 $A$ 就是选择一个前缀，这个前缀出现奇数次字母的个数比 $C$ 出现奇数次字母的个数少。
这个用 bit 维护就可以了，这样是 nlog26。
进一步分析发现，$C$ 另一种取值每次变化量最多为 1，因此就不需要bit，只需要根据他这一次的变化计算贡献。把前面的结果加以利用。
B.work
每个人有四个参数，求解决na个A和nb个B的最小时间。
做法
对第 $i$ 个人，考虑预处理 $cost(x,y)$ 表示解决 $x$ 个 $A$ 和 $y$ 个 $B$ 的最小代价。
这一部分是 $O(nm^3)$ 的。
然后如果是 $dp(i,x,y)$ 表示前 $i$ 个人解决 $x$ 个 $A$ 和 $y$ 个 $B$，转移枚举 $i$ 选几个 $A$ 几个 $B$，是 $O(nm^4)$。可以获得80分。
考虑优化。
由于答案是所有人的 max，可以考虑二分。
$dp(i,j)$ 表示 $i$ 个人在限制内解决 $j$ 个 $A$ 最多选的 $B$ 的个数。
然后这样发现是不对的。
因为 $cost(x,y)$ 并不是单调的。但是单谷的。
考虑证明。在 $x$ 固定的时候 $y$ 增加使得答案更小，说明把 $B$ 插入 $A$，且为独立的一段。
然后 $B$ 能有效插入的次数显然是有限的。不能插了以后都不能插。
所以 $dp(i,j)$ 应该存一个区间。
判 $nb$ 是否在区间内。
C.sort
题意
自己看吧。
做法
观察到这个 $cnt$ 每次增加的时候会增加一个 $length(A)$。
数形结合，对长度为length(A)的序列 bubble_sort，统计答案，实际上相当于把这个贡献均摊到每个点上。
于是考虑对每个点分别计算贡献。
这个点会连续被排序直到前后两个位置都成为分界线。
于是计算每个位置成为分界线的时间。
冒泡排序是稳定排序，所以Ai相不相同并不重要，可以全部当成不同的做，用双关键字。
然后要把所有 <x 的放到前面去。
考虑冒泡排序的本质，就是分为若干段，每一段进行一个循环左移。
这个线一定会被包含在某一段中，然后一段结束的位置由于已经是分界线，不存在应该往前的，所以发现所有应该往前放的都会往前一位。而且这一段的开头一定不会是应该放在前面的。若是应该放在前面的，则一整段都是，又根据分界线，前面也都是，个数就不对了。
每个点最开始一定会被排一下，所以要和1取个max。
D.magic
题意
自己看。
做法
先考虑暴力，$a+\frac x y=\frac {ay+x} {y}$，然后结合的时候可能还要倒过来。
$x$ 和 $y$ 互质，所以那个 $ay+x$ 和 $y$ 也互质。
所以就不用考虑约分，直接模意义下也可以做。
然后你发现把分子分母上矩阵，就可以做了。
我把线段树维护卡了，直接前缀和，处理矩阵的逆元。
THE END
2022/7/15模拟赛记