牛客练习赛23

昨晚打了一场比赛……感觉不太难的？（E题除外）

还事撸一篇题解罢？

A

Description

懒得写了……（逃

Solution

贪心且尽量选最大的，然后没了……

Code

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
#include <set>

int v1[7] = {100, 50, 20, 10, 5, 2, 1};
int v2[6] = {50, 20, 10, 5, 2, 1};
int main() {
  int T; scanf("%d", &T);
  while(T --) {
    int a, b; scanf("%d%d", &a, &b);
    for(int i = 0; i < 7; i ++) {
      int g = a / v1[i];
      if(i > 0) putchar(' ');
      printf("%d", g);
      a -= v1[i] * g;
    }
    for(int i = 0; i < 6; i ++) {
      int g = b / v2[i];
      printf(" %d", g);
      b -= v2[i] * g;
    }
    puts("");
  }
  return 0;
}

B

Description

还事懒得写……（逃

Solution

如果你自己试过的话会发现尽量均分事很合理的……证明啥的画画函数图像就行了（逃

Code

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
#include <set>
#include <unordered_map>
using ll = long long;
std::unordered_map<int, ll> ma;
ll dp(int n) {
  if(n == 1) return 0;
  if(ma.count(n)) return ma[n];
  ll x = n / 2; ll y = n - x;
  ll ret = x * y + dp(x) + dp(y);
  ma[n] = ret;
  return ret;
}

int main() {
  int T; scanf("%d", &T);
  while(T --) {
    int n; scanf("%d", &n);
    printf("%lld\n", dp(n));
  }
  return 0;
}

C

Description

给定一自然数序列\(a\)，选出一个子序列\(b\)使得\(b\)中所有元素按位与的lowbit尽可能大。要求你输出这个\(b\)。

此外，如果有多解那么取一个\(b\)尽可能长的。

\(n\leq 10^5,a_i<2^{31}\)。

Solution

我们可以枚举那个lowbit是哪一位，然后我们至少要保证\(b\)中每个元素都含有这一位。

然后我们要求按位与起来更低的位都要是0。然后我们知道参与按位与运算的元素越多，每一位就不可能会变大。那么只要取出所有含有我们要求的那一位元素构成\(b\)，还是有更低位元素为1的话，那么我们枚举的这一位就一定不是答案了。

更好的性质是，这种方法是一定能保证\(b\)尽可能长的。

Code

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
#include <set>
#include <climits>
int lowbit(int x) {
  return x & (-x);
}
const int maxn = 100005;
int a[maxn];
int main() {
  int n; scanf("%d", &n);
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &a[i]);
  }
  int ans = 0;
  for(int j = 0; j <= 30; j ++) {
    int sv = INT_MAX;
    for(int i = 1; i <= n; i ++) {
      if((1 << j) & a[i]) sv &= a[i];
    }
    if(sv != 0 && lowbit(sv) >= (1 << j)) {
      ans = std::max(ans, (1 << j));
    }
  }
  if(ans == 0) {
    puts("0"); return 0;
  }
  std::vector<int> vec;
  for(int i = 1; i <= n; i ++) {
    if(a[i] & ans) {
      vec.push_back(a[i]);
    }
  }
  printf("%d\n", vec.size());
  for(int i = 0; i < vec.size(); i ++) {
    if(i > 0) putchar(' ');
    printf("%d", vec[i]);
  }
  puts("");
  return 0;
}

D

Description

给你一个由\(a\ldots i\)为组成字符的字符串\(S\)（\(|S|\leq 3000\)），求有多少abcdefghi的排列使得该排列为\(S\)的子序列。

Solution

我们考虑枚举排列再判定吧。

我们直接搞出来\(S\)的子序列自动机，然后再扔进去一遍就行了。子序列自动机也不难，你每个点的每种字符的边往他后面第一次这个字符出现的地方连就行。

Code

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
#include <set>
const int maxn = 3005;
int go[maxn][9]; int n;
char S[maxn]; int las[9];
void process() {
  for(int i = n; i >= 0; i --) {
    memcpy(go[i], las, sizeof(las));
    if(i > 0) las[S[i] - 'a'] = i;
  }
}
bool check(char *s) {
  int l = strlen(s);
  int u = 0;
  for(int i = 0; i < l; i ++) {
    int c = s[i] - 'a';
    if(!go[u][c]) return false;
    u = go[u][c];
  }
  return true;
}

char s[10] = "abcdefghi";
int main() {
  scanf("%s", S + 1); n = strlen(S + 1);
  process();
  int ans = 0;
  do {
    if(check(s)) ans ++;
  } while(std::next_permutation(s, s + 9));
  printf("%d\n", ans);
  return 0;
}

E

Description

给定正整数\(n, x\)，要你求一个最大的\(b\)满足\(1<b<x\)，且在\(b\)进制下存在一个长为\(n\)的正整数\(a\)（允许有前导0），满足把\(a\)的\(b\)进制表示看成一个序列之后，做出来的\(n\)种循环位移互不相同，且分别可以由\(a\cdot l(1\leq l\leq n)\)得到。

