日常打 cf 状态低迷QAQ连题目都读不清楚了啊
Codeforces Round #539 (Div. 2)
比赛链接: https://codeforces.com/contest/1113
A
题意是有一条 $1$->$2$->…->$n$ 的道路，Sasha 需要开车从 $1$ 到达 $n$，初始燃料为 $0$，每移动一步需要耗费 $1$ 燃料，在每一个城市都可以补充燃料，在第 $i$ 座城市补充 $1$ 燃料的费用是 $i$，车子的燃料上限为 $v$，问最小需要多少钱购买燃料. $(2 \le n \le 100, 1 \le v \le 100)$
容易想到在越前面的城市买燃料越划算，所以在每个位置计算出到达终点还需要的燃料数和距离燃料上限的燃料数，取个最小值，这个就是在该城市所应该买的燃料数量.
AC代码: A.cpp
B
题意给出一个数组，可以从中选出两个数 $a_i$ 和 $a_j$，使其变化为 $\frac{a_i}{x}$ 和 $a_j·x$，需保证 $x$ 是 $a_i$ 的因子，目标是使得数组和最小. $(2 \le n \le 5·10^4,1 \le a_i \le 100)$
比赛的时候 sb 了T^T没看到这样的操作至多做一次…如果只做一次的话就很简单了.
可以想到如果要将除掉的 $x$ 乘给某个数 $a_j$，那么这个数自然是数组的最小值，不妨记为 $Min$.
可以枚举因子 $1$ 到 $100$，从数组中选出最大的能整除当前枚举因子的数 $a_i$，此时最优解为 $\sum_{j=1}^{n}a_{j}+\frac{a_i}{x}+Min·x-Min-a_i$.
AC代码: B.cpp
C
题目给出一个数组，问有多少个偶数长度的区间满足左半区间的异或值等于右半区间的异或值. $(2 \le n \le 3·10^5)$
若用 $pre[i]$ 记录 $a_1$ $\bigoplus$ $a_2$ $\bigoplus$ … $\bigoplus$ $a_i$， $a_l$ $\bigoplus$ $a_{l+1}$ $\bigoplus$ … $\bigoplus$ $a_{mid}$ = $a_{mid+1}$ $\bigoplus$ $a_{mid+2}$ $\bigoplus$ … $\bigoplus$ $a_{r}$可表示为 $pre[mid]$ $\bigoplus$ $pre[mid-x]$ = $pre[mid+x]$ $\bigoplus$ $pre[mid]$，$x$ 为区间长度的一半，即 $pre[mid-x]$ = $pre[mid+x]$.
因此只需要从 $pre$ 数组中挑选出值相同且间隔为偶数的下标，其任意两个下标组合所表示的区间均符合题意.
AC代码: C.cpp
D
题目给出一个回文串，可以分割成几段重新组合，问最少需要分割几次能组合出一个与原串不同的回文串. $(1 \le s \le 5000)$
首先考虑 $aaaa$ 这种字符完全相同的回文串，显然不可能构造出新的回文串.
然后对于回文串的长度奇偶进行分类讨论:
奇数回文串: 可以考虑成 $abcba$ 这种类型，显然可以保留中间元素，交换两边字符串组成 $bacab$ 即可，需要分割两次. 然后需要特殊考虑 $aabaa$ 这种类型，按上述方法构建出的回文串仍与原串相同，这种情况也无法构造出新的回文串.
偶数回文串: 对于 $aabbccbbaa$ 这样的回文串，可以考虑以开头字符 $a$ 所延伸的最长前缀 $aa$，划分出 $aab$/$bccb$/$baa$，需要分割两次，交换首尾两截，得到 $baabccbaab$. 可以想到，对于任何除完全相同以外的所有偶数回文串，都可以使用以上的构造方法，即最多两次就能构造出新的回文串. 然而对于 $abba$ 这样的情况，我们只需要分割一次就可以构造成功. 考虑 $abbaabba$ 这个例子，我们发现从中间分割得到左右的字符串完全相同，因而无法直接构造成功. 递归地继续分析左子字符串 $abba$，发现其左右字符串并不相同，因而我们可以从中间分割得到一个新的回文串 $baabba$/$ab$. 只要我们在递归的过程中发现 $abba$ 这样左右不同的情况，都可以通过一次分割完成构造. 因为出现 $abba$ 说明此前的字符串形式均为 $abba$/$abba$ 这样类型的情况，将其移至分半移至末尾就能构造出新的回文串了.
AC代码: D.cpp
E
To be continued…
F
题意是问有多少颗 $n$ 个结点的树满足条件: 边值的范围是 $1$ ~ $m$，其中结点 $a$ 和结点 $b$ 的路径距离为 $m$.
考虑枚举结点 $a$ 和结点 $b$ 中存在的边数 $i$，那么 $a$ 和 $b$ 的路径上一定存在 $i-1$ 个结点，共有 $A(n-2,i-1)$ 种可能. 路径距离需要为 $m$，通过隔板法可以得到有 $C(m-1,i-1)$ 种情况. 对于剩余的 $n-1-i$ 条边，可以任意赋予 $1$ ~ $m$ 中的任何一个值，有 $m^{n-1-i}$ 种情况. 对于不在 $a$ 和 $b$ 路径上的点，我们可以利用 Cayley’s formula，得到 $n$ 个有标号点组成的森林，分别属于 $i+1$ 颗树，树的根分别为 $a$ ~ $b$ 上的 $i+1$ 个点，根据公式可知方案数为 $(i+1)·n^{n-i-2}$ (需要注意 $n-i-2$ 可能等于 $-1$，此时 $n^{-1}$ 即为 $n$ 的逆元).
总的方案数即为: $\sum_{i=1}^{n-1}A(n-2,i-1)·C(m-1,i-1)·m^{n-1-i}·(i+1)·n^{n-i-2}$
AC代码: F.cpp