Festival
考虑差分约束。设 $dis_{i,j}$ 表示 $X_i$ 至多比 $X_j$ 大多少，则
- 若 $X_i+1=X_j$，则 $dis_{i,j}=-1,dis_{j,i}=1$，连边 $(i,j,-1)$ 和 $(j,i,1)$。
- 若 $X_i\leq X_j$，则 $dis_{i,j}=0$，连边 $(i,j,0)$。
考虑无解的情况。一种情况是出现负环，另一种情况是出现一个全是 $1$ 边的正环，此时一定存在一个负环。所以只需要判负环即可。
然后每个连通块的答案显然就是最长路的长度加上 $1$。
然而 $600$ 的数据范围跑 Floyd 有些吃力，可以先缩点，在每个连通块内部跑 Floyd 即可。
Letters
显然是将 A 映射为排列后求逆序对，然而字符可能重复。
但是显然 A 中相同字符的顺序在移动前后不会改变，于是我们只要按顺序映射就好了。
Distance
设 $f(x)$ 为 $x$ 唯一分解后每个质因数的指数的和，不难发现 $dis(a,b)=f(a)+f(b)-2f(\gcd(a,b))$。
考虑对于每个 $a_i$ 枚举 $\gcd$，则我们需要 $\mathcal{O}(1)$ 找到满足 $d|a_j$ 的 $f(a_j)$ 最小的最小的 $j$，可以对每个 $d$ 预处理出这个东西。
然而这样子可能会有 $i=j$ 的情况，所以还需要记一个次小值。
Rendezvous
显然原图是基环外向森林，于是两个点会有三种情况：
- 不在一个连通块内，答案为
-1 -1。 - 在环上同一个点的子树内，此时两个点跳到 LCA 最优。
- 在同一个环上不同点的子树内，此时先跳到环上的点上，然后可以 $u$ 跳到 $v$ 或者 $v$ 跳到 $u$，两种情况比一下即可。
Well
先考虑没有 $\exists k$ 使得 $a_k=0$ 的情况怎么做。
显然可以二分答案，而二分后最优的调整方法显然是从前往后扫一遍，如果 $a_{i+1}-a_i>mid$ 就把 $a_{i+1}$ 改成 $a_i+mid$，再从后往前类似地扫一遍。
现在考虑 $\exists k$ 使得 $a_k=0$ 的情况。考虑枚举这个 $k$，则我们还需要把 $k$ 左边的一段区间变成一条斜率为 $-mid$ 的直线，把 $k$ 右边的一段区间变成一条斜率为 $mid$ 的直线。check 时先预处理每个 $k$ 影响到的范围然后枚举即可。
Tour de Byteotia
显然删有端点 $\leq k$ 的边更优。
于是我们先把所有两端点都 $>k$ 的边加进来，再考虑其它边，如果加入后不会成环就可以加入。用并查集维护即可。
可以证明这样子是最优的，然而我只会感性理解（
Vouchers
暴力就是直接模拟，显然过不去。
但是这个东西是倍数的形式，所以我们可以记录上一个 $a_i=c$ 时取到了哪里，然后从那个位置开始继续推。
注意到 $b_k\leq 10^6$，所以当位置到达 $10^6$ 之后时就没有必要继续往后推了。
于是这样子复杂度是调和级数的。
需要注意的是客人的编号需要开 long long 存储。
Cloakroom
考虑将所有询问离线并按左端点从小到大排序。则 $a_i\leq m$ 的限制我们可以通过将物品按左端点排序并依次加入来解决。
考虑 DP。设 $dp_i$ 表示物品权值之和为 $i$ 时右端点最远能到哪。这样子对于每个询问我们只需要查询 $dp_k$ 是否大于 $m+s$ 即可。
转移类似于 0/1 背包。
A Horrible Poem
首先有一个结论，即 $s[l,r]$ 有一个长度为 $t$ 的循环节当且仅当 $s[l,r-t]=s[l+t,r]$。
一个显然的想法是枚举 $r-l+1$ 的约数然后依次判断，可惜过不了。
于是换一种思路。可以发现如果 $s[l,r]$ 有一个长度为 $t$ 的循环节，则它也一定有长度为 $d$ 的循环节，其中 $d|t$。而 $s[l,r]$ 一定有一个长度为 $r-l+1$ 的循环节。因此可以枚举 $r-l+1$ 的所有质因数并依次尝试除掉，如果除掉后仍然是循环节就可以除掉。这样子就可以得到最小循环节。
判断字符串相等可以用哈希实现。可以线性筛预处理出每个数的最小质因数来做到 $\mathcal{O}(\log n)$ 质因数分解。
Fibonacci Representation
一个贪心是每次找到恰好比 $n$ 大、小的两个斐波那契数，然后选择差值较小的那一个作为其斐波那契表示中的数。
正确性需要证明两个结论，具体可以看这里。
Squarks
把所有 $a_i+a_j$ 从小到大排序，再假设 $a$ 是单增的，则最小的两个一定是 $a_1+a_2$ 和 $a_1+a_3$。
假如我们知道了 $a_2+a_3$，我们就能够解出 $a_1,a_2,a_3$，从而递推出后面的数。具体的，在推出 $a_i$ 后，把所有 $a_j+a_i(j<i)$ 去掉，然后最小的那个一定是 $a_1+a_{i+1}$，即可得到 $a_{i+1}$。
如果直接用 multiset 实现是 $\mathcal{O}(n^3\log n)$ 的，容易被卡常。实际上用 unordered_map 记录每个数的出现次数即可。
Bidding
考虑 DP。设 $dp_{x,y}$ 表示 $(x,y)$ 时的最优决策（$0$ 为必败态），转移看哪种操作会走到必败态即可。
然而复杂度爆炸。注意到 $x$ 只可能是 $2^i\times 3^j$ 的形式，所以可以设 $dp_{i,j,y}$ 表示 $(2^i\times 3^j,y)$ 时的最优决策，转移不变。
因为没有给一个 init()，所以需要记一个全局变量使得只在第一个 _opt(n,x,y) 时 DP 一次。
// ====================================
// author: M_sea
// website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;
int pw2[16],pw3[11],dp[16][11][30010],flag=0;
extern "C" int _opt(int n,int x,int y) {
if (!flag) {
pw2[0]=pw3[0]=1;
for (int i=1;i<=15;++i) pw2[i]=pw2[i-1]*2;
for (int i=1;i<=10;++i) pw3[i]=pw3[i-1]*3;
for (int k=n;~k;--k)
for (int i=15;~i;--i)
for (int j=10;~j;--j) {
if (pw2[i]*pw3[j]+k>=n) dp[i][j][k]=0;
else {
if (!dp[0][0][pw2[i]*pw3[j]+k]) dp[i][j][k]=1;
if (!dp[i+1][j][k]) dp[i][j][k]=2;
if (!dp[i][j+1][k]) dp[i][j][k]=3;
}
}
flag=1;
}
int c2=0,c3=0;
while (x&&x%2==0) x/=2,++c2;
while (x&&x%3==0) x/=3,++c3;
return dp[c2][c3][y];
}Salaries
先确定每个节点可能取到的值中的最大值。我们只要 DFS 一遍，每次把 $<$ 父节点权值的还没被已经确定的点和祖先节点填的最大的数填进去即可。
接着从小到大考虑所有最大值 $w$。如果最大值为 $w$ 的节点只有一个且最大值 $<w$ 的节点有 $w-1$ 个，则这个节点的权值一定为 $w$。
这样子就可以确定能确定的点的权值了。
Leveling Ground
考虑对原序列差分，则操作变为选两个数一个加 $a$ 一个减 $a$ 或一个加 $b$ 一个减 $b$。
先只考虑每一个位置，设差分后的数组为 $d_i$，该位置加 $a$ 的次数为 $x_i$，加 $b$ 的次数为 $y_i$，则应有 $ax_i+by_i=d_i$，可以通过 exgcd 解出一组解。而我们想要 $|x_i|+|y_i|$ 最小，而这个最小值只有四种情况（$x_i$ 是最小非负整数、$x_i$ 是最大非正整数、$y_i$ 是最小非负整数、$y_i$ 是最大非正整数），直接算一下即可。
然而每个位置最优时全局不一定合法（因为要 $\sum x_i=0$）。假设 $\sum x_i>0$，则我们每次可以把一个 $x_i$ 减去 $b/\gcd(a,b)$、把对应的 $y_i$ 加上 $a/\gcd(a,b)$，用一个堆维护即可。$\sum x_i<0$ 类似。
Minimalist Security
显然可以对于每个连通块单独计算最值后累加得到总的最值。下面只考虑一个连通块。
设某个点的减少量为 $x$，则连通块中其它所有点的减少量都可以表示成 $x+b_u$ 或者 $-x+b_u$ 的形式，又有减少量 $\in[0,p_u]$，从而可以解出 $x$ 的范围，然后就是简单的一次函数最值问题了。
需要注意的是环的处理。对于偶环，需要用剩下的一条边检验；对于奇环，可以直接解出 $x$ 来判断有无解。
Warehouse Store
贪心，如果当前存货够的话就卖掉，否则考虑将之前买东西最多的那个客人替换成当前这个。用堆维护一下即可。
Prefixuffix
思考一下可以发现，满足条件的前后缀大概是 ab......ba 的形式。于是可以考虑枚举 a 的长度，然后求出 b 的最长长度。
然而里面的东西并不好求。设 a 的长度为 $i$ 时 b 的最长长度为 $f_i$，可以发现 $f_i\geq f_{i-1}-2$，移项后得到 $f_{i-1}\leq f_i+2$。
于是可以从大到小计算所有 $f_i$，时间复杂度显然是 $\mathcal{O}(n)$ 的。这样子最后再枚举 $i$ 即可。
判断字符串相等可以使用哈希。然而直接自然溢出会 GG，最好写双哈希。
1 条评论
M_sea 板切 POI /se ::QQ:Y.qq27::