只会ABC, 但是第一题好像数据出锅了rejudge后wa的全过了, 卡了半个小时?(雾)实际做题时间大概40分钟

A. 怪盗-1412

Solution

贪心的放, 怎么放最贪呢? 4 和 2 可以不用管直接放一起, 重点在两个1
因为最终答案是
要把 n 拆分成 和 , 比如 5 拆成 1 和 4 或者 2 和 3
肯定是拆成 和 最优啦

Code

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);
  int t;
  cin >> t;
  while(t--) {
    ll n, m, k;
    cin >> n >> m >> k;
    ll ans = 0;
    if(n < 2 || m < 1 || k < 1) {
      cout << 0 << "\n";
    } else {
      if(n & 1) {
        cout << n / 2 * (n / 2 + 1) * m * k << "\n";
      } else {
        cout << n / 2 * n / 2 * m * k << "\n";
      }
    }
  }
  return 0;
}

B. Dis2

Solution

发现对于一个节点，如果他连接的节点大于等于2个的话，那么它所连的点互为距离为2的点，直接做即可

code

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const int N = 2e5 + 5;

vector<int> G[N];
ll cnt[N];

int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);
  int n;
  cin >> n;
  int u, v;
  for(int i = 1; i <= n - 1; i++) {
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  for(int i = 1; i <= n; i++) {
    if(G[i].size() >= 2) {
      for(int j = 0; j < G[i].size(); j++) {
        int son = G[i][j];
        cnt[son] += (G[i].size() - 1);
      }
    }
  }
  for(int i = 1; i <= n; i++) {
    cout << cnt[i] << "\n";
  }
  return 0;
}

C. 序列卷积之和

Solution

看着挺吓人的，卷积，FFT? NTT?
先打个表再说

  // ll ans = 0;
  // map<pair<int, int>, int> mp;
  // for(int i = 1; i <= n; i++) {
  //   for(int j = i; j <= n; j++) {
  //     for(int k = i; k <= j; k++) {
  //       for(int l = k; l <= j; l++) {
  //         mp[{k, l}]++;
  //         ans += a[k] * a[l];
  //         ans %= mod;
  //       }
  //     }
  //   }
  // }
  // for(auto &x: mp) {
  //   cout << x.first.first << ' ' << x.first.second << ' ' << x.second << "\n";
  // }
  // cout << ans << "\n";

以第一个样例为例子，找出任意两对的贡献
比如 1 1 4, 说明 出现了4次，那么贡献就是
分为四组，发现每一组的贡献是
其中 表示 乘上系数 后的前缀和(就是最后一列 4 3 2 1那个乘上 )
简单来说就是第一组需要
算出 组的贡献，这题做完了

Code

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

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

ll a[N];
ll sum[N], cnt[N];
int n;
int main() {
  sum[0] = 0;
  ios::sync_with_stdio(false), cin.tie(nullptr);
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i], cnt[i] = a[i] * (n - i + 1) % mod;
  for(int i = 1; i <= n; i++) {
    sum[i] = (sum[i - 1] + cnt[i]) % mod;
  }
  ll ans = 0;
  for(int i = 1; i <= n; i++) {
    ll p = (sum[n] - sum[i - 1] + mod) % mod;
    ll now = (a[i] * i) % mod;
    now = (now * p) % mod;
    ans += now;
    ans %= mod;
  }
  cout << ans << "\n";

  return 0;
}