比賽傳送門
正好跟cf時間撞上了，然而我太菜了cf的題做不出來，就來看了看牛客的題
真的好簡單啊…
A DongDong破密碼
題意：将一個01串 a a a（長度為 n n n）向右移動 m m m次，最後求出這 n + m − 1 n+m-1 n+m−1位每一位的異或值，得到一個新串 b b b。（這個描述不太清楚，建議看原題有張圖）現在給出串 b b b，請你求出原串 a a a。
題解： b [ i ] b[i] b[i]的值其實就代表了 a [ i − m + 1... i ] a[i-m+1...i] a[i−m+1...i]這一段區間上的 1 1 1的個數的奇偶性。維護一個字首和數組 s [ i ] s[i] s[i]表示 a a a串前 i i i位一共有多少個 1 1 1，那麼比較 b [ i ] b[i] b[i]與 s [ i − 1 ] − s [ i − m ] s[i - 1]-s[i-m] s[i−1]−s[i−m]的奇偶性就可以知道第 i i i位是否是 1 1 1。
#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>
template <typename T> inline void read(T& x) {
int f = 0, c = getchar(); x = 0;
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
if (f) x = -x;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
read(x); read(args...);
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
}
const int maxn = 1e6 + 7;
char str[maxn];
int ps[maxn], n, m;
int a[maxn], s[maxn];
int main() {
read(n, m);
scanf("%s", str + 1);
for (int i = 1; i <= n + m - 1; ++i) ps[i] = str[i] - '0';
for (int i = 1; i <= m; ++i) {
if (ps[i] ^ (s[i - 1] & 1)) a[i] = 1, s[i] = s[i - 1] + 1;
else a[i] = 0, s[i] = s[i - 1];
}
for (int i = m + 1; i <= n; ++i) {
if (ps[i] ^ ((s[i - 1] - s[i - m]) & 1)) a[i] = 1, s[i] = s[i - 1] + 1;
else a[i] = 0, s[i] = s[i - 1];
}
for (int i = 1; i <= n; ++i) write(a[i]);
return 0;
}
B DongDong認親戚
題意略。并查集裸題。可以用map将人名映射到編号。代碼略。
C DongDong跳一跳
題意：有 n n n根柱子，每根柱子都有一個高度和柱子上面魚幹的數量，一隻貓開始的時候可以選擇站在任意一根柱子上，每次跳躍不限長度而且隻能從左向右跳躍，但隻能跳到高度與目前所站高度差絕對值小于等于 m m m的柱子上。它會吃掉經過的柱子上的魚幹。請最大化這隻貓能吃到的魚幹數量（最終不一定要落在第n根柱子上）。
算法1：設 f i f_i fi表示它從左往右跳到 i i i号柱子上，最多能吃到多少魚幹。轉移顯然
f i = max f j + a i , 1 ≤ j < i , ∣ h j − h i ∣ ≤ m f_i=\max{f_j}+a_i,1\leq j<i,|h_j-h_i|\leq m fi=maxfj+ai,1≤j<i,∣hj−hi∣≤m
這樣做時間複雜度是 O ( n 2 ) O(n^2) O(n2)，不夠優秀。
發現這裡是一個二維數點，用線段樹優化即可。
具體一點：我們可以求出 l i = max ( 1 , h i − m ) , r i = h i + m l_i=\max(1,h_i-m),r_i=h_i+m li=max(1,hi−m),ri=hi+m，那麼我們必須從滿足 l i ≤ h j ≤ r i l_i\leq h_j\leq r_i li≤hj≤ri的 f j f_j fj中取一個最大的轉移過來，這就是區間查最大值，用線段樹維護一下就好。如果覺得空間有點緊，可以再離散化一下。
這個做法我沒寫，不過我看到有人寫了，就說一下。
算法2：改變狀态的定義。設 f ( i , j ) f(i,j) f(i,j)表示前 i i i個柱子中，跳到高度為 j j j的柱子上最多能吃多少。那麼
f ( i , j ) = max f ( i − 1 , k ) , l i ≤ k ≤ r i f(i,j)=\max{f(i-1,k)},l_i\leq k\leq r_i f(i,j)=maxf(i−1,k),li≤k≤ri
這時候轉移就變成了真正的區間最大值查詢，你還可以用線段樹優化，但也可以不用，因為這個區間長度是 O ( m ) O(m) O(m)的。然後我們發現 f ( i , ∗ ) f(i,*) f(i,∗)都是從 f ( i − 1 , ∗ ) f(i-1,*) f(i−1,∗)轉移的，是以 i i i這一維可以扔掉，那麼空間複雜度就可以接受了。
#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>
template <typename T> inline void read(T& x) {
int f = 0, c = getchar(); x = 0;
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
if (f) x = -x;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
read(x); read(args...);
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
}
template <typename T> inline void writeln(T x) { write(x); puts(""); }
template <typename T> inline bool chkmin(T& x, const T& y) { return y < x ? (x = y, true) : false; }
template <typename T> inline bool chkmax(T& x, const T& y) { return x < y ? (x = y, true) : false; }
typedef long long LL;
const int maxx = 1e6 + 7;
const int maxn = 2e5 + 7;
int h[maxn], a[maxn];
LL f[maxx];
int n, m, mh;
int main() {
read(n, m);
for (int i = 1; i <= n; ++i) read(h[i], a[i]), chkmax(mh, h[i]);
LL ans = 0;
for (int i = 1; i <= n; ++i) {
int l = std::max(1, h[i] - m), r = std::min(h[i] + m, mh);
LL *j = std::max_element(f + l, f + r + 1);
f[h[i]] = *j + a[i];
chkmax(ans, f[h[i]]);
}
writeln(ans);
return 0;
}
看到有很多人寫這個做法的時候是倒着枚舉 i i i的，事實上不需要吧？…因為這裡隻要高度差的絕對值在 m m m以内，是以從左往右還是從右往左都一樣吧。
D DongDong坐飛機
題意： n n n個點， m m m條有向邊，有邊權。你要從 1 1 1走到 n n n，并且途中有 k k k次機會可以将一條邊的代價減半，求最小代價。
題解：分層圖最短路模闆題。建 n ( k + 1 ) n(k+1) n(k+1)個點，結點 ( i , j ) (i,j) (i,j)表示你走到原圖中的點 i i i并且剩餘 j j j次減半機會。那麼我們就是要從 ( 1 , k ) (1,k) (1,k)走到 ( n , ∗ ) (n,*) (n,∗)。對于原圖中的一條邊 ( u , v , w ) (u,v,w) (u,v,w)，我們枚舉剩餘 i i i次減半機會，連邊 ( ( u , i ) , ( v , i − 1 ) , w / 2 ) ((u,i),(v,i-1),w/2) ((u,i),(v,i−1),w/2)表示使用減半機會，再連邊 ( ( u , i ) , ( v , i ) , w ) ((u,i),(v,i),w) ((u,i),(v,i),w)表示沒使用減半機會。然後跑最短路即可。
我寫的是zkw線段樹優化dijkstra求最短路。
#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>
template <typename T> inline void read(T& x) {
int f = 0, c = getchar(); x = 0;
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
if (f) x = -x;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
read(x); read(args...);
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
}
template <typename T> inline void writeln(T x) { write(x); puts(""); }
template <typename T> inline bool chkmin(T& x, const T& y) { return y < x ? (x = y, true) : false; }
template <typename T> inline bool chkmax(T& x, const T& y) { return x < y ? (x = y, true) : false; }
typedef long long LL;
const int maxn = 11e4 + 7;
const int maxm = 1e6 + 7;
const LL inf = 1e16;
int v[maxm], head[maxn], next[maxm], tot;
LL dist[maxn], w[maxm];
int mp[maxn << 2], M = 1;
int node[10007][17], cnt;
int n, K, m;
inline void ae(int x, int y, LL z) {
v[++tot] = y; w[tot] = z; next[tot] = head[x]; head[x] = tot;
}
inline int cmp(int a, int b) { return dist[a] < dist[b] ? a : b; }
inline void upd(int x) { mp[x] = cmp(mp[x << 1], mp[x << 1 | 1]); }
inline void build(int n) { while (M < n + 2) M <<= 1; mp[0] = n + 1; }
inline void del(int x) { for (mp[x += M] = 0, x >>= 1; x; upd(x), x >>= 1); }
inline void modify(int x, LL nv) { for (int i = x + M; dist[mp[i]] > nv; mp[i] = x, i >>= 1); dist[x] = nv; }
inline void dijkstra(int n, int s) {
for (int i = 0; i <= n; ++i) dist[i] = inf;
build(n); modify(s, 0);
for (int t = 1; t < n; ++t) {
int x = mp[1]; del(x);
for (int i = head[x]; i; i = next[i])
if (dist[v[i]] > dist[x] + w[i])
modify(v[i], dist[x] + w[i]);
}
}
int main() {
read(n, m, K);
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= K; ++j)
node[i][j] = ++cnt;
for (int i = 1; i <= m; ++i) {
int x, y; LL z;
read(x, y, z);
for (int j = K; j; --j) ae(node[x][j], node[y][j - 1], z / 2);
for (int j = 0; j <= K; ++j) ae(node[x][j], node[y][j], z);
}
dijkstra(cnt, node[1][K]);
LL ans = inf;
for (int i = 0; i <= K; ++i) chkmin(ans, dist[node[n][i]]);
if (ans < inf) writeln(ans);
else puts("-1");
return 0;
}
E DongDong數顔色
題意：給一棵樹，樹上的每個節點都有一個顔色 c i c_i ci， m m m次詢問，每次詢問以某個點為根的子樹中有多少種不同的顔色。
題解：簡單來說就是序列上的數顔色（HH的項鍊）+dfs序就好了。
首先你要會序列上的數顔色：詢問一段區間 [ l , r ] [l,r] [l,r]中有多少種不同的顔色。我們設 l a s t ( i ) last(i) last(i)表示 c i c_i ci這個顔色上一次出現的位置，即 l a s t ( i ) last(i) last(i)是最大的 j j j，滿足 c j = c i c_j=c_i cj=ci且 j < i j<i j<i。如果不存在這個位置那麼 l a s t ( i ) = 0 last(i)=0 last(i)=0。那麼求一段區間 [ l , r ] [l,r] [l,r]中有多少種不同的顔色，我們隻要求這段區間中有多少個位置的 l a s t last last值小于 l l l。因為如果 l a s t ( i ) ≥ l last(i)\geq l last(i)≥l，說明它的顔色在這段區間中不是第一次出現，不需要統計。于是隻要離線詢問+樹狀數組，或者主席樹線上回答詢問，或者莫隊都可以搞定（莫隊可能略慢）。
然後如果要問一個子樹中的情況，我們求出這棵樹的dfs序，那麼一棵子樹在dfs序上就對應一個區間，就轉化為了區間數顔色問題。
我寫的是主席樹。
#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>
template <typename T> inline void read(T& x) {
int f = 0, c = getchar(); x = 0;
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
if (f) x = -x;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
read(x); read(args...);
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
}
template <typename T> inline void writeln(T x) { write(x); puts(""); }
template <typename T> inline bool chkmin(T& x, const T& y) { return y < x ? (x = y, true) : false; }
template <typename T> inline bool chkmax(T& x, const T& y) { return x < y ? (x = y, true) : false; }
const int maxn = 1e5 + 207;
int v[maxn << 1], head[maxn], next[maxn << 1], etot;
int st[maxn], ed[maxn], dfn[maxn], cnt;
int pre[maxn], last[maxn];
int col[maxn], n, m;
struct Node {
int lc, rc, sum;
Node() : lc(0), rc(0), sum(0) {}
};
Node T[maxn << 5];
int root[maxn], tot;
inline void ae(int x, int y) {
v[++etot] = y; next[etot] = head[x]; head[x] = etot;
v[++etot] = x; next[etot] = head[y]; head[y] = etot;
}
void dfs(int x, int fa) {
st[x] = ++cnt; dfn[cnt] = x;
for (int i = head[x]; i; i = next[i])
if (v[i] != fa) dfs(v[i], x);
ed[x] = cnt;
}
void insert(int &o, int l, int r, int pos) {
T[++tot] = T[o]; o = tot; ++T[o].sum;
if (l == r) return;
int mid = (l + r) >> 1;
if (pos <= mid) insert(T[o].lc, l, mid, pos);
else insert(T[o].rc, mid + 1, r, pos);
}
int query(int lt, int rt, int lb, int rb, int l, int r) {
if (l > rb || r < lb) return 0;
if (l <= lb && r >= rb) return T[rt].sum - T[lt].sum;
int mid = (lb + rb) >> 1;
return query(T[lt].lc, T[rt].lc, lb, mid, l, r) + query(T[lt].rc, T[rt].rc, mid + 1, rb, l, r);
}
int main() {
read(n, m);
for (int i = 1; i <= n; ++i) read(col[i]);
for (int i = 1, x, y; i < n; ++i) read(x, y), ae(x, y);
dfs(1, 0);
for (int i = 1; i <= n; ++i) {
last[i] = pre[col[dfn[i]]];
pre[col[dfn[i]]] = i;
insert(root[i] = root[i - 1], 0, n, last[i]);
}
while (m--) {
int x; read(x);
writeln(query(root[st[x] - 1], root[ed[x]], 0, n, 0, st[x] - 1));
}
return 0;
}
F DongDong的生成樹
題意： n n n個結點，一開始沒有邊， m m m次操作，詢問目前圖的最小生成樹權值和，或者連一條邊。如果圖未連通輸出-1。
題解：LCT裸題。将邊化為一個新的結點，邊權就是它的點權，LCT維護點權最大值。每次連邊時首先看看兩個端點是否已經連通，沒連通就連，連通的話找出這條路徑上邊權最大的那條邊，看看是否能用新的邊取代使得權值變小。
如果會LCT的話這題沒有任何技術含量。
#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>
template <typename T> inline void read(T& x) {
int f = 0, c = getchar(); x = 0;
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
if (f) x = -x;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
read(x); read(args...);
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
}
template <typename T> inline void writeln(T x) { write(x); puts(""); }
template <typename T> inline bool chkmin(T& x, const T& y) { return y < x ? (x = y, true) : false; }
template <typename T> inline bool chkmax(T& x, const T& y) { return x < y ? (x = y, true) : false; }
typedef long long LL;
const int maxn = 1e4 + 7, maxm = 1e5 + 7, maxsize = maxn + maxm;
const LL inf = 1e16;
int fa[maxsize], ch[maxsize][2], mp[maxsize];
LL val[maxsize];
bool rev[maxsize];
inline int iden(int x) { return ch[fa[x]][0] == x ? 0 : (ch[fa[x]][1] == x ? 1 : -1); }
inline void update(int x) {
mp[x] = x;
if (ch[x][0] && val[mp[ch[x][0]]] > val[mp[x]]) mp[x] = mp[ch[x][0]];
if (ch[x][1] && val[mp[ch[x][1]]] > val[mp[x]]) mp[x] = mp[ch[x][1]];
}
inline void pushdown(int x) {
if (rev[x]) {
rev[ch[x][0]] ^= 1; rev[ch[x][1]] ^= 1;
rev[x] = 0; std::swap(ch[x][0], ch[x][1]);
}
}
inline void rotate(int x) {
int d = iden(x), y = fa[x];
if (~iden(y)) ch[fa[y]][iden(y)] = x;
fa[x] = fa[y];
if ((ch[y][d] = ch[x][d ^ 1])) fa[ch[x][d ^ 1]] = y;
fa[ch[x][d ^ 1] = y] = x;
update(y); update(x);
}
int stk[maxsize];
inline void splay(int x) {
int tp = 1; stk[1] = x;
for (int i = x; ~iden(i); i = fa[i]) stk[++tp] = fa[i];
while (tp) pushdown(stk[tp--]);
while (~iden(x)) {
int y = fa[x];
if (~iden(y)) rotate(iden(y) ^ iden(x) ? x : y);
rotate(x);
}
}
inline void access(int x) {
for (int y = 0; x; x = fa[y = x])
splay(x), ch[x][1] = y, update(x);
}
inline void makeroot(int x) {
access(x); splay(x); rev[x] ^= 1;
}
inline void link(int x, int y) {
makeroot(x); fa[x] = y;
}
inline void cut(int x, int y) {
makeroot(x); access(y); splay(y);
fa[x] = ch[y][0] = 0;
update(y);
}
struct Edge {
int x, y;
LL w;
Edge(int a, int b, LL c) : x(a), y(b), w(c) {}
Edge() : x(0), y(0), w(0) {}
};
Edge es[maxm];
int n, m;
int pa[maxn];
int findf(int x) { return x == pa[x] ? x : pa[x] = findf(pa[x]); }
int main() {
read(n, m);
for (int i = 1; i <= n; ++i) val[i] = -inf;
for (int i = 1; i <= n + m; ++i) mp[i] = i;
LL ans = 0;
int cnt = 0;
for (int i = 1; i <= n; ++i) pa[i] = i;
for (int i = 1; i <= m; ++i) {
int q = getchar(); while (isspace(q)) q = getchar();
if (q == 'Q') writeln(cnt == n - 1 ? ans : -1);
else {
int x, y;
LL z; read(x, y, z);
es[i] = Edge(x, y, z);
val[i + n] = z;
if (findf(x) == findf(y)) {
makeroot(x); access(y); splay(y);
int d = mp[y];
if (es[d - n].w > z) {
cut(es[d - n].x, d); cut(d, es[d - n].y);
ans -= es[d - n].w;
link(x, i + n); link(i + n, y);
ans += z;
}
} else {
pa[findf(x)] = pa[findf(y)];
link(x, i + n);
link(i + n, y);
++cnt; ans += z;
}
}
}
return 0;
}
總的來說這場比賽的題目品質是相當差的。都是些模闆題，就隻能給我這種垃圾退役選手當回憶賽打。
![2021牛客暑期多校訓練營2.I Penguins BFS廣搜 簡單2021牛客暑期多校訓練營2.I Penguins BFS廣搜 簡單[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)