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提出在3x3的格子合并联通块的做法，但感觉不太好写，选择在原代码基础上加两个判断，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 定理的推论。