牛客练习赛67题解
出题人:
T1 牛牛爱字符串
Solution
直接从头到尾扫一遍,抠出每一段连续的数字块。
如果这个数字块开头是零,则需要去除前导0,但注意别把数字0给去了。
注意一下首和尾的细节,即可通过本题。
Code
#include <bits/stdc++.h> 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 牛牛爱位运算
Solution
首先注意到,,拓展到个数则有:。
解释一下,因为实质上是在每一二进制位上取,而,所以恒小于等于,同理恒小于等于。显然个数也是如此。
所以,我们贪心取中最大的数即可。
时间复杂度 。
Code
#include <bits/stdc++.h> 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 牛牛爱博弈
Solution
我们将在模意义下列出来:
我们发现是按照循环的。
如果不为的倍数,则前者可以取一个使得,后者无论怎么取,前者都可以将凑成的倍数(因为有和);
如果为的倍数,则前者无论怎么取,后者都可以将凑成的倍数。
因此,结论为:如果为的倍数,则后者必胜,即必胜;否则前者必胜,即必胜。
时间复杂度:。
Code
#include <bits/stdc++.h> 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 牛妹爱数列
Solution
考虑动态规划。
我们定义表示当前第个位置,将前个位置全变成的最少操作数。
如果当前位置上,则:
,我们可以将单独翻转,也可以将这前缀一起翻转;
,我们可以将前缀翻转,然后把拼上去。
如果当前位置上,则:
,我们可以将前缀翻转,然后把拼上去;
,我们可以将单独翻转,也可以将这前缀一起翻转;
答案记为。
时间复杂度:。
Code
// Author: wlzhouzhuan #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> 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, 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 牛妹游历城市
Solution
相信学过树状数组的同学都对不陌生,。
比如在C++里面,我们可以写作: #define lowbit(x) (x & -x)
这题暴力连边显然有的边,我们考虑如何优化简便。
其实这可以按照二进制中的每一位来建边。
我们设一个阈值,将每个拆成的形式,然后按照分别进行连边。并建立一些虚拟点,跑一个即可,注意特判无法到达终点的情形。
可以发现,这样每一段的位都从起点到了终点,所以正确性显然。
注意,所以需要开(当然你开也可以,但是细节会比较多),空间要开大几倍,估计有选手会因空间开小而MLE。
时间复杂度:。
Code
// Author: wlzhouzhuan #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> 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, int> #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, vector <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 牛妹的苹果树
Solution
很明显,中最远的两点即为区间带权直径。
解释:如果不是直径,则假设和为直径的两端,最远的两点和,那么,不符合直径的定义,矛盾。
那么,我们用一个存储表示从开始往后个数中的直径的两个端点。
考虑如何转移。
肯定是从和转移过来的,那么直径合并其实就是直径端点两两求,最后取两个深度( )最大的点作为新的直径(这个很显然吧)。
每次查询和区间,我们就将两个合并一下即可。
时间复杂度:,时限开的是标程的 倍左右。
Code
// Author: wlzhouzhuan #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> 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, 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, int> g[N][20]; pair <int, int> merge(pair <int, int> x, pair <int, 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, 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, int> res = calc(l, r); print(dist(res.fi, res.se)), putchar('\n'); } return 0; }
全部评论
(7) 回帖