\(n\leq 5\cdot 10^6,x\leq 10^9\)。

Solution

可以书事最难的题力，，，

我们考虑那个\(a\)吧，就当\(b = 10, a = 142857\)来说，构造一个小数\(c\)满足： \[ c = 0.\overline{142857} \] 这个东西既然是个小数，那么一定可以表示为一个分数\(\frac{p}{q}(p\perp q)\)。然后我们发现如果\(a\)合法，那么\(a\cdot b^l(0\leq l < n)\)的小数部分组成的集合和\(a\cdot l(1\leq l\leq n)\)组成的集合事完全一致的。

小数部分显然只会由分子模\(q\)的结果决定，那么上面的结论就等价于\(p\cdot b^l(0\leq l < n)\)组成的集合和\(p\cdot l(1\leq l\leq n)\)组成的集合事一致的。而\(p^{-1}\bmod{q}\)存在，那么给两个集合都乘上这玩意，那么就得到了\(b^l(0\leq l < n)\)和\(l(1\leq l\leq n)\)，然后就会发现\(b\)的这若干次幂和\(Z_{n + 1}\)中的正数一一对应……换言之\(b\)为\(n + 1\)的原根且\(n + 1\)必须为质数。

找原根的话直接枚举判定就行了……要知道原根很密集的（逃

Code

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <queue>
#include <set>
const int N = 10000000;
int phi[N + 5], minp[N + 5];
int prm[N + 5]; bool vis[N + 5];
void sieve() {
  phi[1] = 1; vis[1] = true;
  int cnt = 0;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      phi[i] = i - 1; minp[i] = i;
      prm[cnt ++] = i;
    }
    for(int j = 0; j < cnt && prm[j] <= N / i; j ++) {
      int v = i * prm[j];
      if(v > N) break;
      vis[v] = true; minp[v] = prm[j];
      if(i % prm[j] == 0) {
        phi[v] = phi[i] * prm[j]; break;
      } else {
        phi[v] = phi[i] * phi[prm[j]];
      }
    }
  }
}

using ll = long long;
ll pow_mod(ll a, ll b, ll p) {
  ll ans = 1, res = a % p;
  while(b) {
    if(1LL & b) ans = (ans * res) % p;
    res = (res * res) % p; b >>= 1;
  }
  return ans;
}

bool has_phi(int x) {
  return !vis[x];
}
std::vector<int> V;
void desc(int x) {
  while(x > 1) {
    int p = minp[x];
    V.push_back(p);
    while(x % p == 0) x /= p;
  }
}
bool check(int x, int t, int p) {
  for(int v : V) {
    ll ans = pow_mod(x, t / v, p);
    if(ans == 1LL) return false;
  }
  return true;
}

int gcd(int a, int b) {
  if(!b) return a;
  else return gcd(b, a % b);
}
int main() {
  sieve();
  int n, x; scanf("%d%d", &n, &x);
  if(x <= 2 || vis[n + 1]) {
    puts("-1"); return 0;
  }
/*
  if(n == 1) {
    printf("%d\n", x - 1); return 0;
  }
*/
  int p = n + 1; int t = n;
  desc(t);
  bool ok = false;
  for(int i = x - 1; i > 1; i --) {
    if((gcd(i, p) == 1) && check(i, t, p)) {
      printf("%d\n", i); ok = true;
      break;
    }
  }
  if(!ok) puts("-1");
  return 0;
}

F

Description

给一颗\(n\)个点的以1为根的树，每次随机选择剩下点中的一个将其子树删掉，等没点了游戏终止。

求期望删除次数。

Solution

怎么感觉是一道经典题……

根据期望线性性，我们考虑每个点对答案的贡献。

每个点首先他和他祖先中势必会有一个点被删除，要是祖先被删了那也没它什么戏了。

所以在它做出贡献时必定他和他祖先都在，然后删了它。无论是在什么情况下，他被删了他祖先却没被动的概率都是\(\frac{1}{d}\)（其中\(d\)为他和他祖先的数量）。

然后加起来就好了。

Code

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
#include <set>
using ll = long long;
const ll ha = 998244353LL;
ll pow_mod(ll a, ll b) {
  ll ans = 1, res = a;
  while(b) {
    if(1LL & b) ans = (ans * res) % ha;
    res = (res * res) % ha; b >>= 1;
  }
  return ans;
}
ll inv(ll x) {
  return pow_mod(x, ha - 2LL);
}

std::vector<int> G[100005];
void ins_edge(int u, int v) {
  G[u].push_back(v);
  G[v].push_back(u);
}
ll dfs(int x, int fa, int depth) {
  ll ret = inv(depth);
  for(auto v : G[x]) {
    if(v != fa) {
      ret = (ret + dfs(v, x, depth + 1)) % ha;
    }
  }
  return ret;
}

int main() {
  int n; scanf("%d", &n);
  for(int i = 1; i <= n - 1; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    ins_edge(u, v);
  }
  printf("%lld\n", dfs(1, -1, 1));
  return 0;
}