牛客练习赛60 A-E

A.大吉大利

题目地址：

https://ac.nowcoder.com/acm/contest/4853/A

基本思路：

要满足那么我们不要对数字本身考虑，我们尝试考虑二进制的每一位;
对于每个数两两&那么就相当于对于二进制的每一位两两&;
由于只有1 & 1 = 1，那么如果一位上有cnt个1，那么能组成1 & 1的可能只有cnt * cnt 种;
所以记录二进制每一位1的个数为cnt，然后cnt * cnt * 这一位的二进制基数就是这一位两两&的答案，相加就是这些数两两&的答案；

参考代码：

考虑给新手看，代码改复杂了一点，并且加了注释

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int 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)
#define INF 0x3f3f3f3f
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 maxn = 1e5 + 10;
int n,a[maxn];
signed main() {
    IO;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int ans = 0;
    for (int j = 0; j < 30; j++) {//考虑数据范围,枚举二进制的前30位;
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] >> j & 1 == 1) cnt++; //这一步是用来记录二进制每一位1的个数;
        }
        ans += cnt * cnt * (1 << j); // (1 << j) 是这一位的二进制基数;
    }
    cout << ans << endl;
    return 0;
}

B.三角形周长和

题目地址：

https://ac.nowcoder.com/acm/contest/4853/B

基本思路：

这题的思路应该很简单，我们考虑暴力算出每条边，然后乘以每条边的贡献就行了;
那么每条边的贡献是多少，我们可以在纸上画四个点，五个点的情况连一下，很简单就能发现是(n-2);
所以答案就是任意两点曼哈顿距离*(n-2)

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int 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)
#define INF 0x3f3f3f3f
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 maxn = 1e3 + 10;
const int mod = 998244353;
int n;
pii p[maxn];
int dis(pii a,pii b){//算两点曼哈顿距离;
    return abs(a.first - b.first) + abs(a.second-b.second);
}
signed main() {
    IO;
    cin >> n;
    rep(i, 1, n) {
        cin >> p[i].first >> p[i].second;
    }
    int ans = 0;
    rep(i, 1, n) {
        rep(j, 1, i - 1) {
            ans += dis(p[i], p[j]) % mod * (n - 2) % mod; //注意取模;
            ans %= mod;
        }
    }
    cout << ans << endl;
    return 0;
}

C.操作集锦

原题地址：

https://ac.nowcoder.com/acm/contest/4853/C

图片说明

基本思路：

我太菜了比赛时没想出来(QAQ)，所以思路参照官方代码然后进一步解释一下;
这题难点在如何完美去掉重复的情况,官方题解的表述如下;
图片说明
这个很容易发现可能对我们这样的dp菜鸟不太友好,所以我具体解释一下:
为什么dp[i][j] - dp[pre[s[i]] - 1][j - 1]就能去掉重复情况，首先我们考虑对于结尾字符相同且长度相同的串，由于 i 一定是大于pre[s[i]] ,也就是说在计算dp[i][j]子串的可能数量时，一定是重复计算了之前一个以相同字符结尾的子串的，所以我们发现这样相减就一定那减掉两个相同字符之间出现过的所有重复情况，即完成去重(还理解不了，可以写个字符串,慢慢理解一下，或者看其他大佬的题解，可能我表述也不是太清楚);

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int 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)
#define INF 0x3f3f3f3f
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 maxn = 1e3 + 10;
const int mod = 1e9 + 7;
int n,k;
string str;
int dp[maxn][maxn],pre[26];
signed main() {
    IO;
    cin >> n >> k;
    cin >> str;
    str = " " + str;
    mset(pre, 0);
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        dp[i][0] = 1;
        for (int j = 1; j <= k; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
            if (pre[str[i] - 'a'] != 0) dp[i][j] -= dp[pre[str[i] - 'a'] - 1][j - 1];
            dp[i][j] = (dp[i][j] % mod + mod) % mod;//防止出现负数;
        }
        pre[str[i] - 'a'] = i;
    }
    cout << dp[n][k] << endl;
    return 0;
}

注意：由于取模后相减可能会出现变为负数的情况，记得处理一下。

D.斩杀线计算大师

题目地址：

https://ac.nowcoder.com/acm/contest/4853/D

基本思路：

这题由于复杂度过于玄学，似乎只要胆子大就能过，我太菜了算不来复杂度，就说下我的做法。

