## 牛客练习赛题解 出题人：$Alan233$ ## T1 Alan爱字符串 ## **Solution** 直接从头到尾扫一遍，抠出每一段连续的数字块。 如果这个数字块开头是零，则需要去除前导0，但注意别把数字0给去了。 注意一下首和尾的细节，即可通过本题。 **Code** ```cpp #include <bits> using namespace std; const int N = 100005; char s[N]; int n; int main() { while (gets(s + 1)) { n = strlen(s + 1); int flag = 0; for (int i = 1; i <= n; i++) { if (isdigit(s[i])) { int j = i; while (j < n && isdigit(s[j + 1])) j++; while (i < j && s[i] == '0') i++; if (flag) putchar(' '); flag = 1; for (int _ = i; _ <= j; _++) { putchar(s[_]); } i = j; } } puts(""); } return 0; } ``` ## T2 Alan爱位运算 ## **Solution** 首先注意到，$a \& b \le a$，拓展到$k$个数则有：$a_1 \& a_2 \& ... \& a_k \le a_1,a_2,...,a_k$。 解释一下，因为$a \& b$实质上是在每一二进制位上取$min$，而$min(x,y)\le x,y$，所以$a\&b$恒小于等于$a$，同理恒小于等于$b$。显然$k$个数也是如此。 所以，我们**贪心**取$a_1,a_2,...,a_n$中最大的数即可。 时间复杂度 $O(n)$。 **Code** ```cpp #include <bits> using namespace std; int _, n, x; int main() { scanf("%d", &_); while (_--) { scanf("%d", &n); int ret = 0; for (int i = 1; i <= n; i++) { scanf("%d", &x); ret = max(ret, x); } printf("%d\n", ret); } return 0; } ``` ## T3 Alan爱博弈 ## **Solution** 我们将$2^k$在模$3$意义下列出来：$1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2...$ 我们发现是按照$\{ 1,2\}$循环的。 如果$n$不为$3$的倍数，则前者可以取一个$2^k$使得$2^k \mod 3=n\mod 3$，后者无论怎么取，前者都可以将$n$凑成$3$的倍数（因为有$1$和$2$）； 如果$n$为$3$的倍数，则前者无论怎么取，后者都可以将$n$凑成$3$的倍数。 因此，结论为：如果$n$为$3$的倍数，则后者必胜，即$Frame$必胜；否则前者必胜，即$Alan$必胜。 时间复杂度：$O(T)$。 **Code** ```cpp #include <bits> using namespace std; long long n; int T; int main() { cin >> T; while (T--) { cin >> n; if (n % 3 == 0) cout << "Frame" << '\n'; else cout << "Alan" << '\n'; } return 0; } ``` ## T4 Alan爱数列 ## **Solution** 考虑**动态规划**。 我们定义$dp[i][0/1]$表示当前第$i$个位置，将前$i$个位置全变成$0/1$的最少操作数。 如果当前位置上$a[i]=1$，则： $dp[i][0]=min(dp[i - 1][0] + 1, dp[i - 1][1] + 1)$，我们可以将$a[i]$单独翻转，也可以将这前缀$1$一起翻转； $dp[i][1] = min(dp[i - 1][1], dp[i - 1][0] + 1)$，我们可以将前缀$0$翻转，然后把$a[i]$拼上去。 如果当前位置上$a[i]=0$，则： $dp[i][0] = min(dp[i - 1][0], dp[i - 1][1] + 1)$，我们可以将前缀$1$翻转，然后把$a[i]$拼上去； $dp[i][1] = min(dp[i - 1][0] + 1, dp[i - 1][1] + 1)$，我们可以将$a[i]$单独翻转，也可以将这前缀$0$一起翻转； 答案记为$min(dp[n][0],dp[n][1])$。 时间复杂度：$O(n)$。 **Code** ```cpp // Author: wlzhouzhuan #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits> using namespace std; #define ll long long #define ull unsigned long long #define rint register int #define rep(i, l, r) for (rint i = l; i <= r; i++) #define per(i, l, r) for (rint i = l; i >= r; i--) #define mset(s, _) memset(s, _, sizeof(s)) #define pb push_back #define pii pair <int> #define mp(a, b) make_pair(a, b) inline int read() { int x = 0, neg = 1; char op = getchar(); while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); } while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); } return neg * x; } inline void print(int x) { if (x < 0) { putchar('-'); x = -x; } if (x >= 10) print(x / 10); putchar(x % 10 + '0'); } const int N = 100005; int a[N], dp[N][2], n; int main() { n = read(); rep(i, 1, n) a[i] = read(); rep(i, 1, n) { if (a[i] == 1) { dp[i][0] = min(dp[i - 1][0] + 1, dp[i - 1][1] + 1); dp[i][1] = min(dp[i - 1][1], dp[i - 1][0] + 1); } else { dp[i][0] = min(dp[i - 1][0], dp[i - 1][1] + 1); dp[i][1] = min(dp[i - 1][0] + 1, dp[i - 1][1] + 1); } } printf("%d\n", dp[n][0]); return 0; } ``` ## T5 Alan游历城市 ## **Solution** 相信学过树状数组的同学都对$lowbit$不陌生，$lowbit(x) = x \ and \ -x$。 比如在C++里面，我们可以写作： `#define lowbit(x) (x & -x)` 这题暴力连边显然有$n^2$的边，我们考虑如何优化简便。 其实这可以按照二进制中的每一位来建边。 我们设一个阈值$B=256$，将每个$a_i$拆成$x\times 256^3 + y\times 256^2 + z \times 256 + t$的形式，然后按照$x,y,z,t$分别进行连边。并建立一些虚拟点，跑一个$dijkstra$即可，注意特判无法到达终点的情形。 可以发现，这样每一段的位都从起点到了终点，所以正确性显然。 注意$a_i\le 2^{32}$，所以需要开$long\ long$（当然你开$unsigned\ int$也可以，但是细节会比较多），空间要开大几倍，估计有选手会因空间开小而MLE。 时间复杂度：$O(nlogn)$。 **Code** ```cpp // Author: wlzhouzhuan #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits> using namespace std; #define ll long long #define ull unsigned long long #define rint register int #define rep(i, l, r) for (rint i = l; i <= r; i++) #define per(i, l, r) for (rint i = l; i >= r; i--) #define mset(s, _) memset(s, _, sizeof(s)) #define pb push_back #define pii pair <long long=""> #define mp(a, b) make_pair(a, b) inline ll read() { ll x = 0, neg = 1; char op = getchar(); while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); } while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); } return neg * x; } inline void print(int x) { if (x < 0) { putchar('-'); x = -x; } if (x >= 10) print(x / 10); putchar(x % 10 + '0'); } ll lowbit(ll x) { return x & -x; } const int N = 2000005, B = 256; const ll inf = 1e18; struct Edge { int to, nxt; ll val; } edge[N]; int head[N], tot; void add(int u, int v, ll w) { edge[++tot] = {v, head[u], w}; head[u] = tot; } int n, s, t; priority_queue <pii>, greater <pii>> pq; ll dis[N]; void dijkstra(int s, int t) { rep(i, 0, t) dis[i] = inf; pq.push(make_pair(0, s)); dis[s] = 0; while (!pq.empty()) { pii fro = pq.top(); pq.pop(); int u = fro.second; if (dis[u] < fro.first) continue; for (rint i = head[u]; i; i = edge[i].nxt) { int v = edge[i].to; if (dis[v] > dis[u] + edge[i].val) { dis[v] = dis[u] + edge[i].val; pq.push(make_pair(dis[v], v)); } } } } void work() { mset(head, 0), mset(edge, 0); n = read(), tot = 0; s = 8 * B, t = 8 * B + n - 1; rep(i, 0, B - 1) { rep(j, 0, B - 1) if (i & j) { ll p = lowbit(i & j); rep(k, 0, 3) { add(k * B + i, (4 + k) * B + j, p << (k * 8)); } } } rep(i, 0, n - 1) { ll a = read(); int fro = s + i; rep(k, 0, 3) { int to = a >> (8 * k) & (B - 1); add(fro, k * B + to, 0); add((4 + k) * B + to, fro, 0); } } dijkstra(s, t); if (dis[t] >= inf) { puts("Impossible"); } else { printf("%lld\n", dis[t]); } } int main() { int T = read(); while (T--) work(); return 0; } ``` ## T6 Alan的苹果树 ## **Solution** 很明显，$l,l+1,l+2,...,r$中最远的两点即为**区间带权直径**。 解释：如果不是直径，则假设$d_1$和$d_2$为直径的两端，最远的两点$s$和$t$，那么$dist(s,t) > dist(d_1,d_2)$，不符合直径的定义，矛盾。 那么，我们用一个$pair$存储$st[u][i]$表示从$u$开始往后$2^i$个数中的直径的两个端点。 考虑如何转移。 $st[u][i]$肯定是从$st[u][i-1]$和$st[u+2^{i-1}][i-1]$转移过来的，那么直径合并其实就是直径端点两两求$LCA$，最后取两个深度( $dep$ )最大的点作为新的直径（这个很显然吧）。 每次查询$l$和$r$区间，我们就将两个$st$合并一下即可。 时间复杂度：$O(nlogn)$，时限开的是标程的$2$ 倍左右。 **Code** ```cpp // Author: wlzhouzhuan #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits> using namespace std; #define ll long long #define ull unsigned long long #define rint register int #define rep(i, l, r) for (rint i = l; i <= r; i++) #define per(i, l, r) for (rint i = l; i >= r; i--) #define each(i) for (rint i = head[u]; i; i = edge[i].nxt) #define mset(s, _) memset(s, _, sizeof(s)) #define pb push_back #define pii pair <int> #define mp(a, b) make_pair(a, b) inline int read() { int x = 0, neg = 1; char op = getchar(); while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); } while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); } return neg * x; } inline void print(ll x) { if (x < 0) { putchar('-'); x = -x; } if (x >= 10) print(x / 10); putchar(x % 10 + '0'); } const int N = 300001; int n, q; struct Edge { int to, nxt, val; } edge[N << 1]; int head[N], etot; void add(int u, int v, int w) { edge[++etot] = {v, head[u], w}; head[u] = etot; } ll w[N]; int lg[N << 1], a[N << 1], dfn[N], dep[N], tot; int f[N << 1][20]; void dfs(int u, int fa) { f[++tot][0] = u, dfn[u] = tot, dep[u] = dep[fa] + 1; each(i) { int v = edge[i].to; if (v == fa) continue; w[v] = w[u] + edge[i].val; dfs(v, u); f[++tot][0] = u; } } void pre() { lg[1] = 0; for (rint i = 2; i <= tot; i++) lg[i] = lg[i >> 1] + 1; for (rint j = 1; j <= 19; j++) { for (rint i = 1; i + (1 << j) - 1 <= tot; i++) { if (dep[f[i][j - 1]] < dep[f[i + (1 << j - 1)][j - 1]]) { f[i][j] = f[i][j - 1]; } else { f[i][j] = f[i + (1 << j - 1)][j - 1]; } } } } int LCA(int u, int v) { u = dfn[u], v = dfn[v]; if (u > v) swap(u, v); int len = lg[v - u + 1]; if (dep[f[u][len]] < dep[f[v - (1 << len) + 1][len]]) { return f[u][len]; } else { return f[v - (1 << len) + 1][len]; } } ll dist(int u, int v) { return w[u] + w[v] - 2ll * w[LCA(u, v)]; } #define fi first #define se second pair <int> g[N][20]; pair <int> merge(pair <int> x, pair <int> y) { ll dis[6] = {dist(x.fi, x.se), dist(x.fi, y.fi), dist(x.fi, y.se), dist(x.se, y.fi), dist(x.se, y.se), dist(y.fi, y.se)}; int maxid = 0; rep(i, 0, 5) if (dis[i] > dis[maxid]) maxid = i; switch (maxid) { case 0: return x; case 1: return make_pair(x.fi, y.fi); case 2: return make_pair(x.fi, y.se); case 3: return make_pair(x.se, y.fi); case 4: return make_pair(x.se, y.se); case 5: return y; } } void solve() { for (rint i = 1; i <= n; i++) g[i][0] = make_pair(i, i); for (rint j = 1; j <= 19; j++) { for (rint i = 1; i + (1 << j) - 1 <= n; i++) { g[i][j] = merge(g[i][j - 1], g[i + (1 << j - 1)][j - 1]); } } } pair <int> calc(int l, int r) { int len = lg[r - l + 1]; return merge(g[l][len], g[r - (1 << len) + 1][len]); } int main() { n = read(), q = read(); rep(i, 1, n - 1) { int u = read(), v = read(), w = read(); add(u, v, w), add(v, u, w); } dfs(1, 0); pre(); solve(); while (q--) { int l = read(), r = read(); pair <int> res = calc(l, r); print(dist(res.fi, res.se)), putchar('\n'); } return 0; } ``` </int></int></int></int></int></int></int></bits></pii></pii></long></bits></int></bits></bits></bits></bits>