2019 Multi-University Training Contest 8

2024-08-30 09:52:22

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 定理的推论。

最新文章

热门文章