A我们考虑序列的最后一个数字 $x$，那么 $>x$ 的数字在排名中就没有贡献了，所以我们只能让前面 $<x$ 的数尽量靠前。贪心的想我们肯定让这个 $x$ 尽量大，也就是说如果把越大的数放在后面，那么就会有更多小的数在前面。于是答案等价于求反过来的最大字典序。#include <bits/stdc++.h> #define fi first #define se ...
A枚举每个矩形，前缀和优化即可。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back ...
A. 寿司晚宴暴力 dp 是设 $f_{S_1,S_2}$ 表示两个人选的质因子的集合，转移直接预处理每个数的集合转移。这种题肯定是按照 $\sqrt n$ 分类讨论：对于 $\leq \sqrt n$ 的质数只有 $8$ 个，先状压，然后将其他的数字，如果最大的质因子 $> \sqrt n$ 就按照这个分类。显然每一类如果要选肯定都只会选给同一个人，所以对每一类先预处理 $g_{S}...
A考虑对串的反串建后缀树，答案就是叶子节点个数。注意到这时的叶子节点一定是一段前缀，如果一个前缀 $s[1\ldots i]$ 是叶子节点当且仅当它不属于任何一个点的 border 集合，所以问题变成了求每个前缀的 border 集合的并的大小，用 kmp 解决即可。这里发现一个结论：每个前缀的 border 集合的并的大小等于 $\max{fail_i}$。证明要考虑这个命题等价于叶子节点...