5.28 模拟赛
A 科学怪人可以发现,只需要求出 $(\frac{n}{\gcd(n,b)},0) , (0,\frac{n}{\gcd(n,a)}),(a,b)$ 的所有线性组合即可。 直接 bfs ,由于最终只有 $O(n)$ 对,答案是 $O(n)$ 的。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676 ...
阅读更多
5.27 模拟赛
神仙场。 A Number原题链接 对每个数码分开考虑。对于一个数码来说,我们其实需要求的是一个最小的数 $i$ 使得 \sum_{j \le i} (d - S(j,d)) < 0最后对每个数码的答案取最小值即可。 我们考虑这个东西怎么求。这个东西本身不太具有二分性,但是我们考虑对 $1 \sim 10^i - 1$ 求出这个前缀中的最小的前缀和以及整个的前缀和即可。然后我们就可以从高位到低位填数,从 $0$ 到 $9$ 枚举这位的数码,然后看看如果填入这个数后低位的最小前缀和会不会导致整 ...
阅读更多
5.25 训练
三道 Petrozavodsk 和 Open Cup Different Summands Counng链接 反套路题。介绍一下 $O(m^3\log n)$ 的卡常做法和 $O(m^3)$ 的标算。 我们考虑对于一个数,算出它恰好没有出现过的方案数,然后用总方案减去这个就是出现过的方案数量。前面这个可以方便地容斥成钦定,而如果是钦定且这题是有序拆分就可以用插板来安排剩下的数。 \sum_{a=1}^n\left(\binom{n-1}{m-1} - \sum_{k = 0}^{\min(m ...
阅读更多
5.20 模拟赛
A 求出 $n$ 个数都是不到 $m$ 质数,且 Nim 游戏后手必胜的方案数。 $n \le 10^9,m\le 10^6$ 给定模数。 考虑到质数没啥好的性质,看起来也只能够去算这个异或卷积 $n$ 次方。 但是直接写完发现这东西巨慢无比。考虑怎么优化常数。 可以发现最后只需要求 $A[0]$ ,这个数在异或卷积式子可以看出为所有数的和,而 $\text{IFWT}$ 在异或卷积其实就是做一次 $\text{FWT}$ 然后每个数除以 $len$ 。因此我们最后没必要做一次 $\text{ ...
阅读更多
PKUSC 部分题解
D1T1 D2T1 非常签到,就不写了。 不会真的有人写 D1T3 吧,不会吧不会吧 D1T2首先考虑部分分,部分分就是直接求 $\max[l,l+c]$ 为初始值走 $[l+c,r+c]$ 的单调栈的长度。 我们考虑设数组 $b_i$ 表示在经历若干操作后, $A_i$ 的值变成了原序列中 $[i,b_i]$ 的最大值。 考虑 $b_i$ 的转移,不难发现就是一次区间平移然后往最后插入一个 $b_r$ 。 但是即使维护了 $bi$ 仍然不好方便地做这个东西。然后就有一个非常神仙的转化:设 $c ...
阅读更多
5.4 做题
T1 NEERC2016 Cactus Construction考虑一棵树怎么做。容易想到,我们保证递归完一棵子树得时候根为 $2$ ,其他内容为 $3$ ,然后当前点 $u$ 设 $1$ ,于是每次就连 $1 \to 2$ 然后把 $2$ 整成 $3$ ,再做下一棵子树即可。这样只需要三种颜色。 考虑仙人掌咋办。还是类似地,我们尝试做完一个环的时候把最上面设置成 $2$ ,这里为了方便,可以类似圆方树把一条边也看成长度为 $2$ 的环。然后考虑类似建立圆方树的过程。如果一个儿子 $v$ 自己为 ...
阅读更多
Burnside 引理 & Polya 杂题
终于做了一些比 入门篇 难一些的题。 A AUOJ1600 礼物其实是道板子+式子题。大概是 Burnside 引理的第一种题型(强行拼上去)。 我们考虑设 $f(a,b)$ 为 $a$ 个点形成环,从中选择 $b$ 个位置选中,且选中位置没有连续 $k$ 个的方案数量。 由于是循环同构,我们枚举置换再算环的个数,然后就可以得到和入门篇基本一样的式子,然后最后就是: \sum_{i | n,i | m} f(\frac n i ,\frac m i) \varphi(i)考虑怎么快速计算 $ ...
阅读更多
4.28 写题
B Parades这题有一个关键的性质:可以发现一定有一种全局最优解满足每个点都是局部最优解。具体来说,由于每个点向上只有一条边,所以即使你在这个点子树的时候放弃选择一条路径,也只能最多获得 $1$ 的贡献,还不如直接选择子树之内。(感觉这种性质在权值全 $1$ 的时候都可以尝试一下有没有) 于是我们设 $dp[u]$ 表示 $u$ 子树最多可以选多少个路径,再对每个子树维护出一个集合,这个集合中的点满足存在一个选择最多路径的方案,使得这个点没有被覆盖。 考虑转移,由于 $n \le 10^3$ ...
阅读更多
4.27 高斯消元 杂题
A (False) faces题解在 这里 。 B Pachinko我们考虑设出 $s{i,j}$ 表示经过 $s{i,j}$ 的期望次数。那么可以对每个格子列出一个方程。由于每个 T 位置不会往外走,也就是说走到这个点就结束了,所以期望次数可以直接看成一个概率,最后除以会结束的总概率即可。但是直接进行高斯消元是 $O(n^3m^3)$ 的,无法接受。 然后会发现这个矩阵非常有性质。由于这个矩阵是 $n \times m,10^4 \times 20$ 的,而一个位置的方程仅在 $[i-m,i+ ...
阅读更多
4.26 写题
A Yet Another LCP Problem考虑反过来看串,如果建立前缀树,会发现这个 LCP 长度的问题就可以看成对于所有一类集合的点都到根全部 +1 ,对所有二类集合点求和。但是由于一般来说前缀树显然是建不出来的只能建出 parent 树,而如果建出 parent 树后,相当于这个点父亲到根的所有串全部 +1 ,然后需要特殊处理当前点。因此树剖显得挺难受,于是考虑建立虚树后 dfs 两遍做即可。细节可以参考代码。 复杂度 $O(n\log n)$ 对每个点上串的长度需要排序,以及建虚树 ...
阅读更多