• 周三. 12 月 11th, 2024

5G编程聚合网

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

热门标签

2021暑假模拟赛9

admin

11 月 28, 2021

A[HDU7053(800)]

#include<cstdio>
const double eps = 1e-4;
int T;
double p,q;
void sol()
{
    scanf("%lf%lf",&p,&q);
    if(q>=p)puts("N0 M0R3 BL4CK 1CE TEA!");
    else puts("ENJ0Y YOURS3LF!");
}
int main()
{
    scanf("%d",&T);
    while(T--)sol();
    return 0;
}

View Code

 B[GYM103102B(1600)]

仔细观察这几个操作,目的在于把所有的$1$移到最右边,那么可以通过后缀和算出来把所有的$1$移过去需要几步,然后通过观察,发现这些操作本质上相当于每次减少$1$步或$2$步,那么这就是一个经典的博弈问题了,只需要看总步数$mod3$即可,因为只要后手能控制总步数$mod3=0$那么总是能赢的。

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string S;
  cin >> S;
  int N = S.size();
  long long cnt = 0;
  long long zero = 0;
  for (int i = N - 1; i >= 0; --i) {
    if (S[i] == '0') {
      zero ++;
    } else {
      cnt += zero;
    }
  }
  if (cnt % 3 == 0) {
    cout << "Bob" << '
';
  } else {
    cout << "Alice" << '
';
  }
}

View Code

C[HDU7055(1600)]

首先考虑对于每个字符单独统计,设某字符在前缀$[1…i]$中出现次数为$cnt[i]$,那么这个字符的贡献是$sum_{i=1}^{n}sum_{j=i+1}^{n}{(cnt[j]-cnt[i])^2}$。

把这个式子拆一下,得到$(n-1)sum_{i=1}^{n}{cnt[i]^2}-sum_{i=1}^{n}sum_{j=i+1}^{n}{2cnt[i]cnt[j]}$,用前缀和计算即可,不过需要比较精细的实现防止超时。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int mod = 998244353;
int pre[N];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    int n = s.size();
    long long ans = 0;
    for (char c = 'a'; c <= 'z'; ++c) {
      for (int i = 0; i < n; ++i) {
        pre[i + 1] = pre[i] + (s[i] == c);
      }
      long long s = 0;
      for (int i = 1; i <= n; ++i) {
        ans += 1ll * pre[i] * pre[i] * n;
        ans -= 2ll * pre[i] * s;
        ans %= mod;
        if (ans < 0) {
          ans += mod;
        }
        s += pre[i];
      }
    }
    cout << ans << '
';
  }
}

View Code

D[CF1537F(2200)]

这种题一般是一个套路,首先观察这个操作,发现本质上相当于一个点可以把自己的权值随意传给到自己距离为偶数的点。那么将这张图二分图染色,如果能染色则白色与白色黑色与黑色之间能互相传递,否则整张图能直接随便传递,于是最后分类讨论一下即可。

#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, M;
    cin >> N >> M;
    vector<long long> v(N);
    for (int i = 0; i < N; ++i) {
      cin >> v[i];
    }
    vector<long long> t(N);
    for (int i = 0; i < N; ++i) {
      cin >> t[i];
    }
    vector<vector<int>> adj(N);
    for (int i = 0; i < M; ++i) {
      int X, Y;
      cin >> X >> Y;
      X --;
      Y --;
      adj[X].push_back(Y);
      adj[Y].push_back(X);
    }
    vector<int> col(N, -1);
    auto dfs = [&] (auto &&f, int X, int C) -> bool {
      col[X] = C; 
      for (int Y : adj[X]) {
        if (col[Y] == -1) {
          if (!f(f, Y, C ^ 1)) {
            return false;
          }
        } else if (col[X] == col[Y]) {
          return false;
        }
      }
      return true;
    };
    if (!dfs(dfs, 0, 0)) {
      if (abs(accumulate(v.begin(), v.end(), 0LL)) % 2 == abs(accumulate(t.begin(), t.end(), 0LL)) % 2) {
        cout << "YES" << '
';
      } else {
        cout << "NO" << '
';
      }
    } else {
      vector<long long> dv(2);
      vector<long long> dt(2);
      for (int i = 0; i < N; ++i) {
        dv[col[i]] += v[i];
        dt[col[i]] += t[i];
      } 
      if (dv[0] - dt[0] == dv[1] - dt[1]) {
        cout << "YES" << '
';
      } else {
        cout << "NO" << '
';
      }
    }
  }
}

View Code

发表回复