2019 Multi-University Training Contest 8
C. Acesrc and Good Numbers
题意 \(f(d,n)\) 表示 1 到 n 中，d 出现的次数。求小于等于 x 的最大的 \(n\) 满足 \(f(d,n)=n\)。
做法
- 令 \(g(d,n)=f(d,n)-f(n)\)，我们要求小于等于 \(x\) 极大的零点。
- 注意到 \(n>10^{12}\) 一定不存在零点。 [比赛时注意到了这点]
- Big-Small 战法。
- 取 B 等于 \(10^6\)，求 \(g(d,x)\)，可以将 \(x\) 写成 \(x=k*B + t\) 形式。\(t = x\%B\)
- 按 \(k\) 值对 \(x\) 进行分块。
- 如果 \(k\) 中有 d，那么 \(g(kB+t)\) 是关于 \(t\) 递增的。
- 否则，\(|g(kB)|\) 不能太大，否则解体。
E. Acesrc and String Theory
solved by sdcgvhgj 284min -2
题意 求循环重复k次的子串的数量
做法
- 枚举循环节大小len，那么合法串一定同时包含i和i+len两个位置
- 计算左端点在\([i-len+1,i]\)的串包含i和i+len两个位置的合法左端点有哪些
- 设i和i+len这两个前缀的最长公共后缀为k1,这两个后缀的最长公共前缀为k2
- 那么合法位置的区间为\([max(i-len+1,i-k1+1),min(i,i+k2-(k-1)*len)]\)
- k=1需要特判
- 算后缀数组的时候字符串结束要置0，RE了两发
I. Calabash and Landlord
solved by sdcgvhgj 123min -4
题意 求两个矩形将平面划分成了几个联通块
做法
- 枚举8个点两两中点check在哪些矩形中，算出不同包含关系的数量作为答案，WA
- 意识到只包含在一个矩形中的区域可以有两块，rdc提出在3×3的格子合并联通块的做法，但感觉不太好写，选择在原代码基础上加两个判断，WA
- 意识到应该枚举16个点的两两中点，或直接9个格子的中点，写错两发后AC
K. Roundgod and Milk Tea
solved by rdc, 63min -3
题意 \(n\) 个班级，第 \(i\) 个有 \(a_i\) 个人，\(b_i\) 杯奶茶，每个人只能喝别的班的奶茶，输出最多能喝多少杯奶茶。
做法
- 二分图最大匹配问题，Hall 定理。\(|M|=|U|-max_{S \subset U} (|S|-|N(S)|)\)
- 对 \(U\) 进行讨论，要么为空集，要么为全集。
复盘
- 一开始认为给每个人任意匹配一杯奶茶都是合法的。
- 然后 WA，然后开始贪心匹配奶茶多的班级。
- 很盲目。
- 再盲猜 Hall 定理，就过了。
- 比赛的时候想到的 Hall 定理是二分图存在完美匹配的充要条件，但还是不会证。
- 题解中的做法，是 Hall 定理的推论。
