• 周四. 5月 30th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

2021暑假模拟赛8

admin

11月 28, 2021

A[CF1208A(900)]

由于异或的性质,容易找到序列出现$%3$的规律。

#include <bits/stdc++.h>
using namespace std;
int main() {
  int T;
  cin >> T;
  while (T --) {
    int A, B, N;
    cin >> A >> B >> N;
    if (N % 3 == 0) {
      cout << A << '
';
    } 
    if (N % 3 == 1) {
      cout << B << '
';
    }
    if (N % 3 == 2) {
      cout << (A ^ B) << '
';
    }
  }
  return 0;
}

View Code

B[CF1541C(1400)]

可以发现把边从小到大串起来比较优,于是把$d$从小到大排序,利用前缀和计算答案即可。

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T --> 0) {
    int N;
    cin >> N;
    vector<long long> d(N);
    for (int i = 0; i < N; ++i) {
      cin >> d[i];
    }
    sort(d.begin(), d.end());
    long long Ans = d[N - 1];
    long long S = 0;
    for (int i = 0; i < N; ++i) {
      Ans -= 1LL * i * d[i];
      Ans += S;
      S += d[i];
    }
    cout << Ans << '
';
  }
}

View Code

C[CF1529C(1600)]

需要一个观察,当每个点的取值为$l[i]$或$r[i]$时答案比较优,因为取极值的答案总会更好一些。考虑$dp[x][0/1]$表示$x$点的取值,简单分类讨论转移即可。

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T --> 0) {
    int N;
    cin >> N;
    vector<vector<int>> V(N, vector<int> (2));
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < 2; ++j) {
        cin >> V[i][j];
      }
    }
    vector<vector<int>> adj(N);
    for (int i = 0; i < N - 1; ++i) {
      int X, Y;
      cin >> X >> Y;
      X --;
      Y --;
      adj[X].push_back(Y);
      adj[Y].push_back(X);
    }
    vector<vector<long long>> dp(N, vector<long long> (2));
    auto dfs = [&] (auto &&f, int X, int F) -> void {
      for (int Y : adj[X]) {
        if (Y != F) {
          f(f, Y, X);
          for (int i = 0; i < 2; ++i) {
            dp[X][i] += max(dp[Y][0] + abs(V[X][i] - V[Y][0]), dp[Y][1] + abs(V[X][i] - V[Y][1]));
          }
        }
      }
    };
    dfs(dfs, 0, -1);
    cout << max(dp[0][0], dp[0][1]) << '
';
  }
}

View Code

D[CF1188B(2300)]

考虑这个式子的形式,发现很像平方差公式,于是两边同时乘以$(a_i-a_j)$,变成$(a^4_i-a^4_j) = k(a_i-a_j)$ $mod$ $p$。

移项可得$a^4_j-ka_j=a^4_i-ka_i$,于是利用$map$计数即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
int n, p, k;
map<int, int> mp;
int main() {
    scanf("%d%d%d", &n, &p, &k);
    for(int i = 1; i <= n; ++i) {
        int t; scanf("%d", &t);
        ++mp[((1LL * t * t % p * t % p * t % p - 1LL * k * t % p) % p + p) % p];
    }
    int ans = 0;
    for(map<int, int> :: iterator it = mp.begin(); it != mp.end(); ++it) ans = (ans + 1LL * it -> second * (it -> second - 1) / 2 % p) % p;
    printf("%d
", ans);
    return 0;
}

View Code

《2021暑假模拟赛8》有一个想法
  1. Wow, superb blog structure! How lengthy have you been running a blog for?
    you make blogging look easy. The overall glance of your web site is wonderful, let alone the content material!
    You can see similar here najlepszy sklep

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注