Monthly Archives

25 Articles

信息学奥林匹克竞赛

P5330:[SNOI2019]数论 – 题解

Posted by kal0rona on

主要思路

复盘一年前做过的题,现在感觉确实简单。

考虑表示成 \(d’ \in A, d = d’ + xP\),然后算有多少个 \(x\) 满足 \(d\) 在 \(B\) 中。暴力直接枚举。考虑优化暴力,我们发现这个肯定是有个循环节的,长度为 \(\text{lcm}(P, Q)\),这个可以做一个轻微的优化。

我们考虑把这个模 \(Q\) 想成一个环形带,然后把起始位置为 \(start_pos\) 的 \(d \in B\) 在这个纸带上进行标记、做前缀和,为了方便判断前缀和的加减顺序,我们还要标记排名。

计算的时候,对于 \(A_i\),我们需要知道这个元素 \(T\) 经历了多少次(\(cnt\))循环,然后完整循环的总和算进去。算完这个之后,我们来算开头和结尾。开头位置肯定就是 \(A_i \bmod Q\),结尾则是 \((A_i + cnt * P \bmod loop) \bmod Q\)。然后前缀和搞下即可。

信息学奥林匹克竞赛

BZOJ3162:独钓寒江雪 – 题解

Posted by kal0rona on

主要思路

刚看这题我人都是懵的…仔细看了看能大概想到,定一个根然后做 DP 得到方案,然后对于相同形态的子树进行方案分配即可。(但是不会写)

具体而言,转换成有根树的方法就是用重心来做根(如果有两个重心的话,就加一个虚根),并且每次 DFS 完之后用 Hash 值排序,然后进行分组转移。

转移的时候,可以给每一种情况进行标号,然后用前缀的组合意义来做转移即可。具体:\( dp[i] = \sum_{uniqueType \in subtree} {dp[uniqueType] + |subtree| – 1 \choose |subtree|} \)。

如果加了虚点,那就判一下就好了。