早上起来找几道有意思点的题(过的人少)来写一写吧, 太简单就不写了

B. k-size字符串

Solution

赛后发现自己通过 90%, 先去上课, 回来写
update 没想到过了五六天了
这题一看数据范围 k 好大, 组合数怎么做啊
然后显然 的时候是无解的
那么对 的讨论降到的 级别
既然一定要k个, 考虑先放足k个满足条件的情况即
ababab 这样放, 这样要考虑一下当 为奇数的时候 a, b的个数相差1，偶数的时候相等
同理我们考虑bababa，当偶数时这两种情况的数量是一样的乘 2 就行，奇数的话就两者的种类相加
那么我们只需要考虑放了 abababab... 后对于剩下的 a, b的分配方案是多少
我们分析偶数的情况, 显然剩下 个 和 个
可以用隔板法的思想, 转换成 个球要放到 个盒子里, 允许为空的方案
显然为 , 同理可以计算其他的, 方案加起来就可以了

Code

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll mod = 1e9 + 7;
const int N = 2e5 + 5;

ll fac[N], inv[N];

ll qpow(ll a, ll b) {
  ll res = 1;
  while(b) {
    if(b & 1) {
      res = res * a % mod;
    }
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}

void init() {
  fac[0] = 1;
  for(int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % mod;
  inv[N - 1] = qpow(fac[N - 1], mod - 2);
  for(int i = N - 2; i >= 0; i--) {
    inv[i] = inv[i + 1] * (i + 1) % mod;
  }
}

ll C(int n, int m) {
  if(n < m) return 0;
  return 1LL * fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int main() {
  init();
  int n, m, k;
  cin >> n >> m >> k;
  if(n + m < k) {
    cout << 0 << "\n";
  } else if(k & 1) {
    ll p1 = C(n - 1, k / 2) * C(m - 1, k / 2 - 1) % mod;
    ll p2 = C(n - 1, k / 2 - 1) * C(m - 1, k / 2) % mod;
    cout << (p1 + p2) % mod << "\n";
  } else {
    cout << (2 * C(n - 1, k / 2 - 1) * C(m - 1, k / 2 - 1)) % mod << "\n";
  }
  return 0;
}

C. 白魔法师

Solution

这一题我卡了很久, 思路是对的, 但是一直 , 重构了几次代码后过了, 很神奇
我的做法是先预处理出所有白色节点的所处连通块编号和这个连通块的大小
然后我们再枚举一个黑色的节点, 看这个节点所连接的点是否白色连通块
最理想的情况下就是一个黑色节点连接两个白色的连通块, 此时贡献就是 ( 为白色连通块)
有些节点只有一条边连着一个白色连通块, 此时贡献就是
如果每个黑色节点都没有连接白色连通块, 答案为 是最大的连通块大小

Code

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const int mod = 1e9 + 7;
const int N = 2e5 + 5;
vector<int> G[N];
string s;
int vis[N];
int cnt, cur, a[N];
void dfs(int u) {
  vis[u] = cur;
  for(int i = 0; i < G[u].size(); i++) {
    int v = G[u][i];
    if(!vis[v] && s[v] == 'W') {
      dfs(v);
      cnt++;
    }
  }
}
int main() {
  int n;
  cin >> n >> s;
  s = ' ' + s;
  for(int i = 1; i <= n - 1; i++) {
    int u, v;
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  for(int i = 1; i <= n; i++) {
    if(!vis[i] && s[i] == 'W') {
      cnt = 1, cur++;
      dfs(i);
      a[cur] = cnt;
    }
  }
  int ans = 1;
  for(int i = 1; i <= cur; i++) ans = max(ans, a[i]);
  for(int i = 1; i <= n; i++) {
    if(s[i] == 'B') {
      int cot = 1;
      for(int j = 0; j < G[i].size(); j++) {
        int v = G[i][j];
        cot += a[vis[v]];
      }
      ans = max(ans, cot);
    }
  }
  cout << ans << "\n";
  return 0;
}

J. 异或和之和

Solution

不知道这个题为什么过的人这么少, 好像套路挺常规的, 做过不少次了
异或我们考虑从二进制考虑, 因为有三个数字
我们可以分析最多有 种组合情况, 但是想要有贡献的其实只有两种
分别是 和 (仔细想想是不是这样)
比如 和 异或还是 , 此时跟 异或变成 , 这一位就是 , 有贡献
那么剩下的工作就是统计 个二进制位上的 个数, 计算贡献即可

Code

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const int mod = 1e9 + 7;
const int N = 1e6 + 5;

ll a[N];
ll dp[70][2];
ll qpow(ll a, ll b) {
  ll res = 1;
  while(b) {
    if(b & 1) {
      res = res * a % mod;
    }
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}
int main() {
  cin.ios::sync_with_stdio(false), cin.tie(nullptr);
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];
  for(int i = 1; i <= n; i++) {
    for(int j = 0; j <= 63; j++) {
      if(a[i] & (1LL << j)) {
        dp[j][1]++;
      } else {
        dp[j][0]++;
      }
    }
  }
  ll ans = 0;
  for(int i = 0; i <= 63; i++) {
    ll p = qpow(2, i);
    ll num0 = dp[i][0], num1 = dp[i][1];
    if(num0 >= 2 && num1 >= 1) {
      ans += qpow(2, i) * (((num0 - 1) * num0 / 2) * (num1) % mod) % mod;
    }
    ans %= mod;
    if(num1 >= 3) {
      ans += num1 * (num1 - 1) * (num1 - 2) / 6 % mod * qpow(2, i) % mod;
    }
    ans %= mod;
    //cout << ans << "\n";
  }
  cout << ans << "\n";
  return 0;
}