A - AtCoder Quiz 3

if题

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

signed main()
{
  int N; cin >> N;
  printf("AGC"); printf("%03d\n", (N < 42) ? N : N + 1);

  return 0;
}

B - Triple Metre

判断给定字符串是否是无限个”oxx”的子串

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

signed main()
{
  string S;
  cin >> S; 
  int len = S.size();

  for (int i = 0; i < len; i ++)
  {
    if (S.substr(i, i + 2) == "oo" || S.substr(i, 3) == "oxo" || S.substr(i, 3) == "xxx")
    {
      puts("No");
      return 0;
    }
  }
  puts("Yes");

  return 0;
}

C - X drawing

斜率绝对值为1则打’#’，否则打’.’

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define For(i,a,b) for (int i = a; i <= b; i ++)
#define Dow(i,a,b) for (int i = b; i >= a; -- i)

int ans;

signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int N, A, B; cin >> N >> A >> B;
  int P, Q, R, S; cin >> P >> Q >> R >> S;
  For(i,P,Q){For(j,R,S) putchar((abs(i - j) == abs(A - B)) ? '#' : '.');puts("");}

  return 0;
}

D - Destroyer Takahashi

贪心，一次可摧毁D距离内的所有墙壁，问最小摧毁次数

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

typedef long long ll;
#define int ll

int ans;

signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, d; 
  cin >> n >> d;

  vector<pair<int, int>> a(n);
  for (auto &[l, r] : a)
  {
    cin >> l >> r;
  }

  sort(a.begin(), a.end(), [](const pair<int, int> &x, const pair<int, int> &y){return x.second < y.second;});

  int dl = -1, dr = -1;
  for (auto [l, r] : a)
  {
    if ((dr < l) || (dl > r))
    {
      ans ++;
      dl = r;
      dr = r + d - 1;
    }
  }
  cout << ans << "\n";

  return 0;
}

E - Fraction Floor Sum

数论分块板题

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

typedef long long ll;
#define int ll

signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int N; cin >> N;

  int ans = 0;
  for (int i = 1, j; i <= N; i = j + 1) // r = n / (n / l)
  {
    j = N / (N / i);
    ans += (j - i + 1) * (N / i);
  }
  cout << ans << "\n";

  return 0;
}

F - Predilection

给定一组序列，邻位可以合并并且保留两数sum，问最多可以组成序列个数

我们给出的方案是递推每一层可用方案数，并对重复进行筛选

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int maxn = 2e5 + 5;
const int P = 998244353;
signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int N;
  cin >> N;

  vector<int> a(N + 1, 0);
  for (int i = 1; i <= N; i ++)
  {
    cin >> a[i];
    a[i] += a[i - 1];
  }
  map<int, int> mp;
  vector<int> dp(N, 0);
  for (int i = 1; i < N; i ++)
  {
    if (mp.count(a[i]) == 0)
    {
      dp[i] = (dp[i - 1] * 2 % P + 1) % P;
    }
    else 
    {
      dp[i] = ((dp[i - 1] * 2 % P - dp[mp[a[i]] - 1]) % P + P) % P;
    }
    mp[a[i]] = i;
  }
  cout << (dp[N - 1] + 1) % P << "\n";

  return 0;
}

G - GCD Permutation

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int Prime[maxn], mul[maxn], a[maxn], calc[maxn], tot;
bool NotPrime[maxn];
vector<int> sz[maxn];

inline void EulerSieve()
{
  for (int i = 2; i <= maxn; i ++)
  {
    if (!NotPrime[i]) Prime[++ tot] = i, mul[i] = -1;
    for (int j = 1; Prime[j] <= maxn / i; j ++)
    {
      mul[i * Prime[j]] = -mul[i];
      NotPrime[i * Prime[j]] = true;
      if (i % Prime[j] == 0)
      {
        mul[i * Prime[j]] = 0;
        break;
      }
    }
  }
  for (int i = 2; i <= maxn; i ++)
  {
    if (mul[i] == 0) continue;
    for (int j = i; j <= maxn; j += i)
    {
      sz[j].push_back(i);
    }
  }
}

signed main()
{
  EulerSieve();
  long long ans = 0;
  int n; scanf("%d", &n);
  for (int i = 1; i <= n; i ++) scanf("%d", a + i);
  for (int i = 2; i <= n; i ++)
  {
    if (mul[i] == 0) continue;
    for (int j = i; j <= maxn; j += i)
    {
      for (int k : sz[a[j]])
      {
        calc[k] ++;
        ans += mul[i] * mul[k] * calc[k];
      }
    }
    for (int j = i; j <= maxn; j += i)
    {
      for (int k : sz[a[j]])
      {
        calc[k] --;
      }
    }
  }
  cout << ans << "\n";

  return 0;
}