【题解】牛客练习赛67

牛客练习赛67题解

出题人： $Alan233$

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

首先注意到， $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

#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

我们将 $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

#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

考虑动态规划。

我们定义 $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

// 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

相信学过树状数组的同学都对 $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

// 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

很明显， $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

// 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;
}