牛客练习赛47 题解
GKxx
2019-06-08 00:14:07
[比赛传送门](https://ac.nowcoder.com/acm/contest/904#question)
正好跟cf时间撞上了，然而我太菜了cf的题做不出来，就来看了看牛客的题
真的好简单啊......
### A DongDong破密码
题意：将一个01串$a$（长度为$n$）向右移动$m$次，最后求出这$n+m-1$位每一位的异或值，得到一个新串$b$。（这个描述不太清楚，建议看原题有张图）现在给出串$b$，请你求出原串$a$。
题解：$b[i]$的值其实就代表了$a[i-m+1...i]$这一段区间上的$1$的个数的奇偶性。维护一个前缀和数组$s[i]$表示$a$串前$i$位一共有多少个$1$，那么比较$b[i]$与$s[i - 1]-s[i-m]$的奇偶性就可以知道第$i$位是否是$1$。
```cpp
#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$根柱子，每根柱子都有一个高度和柱子上面鱼干的数量，一只猫开始的时候可以选择站在任意一根柱子上，每次跳跃不限长度而且只能从左向右跳跃，但只能跳到高度与当前所站高度差绝对值小于等于$m$的柱子上。它会吃掉经过的柱子上的鱼干。请最大化这只猫能吃到的鱼干数量（最终不一定要落在第n根柱子上）。
算法1：设$f_i$表示它从左往右跳到$i$号柱子上，最多能吃到多少鱼干。转移显然
$$f_i=\max{f_j}+a_i,1\leq j<i,|h_j-h_i|\leq m$$
这样做时间复杂度是$O(n^2)$，不够优秀。
发现这里是一个二维数点，用线段树优化即可。
具体一点：我们可以求出$l_i=\max(1,h_i-m),r_i=h_i+m$，那么我们必须从满足$l_i\leq h_j\leq r_i$的$f_j$中取一个最大的转移过来，这就是区间查最大值，用线段树维护一下就好。如果觉得空间有点紧，可以再离散化一下。
这个做法我没写，不过我看到有人写了，就说一下。
算法2：改变状态的定义。设$f(i,j)$表示前$i$个柱子中，跳到高度为$j$的柱子上最多能吃多少。那么
$$f(i,j)=\max{f(i-1,k)},l_i\leq k\leq r_i$$
这时候转移就变成了真正的区间最大值查询，你还可以用线段树优化，但也可以不用，因为这个区间长度是$O(m)$的。然后我们发现$f(i,*)$都是从$f(i-1,*)$转移的，所以$i$这一维可以扔掉，那么空间复杂度就可以接受了。
```cpp
#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$的，事实上不需要吧？...因为这里只要高度差的绝对值在$m$以内，所以从左往右还是从右往左都一样吧。
### D DongDong坐飞机
题意：$n$个点，$m$条有向边，有边权。你要从$1$走到$n$，并且途中有$k$次机会可以将一条边的代价减半，求最小代价。
题解：分层图最短路模板题。建$n(k+1)$个点，结点$(i,j)$表示你走到原图中的点$i$并且剩余$j$次减半机会。那么我们就是要从$(1,k)$走到$(n,*)$。对于原图中的一条边$(u,v,w)$，我们枚举剩余$i$次减半机会，连边$((u,i),(v,i-1),w/2)$表示使用减半机会，再连边$((u,i),(v,i),w)$表示没使用减半机会。然后跑最短路即可。
我写的是zkw线段树优化dijkstra求最短路。
```cpp
#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$，$m$次询问，每次询问以某个点为根的子树中有多少种不同的颜色。
题解：简单来说就是序列上的数颜色（HH的项链）+dfs序就好了。
首先你要会序列上的数颜色：询问一段区间$[l,r]$中有多少种不同的颜色。我们设$last(i)$表示$c_i$这个颜色上一次出现的位置，即$last(i)$是最大的$j$，满足$c_j=c_i$且$j<i$。如果不存在这个位置那么$last(i)=0$。那么求一段区间$[l,r]$中有多少种不同的颜色，我们只要求这段区间中有多少个位置的$last$值小于$l$。因为如果$last(i)\geq l$，说明它的颜色在这段区间中不是第一次出现，不需要统计。于是只要离线询问+树状数组，或者主席树在线回答询问，或者莫队都可以搞定（莫队可能略慢）。
然后如果要问一个子树中的情况，我们求出这棵树的dfs序，那么一棵子树在dfs序上就对应一个区间，就转化为了区间数颜色问题。
我写的是主席树。
```cpp
#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$个结点，一开始没有边，$m$次操作，询问当前图的最小生成树权值和，或者连一条边。如果图未连通输出-1。
题解：LCT裸题。将边化为一个新的结点，边权就是它的点权，LCT维护点权最大值。每次连边时首先看看两个端点是否已经连通，没连通就连，连通的话找出这条路径上边权最大的那条边，看看是否能用新的边取代使得权值变小。
如果会LCT的话这题没有任何技术含量。
```cpp
#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;
}
```
总的来说这场比赛的题目质量是相当差的。都是些模板题，就只能给我这种垃圾退役选手当回忆赛打。