Contest Info

date: 2018.10.07 12:40-17:40

practice link

Solutions

B. Fraction

签到题。

C. Rotate String

题目大意：给你一个字符串 \(s\)，求长度和 \(s\) 相同，字典序小于等于 \(s\) 的最小表示的数量。

题解：首先我们可以把问题转换为：求所有循环不同构的最小表示小于等于 \(s\) 的串的数量。然后用 \(burnside\) 引理即可转换为最小表示小于等于 \(s\) 的串的数量。

显然我们可以把 \(s\) 替换为小于等于它的最大的最小表示。我们从右往左，尝试将每个大于 \(s_{0}\) 的字符减小，再将它后面的所有字符设为 z，如果此时 \(s\) 是最小表示，那么停止。可以证明这样的贪心是正确的。

之后我们枚举目标串向左循环移动使得它小于 \(s\) 的最早的位置，以及它小于 \(s\) 的第一个字符。这样就不重不漏地枚举了所有符合要求的串。

那么目标串会有两种 pattern。第一种是 \(???s_{0}s_{1}s_{2}\cdots s_{m}r???\)，其中 \(r\) 表示小于 \(s_{m+1}\) 的某个字符。显然 \(r\) 后的字符可以任取，但是我们需要使更早的问号开头的字典序大于等于 \(s\)。

可以证明，这一条件等价于前面问号的任意后缀的字典序必须大于 \(s\)（不能等于）。我们用 \(dp\) 来求这个填法。设 \(dp[i][j]\) 表示长度为 \(i\) 的串，前面 \(j\) 个字符是 \(s_{0}\cdots s_{j-1}\)，满足条件的方案数。那么 \(dp[i][j]=dp[i][j+1]+dp[i-j-1][0]\times('z'-s_{j})\)。证明略。

另一种 pattern 是 \(s_{w+1}\cdots s_{m}r???s_{0}\cdots s_{w}\)。我们可以类似地证明，从 \(s_{w+1}\) 到问号的这段字符串的每一个后缀的字典序都要严格大于 \(s\)。不妨设 \(s_{m}\) 前最长的一段和 \(s\) 相等的长度为 \(k\)，即 \(s_{m-k+1}\cdots s_{m}=s_{0}\cdots s_{k-1}\)。分别讨论 \(r\) 填 \(s_{k}\) 或大于 \(s_{k}\) 即可。

最后再统计一下最小表示等于 \(s\) 的串，这个随便怎么处理都行。

时间复杂度 \(\mathcal{O}(\sigma_{2}(|S|))\)。

D. Triangle

签到题

E. The Fastest Runner Ms. Zhang

题目大意：

给出一个\(n\le10^5\)个点\(n\)条边，每条边边权为\(1\)的简单无向连通图，选两个点\(S\)和\(T\)，从\(S\)出发经过每个点至少一次并停在\(T\)，最小化路径长度，相同时最小化有序对\((S,T)\)的字典序。

题解：

先建出基环外向树，设环上有\(x\)个点，分\(S\)和\(T\)所在子树在环上的根，记为\(rt(S)\)和\(rt(T)\)，是否相同两种情况讨论：

• 相同，则\(S\)到\(T\)的链上边只会经过一次，其它树边经过\(2\)次，环上的边都经过一次，路径长度为\(2n-x-dis(S,T)\).
• 不同，则\(S\)和\(T\)分别到\(rt(S)\)和\(rt(T)\)的链上的边只会经过一次，其它树边经过\(2\)次，环上会从\(rt(S)\)走一圈到达离\(rt(T)\)较近的一个\(rt(S)\)的邻点，再走到\(rt(T)\)，路径长度为\(2n-dis(S,rt(S))-dis(T,rt(T))-x-dis(rt(S),rt(T))-2\).

树dp求出每棵子树最长链和到根最长链即可，环上的部分单调队列优化一下，时间复杂度\(O(n)\).

F. Harmonic Value Description

签到题。

I. Sequence II

题目大意：

给出一个数列\(a_1,\cdots,a_n\)，\(m\)次询问，每次给出一个区间\([l,r]\)，把区间中每种数最左边的位置下标取出从小到大排序得到一个新的数列\(p_1,\cdots,p_k\)，求\(p_{\lceil\frac{k}{2}\rceil}\)，强制在线。

题解：

对于数列\(a\)每个位置求\(pre_i\)为考虑前缀\(i-1\)，与\(a_i\)相同的数最右出现的位置（没有则为\(0\)），那么对于区间\([l,r]\)，数列\(p\)中的数满足\(pre_i<l\)且\(i\in[l,r]\)。

将\(pre_i\)作为第一维，\(i\)作为第二维，用主席树维护，则可以一次询问求出\(k\)，然后再在线段树上一次二分求出答案，时空复杂度\(O(n\log{n})\).

K. Binary Indexed Tree

题目大意：定义树状数组的实现方式如下：

void add (int x, int t){
    for (int i = x; i != 0; i -= i & (-i))
        a[i] += t;
}

修改区间 \([l,r]\) 时调用 add(r, 1) 及 add(l-1, -1)。定义区间 \([l,r]\) 的价值为修改它时真正改变了的位置，即修改 \(r\) 和修改 \(l-1\) 时抵消的位置不算。求所有 \([1,n]\) 的子区间的价值和。

题解：修改 \([l,r]\) 时，真正改变的位置即为 \(\text{bitcount}(r)+\text{bitcount}(l-1)-2\text{bitcount}(x)\)，其中 \(x\) 是 \(l-1\) 和 \(r\) 的最长公共前缀。

我们分两个部分计算该答案。显然减号前面的答案为 \(n\sum_{i=0}^{n}\text{bitcount}(i)\)。减号后面的答案只需要枚举 \(l\) 和 \(r\) 的最长公共前缀的长度，然后数位 \(dp\) 即可。

Dirt Replay

F: -1 写反了（没自己测试）

G: -1 写错了（自己没法测试）