前言
博主参加了NOI2020的同步赛，赛场上原本每天的t1都稳到手，无奈一题被卡常，一题输出输反了，最后得到了65pts的好成绩。d1t2想到了dp再优化，奈何手速慢了（老年选手）没得到分。两天t1都没看清数据范围每天都丢了1h花在无意义的思考上。值得反思。
总而言之，今年的NOI比较偏向于考察思维，代码量有长有短。
美食家
首先很容易想到DP
[f_{i,v}=max{f_{i-w,u}}+c_v[+y_j]
]
这里(y_j)根据题意当(i=t_j)且(v=x_j)时产生的额外贡献。
仔细观察(wleqslant 5)，这点很重要。容易联想到动态DP，这里用一个(wn imes wn)的矩阵维护转移，因为(max)对加法满足结合律，且只有(kleqslant 200)项转移比较特殊，其他的直接预处理出来连续的一段转移矩阵即可，复杂度(mathcal O((nw)^3klog n))，无法通过。
对于转移矩阵(A)，维护(A^{2^i})，将一段连续的转移分解并且往向量上乘，复杂度降为(mathcal O((nw)^3log n+(nw)^2klog n))，可以通过本题。注意常数。
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a, i##end = b; i <= i##end; ++i)
#define per(i, a, b) for (int i = a, i##end = b; i >= i##end; --i)
#define rep0(i, a) for (int i = 0, i##end = a; i < i##end; ++i)
#define per0(i, a) for (int i = (int)a-1; ~i; --i)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define chkmax(a, b) a = max(a, b)
#define chkmin(a, b) a = min(a, b)
#define x first
#define y second
#define enter putchar('
')
typedef long long ll;
inline int read() {
int w = 0, f = 1; char c;
while (!isdigit(c = getchar())) c == '-' && (f = -1);
while (isdigit(c)) w = w*10+(c^48), c = getchar();
return w * f;
}
const int maxL = 255;
const int maxn = 55;
const int maxk = 205;
const int inf = 1<<30;
struct Matrix {
ll a[maxL][maxL];
int n, m;
ll *operator [] (int i) { return a[i]; }
};
Matrix operator * (Matrix A, Matrix B) {
Matrix C; C.n = A.n, C.m = B.m;
rep0(i, A.n) rep0(j, B.m) C[i][j] = -1ll*inf*inf;
rep0(k, A.m)
rep0(i, A.n)
rep0(j, B.m)
C[i][j] = max(C[i][j], A[i][k] + B[k][j]);
return C;
}
int n, m, T, k;
int c[maxn], L, t[maxk], lst[maxk];
Matrix A[32], B[maxk], x;
bool cmp(int a, int b) { return t[a] < t[b]; }
void jump(int d) {
rep(j, 0, L)
if (d & (1<<j)) x = A[j]*x;
}
int main() {
n = read(), m = read(), T = read(), k = read();
L = log2(T);
rep0(i, n) c[i] = read();
A[0].n = A[0].m = 5*n;
rep0(i, A[0].n)
rep0(j, A[0].m)
A[0][i][j] = i == j+n ? 0 : -1ll*inf*inf;
rep(i, 1, m) {
int u = read()-1, v = read()-1, w = read()-1;
A[0][v][w*n+u] = c[v];
}
rep(i, 1, L) A[i] = A[i-1]*A[i-1];
rep(i, 1, k) {
t[lst[i] = i] = read(); int x = read()-1, y = read();
memcpy(&B[i], &A[0], sizeof(Matrix));
rep0(j, 5*n) if (B[i][x][j] != -inf) B[i][x][j] += y;
}
std::sort(lst+1, lst+k+1, cmp);
x.n = 5*n, x.m = 1;
rep0(i, x.n) x[i][0] = i ? -inf : 0;
rep(i, 1, k) {
jump(t[lst[i]] - t[lst[i-1]] - 1);
x = B[lst[i]]*x;
}
jump(T - t[lst[k]]);
printf("%lld", max(-1ll, x[0][0] + c[0]));
return 0;
}
命运
上来就想到容斥，但感觉不太能做，注意到(u_i)一直是(v_i)的祖先，不难想到这样的DP：设(f_{i,j})表示节点(i)处目前往上(j)条边之前必选一条边的状态，先考虑链的转移
[egin{cases}f_{i,j}=f_{son,j+1}&jleqslant up_i\f_{i,up_i}=sum_{j>0}f_{son,j}+sum_{j>up_i}f_{son,j}end{cases}
]
其中(up_i)表示当前节点(v_j)对应(u_j)对深度限制的最大值，即(up_i=dep_i-max{dep_{u_j}},forall v_j=i)。选边对应了前面部分对转移，不选边对应后面部分的转移。
对于分叉的转移，假设有(f_x)和(f_y)两个转移数组，合并一定有
[f_x'=f_x imes suf_{g_{x+1}}+g_x imes suf_{f_{x+1}}+f_x imes g_x
]
对于(f_x)和(g_x)，有值的位置需要合并到一起，这里使用线段树合并解决问题。需要的操作：单点修改、区间查询、区间清零、合并。注意区间操作全部可以变成后缀操作，其次对于下标平移提前算好，偏移量与深度有关。
复杂度(mathcal O(nlog n))。可能有些卡常。
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a, i##end = b; i <= i##end; ++i)
#define per(i, a, b) for (int i = a, i##end = b; i >= i##end; --i)
#define rep0(i, a) for (int i = 0, i##end = a; i < i##end; ++i)
#define per0(i, a) for (int i = (int)a-1; ~i; --i)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define chkmax(a, b) a = max(a, b)
#define chkmin(a, b) a = min(a, b)
#define x first
#define y second
#define pb push_back
#define mp std::make_pair
#define enter putchar('
')
typedef long long ll;
inline int read() {
int w = 0, f = 1; char c;
while (!isdigit(c = getchar())) c == '-' && (f = -1);
while (isdigit(c)) w = w*10+(c^48), c = getchar();
return w * f;
}
const int maxn = 500005;
const int P = 998244353;
struct Edge {
int v, nxt;
} e[maxn*2];
int G[maxn], edges;
void init() { edges = 0; memset(G, -1, sizeof G); }
void adde(int u, int v) { e[edges++] = (Edge){v, G[u]}; G[u] = edges-1; }
int n, m;
int inc(int a, int b) { return (a += b) >= P ? a-P : a; }
int mul(int a, int b) { return 1ll*a*b%P; }
int lc[maxn*20], rc[maxn*20], tag[maxn*20], sumv[maxn*20], tot = 0, rt[maxn];
int newnode() { return tag[++tot] = 1, tot; }
void pushdown(int o) {
if (lc[o]) tag[lc[o]] = mul(tag[lc[o]], tag[o]), sumv[lc[o]] = mul(sumv[lc[o]], tag[o]);
if (rc[o]) tag[rc[o]] = mul(tag[rc[o]], tag[o]), sumv[rc[o]] = mul(sumv[rc[o]], tag[o]);
tag[o] = 1;
}
void pushup(int o) { sumv[o] = inc(sumv[lc[o]], sumv[rc[o]]); }
void reset(int &o, int l, int r, int p) {
if (!o || r < p) return;
if (p <= l) { tag[o] = sumv[o] = 0; return; }
pushdown(o);
int mid = l+r>>1;
reset(lc[o], l, mid, p), reset(rc[o], mid+1, r, p);
pushup(o);
}
void modify(int &o, int l, int r, int p, int v) {
if (!o) o = newnode();
if (l == r) { sumv[o] = inc(sumv[o], v); return; }
pushdown(o);
int mid = l+r>>1;
p <= mid ? modify(lc[o], l, mid, p, v) : modify(rc[o], mid+1, r, p, v);
pushup(o);
}
void merge(int &x, int y, int l, int r, int fs, int gs) {
if (!x && !y) return;
if (!x) { x = y, sumv[x] = mul(sumv[x], fs), tag[x] = mul(tag[x], fs); return; }
else if (!y) { sumv[x] = mul(sumv[x], gs); tag[x] = mul(tag[x], gs); return; }
if (l == r) {
sumv[x] = inc(inc(mul(sumv[x], gs), mul(sumv[y], fs)), mul(sumv[x], sumv[y]));
return;
}
pushdown(x), pushdown(y);
int mid = l+r>>1;
merge(lc[x], lc[y], l, mid, inc(fs, sumv[rc[x]]), inc(gs, sumv[rc[y]])), merge(rc[x], rc[y], mid+1, r, fs, gs);
pushup(x);
}
int query(int o, int l, int r, int p) {
if (!o || r < p) return 0;
if (p <= l) return sumv[o];
pushdown(o);
int mid = l+r>>1;
return inc(query(lc[o], l, mid, p), query(rc[o], mid+1, r, p));
}
std::vector<int> A[maxn];
int dep[maxn];
void dp(int u, int f) {
dep[u] = dep[f]+1;
int offset = n-dep[u], up = dep[u];
rep0(i, A[u].size()) if (dep[A[u][i]]) chkmin(up, dep[u]-dep[A[u][i]]);
if (e[G[u]].v == f && e[G[u]].nxt == -1) return modify(rt[u], 1, n, offset+up, 1);
for (int i = G[u]; ~i; i = e[i].nxt) {
int v = e[i].v;
if (v == f) continue;
dp(v, u);
modify(rt[v], 1, n, offset+up, inc(query(rt[v], 1, n, offset), query(rt[v], 1, n, offset+up+1)));
reset(rt[v], 1, n, offset+up+1);
if (rt[u]) merge(rt[u], rt[v], 1, n, 0, 0); else rt[u] = rt[v];
}
}
int main() {
n = read(); init();
rep(i, 2, n) {
int u = read(), v = read();
adde(u, v), adde(v, u);
}
m = read();
rep(i, 1, m) {
int x = read(), y = read();
A[y].pb(x);
}
dp(1, 1);
printf("%d", query(rt[1], 1, n, n));
return 0;
}
时代的眼泪
不会正解
制作菜品
理解清题目后很容易发现结论：如果(n=m+1)种原材料做(m)道菜（这里保证(sum d_i=m imes k)），则一定保证有解，因为一定有一种材料质量(d_ileqslant k)，每次选择这份材料加上最大的那一种材料一定可以凑出来(k)（否则一定能推出矛盾，如果追求严谨性）。除了最后一把一定能消掉两种材料，前面每一次都能消掉一种材料。对于(nleqslant m)种原材料显然可以拆分成(m+1)部分，同样有解。
如果(n+2)种原材料做(m)道菜？不难想到将这些原材料划分成两部分(S)和(T)，使得(sum_{iin S}d_i=(|S|-1) imes k)以及(sum_{iin T}d_i=(|T|-1) imes k)（保证其一则另外一个也能成立），不难证明这是有解的充要条件。
由于数据中(n-2leqslant m)（博主同步赛没看到这个条件白费了1h多），问题只需要分成上面两类。第一类根据证明非常好解决，复杂度(O(nm))。现在考虑第二类，问题是：是否存在子集(S)，使得(sum_{iin S}d_i=(|S|-1) imes k)，改写该式
[sum_{iin S}d_i-k=-k
]
变成带负下标的01背包问题了。对于求出一组解，根据转移决策点反推出结合(S)和(overline S)，变成问题1，否则一定无解。由于(nleqslant 500)，(kleqslant 5000)，所以情况2中背包大小为(nk)，复杂度(mathcal O(n^2k))，仍然无法通过。
注意到这里背包只需要判定不需要求最优解，可以使用bitset优化，综上总复杂度最坏为(mathcal O(Tn^2k/w))，可以通过此题。
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a, i##end = b; i <= i##end; ++i)
#define per(i, a, b) for (int i = a, i##end = b; i >= i##end; --i)
#define rep0(i, a) for (int i = 0, i##end = a; i < i##end; ++i)
#define per0(i, a) for (int i = (int)a-1; ~i; --i)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define chkmax(a, b) a = max(a, b)
#define chkmin(a, b) a = min(a, b)
#define x first
#define y second
#define enter putchar('
')
typedef long long ll;
inline int read() {
int w = 0, f = 1; char c;
while (!isdigit(c = getchar())) c == '-' && (f = -1);
while (isdigit(c)) w = w*10+(c^48), c = getchar();
return w * f;
}
using std::vector;
using std::pair;
using std::make_pair;
const int maxn = 505;
const int offset = 2500005;
int n, m, k;
int b[maxn], d[maxn];
std::bitset<5000010> f[maxn];
void solve(vector<pair<int, int> > &A, int n) {
rep(i, 1, n) {
int maxi = -1, mini = -1;
rep0(i, A.size()) {
if (A[i].x && (mini == -1 || A[i].x < A[mini].x)) mini = i;
if (A[i].x && (maxi == -1 || A[i].x >= A[maxi].x)) maxi = i;
}
if (A[mini].x >= k) {
printf("%d %d
", A[mini].y, k);
A[mini].x -= k;
}
else {
printf("%d %d %d %d
", A[mini].y, A[mini].x, A[maxi].y, k-A[mini].x);
A[maxi].x -= k-A[mini].x; A[mini].x = 0;
}
}
}
int main() {
for (int T = read(); T; T--) {
n = read(), m = read(), k = read();
rep(i, 1, n) d[i] = read();
if (n == m+2) {
f[0].reset(); f[0][offset + k] = 1;
memset(b, 0, sizeof b);
int ok = 0;
rep(i, 1, n) {
int x = d[i]-k;
f[i] = f[i-1] | (x < 0 ? (f[i-1] >> (-x)) : (f[i-1] << x));
if (f[i][offset]) {
ok = 1;
for (int pt = offset, j = i; j; j--)
if (f[j-1][pt - d[j] + k]) b[j] = 1, pt -= d[j] - k;
break;
}
}
if (!ok) printf("-1
");
else {
vector<pair<int, int> > A, B;
rep(i, 1, n) if (b[i]) A.push_back(make_pair(d[i], i)); else B.push_back(make_pair(d[i], i));
solve(A, A.size() - 1), solve(B, B.size() - 1);
}
} else {
vector<pair<int, int> > A;
rep(i, 1, n) A.push_back(make_pair(d[i], i));
solve(A, m);
}
}
return 0;
}
超现实树
在清楚地读完题面后以及观察数据和范围后，很快会想到三棵树合并的思路：其他部分一样，仅仅树的某一个位置上，一棵树有左叶子，一棵树有右叶子，一棵树左右叶子都有，将三棵树合并成一棵树，删掉左右叶子。通过哈希来判断三棵树是否有这样的差异，复杂度(mathcal O(n))。然而这个方法连样例5都跑不过去，只能拿到40pts的好成绩，仔细跑一跑深度=3的情况，造一造数据发现这个方法能被卡掉。
博主在这个基础上改写了某些部分，比如加强了判定，把一些漏洞判掉了，貌似没有问题了，仍然只有48pts。
阅读题解后发现门摸偏了。设所有树中最大高度为(D)，有一个结论：对于一条链，如果仅仅在链上添加叶子，得到的树称为树枝，显然深度为(D)的树枝的数量只有(2^{2(D-1)})种，如果所有深度为(D)的树枝都能被生成出来，那么一定是完备的。这个结论很重要。
于是只需要判断所有树枝能否被生成出来，可以采取合并的方式，这里合并不能按照三棵树合并的方法，这样只有72pts，要将含有两片叶子的树拆分成两种树枝（最后一个节点在左和在右），然后按照四棵树的规则合并。因为三棵树中含有两片叶子的树无法区分左叶子还是右叶子能全部生成出来对应所有树枝。
可以采用哈希，更简单的方法是使用递归合并。复杂度(mathcal O(n))。
// 哈希
#include <bits/stdc++.h>
#include <tr1/unordered_map>
#define rep(i, a, b) for (int i = a, i##end = b; i <= i##end; ++i)
#define per(i, a, b) for (int i = a, i##end = b; i >= i##end; --i)
#define rep0(i, a) for (int i = 0, i##end = a; i < i##end; ++i)
#define per0(i, a) for (int i = (int)a-1; ~i; --i)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define chkmax(a, b) a = max(a, b)
#define chkmin(a, b) a = min(a, b)
#define x first
#define y second
#define pb push_back
#define mp std::make_pair
#define enter putchar('
')
typedef long long ll;
inline int read() {
int w = 0, f = 1; char c;
while (!isdigit(c = getchar())) c == '-' && (f = -1);
while (isdigit(c)) w = w*10+(c^48), c = getchar();
return w * f;
}
using std::tr1::unordered_map;
using std::vector;
const int maxn = 2000005;
const int P0 = 998244353, P1 = 1004535809;
unordered_map<int, int> H0, H1;
int n, dep[maxn*4], h0[maxn*4], h1[maxn*4];
vector<int> T[maxn*4], Q[maxn];
int ch[maxn][2], sz[maxn];
bool dfs1(int u) {
sz[u] = 1; int ans = 1;
if (ch[u][0]) ans &= dfs1(ch[u][0]), sz[u] += sz[ch[u][0]];
if (ch[u][1]) ans &= dfs1(ch[u][1]), sz[u] += sz[ch[u][1]];
return ans && min(sz[ch[u][0]], sz[ch[u][1]]) <= 1;
}
void dfs2(int u, int x) {
if (!ch[u][0] && !ch[u][1]) return;
dep[x]++;
if (sz[ch[u][0]] >= sz[ch[u][1]]) T[x].pb(sz[ch[u][1]]<<1), dfs2(ch[u][0], x);
else T[x].pb(sz[ch[u][0]]<<1|1), dfs2(ch[u][1], x);
}
int main() {
for (int N = read(); N; N--) {
int m = read(), up = 0, u;
rep(i, 1, m) {
int size = read();
rep(j, 1, size) ch[j][0] = read(), ch[j][1] = read();
if (dfs1(1)) {
dfs2(1, n), Q[dep[n]].pb(n), chkmax(up, dep[n]);
rep0(j, T[n].size()) h0[n] = (4ll*h0[n]+T[n][j])%P0, h1[n] = (4ll*h1[n]+T[n][j])%P1;
if (T[n].size() && T[n][T[n].size()-1] == 2) {
n++; Q[dep[n] = dep[n-1]].pb(n);
rep0(i, T[n-1].size()) T[n].pb(T[n-1][i]);
T[n][T[n].size()-1] = 3;
rep0(j, T[n].size()) h0[n] = (4ll*h0[n]+T[n][j])%P0, h1[n] = (4ll*h1[n]+T[n][j])%P1;
}
n++;
}
}
for (;;) {
while (up && Q[up].empty()) up--;
if (!up) break;
H0.clear(), H1.clear();
rep0(i, Q[up].size()) u = Q[up][i], H0[h0[u]] = 1, H1[h1[u]] = 1;
while (!Q[up].empty()) {
int u = Q[up][Q[up].size()-1]; Q[up].pop_back();
if (T[u][T[u].size()-1]) continue;
if (H0.find((h0[u]+1)%P0) != H0.end() && H1.find((h1[u]+1)%P1) != H1.end() && H0.find((h0[u]+2)%P0) != H0.end() && H1.find((h1[u]+2)%P1) != H1.end() && H0.find((h0[u]+3)%P0) != H0.end() && H1.find((h1[u]+3)%P1) != H1.end()) {
rep0(i, (int)T[u].size()-1) T[n].pb(T[u][i]);
rep0(j, T[n].size()) h0[n] = (4ll*h0[n]+T[n][j])%P0, h1[n] = (4ll*h1[n]+T[n][j])%P1;
Q[dep[n] = dep[u]-1].pb(n), n++;
}
}
}
printf("%s
", Q[0].size() ? "Almost Complete" : "No"); Q[0].clear();
rep0(i, n) T[i].clear(), dep[i] = h0[i] = h1[i] = 0;
}
return 0;
}
// 递归
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a, i##end = b; i <= i##end; ++i)
#define per(i, a, b) for (int i = a, i##end = b; i >= i##end; --i)
#define rep0(i, a) for (int i = 0, i##end = a; i < i##end; ++i)
#define per0(i, a) for (int i = (int)a-1; ~i; --i)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define chkmax(a, b) a = max(a, b)
#define chkmin(a, b) a = min(a, b)
#define x first
#define y second
#define pb push_back
#define mp std::make_pair
#define enter putchar('
')
typedef long long ll;
inline int read() {
int w = 0, f = 1; char c;
while (!isdigit(c = getchar())) c == '-' && (f = -1);
while (isdigit(c)) w = w*10+(c^48), c = getchar();
return w * f;
}
const int maxn = 2000005;
using std::vector;
using std::pair;
vector<int> lc[maxn], rc[maxn];
vector<pair<int, int> > tmp;
bool dfs(vector<pair<int, int> > &A) {
if (A.empty()) return 0;
vector<pair<int, int> > A0, A1, A2, A3;
rep0(i, A.size()) {
int x = lc[A[i].x][A[i].y], y = rc[A[i].x][A[i].y];
if (!x && !y) return 1;
if (!y) A0.pb(mp(A[i].x, x));
else if (!x) A1.pb(mp(A[i].x, y));
else {
if (!lc[A[i].x][y] && !rc[A[i].x][y]) A2.pb(mp(A[i].x, x));
if (!lc[A[i].x][x] && !rc[A[i].x][x]) A3.pb(mp(A[i].x, y));
}
}
return dfs(A0) && dfs(A1) && dfs(A2) && dfs(A3);
}
int main() {
for (int T = read(); T; T--) {
int n = read(); tmp.clear();
rep0(i, n) {
int sz = read(); lc[i].resize(sz+1), rc[i].resize(sz+1);
rep(j, 1, sz) lc[i][j] = read(), rc[i][j] = read();
tmp.pb(mp(i, 1));
}
printf("%s
", dfs(tmp) ? "Almost Complete" : "No");
}
return 0;
}
翻修道路
这题也不会