牛客练习赛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) 回帖