A 大吉大利

Solution

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e5 + 5;
const ll mod = 1e9 + 7;
const int DEG = 30;
const double PI = acos(-1.0);
const double eps = 1e-12;
const ll inf = 1e18;
static auto fast_iostream = [](){
  ios::sync_with_stdio(false);
  cout.tie(nullptr);
  return 0;
}();
ll dp[50];
ll a[N];
int main(){
  int n;
  cin >> n;
  ll sum = 0;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
    sum += a[i];
    for(int j = 0; j < 31; j++){
      if((a[i] >> j) & 1){
        dp[j]++;
      }
    }
  }
  ll ans = 0;
  for(int i = 1; i <= n; i++){
    for(int j = 0; j < 31; j++){
      if((a[i] >> j) & 1){
        ans += (1 << j) * dp[j];
        dp[j]--; // 去掉这一行 ans直接就是本题答案
      }
    }
  }
  cout << ans * 2 - sum << "\n";
  return 0;
}

B 三角形周长和

Solution

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e5 + 5;
const ll mod = 998244353;
const int DEG = 30;
const double PI = acos(-1.0);
const double eps = 1e-12;
const ll inf = 1e18;
static auto fast_iostream = [](){
  ios::sync_with_stdio(false);
  cout.tie(nullptr);
  return 0;
}();
pair<int, int> p[N];
int main(){
  ll n;
  cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> p[i].first >> p[i].second;
  }
  ll ans = 0;
  for(int i = 1; i <= n; i++){
    for(int j = i + 1; j <= n; j++){
      ans += abs(p[i].first - p[j].first);
      ans += abs(p[i].second - p[j].second);
      ans %= mod;
    }
  }
  cout << (ans * (n - 2)) % mod<< "\n";
  return 0;
}

C 操作集锦

Solution

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e5 + 5;
const ll mod = 1e9 + 7;
const int DEG = 30;
const double PI = acos(-1.0);
const double eps = 1e-12;
const ll inf = 1e18;
static auto fast_iostream = [](){
  ios::sync_with_stdio(false);
  cout.tie(nullptr);
  return 0;
}();
int n;
int k;
ll dp[1005][1005][26], s[1005][1005], ans;
int main()
{
    cin >> n >> k;
    string t;
    cin >> t;
    t = ' ' + t;
    if(k == 0){
      cout << 1 << "\n";
      return 0;
    }
    for(int i = 1; i <= n; i++){
      dp[i][1][t[i] - 'a'] = 1;
      for(int j = 1; j <= i; j++){
        for(int c = 0; c < 26; c++){
          if(t[i] - 'a' == c){
            dp[i][j][c] += s[i-1][j-1]; 
          }
          else{ 
            dp[i][j][c] += dp[i-1][j][c];
          }
          s[i][j] += dp[i][j][c];
          dp[i][j][c] %= mod;
          s[i][j] %= mod;
        }
      }
    }
    ll ans = 0;
    for(int i = 0; i < 26; i++){
      ans += dp[n][k][i];
      ans %= mod;
    }
    cout << ans << "\n";
}

D 斩杀线计算大师

Solution

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e5 + 5;
const ll mod = 1e9 + 7;
const int DEG = 30;
const double PI = acos(-1.0);
const double eps = 1e-12;
const ll inf = 1e18;
static auto fast_iostream = [](){
  ios::sync_with_stdio(false);
  cout.tie(nullptr);
  return 0;
}();
ll extgcd(ll a,ll b,ll& x,ll& y){
    ll d = a;
    if(b != 0){
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }
    else{
        x = 1;
        y = 0;
    }
    return d;
}
int main(){
  ll a, b, c, k;
  cin >> a >> b >> c >> k;
  ll x, y;
  ll now = __gcd(a, b);
  ll i = 0;
  while(1){ //枚举 z 的值
    if((k - c * i) % now == 0) break;
    i++;
  }
  ll right = k - c * i;
  ll x1, y1, b1;
  extgcd(a, b, x, y);
  //求正整数解
  b1 = b / now;
  x1 = (x + b1) * (right / now);
  x1 = (x1 % b1 + b1) % b1;
  y1 = (right - a * x1) / b;
  cout << x1 << ' ' << y1 << ' ' << i << "\n";
  return 0;
}

E 旗鼓相当的对手

Solution

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e5 + 5;
const ll mod = 1e9 + 7;
const int DEG = 30;
const double PI = acos(-1.0);
const double eps = 1e-12;
const ll inf = 1e18;
vector<int> G[N];
bool vis[N];
int n, k;
int dep[N], par[N], son[N];
ll sz[N], a[N], ans[N], cnt[N], sum[N];
void init(){
  memset(son, -1, sizeof(son));
}
void dfs1(int u, int fa){
  dep[u] = dep[fa] + 1;
  par[u] = fa;
  sz[u] = 1;
  for(int i = 0; i < G[u].size(); i++){
    int v = G[u][i];
    if(v == fa) continue;
    dfs1(v, u);
    sz[u] += sz[v];
    if(son[u] == -1 || sz[v] > sz[son[u]]){ // 轻重链剖分,只取重链
      son[u] = v;
    }
  }
}
void add(int u, int type){
  sum[dep[u]] += type * a[u];
  cnt[dep[u]] += type;
  for(int i = 0; i < G[u].size(); i++){
    int v = G[u][i];
    if(v == par[u] || vis[v]) continue;
    add(v, type);
  }
}
void query(int u, int lca){
  int d = k + 2 * dep[lca] - dep[u];
  if(d > 0){
    ans[lca] += sum[d];
    ans[lca] += cnt[d] * a[u];
  }
  for(int i = 0; i < G[u].size(); i++){
    int v = G[u][i];
    if(v == par[u]) continue;
    query(v, lca);
  }
}
void dfs2(int u, int op){
  for(int i = 0; i < G[u].size(); i++){
    int v = G[u][i];
    if(v == par[u] || v == son[u]) continue; // 不取重链
    dfs2(v, 0);
  }
  if(son[u] != -1){
    dfs2(son[u], 1);
    vis[son[u]] = 1;
  }
  for(int i = 0; i < G[u].size(); i++){
    int v = G[u][i];
    if(v == par[u] || vis[v]) continue;
    query(v, u);
    add(v, 1);
  }
  sum[dep[u]] += a[u];
  cnt[dep[u]] += 1;
  if(son[u] != -1) vis[son[u]] = false;
  if(!op){ //删去轻链
    for(int i = 0; i < G[u].size(); i++){
      int v = G[u][i];
      if(v == par[u] ||vis[v]) continue;
      add(v, -1);
    }
    sum[dep[u]] -= a[u];
    cnt[dep[u]] -= 1;
  }
}
int main(){
  init();
  cin >> n >> k;;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  for(int i = 1; i <= n - 1; i++){
    int u, v;
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  dfs1(1, 0);
  dfs2(1, 1);
  for(int i = 1; i <= n; i++){
    cout << ans[i] << " \n"[i == n];
  }
  return 0;
}

F 几何带师(待补QAQ)