考虑暴力枚举z得到式子ax + by = k - cz;
然后用拓展欧几里得计算 ax + by = k - cz 的最小正整数解

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int 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)
#define INF 0x3f3f3f3f
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');
}
int a,b,c,k;
void exgcd(int a,int b,int &x,int &y,int &d) {
    if (!b) {
        x = 1, y = 0, d = a;
        return;
    }
    int xx, yy;
    exgcd(b, a % b, xx, yy, d);
    x = yy, y = xx - (a / b) * yy;
}
bool solve(int a,int b,int c,int z) {
    int x0, y0, d;
    exgcd(a, b, x0, y0, d);
    if (c % d) {
        return false;
    }
    int x, y, X1, Y1;
    x = x0 * (c / d), y = y0 * (c / d);
    X1 = (x % (b / d) + (b / d)) % (b / d); //x的最小正整数取值
    Y1 = (c - a * X1) / b; //对应的y的值
    cout << X1 << " " << Y1 << " " << z << endl;
    return true;
}
signed main() {
    IO;
    cin >> a >> b >> c >> k;
    for (int z = 0; z * c <= k; z++) {
        int t1 = k - z * c;
        if (solve(a, b, t1, z)) {
            break;
        }
    }
    return 0;
}

E.旗鼓相当的对手

题目地址：

https://ac.nowcoder.com/acm/contest/4853/E

基本思路：

我学了一晚上dsu on tree,参考了许多大佬的题解才好不容易把这题搞出来(我太菜了),可能我自己思路也不是很清晰,大家可以参考着看。

我们参考出题人的题解,这题的关键除了dsu on tree以外是将问题转化;
dsu on tree能优化对于子树的查询,那么我们到底要查询的是什么,我们看题我们要找到对于节点u子树上距离为k的点对;
我们知道树上两点的距离为 deep[u] + deep[v] + 2 * deep[lca(u,v)],那么对于子树下的每个节点now,我们要找到另一个节点u要满足deep[u] + deep[now] + 2 * deep[lca(u,now)] = k,那么转换一下即是deep[u] = k + 2 * deep[lca(u,now)] - deep[now],其中lca(u,now)为查询到的子树的根;
然后就是dsu on tree的模板套上面的查询,具体的实现细节我们可以参考代码注释。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int 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)
#define INF 0x3f3f3f3f
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 maxn = 1e5 + 10;
bool vis[maxn];
int n,k,w[maxn],son[maxn],sz[maxn],par[maxn],dep[maxn];
int cnt[maxn],sum[maxn],ans[maxn];
vector<int> G[maxn];
void dfs1(int u,int p) {
  dep[u] = dep[p] + 1;
  par[u] = p;
  sz[u] = 1;
  for (auto to : G[u]) {
    if (to == p) continue;
    dfs1(to, u);
    sz[u] += sz[to];
    if (sz[to] > sz[son[u]]) {
      son[u] = to;
    }
  }
}
void add(int u, int type){//这里使用type可以方便在之后删除轻儿子贡献;
  sum[dep[u]] += type * w[u];//根据题目rating的计算方法先算一个点对于rating的贡献;
  cnt[dep[u]] += type;//这里记录这样的点对存在的数目,方便计算另一个点对rating的贡献;
  for(auto to : G[u]){
    if(to == par[u] || vis[to]) continue;
    add(to, type);
  }
}
void query(int u,int lca){//这里的lca是子树的根节点;
  int d = k + 2 * dep[lca] - dep[u];//d为计算出来的与u距离k的对应点的深度;
  if(d > 0){
    ans[lca] += sum[d];//将之前计算的另一个点对于rating的贡献加入答案;
    ans[lca] += cnt[d] * w[u];//这里用cnt * w算出来的即是这个点对于rating的贡献;
  }
  for(auto to : G[u]){
    if(to == par[u]) continue;
    query(to,lca);
  }
}
void dfs2(int u,int keep) {
  for (auto to : G[u]) {
    if (to == par[u] || to == son[u]) continue;//处理轻儿子的部分;
    dfs2(to, 0);//keep=0代表这部分贡献要在之后消除;
  }
  if (son[u]) dfs2(son[u], 1), vis[son[u]] = true;//处理重儿子部分,贡献不需要消除;
  //因为重儿子贡献不消除vis数组记录防止重复计算;
  for (auto to : G[u]) {
    if (to == par[u] || vis[to]) continue;
    query(to, u);
    add(to, 1);
  }
  sum[dep[u]] += w[u];
  cnt[dep[u]]++;
  if (son[u]) vis[son[u]] = false;
  if (!keep) {//将轻儿子的贡献消除;
    for (auto to : G[u]) {
      if (to == par[u] || vis[to]) continue;
      add(to, -1);
    }
    sum[dep[u]] -= w[u];
    cnt[dep[u]]--;
  }
}
signed main() {
  IO;
  cin >> n >> k;
  rep(i, 1, n) cin >> w[i];
  rep(i, 1, n - 1) {
    int u, v;
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  mset(vis, false);
  dfs1(1, 0);
  dfs2(1, 1);
  rep(i, 1, n) cout << ans[i] << " ";
  cout << endl;
  return 0;
}