Preface
???\(11\) 个 \(330\)pts 是什么实力,\(11\) 个 rk1 是什么实力,没一个人会 T4 是什么实力???
???我 T4 想了一个世纪的图论,建图想到了,BFS 想到了,存储想到了,计算答案的方式也想到了,然后脑子短路了没记起来 BFS 可以多源?????
这对吗。
这很对,你这么菜你还想奢望啥。
T1
| 估分 | 得分 | 挂分 |
|---|---|---|
| \(100\) | \(100\) | \(0\) |
哎哎大家都是怎么看懂题的,你们怎么都精通化学。。。我实在看不懂啊,我总不能挂在 T1 阅读理解上吧。。。
简单题,但是模拟,我们只需要把字符串读进来然后根据 -> 拆成左右两边,再两边分别根据 + 拆成各个小部分,桶记录每个元素个数然后判是否相等即可。
T2
| 估分 | 得分 | 挂分 |
|---|---|---|
| \(100\) | \(100\) | \(0\) |
spj 题真的不好测大样例啊。
考虑贪心,为了空出尽可能多的杯子,我们就把酒尽可能倒到容量大的杯子里,于是排个序做就完了。
T3
| 估分 | 得分 | 挂分 |
|---|---|---|
| \(100\) | \(100\) | \(0\) |
答案最大是 \(n+2+\sum b\),在此基础上考虑所有横线穿插(不包括最底下,但包括最顶上)的“合并”,用容斥解决问题。
考虑第 \(i\) 个柱子和第 \(i+1\) 个柱子之间有多少条横线可以一笔画,显然只要求出满足 \(x \frac{a_i}{b_i} = y \frac{a_{i+1}}{b_{i+1}}\) 的最小正整数解 \((x,y)\) 就可以得到之间能一笔画的横线数量 \(\min(\lfloor \frac{b_i}{x} \rfloor , \lfloor \frac{b_{i+1}}{y} \rfloor)\) 了。
于是问题就变成了求这个 \((x,y)\)!分数不好搞,把这个式子变个形 \(x a_i b_{i+1} = y a_{i+1} b_i\)。两边分别除掉 \(g = \gcd (a_i b_{i+1} , a_{i+1} b_i)\),这样两边除了 \(x\) 或 \(y\) 的部分就互质了,显然 \((x,y) = (\frac{a_{i+1} b_i}{g},\frac{a_i b_{i+1}}{g})\) 是最小的一组解。
然后就做完了……记得开 long long。
T4
| 估分 | 得分 | 挂分 |
|---|---|---|
| \(30\) | \(30\) | \(0\) |
\(30\) 分是送你的,模拟一下就完了,但是谁会 \(60\) 分解啊。。。和正解有什么区别!
建图,\(0 \sim 2^{m}-1\) 这些数都是图上的点。一条边的边权为 \(1\),且只会连接哈明距离为 \(1\) 的两个节点。
考虑从每个点 \(a_i\) 出发做 BFS,这样到每个点的最短路 \(dis\) 就可以快速得到了。但是我们答案要的是最大呀,怎么办?反过来不就是了,对于每个 \(a_i\) 存在且仅存在一个 \(a'_i\) 使得 \(a_i \oplus a'_i = 2^m -1\),显然 \(m - dis_{a'_i}\) 就是 \(a_i\) 所要的最大哈明距离的答案!
就做完了。
Summary
很可惜,T4 就差一点点了……但是没关系,就算累积一个经验吧。
继续加油。
