$\texttt{D1A.Good}$
题目描述
难度：★
设 $f(i)$ 表示 $i$ 的各个数位数字相加之和。
给出三个正整数 $n, x, k$，集合 $S$ 满足性质：
- $x \in S$；
- 如果正整数 $y$ 满足 $y\leq n, y-f(y) \times k \in S$，那么 $y \in S$；
- 如果正整数 $y$ 满足 $y\leq n, y^c \in S(c>1,c\in Z)$，那么 $y \in S$。
$1\leq n\leq 10^7, 1\leq x, k\leq n$，求 $|S|$。
思路
建一个图，边 $(u,v)$ 表示若 $u\in S$，那么 $v \in S$。
枚举所有 $y$，第一类边显然只有 $O(n)$ 条，第二类边根据根号分类，也只有 $O(n)$ 条。
建图后 $\mathcal{BFS}$ 一遍即可。
代码
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 1e7 + 10;
int f[N];
bool vis[N];
int h[N], e[N * 2], ne[N * 2], idx;
void addedge(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int main() {
int n, x, k;
scanf("%d%d%d", &n, &x, &k);
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ ) {
f[i] = f[i / 10] + i % 10;
int t = i - f[i] * k;
if (t >= 1) addedge(t, i);
long long k = 1ll * i * i;
if (i != 1)
for (int j = 2; k <= n; j ++, k *= i )
addedge(k, i);
}
int cnt = 0;
queue<int> q;
q.push(x);
vis[x] = 1;
while (q.size()) {
int t = q.front();
q.pop();
cnt ++ ;
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (!vis[j])
q.push(j), vis[j] = 1;
}
}
printf("%d\n", cnt);
return 0;
}
$\texttt{D1B.Number}$
题目描述
难度：★★★
空间限制：$\texttt{64mb}$，时间限制：$\texttt{1000ms}$
给定正整数 $n,k,x$，满足 $x \in {[0,2^n)}$，一个数不优美，当且仅当这个数的二进制下后 $n$ 位（包括前导零）满足不存在任何长度位 $k$ 的连续回文子串。
要求的是 $[0,x)$ 中有多少不优美数。
另外题目中的 $x$ 会以二进制形式给出，其中的每一位为 $0,1,?$，若其中一位为 $?$ 那么这一位可以是 $0$ 或 $1$，题目的答案变为所有可能的 $x$ 的前缀不优美数之和。
$n\leq 1600, 0\leq x < 2^n, 2\leq k\leq 20$。
思路
前置知识：状压 $\mathfrak{dp}$，$\mathfrak{AC}$ 自动机
首先考虑没有问号的情况，很显然有一种数位 $dp$ 的 $O(n 2^k k)$ 的做法，预处理 $f_{i,s}$ 表示 $i$ 位字符串，且后 $k$ 位为 $s$ 的不优美数个数，但本题还需要存第 $i$ 位前的 $k$ 个字符，所以复杂度 $O(n 2^k k)$。
但是这种数位 $dp$ 没有办法处理带有 $?$ 的情况，所以我们换种思路，设 $f_{i,s,lim}$ 表示从高位到低位已经填写了 $i$ 个字符，且最后 $k$ 位为 $s$ 的方案数，$lim$ 表示是否顶到了上限。
以下表示 $f$ 数组的定义，其中 $X[i]$ 表示所有可能的 $x$ 取出前 $i$ 位后的不可重集合。
for (int i = 1; i <= n; i ++ )
{
for (x' : X[i])
{
for (s' = 0; s' < x'; s' ++ )
{
f[i][s & ((1 << k) - 1)][i == s'] ++ ;
}
}
}
有了这个定义，我们可以轻松推出式子，时间复杂度 $O(n2^k)$。
发现记录 $s$ 的这维有点浪费，我们将所有长度位 $k$ 的回文串塞进一个 $AC$ 自动机，于是自动机一共有 $O(2^{k/2}k)$ 个状态，然后每加一个字符，就在自动机上走一步，用状态 $p$ 代替串 $s$。
于是复杂度降为 $O(n2^{k/2}k)$，注意空间也要用滚动数组压缩。
代码
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
struct AC_Build {
#define M 40010
int trie[M][2], mark[M], fail[M], tot_;
void ins(string s) {
int p = 0;
for (int i = 0; i < s.size(); i ++ ) {
int c = s[i] - 48;
if (!trie[p][c]) trie[p][c] = ++ tot_;
p = trie[p][c];
}
mark[p] = 1;
} void build() {
queue<int> Q;
for (int i = 0; i < 2; i ++ )
if (trie[0][i])
Q.push(trie[0][i]);
while (Q.size()) {
int t = Q.front();
Q.pop();
int z = fail[t];
for (int i = 0; i < 2; i ++ )
if (!trie[t][i]) trie[t][i] = trie[z][i];
else fail[trie[t][i]] = trie[z][i], Q.push(trie[t][i]);
}
}
#undef M
} A;
void find_s(int n, string s) {
if (s.size() == n / 2) {
string t = s;
reverse(s.begin(), s.end());
if (n & 1) {
A.ins(s + "0" + t);
A.ins(s + "1" + t);
} else {
A.ins(s + t);
}
return;
}
find_s(n, s + "0");
find_s(n, s + "1");
}
const int MOD = 1e9 + 7;
struct modint {
int a;
const modint operator + (const modint &b) const {
return modint({(a + b.a) % MOD});
}
void operator += (const modint b) {
a = (a + b.a) % MOD;
}
const int operator = (const int b) {
a = b;
return a;
}
const int operator = (const modint b) {
a = b.a;
return a;
}
} f[2][40010][2];
char str[2010];
int main() {
// freopen("number.in", "r", stdin);
// freopen("number.out", "w", stdout);
int n, k;
scanf("%d%d%s", &n, &k, str + 1);
find_s(k, "");
A.build();
int tot = A.tot_;
f[0][0][1] = 1;
for (int i = 1; i <= n; i ++ ) {
int o = i & 1;
for (int j = 0; j <= tot; j ++ ) f[o][j][0] = f[o][j][1] = 0;
for (int j = 0; j <= tot; j ++ ) {
if (A.mark[j]) continue;
int t0 = A.trie[j][0], t1 = A.trie[j][1];
f[o][t0][0] += f[o ^ 1][j][0];
f[o][t1][0] += f[o ^ 1][j][0];
if (str[i] == '?') {
f[o][t0][0] += f[o ^ 1][j][0];
f[o][t1][0] += f[o ^ 1][j][0];
}
if (str[i] == '0') f[o][t0][1] += f[o ^ 1][j][1];
if (str[i] == '1') f[o][t1][1] += f[o ^ 1][j][1], f[o][t0][0] += f[o ^ 1][j][1];
if (str[i] == '?') f[o][t1][1] += f[o ^ 1][j][1], f[o][t0][0] += f[o ^ 1][j][1], f[o][t0][1] += f[o ^ 1][j][1];
}
for (int j = 0; j <= tot; j ++ )
if (A.mark[j])
f[o][j][0] = f[o][j][1] = 0;
}
modint ans; ans = 0;
for (int j = 0; j <= tot; j ++ )
if (!A.mark[j])
ans += f[n & 1][j][0];
printf("%d\n", ans.a);
return 0;
}
$\texttt{D1C.Xor}$
难度：★★★★
圆方树硬套线性基
#include <bits/stdc++.h>
#define pb push_back
#define il inline
#define re register
using namespace std;
il int qr() {
char a, b, c, d, e;
a = getchar(), b = getchar(), c = getchar(), d = getchar(), e = getchar();
a -= 48, b -= 48, c -= 48, d -= 48, e -= 48;
return (a << 24) + (b << 18) + (c << 12) + (d << 6) + e;
}
il int qr_() {
char a, b, c;
a = getchar(), b = getchar(), c = getchar();
a -= 48, b -= 48, c -= 48;
return (a << 12) + (b << 6) + c;
}
il void write(int x) {
int lt = (1 << 6) - 1;
char a = (x >> 24 & lt) + '0', b = (x >> 18 & lt) + '0', c = (x >> 12 & lt) + '0', d = (x >> 6 & lt) + '0', e = (x & lt) + '0';
putchar(a), putchar(b), putchar(c), putchar(d), putchar(e);
}
const int N = 500010;
int n, m, h[N], h2[N], e[N * 4], w[N * 4], ne[N * 4], idx;
il void addedge(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
} il void addedge2(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h2[a], h2[a] = idx ++ ;
}
void Swap(int &x, int &y) {
x ^= y ^= x ^= y;
}
struct Line_Base {
int a[40] = {0}, b[40] = {0};
il void insert(int x, int pos) {
for (re int i = 30; i >= 0; i -- )
if (x >> i & 1) {
if (a[i]) {
if (a[i] < pos) Swap(b[i], x), Swap(a[i], pos);
x ^= b[i];
} else {
a[i] = pos, b[i] = x;
break;
}
}
} il void exchange() {
for (re int i = 30; i >= 0; i -- )
for (re int j = i - 1; j >= 0; j -- )
if (b[i] >> j & 1)
b[i] ^= b[j];
} il void erase(int x) {
for (re int i = 30; i >= 0; i -- )
if (a[i] < x)
a[i] = b[i] = 0;
} il int count() {
int cnt = 0;
for (re int i = 30; i >= 0; i -- )
if (b[i] > 0)
cnt ++ ;
return cnt;
} il void clr() {
for (re int i = 0; i < 40; i ++ ) a[i] = b[i] = 0;
} il void out() {
for (re int i = 30; i >= 0; i -- )
if (b[i] > 0) cout << b[i] << ' ';
cout << endl;
}
} g[N];
il Line_Base merge(Line_Base A, Line_Base B) {
Line_Base C = A;
for (re int i = 30; i >= 0; i -- )
if (B.a[i])
C.insert(B.b[i], B.a[i]);
return C;
}
int fa[N], fw[N], fi[N], tot;
int lengh[N], dep[N];
il void build_circle(int up, int down, int len) {
++ tot;
for (re int i = down; ; i = fa[i]) {
addedge2(tot, i, dep[i] ^ dep[up]);
addedge2(i, tot, dep[i] ^ dep[up]);
if (i == up) break;
}
lengh[tot] = len;
}
int dfn[N], low[N], times;
void tarjan(int u, int ffa) {
dfn[u] = low[u] = ++times;
for (re int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
dep[j] = dep[u] ^ w[i];
fa[j] = u, fw[j] = w[i], fi[j] = i;
tarjan(j, u);
low[u] = min(low[u], low[j]);
if (dfn[u] < low[j]) addedge2(u, j, w[i]), addedge2(j, u, w[i]);
} else if (j != ffa) {
low[u] = min(low[u], dfn[j]);
}
}
for (re int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (dfn[u] < dfn[j] && fi[j] != i)
build_circle(u, j, dep[j] ^ dep[u] ^ w[i]);
}
}
int p[N][22], d[N], dis[N];
void dfs(int u, int fa) {
g[u] = g[fa], d[u] = d[fa] + 1;
if (u > n) g[u].insert(lengh[u], d[u]);
p[u][0] = fa;
for (re int i = 1; i < 20; i ++ ) p[u][i] = p[p[u][i - 1]][i - 1];
for (re int i = h2[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa) continue;
dis[j] = dis[u] ^ w[i];
d[j] = d[u] + 1;
dfs(j, u);
}
}
il int find_lca(int x, int y) {
if (d[x] > d[y]) swap(x, y);
for (re int i = 19; i >= 0; i -- )
if (d[p[y][i]] >= d[x])
y = p[y][i];
if (x == y) return x;
for (re int i = 19; i >= 0; i -- )
if (p[x][i] != p[y][i])
x = p[x][i], y = p[y][i];
return p[x][0];
}
il int check(Line_Base B, int s, int val) {
int t = (val ^ s) & s;
int nw = t;
for (re int i = 30; i >= 0; i -- )
if (nw >> i & 1)
nw ^= B.b[i];
if (nw == 0) return B.count();
return -1;
}
Line_Base gt[40];
il void qry(Line_Base A, int k, int s, int val) {
k ++ ;
for (int i = 1; i <= 31; i ++ ) {
gt[i] = gt[i - 1];
if (A.b[i - 1]) gt[i].insert(A.b[i - 1] & s, A.a[i - 1]);
}
int tmp = check(gt[31], s, val), cnt = A.count();
if (tmp == -1) return printf("-1"), void();
if (k > (1 << cnt - tmp)) return printf("-1"), void();
int nw = val;
for (re int i = 30; i >= 0; i -- ) {
if (A.b[i] == 0) continue;
if (nw >> i & 1) nw ^= A.b[i];
int rr = A.b[i];
A.a[i] = A.b[i] = 0;
cnt -- ;
int y = check(gt[i], s, nw);
int num = 0;
if (y == -1) nw ^= rr;
else {
num = 1 << cnt - y;
if (k > num) nw ^= rr, k -= num;
}
}
write(nw);
}
int main() {
n = qr(), m = qr();
tot = n;
memset(h, -1, sizeof h);
memset(h2, -1, sizeof h);
for (re int i = 0; i < m; i ++ ) {
int u, v, w;
u = qr_(), v = qr_(), w = qr();
addedge(u, v, w), addedge(v, u, w);
}
tarjan(1, 0);
dfs(1, 0);
int Q;
Q = qr();
while (Q -- ) {
int a, b, k, s;
a = qr_(), b = qr_(), k = qr(), s = qr();
int vv = dis[a] ^ dis[b];
Line_Base U = merge(g[a], g[b]);
U.erase(d[find_lca(a, b)]);
qry(U, k, s, vv);
}
return 0;
}
$\texttt{D2B.Tree}$
题目描述
难度：★★
给定一棵树，每个节点有权值 $a_i$，对于所有 $i$，求 $\max_{j=1}^n [a_j\ge a_i] \operatorname{dist}(i,j)$。
思路
一个明显的方法是点分治套树状数组，复杂度 $O(n\log^2 n)$。
另一种是发现离节点 $i$ 最远的点一定是树直径的端点，所以按照权值从大到小的顺序加入虚树，动态维护直径。
代码
#include <bits/stdc++.h>
#define il inline
#define re register
using namespace std;
const int N = 200010;
int n, m;
int Max(int a, int b) {
return a > b ? a : b;
}
struct tree {
int tr[N];
il void init() {
for (re int i = 0; i < N; i ++ ) tr[i] = -2e9;
} il void clear(int x) {
for (re int i = x; i <= m; i += i & -i)
tr[i] = -2e9;
} il void add(int x, int k) {
for (re int i = x; i <= m; i += i & -i)
tr[i] = Max(tr[i], k);
} il int qry(int x) {
int res = -2e9;
while (x) {
res = Max(res, tr[x]);
x -= x & -x;
}
return res;
}
} Tr;
int a[N], vis[N], h[N], e[N * 2], ne[N * 2], idx;
int ans[N];
void addedge(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int get_size(int u, int fa) {
int res = 1;
for (re int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa || vis[j]) continue;
res += get_size(j, u);
}
return res;
}
int get_d(int u, int fa, int all, int &dd) {
int siz = 1, mx = 0;
for (re int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa || vis[j]) continue;
int tmp = get_d(j, u, all, dd);
siz += tmp, mx = Max(mx, tmp);
}
if (mx <= all / 2 && all - siz <= all / 2) dd = u;
return siz;
}
void dfs(int u, int fa, int depth) {
Tr.add(a[u], depth);
for (re int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa || vis[j]) continue;
dfs(j, u, depth + 1);
}
}
void dfs2(int u, int fa, int depth) {
ans[u] = Max(ans[u], Tr.qry(a[u]) + depth);
for (re int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa || vis[j]) continue;
dfs2(j, u, depth + 1);
}
}
void dfs3(int u, int fa) {
Tr.clear(a[u]);
for (re int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa || vis[j]) continue;
dfs3(j, u);
}
}
void calc(int u) {
vector<int> v;
for (re int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (!vis[j]) v.push_back(j);
}
vis[u] = 1;
Tr.add(a[u], 0);
for (re int i : v) {
dfs2(i, 0, 1);
dfs(i, 0, 1);
}
ans[u] = Max(ans[u], Tr.qry(a[u]));
Tr.clear(a[u]);
for (re int i : v) dfs3(i, 0);
reverse(v.begin(), v.end());
Tr.add(a[u], 0);
for (re int i : v) {
dfs2(i, 0, 1);
dfs(i, 0, 1);
}
Tr.clear(a[u]);
for (re int i : v) dfs3(i, 0);
for (re int i : v) {
int d;
get_d(i, 0, get_size(i, 0), d);
calc(d);
}
}
int main() {
Tr.init();
scanf("%d", &n);
vector<int> VV;
for (int i = 1; i <= n; i ++ ) {
scanf("%d", &a[i]);
a[i] = -a[i];
VV.push_back(a[i]);
}
sort(VV.begin(),VV.end());
VV.erase(unique(VV.begin(), VV.end()), VV.end());
m = VV.size();
unordered_map<int, int> ma;
for (int i = 0; i < m; i ++ ) ma[VV[i]] = i + 1;
for (int i = 1; i <= n; i ++ ) a[i] = ma[a[i]];
memset(h, -1, sizeof h);
for (int i = 1; i < n; i ++ ) {
int u, v;
scanf("%d%d", &u, &v);
addedge(u, v), addedge(v, u);
}
int d;
get_d(1, 0, n, d);
calc(d);
for (int i = 1; i <= n; i ++ ) printf("%d ", ans[i]);
return 0;
}
$\texttt{D2C.Rev}$
题目描述
难度：★★★★
给定一个序列 $A$，每次操作可以选择一个区间使得区间内所有数乘以 $-1$，求最少操作数满足操作完后对于任意两个不相等的 $i,j(1 < i,j \leq n)$，$\lvert a_i - a_{i-1} \rvert \ne \lvert a_j - a_{j-1} \rvert$。
$n\leq 10^5，\lvert a_i \rvert \leq 10^9$。
思路
定义 $b_i = \lvert |a_i - a_{i-1}|$。
对于每一个 $i$，最终 $b_i$ 的值只可能为两个，$\lvert a_i-a_{i-1} \rvert$ 和 $\lvert a_i+ a_{i-1} \rvert$。
我们将所有可能的 $b_i$ 离散化，每一次操作相当于是改变 $l$ 和 $r+1$ 位置上的 $b_i$。
初始时从 $\lvert a_i+a_{i-1} \rvert$ 向 $\lvert a_i-a_{i-1}\rvert$ 连边，若 $b_i$ 改变，则这条边的方向改变，当某一个点的入度大于 $1$ 时，不满足条件。
问题变为求最少改变图中的多少条边的方向使得图中所有点入度小于等于 $1$。
对于有向图中的每个连通块，它要么是树，要么是基环树，因为若边数大于点数，那么一定不存在合法方案，输出 $-1$。
对于基环树来说，在环以外的边一定是固定的，环内边只有两种选择，轻松搞定。
对于树来说，我们需要规定一个点为根，然后每条边从深度小的到深度大的，计算此时需要改变的边的数量，这个计算可以使用换根 $\textrm{dp}$。
求出最小改变的边数后，答案即为 $\lfloor \frac{edge+1}{2}\rfloor$。
本题思维性较高，代码细节多。
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 200010;
int h[N], e[N], w[N], ne[N], idx;
int dep[N], ans;
bool vis[N], vis2[N];
void addedge(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
stack<int> stk;
vector<int> circle;
int dfs(int x, int fa) {
stk.push(x);
vis[x] = 1;
for (int i = h[x]; ~i; i = ne[i]) {
int j = e[i];
if ((i ^ 1) == fa) continue;
if (vis[j]) {
int tmp = dep[x] - dep[j] + w[i];
while (1) {
int y = stk.top();
circle.push_back(y);
stk.pop();
if (y == j) break;
}
while (stk.size()) stk.pop();
ans += min(tmp, (int)circle.size() - tmp);
return 1;
}
dep[j] = dep[x] + w[i];
if (dfs(j, i)) return 1;
}
stk.pop();
return 0;
}
void dfs2(int u, int fa) {
vis[u] = 1;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (vis2[j] || j == fa) continue;
ans += w[i];
dfs2(j, u);
}
}
int mx;
void dfs3(int u, int fa, int nw) {
mx = max(mx, nw);
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa) continue;
dfs3(j, u, w[i] ? nw + 1 : nw - 1);
}
}
int p[N], siz[N], cnt[N];
int find(int x) {
return x == p[x] ? x : p[x] = find(p[x]);
}
int main() {
int n;
scanf("%d", &n);
vector<int> a(n + 10), b(n + 10), c(n + 10), v;
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for (int i = 2; i <= n; i ++ ) {
b[i] = abs(a[i] + a[i - 1]);
c[i] = abs(a[i] - a[i - 1]);
v.push_back(b[i]), v.push_back(c[i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
unordered_map<int, int> ma;
for (int i = 0; i < v.size(); i ++ ) ma[v[i]] = i + 1, p[i + 1] = i + 1, siz[i + 1] = 1;
memset(h, -1, sizeof h);
for (int i = 2; i <= n; i ++ ) {
b[i] = ma[b[i]], c[i] = ma[c[i]];
addedge(b[i], c[i], 0), addedge(c[i], b[i], (b[i] ^ c[i]) ? 1 : 0);
int x = find(b[i]), y = find(c[i]);
if (x != y) {
p[x] = y;
cnt[y] += cnt[x];
siz[y] += siz[x];
}
cnt[y] ++ ;
}
for (int i = 1; i <= v.size(); i ++ ) {
if (cnt[find(i)] > siz[find(i)]) {
puts("-1");
return 0;
}
if (!vis[i]) {
if (dfs(i, 0)) {
for (int i : circle) vis2[i] = 1;
for (int i : circle) dfs2(i, 0);
circle.clear();
} else {
dfs2(i, 0);
mx = 0;
dfs3(i, 0, 0);
ans -= mx;
}
}
}
printf("%d\n", (ans + 1) / 2);
return 0;
}
$\texttt{D3A.茵蒂克丝}$
题目描述
难度：★★
给你两个序列长度为 $n$ 的序列 $a,b$ 和一个正整数 $k$，接下来 $Q$ 次询问，每次询问给定 $l,r$，求
$$\max_{[l\leq l’\leq r’\leq r]\wedge [r’-l’+1\ge k]} \frac{\sum_{i=l’}^{r’} a_i}{\sum_{i=l’}^{r’} b_i}$$
并将答案以分数形式输出，强制在线。
$n,Q\leq 10^6, 1\leq a_i,b_i\leq 10^7, k\leq 20$。
思路
将 $\frac{\sum_{i=l}^{r} a_i}{\sum_{i=l}^{r} b_i}$ 想象成对于 $b_{l}$ 个 $a_{l}$，$b_{l+1}$ 个 $a_{l+1} \cdots$，$b_r$ 个 $a_r$ 求平均值，若将两个平均值分别为 $w,v$ 的区间和并，那么合并后的区间的平均值小于等于 $\max\{w,v\}$，也就是说区间越小越好。
对于所有区间长度大于等于 $2k$ 的区间，一定不如它的某个长度 $\ge k$ 的区间，所以区间长度范围为 $[k,2k)$，这种区间一共只有 $nk$ 个。
设 $f_i$ 表示长度在 $[k,2k)$ 范围内的以 $i$ 结尾的区间的最大均值。
设 $g_{l,r}$ 表示区间 $[l,r]$ 的连续子区间的最大均值（$k\leq r-l+1 < 2k$），可以直接求出。
于是对于每次询问，$\mathcal{ST}$ 表求出 $\max_{i=l+2k-2}^r f_i$，然后再取 $g_{l,\min\{l+2k-3,r\}}$ 即可。
时间复杂度 $O(n\log n)$。
代码
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define ll long long
using namespace std;
const int N = 1e6 + 10;
int k, a[N], b[N], lgn[N];
long long sa[N], sb[N];
struct FRAC {
long long a, b;
} f[N][23], g[N][25];
int qrd() {
int w = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {ch = getchar();}
while (ch >= '0' && ch <= '9') {w = (w << 3) + (w << 1) + ch - 48; ch = getchar();}
return w;
}
inline FRAC Max(FRAC X, FRAC Y) {
if (Y.a * 1.0 / X.a > Y.b *1.0 / X.b) return Y;
else return X;
}
inline FRAC qry(int l, int r) {
if (l > r) return FRAC({0, 1});
int g = lgn[r - l + 1];
return Max(f[r][g], f[l + (1 << g) - 1][g]);
}
inline FRAC ask(int l, int r) {
if (r - l + 1 < k) return FRAC({0, 1});
return g[r][r - l + 1 - k];
}
int main() {
lgn[0] = -1;
int n, q, type;
scanf("%d%d%d%d", &n, &k, &q, &type);
for (int i = 1; i <= n; i ++ ) lgn[i] = lgn[i >> 1] + 1;
for (register int i = 1; i <= n; i ++ ) a[i] = qrd(), sa[i] = sa[i - 1] + a[i];
for (register int i = 1; i <= n; i ++ ) b[i] = qrd(), sb[i] = sb[i - 1] + b[i];
for (register int j = 1; j <= n; j ++ ) {
f[j][0] = FRAC({0, 1});
for (register int i = k; i < 2 * k; i ++ )
if (j >= i)
f[j][0] = Max(f[j][0], FRAC({sa[j] - sa[j - i], sb[j] - sb[j - i]}));
}
for (register int i = 1; i <= n; i ++ )
for (register int j = 1; j <= 20; j ++ )
if (i - (1 << j) >= 0)
f[i][j] = Max(f[i][j - 1], f[i - (1 << j - 1)][j - 1]);
for (register int i = k; i <= n; i ++ ) g[i][0] = FRAC({sa[i] - sa[i - k], sb[i] - sb[i - k]});
for (register int i = 1; i < k; i ++ )
for (register int j = k + i; j <= n; j ++ )
g[j][i] = Max(Max(g[j][i - 1], g[j - 1][i - 1]), FRAC({sa[j] - sa[j - k - i], sb[j] - sb[j - k - i]}));
int lastans = 0;
while (q -- ) {
int l = qrd(), r = qrd();
l ^= (type * lastans);
l = l % n + 1;
r ^= (type * lastans);
r = r % n + 1;
if (l > r) swap(l, r);
FRAC ans = qry(l + 2 * k - 1, r);
FRAC res = ask(l, min(l + 2 * k - 2, r));
ans = Max(ans, res);
long long tmp = __gcd(ans.a, ans.b);
printf("%lld/%lld\n", ans.a / tmp, ans.b / tmp);
lastans = ans.a / tmp;
}
return 0;
}
$\texttt{D3B.御坂美琴}$
题目描述
题目难度：★★★
给定一个有向图，每条边用 $(a,b,r,p)$ 表示，当御坂美琴的硬币数量大于等于 $r$ 时才能走这条边，走过之后加上 $p$ 个硬币。
求对于每一个点，至少需要多少初始硬币才能使得从该点出发能永远不停地走下去，无解则输出 $-1$。
$2\leq n,m\leq 2\times 10^5, 0\leq r_i,p_i\leq 10^9$，保证图不存在自环但可能有重边。
思路
对图使用拓扑，每次删除没有出边的点，这些点的答案必为 $-1$，删除之后所有点满足出边大于 $0$。
设 $f_i$ 表示 $i$ 点的答案，若有一条边 $(i,v,r,p)\in E$，那么一定有 $f_i \leq \max\{f_v - p,r\}$，也就是说 $f_i \leq r$ 或 $f_i \leq f_v$，能够有资格更新 $f_i$ 的一定比 $f_i$ 大。
我们初始时定义一个大根堆，向大根堆塞 $(r_i, a_i, i)$ 表示 $a_i$ 可以被 $r_i$ 更新。
循环执行如下操作：
- 取出大根堆的根 $(w,v, id)$
- 删除边 $id$，若已经删除则跳过后面所有步骤
- 如果这条边是 $v$ 的最后一条出边，那么 $f_v=w$
- $v$ 标记为已确定，对于所有边 $(u,v,r,p)$，将 $(f_v-p,u)$ 加入堆中
于是我们在 $O(n\log n)$ 的复杂度下解决了此问题。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, m, deg[N], rp[N], vis[N], ans[N];
int u[N], v[N], r[N], p[N];
int h[N], e[N], w[N], ne[N], used[N], idx;
vector<int> to[N];
priority_queue<pair<int, pair<int, int>>> H;
void addedge(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void toposort() {
queue<int> Q;
for (int i = 1; i <= n; i ++ )
if (deg[i] == 0)
Q.push(i);
while (Q.size()) {
int t = Q.front();
Q.pop();
vis[t] = 1;
for (int j : to[t]) {
if (-- deg[j] == 0) Q.push(j);
}
}
for (int i = 1; i <= n; i ++ )
if (vis[i])
ans[i] = -1;
for (int i = 1; i <= m; i ++ ) {
int a = u[i], b = v[i];
if (!vis[a] && !vis[b]) {
addedge(b, a, p[i]);
rp[a] ++ ;
H.push({r[i], {a, idx - 1}});
}
}
}
int main() {
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for (int i = 1; i <= m; i ++ ) {
scanf("%d%d%d%d", &u[i], &v[i], &r[i], &p[i]);
to[v[i]].push_back(u[i]);
deg[u[i]] ++ ;
}
toposort();
while (H.size()) {
auto tmp = H.top();
H.pop();
int val = tmp.first, st = tmp.second.first, eid = tmp.second.second;
if (vis[st]) continue;
if (!used[eid]) {
used[eid] = 1;
rp[st] -- ;
if (rp[st] == 0) {
ans[st] = val, vis[st] = 1;
for (int j = h[st]; ~j; j = ne[j]) {
if (!vis[e[j]]) {
H.push({ans[st] - w[j], {e[j], j}});
}
}
}
}
}
for (int i = 1; i <= n; i ++ ) printf("%d ", ans[i]);
return 0;
}
$\texttt{D3C.欧提努斯}$
题目描述
难度：★★★★
给定 $n$ 个柱子，高度分别为 $h_1,h_2,\cdots,h_n$，你需要求所有 $h$ 的排列方案下，一共有多少不同的接水量。
接水量可以形象地表示为
$$\sum_{i=1}^n \min\{\max_{j=i}^n \{h_j\},\max_{j=1}^i \{h_j\}\}-h_i$$
例如下图中 $H$ 表示柱子，$R$ 表示接水量。
H
HRRH
HRRH
HHRHH
HHHHH
$2\leq n\leq 2000,1\leq h_i\leq 50$
思路
思维题，先给出结论。
结论：对于 $h$ 的一个排列，它的接水量为 $w$，那么一定有一种让 $h_n=\max_{j=1}^n\{h_j\}$ 的排列方案使得接水量仍为 $w$。
证明：
设 ${premax}_i$ 为 $i$ 的前缀最大值，${sufmax}_i$ 为 $i$ 的后缀最大值。
接水量等于 $\sum_{i=1}^n \min\{{premax}_i,{sufmax}_i\} - h_i$ 由于都要减去 $h_i$，所以 $h_i$ 先省略。
设 $pos$ 表示 $h$ 的最大值所在位置，若 $i < pos$ 则 $sufmax=h_{max}$，否则 $premax=h_{max}$，
那么接水量简化为 $\sum_{i=1}^{pos-1} {premax}_i + \sum_{i=pos+1}^n {sufmax}_i$。
若 $i<pos$，设 $b_i = {premax}_i$，否则设 $b_i={sufmax}_i$，我们将所有除了 $pos$ 以外的位置按照 $b_i$ 从小到大排序，最后一个位置为 $h_max$，我们发现新的排列的 ${premax}_i=b_i$，所以接水量一样，结论成立。
于是问题变为删除其中一个 $h_{max}$，求任意排列下不同的前缀最大值之和数量。
观察前缀最大值，若一个数是它前缀中最大的，且不存在与它同样大的，那么称这个点为实点，否则为虚点。
按 $h$ 从小到大的顺序加入排列，那么加入过程中，某些点将会变为虚点，所以加入虚点备选集合，否则它是实点，从虚点备选中拉几个放在该点右侧。
设 $f_{i,j,k}$ 表示加入了所有前 $i$ 个点，备选集合有 $j$ 个点，是否有接水量为 $k$ 的排列。
若该点加入虚点，$f_{i+1,j+1,k}\gets f_{i,j,k}$；否则该点为实点，对于 $0\leq t\leq j$， $f_{i+1,j-t,k+(t+1)\times h_{i+1}}\gets f_{i,j,k}$。
运用类似完全背包的思想，我们可以不用枚举 $t$，而是 $f_{i,j-1,k+h_i}\gets f_{i,j,k}$。
由于这是一个只存在 $01$ 的 dp，可以使用 bitset，复杂度降为 $O(\frac{n^3h}{w})$。
我们发现对于同样高度的一段柱子，最多只有 $1$ 个实点，重新设置 $f_{i,j,k}$ 表示加入了高度小于等于 $i$ 的柱子，设高度为 $i$ 的柱子有 $cnt_i$ 个。
默认所有高度 $i+1$ 的点为虚点，重新定义 $j’$ 为 $i-j$，用 $j’$ 代替 $j$，这样就可以不改变 $j$。
若存在实点，那么 $f_{i,j+1,k+i} \gets f_{i,j,k}$；然后 $f_{i+1,j,k}\gets f_{i,j,k}$。
时间复杂度 $O(\frac{n^2h^2}{w})$。
代码
代码十分简单，甚至可以省去第一维。
#include <bits/stdc++.h>
using namespace std;
const int N = 2010, H = 55;
bitset<N * H> dp[N];
int main() {
int n, mx = 0, all = 0;
scanf("%d", &n);
vector<int> cnt(55);
for (int i = 1; i <= n; i ++ ) {
int h;
scanf("%d", &h);
cnt[h] ++ , all += h;
mx = max(mx, h);
}
all -= mx, cnt[mx] -- ;
dp[0][0] = 1;
for (int i = 1, sum = 0; i <= 50; i ++ )
if (cnt[i]) {
sum += cnt[i];
for (int j = 0; j < sum; j ++ )
dp[j + 1] |= dp[j] << i;
}
for (int i = all; i <= 100000; i ++ )
if (dp[n - 1][i])
printf("%d ", i - all);
return 0;
}
$\texttt{D3D.食蜂操祈}$
题目描述
难度：★★★★
给定 $n$，以及一个 $1\sim n$ 的排列 $X$，求有多少 $1\sim n$ 的排列 $B$ 满足其能被栈排序且字典序大于等于 $X$，答案对 $998244353$ 取模。
能够被栈排序表示为对于一个排列 $B$，新建一个栈和一个序列 $C$，然后执行任意次如下操作：
- 从 $B$ 的开头取出一个点放入栈内；
- 从栈顶取出点到序列 $C$ 的末尾；
若存在一种执行顺序使得最终 $C$ 单调上升，则称 $B$ 可以被栈排序。
$3\leq n\leq 10^6$。
思路
思维好题。
设 $K_n$ 表示第 $n$ 项卡特兰数。
性质 $\textrm{I}$：一个排列 $B$ 可以被栈排序当且仅当对于所有 $i$ 满足 $i$ 前面所有大于 $B_i$ 的数单调递减。
性质 $\textrm{II}$：可以被栈排序的 $1\sim n$ 排列个数等于第 $n$ 项卡特兰数。
性质 $\textrm{III}$：$K_n=\sum_{i=0}^{n-1} K_i K_{n-i-1}$
将字典序大于等于转成小于，便于操作。
假设排列前缀已经固定了一些点，且这些点满足性质 $1$，剩下的点在值域上表示为一个一个的连通块。
假设我们有 $x,y$ 在不同的连通块中，且 $x<y$，那么一定存在 $z$ 满足 $x<z<y$ 且 $z$ 已经在前缀中，若在排列中 $y$ 的位置在 $x$ 之前，那么不满足性质 $1$，所以每次只能选择最小的连通块中的点加入前缀，每个连通块独立，答案为每个连通块长度的卡特兰数的乘积。
考虑这个字典序限制，假设我们确定了排列的前 $i-1$ 为，如果 $X_i$ 不在当前的最小连通块中，那么相当与随便选，答案加上卡特兰数之积，然后结束；否则，假设最小连通块长度 $l$，$X_i$ 为其中的第 $k$ 个，将 $\sum_{i=0}^{n-1} K_i K_{n-i-1}$ 分为 $\sum_{i=0}^{k - 2} K_i K_{n-i-1}$ 和 $\sum_{i=k-1}^{n-1} K_i K_{n-i-1}$，这两个直到任意一个就可以求另一个，我们启发式分裂，求这两个多项式中项较小的一个，复杂度相当于启发式合并，$O(n\log n)$。连通块可以用 set 维护。
代码
#include <bits/stdc++.h>
#define ll long long
#define mod 998244353
using namespace std;
const int N = 1000010;
namespace math {
int qpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = 1ll * res * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
}
return res;
}
int Inv(int x) {return qpow(x, mod - 2);}
int fac[N * 2], inv[N * 2], K[N];
int C(int n, int m) {
return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}
void Init(int n) {
fac[0] = 1, inv[0] = 1, K[0] = 1;
for (int i = 1; i <= 2 * n; i ++ ) fac[i] = 1ll * fac[i - 1] * i % mod;
inv[2 * n] = Inv(fac[2 * n]);
for (int i = 2 * n - 1; i >= 1; i -- ) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
for (int i = 1; i <= n; i ++ ) K[i] = 1ll * C(i + i, i) * Inv(i + 1) % mod;
}
}
int main() {
int n, ans = 0;
scanf("%d", &n);
math::Init(n);
set<pair<int, int>> R;
int M = math::K[n];
R.insert({1, n});
for (int i = 1; i <= n; i ++ ) {
int x;
scanf("%d", &x);
if (x > (*R.begin()).second) {
ans = (ans + M) % mod;
break;
}
auto it = R.upper_bound({x + 1, 0});
it -- ;
int l = (*it).first, r = (*it).second;
R.erase(it);
int all = math::K[r - l + 1];
M = 1ll * M * math::Inv(all) % mod;
if (x - l <= r - x + 1) {
int res = 0;
for (int i = l; i < x; i ++ ) res = (res + 1ll * math::K[i - l] * math::K[r - i] % mod) % mod;
res = 1ll * res * M % mod;
ans = (ans + res) % mod;
} else {
int res = 0;
for (int i = x; i <= r; i ++ ) res = (res + 1ll * math::K[i - l] * math::K[r - i] % mod) % mod;
res = 1ll * (all + mod - res) % mod * M % mod;
ans = (ans + res) % mod;
}
if (l < x) {
M = 1ll * M * math::K[x - l] % mod;
R.insert({l, x - 1});
} if (x < r) {
M = 1ll * M * math::K[r - x] % mod;
R.insert({x + 1, r});
}
}
printf("%d\n", (math::K[n] + mod - ans) % mod);
return 0;
}
$\texttt{D4A.朔望}$
题目描述
难度：★★
给出 $n$ 个数，求 $\textrm{lcm} \mod 998244353$。
$n\leq 5000, a_i \leq 10^{18}$
思路
不说了直接上代码，题目描述中省去了原题的一些细节，忽略输入和输出时的处理。
代码
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int main() {
int n;
scanf("%d", &n);
bool all_ji = 1;
vector<long long> a(n + 5);
for (int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]), all_ji &= (a[i] & 1);
for (int i = 1; i <= n; i ++ )
if (a[i] % 2 == 0)
a[i] >>= 1;
for (int i = 1; i <= n; i ++ ) {
__int128 prod = 1;
for (int j = 1; j < i; j ++ ) {
prod = prod * a[j] % a[i];
}
a[i] /= __gcd((long long)prod, a[i]);
}
__int128 ans = 1;
for (int i = 1; i <= n; i ++ ) {
ans = ans * a[i] % mod;
}
if (all_ji) ans = ans * (mod + 1) / 2 % mod;
printf("%d\n", (long long)ans);
return 0;
}
$\texttt{D4B.随机}$
题目描述
难度：★★
给出一个字符集 $\scriptsize\sum$，构造一个字符串满足将其首尾连接组成一个环，环上的每 $3$ 个连续的字符都以平均的方式出现。
$\scriptsize\sum \leq 62$。
思路
欧拉回路题，每一个点表示的是两个字符的一个组合，一条边从 $ab$，连到 $bc$，边权为 $c$，求的就是这个图的欧拉回路。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5010, M = 350010;
int h[N], e[M], ne[M], idx;
char ch[M];
void addedge(int a, int b, char c) {
e[idx] = b, ch[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
string ans = "";
void dfs(int u, char c) {
for (int i = h[u]; ~i; i = h[u]) {
h[u] = ne[i];
dfs(e[i], ch[i]);
}
if (c != ' ') ans += c;
}
int main() {
string s;
cin >> s;
int n = s.size();
memset(h, -1, sizeof h);
for (int i = 0; i < n; i ++ ) {
for (int j = 0; j < n; j ++ ) {
for (int k = 0; k < n; k ++ ) {
addedge(i * n + j + 1, j * n + k + 1, s[k]);
}
}
}
dfs(1, ' ');
reverse(ans.begin(), ans.end());
cout << ans;
return 0;
}
$\texttt{D4C.游走}$
题目描述
难度：★★
给定一颗树，从 $1$ 号节点开始随机游走，当所有点都到达后停止，经过一条边需要花费其边权的时间，问需要花费最少的时间，有多少概率使得游走方式的时间达到游走最优时间，对 $998244353$ 取模。
$n\leq 10^6，w_i \leq 10^9$。
思路
简单树形 $dp$，稍微优化可以达到 $O(n)$。
代码
#include <bits/stdc++.h>
#define i64 long long
using namespace std;
const int N = 1000010, mod = 998244353;
int h[N], e[N * 2], w[N * 2], ne[N * 2], idx;
i64 dep[N], mx;
int deg[N], f[N], invf[N], g[N];
int fac[N], ifac[N], inv[N];
int qpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = 1ll * res * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
}
return res;
}
void init(int n) {
fac[0] = ifac[0] = 1;
for (int i = 1; i <= n; i ++ ) fac[i] = 1ll * fac[i - 1] * i % mod;
ifac[n] = qpow(fac[n], mod - 2);
for (int i = n - 1; i >= 1; i -- ) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
for (int i = 1; i <= n; i ++ ) inv[i] = 1ll * ifac[i] * fac[i - 1] % mod;
}
void addedge(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dfs(int u, int fa) {
mx = max(mx, dep[u]);
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa) continue;
dep[j] = dep[u] + w[i];
dfs(j, u);
}
}
void dfs2(int u, int fa) {
int sons = deg[u] - (u != 1);
if (!sons) {
f[u] = invf[u] = 1;
g[u] = (dep[u] == mx) ? 1 : 0;
return;
}
f[u] = fac[sons], invf[u] = ifac[sons];
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa) continue;
dfs2(j, u);
f[u] = 1ll * f[u] * inv[deg[u]] % mod * f[j] % mod * inv[deg[j]] % mod;
invf[u] = 1ll * invf[u] * deg[u] % mod * invf[j] % mod * deg[j] % mod;
}
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa) continue;
g[u] = (g[u] + 1ll * f[u] * inv[sons] % mod * invf[j] % mod * deg[j] % mod * g[j] % mod) % mod;
}
}
int main() {
int n;
cin >> n;
init(n);
memset(h, -1, sizeof h);
long long sum = 0;
for (int i = 1; i < n; i ++ ) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
addedge(a, b, c), addedge(b, a, c);
deg[a] ++, deg[b] ++ ;
sum += c;
}
dfs(1, 0);
dfs2(1, 0);
printf("%lld %d\n", 2 * sum - mx, g[1]);
return 0;
}
$\texttt{D4D.网络}$
$\texttt{D5B.白石溪}$
题目描述
难度：★★★★
给定 $n$ 个商品的价格 $a_i$ 和收益 $v_i$，以及新价格 $b_i\space (a_i < b_i)$。
$\texttt{Alice}$ 会选择一对整数 $(l,r) \space (1\leq l \leq r \leq n)$，将商品编号在 $l,r$ 之间的数价格改为新价格，其余价格保持不变。
假设 $f(i)$ 表示在拥有 $i$ 圆是所购买物品的最大收益。
给定 $k,E$，求有多少对 $(l,r)$，满足
$$\frac{\sum_{i=1}^k f(i)}{k} \leq E$$
$1\leq n,k\leq 2\times 10^5,nk\leq 10^7,1\leq E\leq 10^9$。
$1\leq v_i \leq 10^4,1\leq a_i < b_i \leq k$。
思路
当固定左节点 $l$ 时，右节点可能的范围一定是一个后缀，设这个后缀以 $ans_l$ 开头，我们要求 $ans$ 数组。
$i$ 越大，$ans_i$ 也越大，$ans$ 具有决策单调性，我们直接采用决策单调性分治。
求 $ans_{mid}$ 的时候使用二分，然后把已确定的范围加入，复杂度 $O(nk\log n)$。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, k, E;
int v[N], a[N], b[N], ans[N];
void make_a(vector<int> &F, int l, int r) {
for (int i = l; i <= r; i ++ )
for (int j = k; j >= a[i]; j -- )
F[j] = max(F[j], F[j - a[i]] + v[i]);
}
void make_b(vector<int> &F, int l, int r) {
if (r == n + 1) return fill(F.begin(), F.end(), -1), void();
for (int i = l; i <= r; i ++ )
for (int j = k; j >= b[i]; j -- )
F[j] = max(F[j], F[j - b[i]] + v[i]);
}
void sol(int l0, int r0, int l1, int r1, vector<int> &F) {
if (l0 > r0) return;
vector<int> G(k + 1), H(k + 1);
if (r0 <= l1) {
int mid0 = (l0 + r0) / 2;
G = F;
make_a(G, l0, mid0 - 1);
make_b(G, mid0, r0 - 1);
int L = l1, R = r1;
while (L < R) {
int mid = L + R >> 1;
H = G;
make_a(H, mid + 1, R);
make_b(H, L, mid);
long long res = 0;
for (int i = 1; i <= k; i ++ ) res += H[i];
if (res > 1ll * E * k) make_b(G, L, mid), L = mid + 1;
else make_a(G, mid + 1, R), R = mid;
}
ans[mid0] = L;
G = F;
make_b(G, mid0, r0), make_a(G, L + 1, r1);
sol(l0, mid0 - 1, l1, L, G);
G = F;
make_a(G, l0, mid0), make_b(G, l1, L - 1);
sol(mid0 + 1, r0, L, r1, G);
} else {
int mid0 = (l0 + r0) / 2;
G = F;
make_a(G, l0, mid0 - 1);
make_b(G, mid0, l1 - 1);
int L = max(mid0, l1), R = r1;
while (L < R) {
int mid = L + R >> 1;
H = G;
make_a(H, mid + 1, R);
make_b(H, L, mid);
long long res = 0;
for (int i = 1; i <= k; i ++ ) res += H[i];
if (res > 1ll * E * k) make_b(G, L, mid), L = mid + 1;
else make_a(G, mid + 1, R), R = mid;
}
ans[mid0] = L;
G = F;
make_b(G, mid0, l1 - 1), make_a(G, L + 1, r1);
sol(l0, mid0 - 1, l1, L, G);
G = F;
make_a(G, l0, mid0), make_b(G, r0 + 1, L - 1);
sol(mid0 + 1, r0, L, r1, G);
}
}
void solve() {
scanf("%d%d%d", &n, &k, &E);
for (int i = 1; i <= n; i ++ ) scanf("%d%d%d", &v[i], &a[i], &b[i]);
vector<int> F(k + 1);
sol(1, n + 1, 1, n + 1, F);
long long res = 0;
for (int i = 1; i <= n; i ++ )
res += n - ans[i] + 1;
printf("%lld\n", res);
}
int main() {
int T = 1;
while (T -- ) solve();
return 0;
}
$\texttt{D6B.璀璨冒险人}$
题目描述
难度：★★
汉诺塔。给出初始第 $i$ 小的圆盘在哪根柱子上，回答将所有圆盘放到第三根柱子上的最少操作次数。
$1\leq n\leq 10^6,1\leq a_i \leq 3$。
思路
设 $dp_{i,0/1/2}$ 表示将 $1\sim i$ 整体放到第 $1/2/3$ 根柱子上的最小操作数。
直接 $dp$ 即可。
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bitset<1000010> f[3];
int id[3] = {0, 1, 2};
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) {
int a;
scanf("%d", &a);
a -- ;
f[id[(a + 1) % 3]][i - 1] = 1;
f[id[(a + 2) % 3]][i - 1] = 1;
swap(id[(a + 1) % 3], id[(a + 2) % 3]);
}
int st = 0;
for (int i = n; i >= 0; i -- ) {
if (f[id[2]][i]) {
st = 1;
}
if (st) cout << f[id[2]][i];
}
if (!st) puts("0");
return 0;
}
$\texttt{D6C.蜃楼}$
题目描述
难度：★★★★
给定 $n$，面值为 $i\space (1\leq i\leq n)$ 的硬币共有 $a_i$ 个，求能组成的金额数量。
$1\leq n\leq 100，0\leq a_i \leq 10^9$。
思路
设 $s$ 表示 $\sum_{i=1}^n i\times a_i$，$p$ 表示 $a_i$ 最大的 $i$。
设 $f_i$ 表示是否有金额为 $i$ 的组合。
那么对于 $i\in [n^3,s-n^3]$，$f$ 具有 $p$ 的周期。
证明：
只要证明对于所有满足 $n^3\leq k \leq k + p\leq s-n^3$ 的 $k$ 满足 $f_k = f_{k+p}$。若 $i$ 个面值为 $j$ 和 $j$ 个面值为 $i$ 是等价的，首先证明若 $f_k=1$，$f_{k+p}=1$，若存在一种 $k$ 的方案使得面值 $p$ 不足 $a_p$，那么直接 $a_p$ 加一即可；否则由于 $k+p\leq s-n^3$，所以一定存在一个 $j$ 满足还剩下至少 $p$ 个，那么加入 $p$ 个 $j$，再去掉 $j-1$ 个 $p$ 即可组成 $k+p$。
同理若 $f_{k+p} = 1$，则 $f_k=1$ 可以证明。
于是 $f_k=f_{k+p}$。
证毕。
我们将值域缩小到了 $2n^3$，用 $bitset$ 做二进制分组多重背包即可。
时间复杂度 $O(n^4\log n/\omega)$。
代码
#include <bits/stdc++.h>
#define i64 long long
using namespace std;
bitset<2000005> f;
int main() {
int n;
scanf("%d", &n);
int mx = 0, p;
long long s = 0;
vector<int> a(n + 5);
for (int i = 1; i <= n; i ++ ) {
scanf("%d", &a[i]);
s += 1ll * i * a[i];
if (a[i] > mx) {
p = i;
mx = a[i];
}
}
f[0] = 1;
for (int i = 1; i <= n; i ++ ) {
vector<int> v;
int pos = 0;
for (int j = 22; j >= 0; j -- )
if (a[i] >> j & 1) {
pos = j; break;
}
for (int j = pos - 1; j >= 0; j -- ) v.push_back(i << j);
v.push_back(1ll * (a[i] - ((1 << pos) - 1)) * i);
for (int k : v) f |= f << k;
}
if (s <= 2 * n * n * n) {
i64 ans = 0;
for (int i = 0; i <= s; i ++ ) ans += f[i];
printf("%lld\n", ans);
} else {
i64 ans = 0;
for (int i = 0; i < n * n * n; i ++ ) ans += f[i] << 1;
i64 len = s - 2 * n * n * n + 1;
vector<int> b(p + 5);
for (int i = n * n * n; i < n * n * n + p; i ++ ) b[i - n * n * n + 1] = f[i];
for (int i = 1; i <= p; i ++ ) b[i] += b[i - 1];
ans += len / p * b[p] + b[len % p];
printf("%lld\n", ans);
}
return 0;
}
$\texttt{E1C.冒险家}$
题目描述
难度：★★★★★
给定一棵树，树上 $n$ 个点，每个点有权值 $a_i$，宝藏会藏在树上一些节点上，已知相邻两个节点不会同时藏有宝藏。
一种藏宝方案的价值为树上藏有宝藏节点权值之和。
设 $M = \sum a_i$，求对于 $x \in [0,M]$，有多少种藏宝方案的价值为 $x$，答案对 $10^9+7$ 取模。
$n\leq 100，a_i\leq 10^5，M\leq 10^5。$
思路
普通的子树 $dp$ 复杂度是 $O(nm^2)$，由于 $m$ 过大，我们考虑 改变dp顺序，设 $f_{i,j}$ 表示，$dfn$ 序小于点 $i$ 的点宝藏方案，那么我们每次只会加入一个点。
设 $f_{i,j, k}$ 表示 $dfn$ 序小于点 $i$ 的点上宝藏，且 $i$ 祖先中的点能否有宝藏的状态为 $j$，宝藏值为 $k$ 的方案数，复杂度 $O(n2^nm)$。
然后思考如何限制宝藏位置不相邻，我们考虑点分树，先对原图建立点分树，发现如果原树上是父子关系，那么点分树上一定是祖孙关系，于是我们点分树上每个点只有 $O(\log n)$ 个祖先，
最后复杂度 $O(n^2m)$。
代码
#include <bits/stdc++.h>
#define i64 long long
using namespace std;
const int N = 110, M = 100010, mod = 1e9 + 7;
int h[N], h2[N], e[N * 4], ne[N * 4], vis[N], idx;
int f[2][1 << 7][M], sum;
int p[N], id[N], dep[N], tot;
vector<int> to[N];
void add(int *a, int *b, int c) {
for (int i = sum; i >= c; i -- )
a[i] = (a[i] + b[i - c]) % mod;
}
void addedge(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void addedge2(int a, int b) {
e[idx] = b, ne[idx] = h2[a], h2[a] = idx ++ ;
}
int ask_siz(int u, int fa) {
int siz = 1;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa || vis[j]) continue;
siz += ask_siz(j, u);
}
return siz;
}
int find(int u, int fa, int all, int &d) {
int siz = 1, mx = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa || vis[j]) continue;
int t = find(j, u, all, d);
siz += t, mx = max(mx, t);
}
if (mx <= all / 2 && all - siz <= all / 2) d = u;
return siz;
}
void build_tree(int u) {
vis[u] = 1;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (vis[j]) continue;
int d;
find(j, u, ask_siz(j, u), d);
p[d] = u;
build_tree(d);
}
}
void dfs(int u) {
id[++ tot] = u;
for (int i = h2[u]; ~i; i = ne[i]) {
int j = e[i];
dep[j] = dep[u] + 1;
dfs(j);
}
}
int main() {
int n;
scanf("%d", &n);
vector<int> w(n + 10);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]), sum += w[i];
memset(h, -1, sizeof h);
memset(h2, -1, sizeof h2);
vector<pair<int, int>> edge(n + 5);
for (int i = 1; i < n; i ++ ) {
int a, b;
scanf("%d%d", &a, &b);
addedge(a, b), addedge(b, a);
edge[i] = {a, b};
}
int rt;
find(1, 0, n, rt);
build_tree(rt);
for (int i = 1; i <= n; i ++ )
if (i != rt)
addedge2(p[i], i);
dfs(rt);
for (int i = 1; i < n; i ++ ) {
int a = edge[i].first, b = edge[i].second;
if (dep[a] > dep[b]) swap(a, b);
to[b].push_back(a);
}
f[tot + 1 & 1][0][0] = 1;
for (int i = tot + 1; i >= 2; i -- ) {
for (int j = 0; j < (1 << dep[id[i + 1]]); j ++ )
for (int k = 0; k <= sum; k ++ )
f[i - 1 & 1][j][k] = 0;
for (int j = 0; j < (1 << dep[id[i]]); j ++ ) {
add(f[i - 1 & 1][j & ((1 << dep[id[i - 1]]) - 1)], f[i & 1][j], 0);
if (!(j >> dep[id[i - 1]] & 1)) {
int tmp = j & ((1 << dep[id[i - 1]]) - 1);
for (int k : to[id[i - 1]]) tmp |= 1 << dep[k];
add(f[i - 1 & 1][tmp], f[i & 1][j], w[id[i - 1]]);
}
}
}
for (int i = 0; i <= sum; i ++ ) printf("%d\n", f[1][0][i]);
return 0;
}
$\texttt{E2C.找箱子}$
题目描述
难度：★★★★
给定 $n$ 个箱子，每个箱子有一个编号但是你不知道。
给定 $m$ 个时刻，第 $i$ 个时刻会给出 $x,y$ 表示 $x$ 的编号小于 $y$ 的。
对于每一个点，求在什么时刻，它的编号被确定，始终没确定输出 $-1$。
$n\leq 2\times 10^5, m\leq 10^6$。
思路
问题简化为每次加有向边，求每一个点什么时候在拓扑序上确定。
我们先对最终图做一遍拓扑序，虽然有些点不确定，设 $a_i$ 表示 $i$ 的拓扑编号。
若一个点 $x$ 确定，那么对于所有 $a_i < a_x$，存在一条链 $i->j_1->j_2…->x$，对于 $a_i>a_x$ 同理。
若 $x$ 拓扑序确定，那么 $j_1$ 也一定有这么一条链，于是条件拆成 $x$ 对 $j_1$ 成立，且存在边 $(i,j_1)$，我们只需要事实维护 $i$ 后继中拓扑序最靠前的 $suf_i$ 即可，条件为 $a_{suf_i} \leq a_x$。
那么只需对动态维护 $a_i<a_x$ 中满足 $a_{suf_i} \leq a_x$ 的数量和 $a_i>a_x$ 中满足 $a_{pre_i} \ge a_x$ 的数量，这个用线段树维护即可。
时间复杂度 $O(n\log n)$，巧妙运用了依赖性。
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 200010, M = 1000100;
int n, m, mx[N << 2], pos[N << 2], tag[N << 2];
int d[N], id[N], a[N], ans[N];
int h[N], e[M], ne[M], idx;
void addedge(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void topsort() {
queue<int> q;
for (int i = 1; i <= n; i ++ ) {
if (!d[i]) q.push(i);
}
int tt = 0;
while (q.size()) {
int t = q.front();
q.pop();
id[++ tt] = t;
a[t] = tt;
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (-- d[j] == 0) q.push(j);
}
}
}
void build(int u, int l, int r) {
if (l == r) {
pos[u] = l;
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pos[u] = pos[u << 1];
}
void modify(int u, int l, int r, int s, int t, int v) {
if (s <= l && r <= t) return mx[u] += v, tag[u] += v, void();
if (tag[u] != 0) {
mx[u << 1] += tag[u], tag[u << 1] += tag[u];
mx[u << 1 | 1] += tag[u], tag[u << 1 | 1] += tag[u];
tag[u] = 0;
}
int mid = l + r >> 1;
if (s <= mid) modify(u << 1, l, mid, s, t, v);
if (t > mid) modify(u << 1 | 1, mid + 1, r, s, t, v);
mx[u] = max(mx[u << 1], mx[u << 1 | 1]);
if (mx[u << 1] == mx[u]) pos[u] = pos[u << 1];
else pos[u] = pos[u << 1 | 1];
}
int main() {
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
vector<pair<int, int>> rin(m + 5);
for (int i = 1; i <= m; i ++ ) {
int x, y;
scanf("%d%d", &x, &y);
addedge(x, y);
d[y] ++ ;
rin[i] = {x, y};
}
memset(ans, -1, sizeof ans);
topsort();
build(1, 1, n);
vector<int> suf(n + 10, n + 1), pre(n + 10);
for (int i = 1; i <= m; i ++ ) {
int x = rin[i].first, y = rin[i].second;
if (a[y] < suf[x]) {
modify(1, 1, n, a[y], suf[x] - 1, 1);
suf[x] = a[y];
}
if (a[x] > pre[y]) {
modify(1, 1, n, pre[y] + 1, a[x], 1);
pre[y] = a[x];
}
while (mx[1] == n - 1) {
ans[id[pos[1]]] = i;
modify(1, 1, n, pos[1], pos[1], -2 * m);
}
}
for (int i = 1; i <= n; i ++ ) printf("%d ", ans[i]);
return 0;
}
$\texttt{E3C.对称差}$
题目描述
难度：★★★★
初始给定 $n$ 个集合，第 $i$ 个集合里面只有一个数字 $i$。
你需要维护 $q$ 次操作，第 $i$ 次操作给出一对 $a_i,b_i$，你需要将 $a_i,b_i$ 两个集合做对称差（可以理解成异或运算），存入一个新的集合，令新的集合编号为 $n+i$。
对于每次操作，如果产生的新集合大小大于 $k$ ，输出 $−1$。否则输出一个数字 $sz$ 表示集合大小，接着在同一行内升序输出输出 $sz$ 个数字表示集合内的数。
$1\leq n,q\leq 5\times 10^5,k\leq 3$。
思路
若 $k=1$，那么对于每一数字 $i$，随机一个 $w_i$ 作为其哈希值，然后集合哈希值为 $f(S)=\bigoplus_{i\in S}w_i$，然后哈希即可。
若 $k=2$，我们将点定为黑点或白点，一定存在某种分发使得，$S$ 和 $T$ 的两个不同的数颜色不同，设 $f(S)$ 表示黑点的哈希值，$g(S)$ 表示白点的哈希值，然后哈希。
分类的时候可以使用二进制分组，就是枚举每一个二进制位，为 $0$ 的为黑点，为 $1$ 的为白点。
若 $k=3$，仿照 $k=2$ 的做法，若分类后一黑二白或一白二黑，那么将单独的那个直接取出来，再转为 $k=2$ 的做法，复杂度 $O(n\log n)$。
代码
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define i64 long long
using namespace std;
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
template <class I>
inline void gi (I &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
// print a signed integer
template <class I>
inline void print (I x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: gi;//use gi to input a signed integer,putc to output a char,print to output a signed integer
using io :: putc;
using io :: print;
mt19937_64 rnd(random_device{}());
i64 rd() {
return rnd() >> 2;
}
i64 w[500010];
struct SelfHash {
#define U (1<<24)
int t[1 << 24];
inline int operator [] (i64 x) {
int hh = x & U - 1;
return (w[t[hh]] ^ x) ? 0 : t[hh];
return t[hh];
}
inline void add(i64 x, int y) {
t[x & U - 1] = y;
}
#undef U
} HA;
i64 c1[22][1000010], c2[22][1000010];
int main() {
int n, q, k;
scanf("%d%d%d", &n, &q, &k);
vector<int> a(q + 5), b(q + 5);
for (int i = 1; i <= q; i ++ ) {
gi(a[i]); gi(b[i]);
}
if (k <= 3) {
vector<int> g(q + 5);
for (int i = 1; i <= n; i ++ ) w[i] = ((rd() >> 20) << 20) | i;
for (int i = 1; i <= n; i ++ ) HA.add(w[i], i);
for (register int j = 0; j < 20; j ++ ) {
for (int i = 1; i <= n; i ++ )
if (i >> j & 1) c1[j][i] = w[i];
else c2[j][i] = w[i];
for (register int i = 1; i <= q; i ++ ) {
c1[j][n + i] = c1[j][a[i]] ^ c1[j][b[i]];
c2[j][n + i] = c2[j][a[i]] ^ c2[j][b[i]];
}
}
for (int i = 1; i <= q; i ++ ) {
set<int> ans;
int flg = 0;
while (ans.size() <= k) {
int mark = 0, st = 0;
for (int j = 0; j < 20; j ++ ) {
i64 t1 = HA[c1[j][n + i]], t2 = HA[c2[j][n + i]];
if (!c1[j][n + i] && !c2[j][n + i]) {
st = 1;
break;
}
if (t1) {
if (!ans.count(t1)) {
ans.insert(t1);
for (int jj = 0; jj < 20; jj ++ )
if (t1 >> jj & 1) c1[jj][n + i] ^= w[t1];
else c2[jj][n + i] ^= w[t1];
}
mark = 1;
break;
} if (t2) {
if (!ans.count(t2)) {
ans.insert(t2);
for (int jj = 0; jj < 20; jj ++ )
if (t2 >> jj & 1) c1[jj][n + i] ^= w[t2];
else c2[jj][n + i] ^= w[t2];
}
mark = 1;
break;
}
}
if (st) break;
if (!mark) {flg = 1; break;}
}
if (flg || ans.size() == k + 1) {
puts("-1");
} else {
printf("%d ", ans.size());
for (auto i : ans) printf("%d ", i);
puts("");
}
}
}
return 0;
}
