2022CCPC威海站 铜牌题解 A C D E G I J 补题

A

//木桶效应
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
map<string, int> cham;
pair<string, int> player[N];
int cnt1[6];
int cnt2[6];
int n, m;
int sum;
signed main()
{
  cin >> n;
  for (int i = 1; i <= n; i++)
  {
    for (int j = 0; j < 5; j++)
    {
      string s;
      cin >> s;
      cham[s] = 1;
    }
  }

  cin >> m;
  for (int i = 1; i <= m; i++)
  {
    cin >> player[i].first >> player[i].second;
    if (cham[player[i].first] == 1)
    {
      cnt1[player[i].second]++;
    }
    else
    {
      cnt2[player[i].second]++;
    }
  }
  int res = 0x3f3f3f;
  for (int i = 1; i <= 5; i++)
  {
    res = min(res, cnt1[i] + cnt2[i]);
  }
  for (int i = 1; i <= 5; i++)
  {
    sum += cnt1[i];
  }
  res = min(sum, res);
  cout << res;
  return 0;
}

C

由于只需要输出一组可行解我们只要找到一组即可 

结论：5点不共线一定能找到可行解，先固定4个点找到不共线的第五个点让后再枚举5个点之间线段的情况如果点到另外四个点斜率均不同，该点是中心点输出这组可行解

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define LL long long
#define ph push_back
#define INF 0x3f3f3f3f
#define PII pair<int, int>
#define y second
#define x first
const int N = 3e5 + 10;
int t;
int n;
PII a[N];
bool flag;
void check()
{
  for (int i = 1; i <= 5; ++i)
  {
    set<PII> sa;
    for (int j = 1; j <= 5; ++j)
    {
      if (i == j)
        continue;
      int x1 = a[i].x;
      int y1 = a[i].y;
      int x2 = a[j].x;
      int y2 = a[j].y;
      int x = x2 - x1;
      int y = y2 - y1;
      int tmp = __gcd(x, y);
      tmp = abs(tmp);
      sa.insert({x / tmp, y / tmp});
    }
    if (sa.size() == 4)
    {
      cout << "YES\n";
      cout << a[i].x << " " << a[i].y << "\n";
      for (int j = 1; j <= 5; ++j)
      {
        if (j != i)
          cout << a[j].x << ' ' << a[j].y << "\n";
      }
      flag = 1;
      return;
    }
  }
}

bool invalid(int k)
{
  set<PII> s;
  int temp;
  int x1;
  int y1;
  for (int i = 1; i <= 4; i++)
  {
    x1 = a[i].x - a[k].x;
    y1 = a[i].y - a[k].y;
    temp = __gcd(x1, y1);
    s.insert({x1 / temp, y1 / temp});
  }
  return s.size() != 1;
}
void solve()
{
  flag = 0;
  cin >> n;
  for (int i = 1; i <= n; ++i)
    cin >> a[i].x >> a[i].y;
  for (int i = 5; i <= n; ++i)
  {
    if (invalid(i))
    {
      flag = 1;
      swap(a[i], a[5]);
      break;
    }
  }
  if (flag)
    check();
  else
    cout << "NO\n";
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cin >> t;
  // t = 1;
  while (t--)
  {
    solve();
  }
  return 0;
}

E

//模拟
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, k;
int a[N];
int main()
{
  cin >> n >> k;
  for (int i = 1; i <= n; i++)
  {
    cin >> a[i];
    if (a[i] < k)
    {
      printf("Python 3.%d will be faster than C++", i);
      return 0;
    }
  }
  for (int i = n + 1;; i++)
  {
    if (a[i - 1] >= a[i - 2])
    {
      cout << " Python will never be faster than C++";
      return 0;
    }
    else
    {
      a[i] = 2 * a[i - 1] - a[i - 2];
      if (a[i] < k)
      {
        printf("Python 3.%d will be faster than C++", i);
        return 0;
      }
    }
  }
}

 G

打表，用哈希（各种限制条件）暴力算出循环节长度（有点赌），计算结果

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
const int N = 5000010;
int x, n;
i64 l, r;
int ans[N];
int t[N];
u64 ts[N];
u64 tm[N];
u64 xo[N];
int pos;
bool check(int l, int r)
{
  for (int a = 1, b = l + 1; b <= r; a++, b++)
  {
    if (t[a] != t[b])
      return false;
  }
  return true;
}
i64 cal(int x)
{
  int T = x / pos;
  int Z = x % pos;
  return T * ans[pos] + ans[Z];
}
signed main()
{
  cin >> x;
  for (i64 i = 1; i <= 5000000; i++)
  {
    i64 tep = __gcd((i * x) ^ x, x);
    t[i] = tep;
    ts[i] = ts[i - 1] + tep;
    tm[i] = tm[i - 1] + tep * tep;
    xo[i] = xo[i - 1] ^ tep;
    if (tep == 1)
      ans[i] = ans[i - 1] + 1;
    else
      ans[i] = ans[i - 1];
    if (i % 2 == 0)
    {
      int j = i / 2;
      if (ts[j] + ts[j] != ts[i])
        continue;
      if (tm[j] + tm[j] != tm[i])
        continue;
      if (xo[i])
        continue;
      if (__builtin_popcount(i) != 1)
        continue;
      if (!check(j, i))
        continue;
      pos = i;
    } //得到循环节结束的位置，即长度
  }
  cin >> n;
  while (n--)
  {
    cin >> l >> r;
    cout << cal(r) - cal(l - 1) << endl;
  }
}