填完了。
T1 food
Description
有 $n$ 个食物，每个食物有 $a_i,b_i$ 两个参数。你的初始质量为 $1$，可以以任意顺序吃这些食物，吃掉一个食物之后，你的质量可以加 $b_i$，或者乘上 $a_i$，最大化质量。
Solution
首先肯定是先加后乘；
然后 $a=1$ 肯定加。
然后剩下的食物里，加只会进行一次，因为如果加多次，调整为只加最大的，剩下的乘是不劣的。
假设加上 $a=1$ 的质量为 $now$，那么把一个数从乘变成加会让全都乘的答案 $ans$ 变为 $ans\times\dfrac{b+now}{a\times now}$，扫一遍找到右边比例的最大值就好了。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
namespace solve
{
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
typedef long long ll;
ll now = 1;
struct node
{
int a, b;
inline double f() { return (b + now) / (long double)1. / ((long double)a * now); }
} a[maxn];
int vis[maxn];
int n;
void main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i].a;
for (int i = 1; i <= n; i++)
cin >> a[i].b;
for (int i = 1; i <= n; i++)
if (a[i].a == 1)
now += a[i].b, vis[i] = 1;
double d = 1;
int pos = -1;
for (int i = 1; i <= n; i++)
{
if (vis[i])
continue;
if (a[i].f() >= d)
pos = i, d = a[i].f();
}
if (pos == -1)
{
now %= mod;
for (int i = 1; i <= n; i++)
if (!vis[i])
now *= a[i].a, now %= mod;
cout << now << endl;
}
else
{
now += a[pos].b, now %= mod;
for (int i = 1; i <= n; i++)
if (!vis[i] && i != pos)
now *= a[i].a, now %= mod;
cout << now << endl;
}
}
}
int main()
{
ios::sync_with_stdio(false);
solve::main();
}
T2 problem
Description
给定长度为 $3 n$、值域为 $[0, 3]$ 的整数序列 $S = s_1 s_2 \cdots s_{3 n}$。你需要首先将 $S$ 中的每个 $0$ 替换为 $[1, 3]$ 中的任意一个整数，得到序列 $T = t_1 t_2 \cdots t_{3 n}$，然后给出 $n$ 个长度为 $3$ 的整数序列 ${\{ a_{i, 1}, a_{i, 2}, a_{i, 3} \}}_{1 \le i \le n}$，使得
- $\forall 1 \le i \le n$，$1 \le a_{i, 1} < a_{i, 2} < a_{i, 3} \le 3 n$；
- $\forall (i_1, j_1) \ne (i_2, j_2)$，$a_{i_1, j_1} \ne a_{i_2, j_2}$；
- $\forall 1 \le i \le n$，$\{ t_{a_{i, 1}}, t_{a_{i, 2}}, t_{a_{i, 3}} \}$ 是 $\{ 1, 2, 3 \}$ 的一个排列且逆序对数为奇数。
认为两个方案本质不同当且仅当序列 $T$ 不同或存在 $a_{i, j}$（$1 \le i \le n$，$1 \le j \le 3$）不同，求以上操作的本质不同的方案数，对 $({10}^9 + 7)$ 取模。
$n\leq19$。
Solution
逆序对数是奇数，也就是说只有 $(1,3,2),(2,1,3),(3,2,1)$ 三种情况。
题目的要求相当于我们把 $3n$ 个数分到 $n$ 个三元组里，不难想到一个 dp：
$g(i,a,b,c,d,e,f)$ 表示当前 $T$ 填了前 $i$ 位，当前为 $(1),(2),(3)$ 的三元组分别有 $a,b,c$ 个；当前为 $(1,3),(2,1),(3,2)$ 的三元组分别有 $d,e,f$ 个的方案数。
这里我们不考虑 $n$ 个三元组的顺序，方案数为 $g(3n,0,0,0,0,0,0)$，再乘上 $n!$ 即可。
转移的时候就枚举这这一位填什么，分到哪个三元组里，乘一个系数转移就好了。
复杂度看似是 $O(n^7)$，但是我们只考虑能转移到最终状态的状态进行转移，比如说 $g(i,n,2,0,0,0,0)$ 这种状态显然就没有意义。多考虑一些类似的状态，状态数会减少很多，可以很快地通过本题。
如果你采用只存合法状态进行转移的方式，我估计会非常快（
Code
注意空间需要滚动数组。
这里放一份当前最优解的代码，是一位拒绝透露姓名的神仙在我代码的基础上进行了一波常数优化得到的（
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
constexpr int mod = 1000000007;
typedef long long ll;
namespace solve
{
const int maxn = 59;
const int maxm = 20;
#define upd(x, y) ((x) = (((x) + (y)) % (mod)))
int g[2][maxm][maxm][maxm][maxm][maxm][maxm];
char str[maxn];
int n;
void main()
{
cin >> n >> (str + 1);
g[0][0][0][0][0][0][0] = 1;
int cur = 1;
for (int i = 1; i <= n * 3; i++)
{
auto&& res(n * 3 - i + 1);
for (int a = 0; 2 * a <= res && a <= i; a++)
for (int b = 0; 2 * a + 2 * b <= res && a + b <= i; b++)
for (int c = 0; 2 * a + 2 * b + 2 * c <= res && a + b + c <= i; c++)
for (int d = 0; 2 * a + 2 * b + 2 * c + d <= res && a + b + c + 2 * d <= i; d++)
for (int e = 0; 2 * a + 2 * b + 2 * c + d + e <= res && a + b + c + 2 * d + 2 * e <= i; e++)
for (int f = 0; 2 * a + 2 * b + 2 * c + d + e + f <= res && a + b + c + 2 * d + 2 * e + 2 * f <= i; f++)
if (g[cur ^ 1][a][b][c][d][e][f])
{
int&& tmp(2 * a + 2 * b + 2 * c + d + e + f), fxj(a + b + c + d + e + f);
auto const& now = str[i];
ll const& lst = g[cur ^ 1][a][b][c][d][e][f];
if (now == '1' || now == '0')
{
if (a < n && tmp + 2 <= res - 1 && fxj < n)
upd(g[cur][a + 1][b][c][d][e][f], lst);
if (c > 0 && f < n)
upd(g[cur][a][b][c - 1][d][e][f + 1], lst * c);
if (e > 0)
upd(g[cur][a][b][c][d][e - 1][f], lst * e);
}
if (now == '2' || now == '0')
{
if (c < n && tmp + 2 <= res - 1 && fxj < n)
upd(g[cur][a][b][c + 1][d][e][f], lst);
if (b > 0 && e < n)
upd(g[cur][a][b - 1][c][d][e + 1][f], lst * b);
if (d > 0)
upd(g[cur][a][b][c][d - 1][e][f], lst * d);
}
if (now == '3' || now == '0')
{
if (b < n && tmp + 2 <= res - 1 && fxj < n)
upd(g[cur][a][b + 1][c][d][e][f], lst);
if (a > 0 && d < n)
upd(g[cur][a - 1][b][c][d + 1][e][f], lst * a);
if (f > 0)
upd(g[cur][a][b][c][d][e][f - 1], lst * f);
}
g[cur ^ 1][a][b][c][d][e][f] = 0;
}
cur ^= 1;
}
ll ans = g[cur ^ 1][0][0][0][0][0][0];
for (ll i = 1; i <= n; ++i) ans = ans * i % mod;
cout << ans << endl;
int res = 3 * n;
for (int a = 0; a <= n && 2 * a <= res; a++)
for (int b = 0; a + b <= n && 2 * a + 2 * b <= res; b++)
for (int c = 0; a + b + c <= n && 2 * a + 2 * b + 2 * c <= res; c++)
for (int d = 0; a + b + c + d <= n && 2 * a + 2 * b + 2 * c + d <= res; d++)
for (int e = 0; a + b + c + d + e <= n && 2 * a + 2 * b + 2 * c + d + e <= res; e++)
for (int f = 0; a + b + c + d + e + f <= n && 2 * a + 2 * b + 2 * c + d + e + f <= res; f++)
g[1][a][b][c][d][e][f] = g[0][a][b][c][d][e][f] = 0;
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
solve::main();
}
T3 box
Description
有 $n$ 个不同的盒子排成一排。在初始状态下，第 $i$ 个盒子放有 $a_i$ 个货物，总货物数量为 $S = \sum_{i = 1}^{n} a_i$。对于非负整数数组 $(b_1, b_2, \ldots, b_n)$ 满足 $\sum_{i = 1}^{n} b_i = S$，考察以下问题：
你想让第 $i$ 个盒子中拥有恰好 $b_i$ 个货物，为此你可以做如下操作若干次：对两个相邻的盒子，把其中一个盒子的恰好一个货物移动至另一个。对 $i, i + 1$（$1 \le i < n$）号盒子做一次操作的代价为 $w_i$。你需要保证在操作中不存在盒子中的货物数量是负数。
在以上问题下，定义从初始状态达到第 $i$ 个盒子拥有恰好 $b_i$ 个货物的状态的最小代价为 $\operatorname{val}(b_1, b_2, \ldots, b_n)$，你需要求出对所有满足 $\sum_{i = 1}^{n} b_i = S$ 的非负整数数组 $(b_1, b_2, \ldots, b_n)$，$\operatorname{val}(b_1, b_2, \ldots, b_n)$ 的和。输出这个答案对 $998244353$ 取模后的结果。
Solution
不会的数学题，越学越认识到自己垃圾的数学水平…
感觉是一篇详细的题解。
我们对每条边算出其对答案的贡献，设 $s_i=\sum_{j=1}^ia_j,S=s_n$，枚举 $j=\sum_{k=1}^ib_k$，那么方案数为前 $i$ 个盒子里放 $j$ 个货物的方案数乘上后 $n-i$ 个盒子里放 $S-j$ 个货物的方案数，这里盒子可以为空，用插板法搞一下就可以得出答案的式子： $$ ans=\sum_{i=1}^n w_i\sum_{j=0}^S|j-s_i|\binom{i+j-1}{i-1}\binom{n-i+S-j-1}{n-i-1} $$ 我们主要关心第二个求和式子。
绝对值显然不好搞，给拆掉，然后把少加的部分补进去。 $$ \begin{aligned} &\sum_{j=0}^S|j-s_i|\binom{i+j-1}{i-1}\binom{n-i+S-j-1}{n-i-1}\\ =&\sum_{j=0}^{S}(j-s_i)\binom{i+j-1}{i-1}\binom{n-i+S-j-1}{n-i-1}+2\sum_{j=0}^{s_i}(s_i-j)\binom{i+j-1}{i-1}\binom{n-i+S-j-1}{n-i-1} \end{aligned} $$ 这里 $j=s_i$ 的项为了方便在两边都算进去了，反正是 $0$ 不影响。
前面和后面的形式是相同的，后一个显然更强一些（因为有循环上界的限制），我们先考虑后一个式子。把后一个求和式子拆开，我们关心的是： $$ s_i\sum_{j=0}^{s_i}\binom{i+j-1}{i-1}\binom{n-i+S-j-1}{n-i-1}-\sum_{j=0}^{s_i}j\binom{i+j-1}{i-1}\binom{n-i+S-j-1}{n-i-1} $$ 想要把这两个式子统一起来，后一个求和式子的 $j$ 要想办法换成一个常数移到外面来，有 $$ j\binom{i+j-1}{i-1}=j\times\frac{(i+j-1)!}{(i-1)!j!}=i\times\frac{(i+j-1)!}{i!(j-1)!}=i\binom{i+j-1}{i} $$ 这样后面的式子就变成 $$ i\sum_{j=0}^{s_i}\binom{i+j-1}{i}\binom{n-i+S-j-1}{n-i-1} $$ 已经基本统一了，但是具体的加一/减一上还需要稍微凑一下，为了方便我们设 $$ f(n,s,i,k)=\sum_{j=0}^k\binom{i+j-1}{i-1}\binom{n-i+s-j-1}{n-i-1} $$ 观察一下，想让 $\dbinom{i+j-1}{i}$ 对上 $\dbinom{i+j-1}{i-1}$ 这一项，$i$ 需要对应 $i-1$，那组合数上面的 $j$ 就得对应 $j+1$，因此我们对刚刚后面的式子进行一个小调整，枚举原来的 $j-1$，这样就变为： $$ i\sum_{j=0}^{s_i-1}\binom{i+j}{i}\binom{n-i+S-j}{n-i-1} $$ 这样就能一一凑上了，上式等于 $i\times f(n+1,s-1,i+1,k-1)$。
把 $f$ 带回最开始的式子，对于每个 $i$，我们要求出： $$ i\times f(n+1,S-1,i+1,S-1)-s_i\times f(n,S,i,S)+2\times f(n,S,i,s_i)-2i\times f(n+1,S-1,i+1,s_i-1) $$ 注意到 $i$ 和 $s_i$ 都是不降的，那么问题就变为：已知 $f(n,s,i,k)$，要快速求出 $f(n,s,i+1,k),f(n,s,i,k+1)$。
$f(n,s,i,k+1)$ 直接根据 $f$ 的定义求就好了，难的是 $i$ 的增加。
我是推不动，这里回到组合意义就很神仙，考虑 $f$ 的组合意义，是总共有 $n$ 个盒子，$s$ 个货物要放到这些盒子里，前 $i$ 个盒子最多放 $k$ 个货物的方案数。怎么理解呢？就是枚举前 $i$ 个盒子放几个货物，同样插板法。
我们需要一个枚举盒子的组合意义，换个思路，等价于第 $k+1$ 个货物所在的盒子大于 $i$。枚举这个盒子 $j$，方案数为前 $j$ 个盒子放 $k$ 个货物的方案数乘上后 $n-j+1$ 个盒子放 $S-k-1$ 个货物的方案数，同样插板法，式子就是： $$ f(n,s,i,k)=\sum_{j=i+1}^n\binom{j+k-1}{j-1}\binom{n-j+s-k-1}{n-j} $$ 这个就可以随着 $i$ 的变化 $O(1)$ 维护了。
把四个 $f$ 分别维护，就做完了，好耶！
Code
namespace solve
{
const int maxn = 3e6 + 10;
const int mod = 998244353;
typedef long long ll;
ll qpow(ll a, ll x, ll p)
{
ll res = 1;
for (; x; x >>= 1, a = a * a % p)
if (x & 1)
res = res * a % p;
return res;
}
ll fac[maxn], ifac[maxn];
int n;
void init(int n = 3e6)
{
fac[0] = 1;
for (int i = 1; i <= n; i++)
fac[i] = fac[i - 1] * i % mod;
ifac[n] = qpow(fac[n], mod - 2, mod);
for (int i = n - 1; i >= 0; i--)
ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
inline ll C(int n, int m) { return m > n || m < 0 || n < 0 ? 0 : fac[n] * ifac[m] % mod * ifac[n - m] % mod; }
int sum[maxn], w[maxn];
int S;
inline ll f(int n, int S, int i, int k)
{
ll res = 0;
for (int j = 0; j <= k; j++)
(res += C(i + j - 1, i - 1) * C(n - i + S - j - 1, n - i - 1) % mod) %= mod;
return res;
}
struct func
{
int n, s, i, k;
ll res;
void init(int n_, int s_, int i_, int k_)
{
n = n_, s = s_, i = i_, k = k_;
res = 0;
for (int j = 0; j <= k; j++)
res += C(i + j - 1, i - 1) * C(n - i + s - j - 1, n - i - 1) % mod;
res %= mod;
}
void movek(int nk)
{
if (nk <= k)
return;
for (int j = k + 1; j <= nk; j++)
res += C(i + j - 1, i - 1) * C(n - i + s - j - 1, n - i - 1) % mod;
res %= mod;
k = nk;
}
void movei(int ni)
{
if (ni <= i)
return;
for (int j = i + 1; j <= ni; j++)
res -= C(j + k - 1, j - 1) * C(n - j + s - k - 1, n - j) % mod;
res %= mod;
i = ni;
}
} f1, f2, f3, f4;
void main()
{
n = read();
for (int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + read();
for (int i = 1; i < n; i++)
w[i] = read();
ll ans = 0;
S = sum[n];
f1.init(n + 1, S - 1, 1, S - 1), f2.init(n, S, 1, S);
f3.init(n, S, 1, 0), f4.init(n + 1, S - 1, 1, -1);
for (int i = 1; i < n; i++)
{
ll res = 0;
f3.movek(sum[i]), f4.movek(sum[i] - 1);
f1.movei(i + 1), f2.movei(i), f3.movei(i), f4.movei(i + 1);
res += i * f1.res % mod;
res -= sum[i] * f2.res % mod;
res += 2 * sum[i] * f3.res % mod;
res -= 2 * i * f4.res % mod;
res %= mod;
ans += w[i] * res % mod, ans %= mod;
}
cout << (ans + mod) % mod << endl;
}
}
int main()
{
int T;
cin >> T;
solve::init();
while (T--)
solve::main();
}
T4 string
Description
给定一个英文小写字母构成的字符串 $S$，你需要找到一个尽可能长的字符串序列 $(T_0, T_1, \ldots, T_l)$，满足：
- $T_0$ 是 $S$ 的子串；
- $\forall 1 \le i \le l$，$\lvert T_i \rvert - \lvert T_{i - 1} \rvert = 1$；
- $\forall 1 \le i \le l$，存在 $S$ 的一个长度为 $\lvert T_i \rvert + 1$ 的子串 $S_i’$，使得 $S_i’$ 的长度为 $\lvert T_{i - 1} \rvert$ 的前缀为 $T_{i - 1}$，长度为 $\lvert T_i \rvert$ 的后缀为 $T_i$。
输出这样的字符串序列的长度的最大值（即 $l$ 的最大值）。
Solution
一个思路很清奇的题目，乍一看以为和19年省选的那个字符串问题差不多，其实完全没关系。
观察一下这个字符串序列，逆向去想一下，可以这么构造：$[i,j]\rightarrow[i-1,j-2]\rightarrow[i-2,j-4]…$ 一直这样下去直到长度为 $0$ 或者到头了。那么答案就有一个显然的下界 $\lfloor n/2\rfloor$。
然后上面这个构造的瓶颈在于走到头就没得走了，我们需要考虑什么时候可以往后跳回去。
然后就是比较重要的性质了：一个串可以往回跳的充要条件是出现了至少两次。
假设出现位置是 $[i_1,j_1],[i_2,j_2]$（$i_1<i_2$)，那么我们从 $[i_2,j_2]$ 开始，按照上述的构造方法构造，当左端点到 $i_1$ 时，我们跳回到 $i_2$ 即可。
反过来的话就是如果只出现一次，那么这个串对应的 $S_i’$ 是唯一的，别的跳不回来。
这样就很简单了，如果可以往回跳那么我们从 $[i_2,j_2]$ 开始一路跳就可以跳到长度为 $0$。
对于一个出现至少两次的串 $[l,r]$，若选择它作为跳的开始，答案为 $r-l+1+\lfloor(n-r)/2\rfloor$。
我们求出以每个下标为右端点的最长的出现至少两次的串，取个 max。
这个事情用 SAM 搞一搞就可以做，就对于每个节点记录最靠左的位置和 siz 就好了。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
namespace solve
{
const int maxn = 2e6 + 10;
int n;
struct SAM
{
int mx[maxn], siz[maxn], ch[maxn][26], father[maxn], pos[maxn];
int lst, tot;
int ans;
void insert(int c, int id)
{
int p = ++tot, f = lst;
siz[p] = 1, mx[p] = mx[f] + 1, lst = p, pos[p] = id;
while (f && !ch[f][c])
ch[f][c] = p, f = father[f];
if (!f)
father[p] = 1;
else
{
int q = ch[f][c];
if (mx[q] == mx[f] + 1)
father[p] = q;
else
{
int nq = ++tot;
memcpy(ch[nq], ch[q], sizeof(ch[q])), father[nq] = father[q], mx[nq] = mx[f] + 1;
pos[nq] = n + 1;
father[p] = father[q] = nq;
while (f && ch[f][c] == q)
ch[f][c] = nq, f = father[f];
}
}
}
vector<int> e[maxn];
void build()
{
for (int i = 2; i <= tot; i++)
e[father[i]].push_back(i);
}
void dfs(int x)
{
for (int v : e[x])
{
dfs(v);
siz[x] += siz[v], pos[x] = min(pos[x], pos[v]);
}
if (siz[x] > 1)
ans = max(ans, (n - pos[x]) / 2 + mx[x]);
}
void clear()
{
for (int i = 1; i <= tot; i++)
e[i].clear(), memset(ch[i], 0, sizeof(ch[i]));
memset(father, 0, sizeof(int) * (tot + 4));
memset(mx, 0, sizeof(int) * (tot + 4));
memset(siz, 0, sizeof(int) * (tot + 4));
memset(pos, 0, sizeof(int) * (tot + 4));
lst = tot = 1;
ans = 0;
}
SAM() { lst = tot = 1; }
} sam;
char s[maxn];
void main()
{
cin >> s;
n = strlen(s);
for (int i = 0; i < n; i++)
sam.insert(s[i] - 'a', i + 1);
sam.build(), sam.dfs(1);
cout << max(sam.ans, n / 2) << endl;
sam.clear();
}
}
int main()
{
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T--)
solve::main();
}