ZR2020 提高十联测 day1
这场早上 vp 了一下，发现 AB 都是 sb 题。。。但是因为 A 一开始算错了复杂度搞了一个吊打 std的复杂度花了将近 2h。。考试的时候还很自闭为什么自己提高组 T1 不会做。。导致 C 没有思考时间了。期望得分 $220$，实际得分 $200$ （因为咕了 T3 的暴力没写）A首先看一下这个式子：$3k^2-3k+1$，常数项看起来就很不舒服，加上 Hint 里面的答案 $\leq...
这场早上 vp 了一下，发现 AB 都是 sb 题。。。但是因为 A 一开始算错了复杂度搞了一个吊打 std的复杂度花了将近 2h。。考试的时候还很自闭为什么自己提高组 T1 不会做。。导致 C 没有思考时间了。期望得分 $220$，实际得分 $200$ （因为咕了 T3 的暴力没写）A首先看一下这个式子：$3k^2-3k+1$，常数项看起来就很不舒服，加上 Hint 里面的答案 $\leq...
A因为 $\gcd$ 是指数取 min，$\text{lcm}$ 是指数取 max，所以我们对于每一个质数分开考虑。设第 $i$ 个数唯一分解后在这个质数上的指数是 $e_i$，设次小值是 $cmx$，答案贡献 $p^{cmx}$。具体实现的时候质因数分解一下即可。B首先序列里一定要有 $k$ 这个值。如果 $k$ 两边有一个 $\geq k$ 的数，就可以把这两个数都变成 $k$，然后每次...
题意给你一个 $|V| = n,|E|=m$, 无自环无重边的无向连通图，要求你从以下两种任务中选择一种完成：找到一个 $=\lceil \sqrt{n} \rceil$ 的独立集找到一个长度 $\geq \sqrt{n}$ 的简单环$5 \leq n \leq 10^5,m \leq 2 \times 10^5$。题解发现自己好多基本事实都掌握的不好。。结论 1：一定存在一个最长的简单环满...
A从小到大填就好了。暴力求一下周围点的 mex。由于每个边只会被访问一次，复杂度 $O(m \log m)$。B维护两个集合 $L,R$ ，我们保证 $L \geq R$。首先从大到小排序，每次遇到一个新的数，如果 $L=R$ 就加到 $L$ 集合中，否则先加到 $R$ 集合中，然后不断从后向前合并 $R$ 集合，然后判断 $L,R$ 最后一位是否相等，再不断消去末尾相等的位置即可。（因为...
A按照题意模拟，每次让小的加上大的就行了，进行 $O(\log n)$ 次一定能求出来一组解。观察迭代方式我们发现操作 $i$ 次后的数对可以表示成 $(f_{i-2}a+f_{i-1}b,f_{i-1}a+f_{i}b)$（其中 $f$ 是斐波那契数列且 $f_0=1$）。B显然一种很好的方式是把匹配同一位置的字符匹配在一起，方案数就是每个位置匹配的字符的个数的乘积。根据一些基本的不等式理...