AtCoder Beginner Contest 230 A ～ G 题解

A. AtCoder Quiz 3

按题目要求输出就行

void solve() {
  int a;
  cin >> a;
  if (a >= 42) ++a;
  printf("AGC%03d", a);
}

B. Triple Metre

就加长一下然后find就好了

void solve() {
  string s;
  for (int i = 0; i < 10; ++i) {
    s += "oxx";
  }
  string ss;
  cin >> ss;
  cout << (s.find(ss) != s.npos ? "Yes" : "No");
}

C. X drawing

判断一下在不在线上就好，我的写法蠢了...

#define ll __int128_t
 
unsigned long long n, a, b, p, q, r, s;
ll la, lb, ra, rb, la2, ra2, lb2, rb2;
 
ll f1(ll x, ll y) {
  return (rb - lb) * x + (la - ra) * y + ra * lb - la * rb;
}
 
ll f2(ll x, ll y) {
  return (rb2 - lb2) * x + (la2 - ra2) * y + ra2 * lb2 - la2 * rb2;
}
 
void solve() {
  cin >> n >> a >> b;
  cin >> p >> q >> r >> s;
  ll kn1 = min(1 - a, 1 - b), km1 = max(n - a, n - b);
  la = a + kn1, ra = a + km1;
  lb = b + kn1, rb = b + km1;
  ll kn2 = max(1 - a, b - n), km2 = min(n - a, b - 1);
  la2 = a + kn2, ra2 = a + km2;
  lb2 = b - kn2, rb2 = b - km2;
  for (ll i = p; i <= q; ++i) {
    for (ll j = r; j <= s; ++j) {
      if (f1(i, j) == 0 || f2(i, j) == 0) {
        cout << '#';
      }
      else {
        cout << '.';
      }
    }
    cout << '\n';
  }
}

因为变成int128前还加了一次直接爆了ll, 导致wa了两个点然后debug了半小时, 所以读入还得用ull读进来, 主要是不想手写int128的读入...

反正我这写法很蠢就是了, 但是题目也看不太懂就没有想太深

D. Destroyer Takahashi

就经典的贪心排个序贪就完事了

struct node {
  ll l, r;
  bool operator < (const node &a) {
    if (r == a.r) {
      return l > a.l;
    }
    return r <= a.r;
  }
} range[N];
 
void solve() {
  ll n, d;
  cin >> n >> d;
  for (int i = 0; i < n; ++i) {
    cin >> range[i].l >> range[i].r;
  }
  ll ans = 0, ed = -2e9;
  sort(range, range + n);
  for (int i = 0; i < n; ++i) {
    if (range[i].l > ed) {
      ++ans;
      ed = range[i].r + d - 1;
    }
  }
  cout << ans;
}

E. Fraction Floor Sum

经典的数论分块板子, 也不用被名词吓到, 就是枚举值域考虑对这个值域有多少个数可以贡献然后算就好了，说不定有人可以因为这题自己发明数论分块（)，我以前打abc的时候就有道最小生成树的板题但我还不知道kruskal最小生成树，然后自己用并查集加贪心把那道题写出来，还是挺有趣的

void solve() {
  ll n;
  cin >> n;
  ll ans = 0;
  for(ll l = 1 , r; l <= n; l = r + 1) {
	  r = n / (n / l);
	  ans += (r - l + 1) * (n / l);
  }
  cout << ans;
}

F. Predilection

F很妙很妙

属于是不看题解基本不可能做出来的dp

dp也是我的弱项还是需要提高

f就是每一个前缀和最后出现的一次是多少

sum就是每一个前缀和的f值加起来

res就是记录前缀和

cur就是每一个fi值应该是多少

先把前缀和算出来，当前不同前缀和加起来显然也就是sum

如果前缀和是0那就有全部都消失的情况所以要++cur

res上一次出现的f值应该减

然后f[res]现在是cur所以要把cur加到sum

如果所有数都是0就得把非法情况减掉

int a[N];

void solve() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  int sum = 1, cur;
  ll res = 0;
  map f;
  f[0] = 1;
  for (int i = 1; i <= n; ++i) {
    res += a[i];
    cur = sum;
    if (res == 0) ++cur;
    if (cur >= mod) cur -= mod;
    sum -= f[res];
    if (sum < 0) sum += mod;
    f[res] = cur;
    sum += f[res];  
    if (sum >= mod) sum -= mod;
  }
  if (res == 0) --cur;
  cout << cur;
}

G. GCD Permutation

这题还是很有趣的

莫比乌斯函数可以看作是一种容斥，容斥过程中 mu[i] 不为 0 才有效

然后这题先找位置然后再找位置上的数就可以做出来了

初始化先mu筛出来，然后再把i的因子筛出来

然后枚举位置的gcd如果有效就把倍数都加进来然后把莫比乌斯函数的值作为系数乘上每个数的因子乘上有多少个数是他的倍数并且可以重复取然后计算贡献就好了。

int mu[N], pr[N], a[N], sz[N];
bool vis[N];
vector v[N];
map mp;
int num, tot;
 
void shai() {
  mu[1] = 1;
  for (int i = 2; i <= 200000; ++i) {
    if (!vis[i]) {
      pr[++tot] = i;
      mu[i] = -1;
    }
    for (int j = 1; j <= tot && i * pr[j] <= 200000; ++j) {
      vis[i * pr[j]] = 1;
      if (i % pr[j]) mu[i * pr[j]] = -mu[i];
      else {
        mu[i * pr[j]] = 0;
        break;
      }
    }
  }
 
  for (int i = 2; i <= 200000; ++i) {
    for (int j = 2; j <= i / j; ++j) {
      if (i % j == 0) {
        if (mu[j]) {
          v[i].push_back(j);
        }
        if (mu[i / j] && (j * j != i)) {
          v[i].push_back(i / j);
        }
      }
    }
    if (mu[i]) {
      v[i].push_back(i);
    }
  }
}
 
ll calc() {
  mp.clear();
  ll res = 0;
  for (int i = 1; i <= num; ++i) {
    for (auto & j : v[sz[i]]) {
      mp[j]++;
    }
  }
  for (auto & i : mp) {
    res += 1ll * -mu[i.first] * i.second *(i.second + 1) / 2;
  }
  return res;
}
 
void solve() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  shai();
  ll ans = 0;
  for (int i = 2; i <= n; ++i) {
    if (mu[i]) {
      num = 0;
      for (int j = i; j <= n; j += i) {
        sz[++num] = a[j];
      }
      ans += -mu[i] * calc();
    }
  }
  cout << ans;
}