以后不准备把打的每一场比赛的题解都挂在 cnblogs 上了因为我懒。

但这次还是想写写。

A

显然，当 \(n < 42\) 时输出 AGC+str(n)；否则，输出 AGC+str(n+1)。时间复杂度为 \(O(1)\)。

注意需要补足 \(3\) 位。

代码：

#include <stdio.h>

int main(){
	int n;
	scanf("%d", &n);
	if (n < 10){
		printf("AGC00%d", n);
	} else if (n < 42){
		printf("AGC0%d", n);
	} else {
		printf("AGC0%d", n + 1);
	}
	return 0;
}

B

直接暴力枚举是否匹配即可。时间复杂度为 \(O(nM)\)。

代码：

#include <stdio.h>
#include <string.h>

const int N = 10 + 7, M = 3e5;
char s[N], t[M + 7];

int main(){
	int n;
	scanf("%s", &s[1]);
	n = strlen(&s[1]);
	for (int i = 1; i <= M; ){
		t[i++] = 'o';
		t[i++] = 'x';
		t[i++] = 'x';
	}
	for (int i = 1; i + n - 1 <= M; i++){
		bool flag = true;
		for (int j = 1; j <= n; j++){
			if (s[j] != t[i + j - 1]){
				flag = false;
				break;
			}
		}
		if (flag){
			printf("Yes");
			return 0;
		}
	}
	printf("No");
	return 0;
}

C

对于每一个位置 \((i, j)\)，显然当 \(i - a = j - b\) 或 \(i - a = b - j\) 时为黑色。

暴力枚举即可。时间复杂度为 \(O(q - p)(s - r)\)。

代码：

#include <stdio.h>

typedef long long ll;

int main(){
	ll n, a, b, p, q, r, s;
	scanf("%lld %lld %lld", &n, &a, &b);
	scanf("%lld %lld %lld %lld", &p, &q, &r, &s);
	for (ll i = p; i <= q; i++){
		for (ll j = r; j <= s; j++){
			if (i - a == j - b || i - a == b - j){
				printf("#");
			} else {
				printf(".");
			}
		}
		printf("\n");
	}
	return 0;
}

D

显然是一个线段覆盖问题。排序后贪心即可。时间复杂度为 \(O(n \log n)\)。

代码：

#include <iostream>
#include <algorithm>

using namespace std;

typedef struct {
	int l;
	int r;
} Wall;

Wall wall[200007];

bool operator <(const Wall a, const Wall b){
	if (a.r != b.r) return a.r < b.r;
	return a.l < b.l;
}

int main(){
	int n, d, ans = 0;
	cin >> n >> d;
	for (int i = 1; i <= n; i++){
		cin >> wall[i].l >> wall[i].r;
	}
	sort(wall + 1, wall + n + 1);
	for (int i = 1, j = 0x80000000; i <= n; i++){
		if (wall[i].l > j + d - 1){
			j = wall[i].r;
			ans++;
		}
	}
	cout << ans;
	return 0;
}

E

显然是一个数论分块怎么直接出板子。时间复杂度为 \(O(\sqrt{n})\)。

代码：

#include <stdio.h>

typedef long long ll;

int main(){
	ll n, ans = 0;
	scanf("%lld", &n);
	for (register ll i = 1, j; i <= n; i = j + 1){
		ll tn = n / i;
		j = n / tn;
		ans += tn * (j - i + 1);
	}
	printf("%lld", ans);
	return 0;
}

F

如果不存在相同的前缀和，显然可以设 \(dp_i\) 表示前 \(i\) 位可以组成的方案数，则 \(dp_i = 2dp_{i - 1} + 1\)。

现在考虑加入相同的前缀和。设 \(pos\) 表示上一个出现当前前缀和的位置，显然，赛后找规律得出减去 \(dp_{pos - 1}\) + 1 即可。

考虑到 \(1 \sim n\) 整体的前缀和重复没有意义，答案为 \(dp_{n - 1} + 1\)。时间复杂度为 \(O(n \log n)\)。

代码：

#include <iostream>
#include <map>

using namespace std;

typedef long long ll;

const int mod = 998244353;
int dp[200007];
ll sum[200007];
map<ll, int> mp;

int main(){
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++){
		int a;
		cin >> a;
		sum[i] = sum[i - 1] + a;
	}
	for (int i = 1; i < n; i++){
		if (!mp.count(sum[i])){
			dp[i] = (dp[i - 1] * 2 % mod + 1) % mod;
		} else {
			dp[i] = ((dp[i - 1] * 2 % mod - dp[mp[sum[i]] - 1]) % mod + mod) % mod;
		}
		mp[sum[i]] = i;
	}
	cout << (dp[n - 1] + 1) % mod;
	return 0;
}

G

前置芝士：莫比乌斯反演

讲一种比较麻烦的做法。

式子就不推了，反正容斥后推起来也很简单。结果为 \(\frac{\displaystyle\sum_{i = 1}^n \mu(i) \sum_{j = 1}^n \mu(j) (\sum_{i \mid k}^n [j \mid p_k])^2 + n^2 - 2(\sum_{i = 1}^n \varphi(i) - 1) + n - 1}{2}\)。

考虑枚举 \(i\)、所有可能的 \(k\) 及 \(P_k\) 的因数并用打了时间戳的数组和树状数组维护后面那个 \(\sum\) 的值即可。时间复杂度为 \(O(n \sqrt{n} \log n \ln n)\)。

看上去时间复杂度可能比较吓人，但你看到这道题的时限较长且远远跑不满时就放心了，实测最大用时在 \(3 \operatorname{s}\) 左右。

赛后看了一下大家的代码，发现直接暴力可过。我真是个 zz。

代码：

#include <stdio.h>
#include <math.h>

typedef long long ll;

const int N = 2e5 + 7;
int prime[N], phi[N], mu[N], P[N], tree_time[N], val_time[N], val[N];
ll sum[N], tree[N];
bool p[N];

inline void init(int n){
	int cnt = 0;
	p[0] = p[1] = true;
	phi[1] = 1;
	mu[1] = 1;
	for (register int i = 2; i <= n; i++){
		if (!p[i]){
			prime[++cnt] = i;
			phi[i] = i - 1;
			mu[i] = -1;
		}
		for (register int j = 1; j <= cnt && i * prime[j] <= n; j++){
			int t = i * prime[j];
			p[t] = true;
			if (i % prime[j] == 0){
				phi[t] = phi[i] * prime[j];
				mu[t] = 0;
				break;
			}
			phi[t] = phi[i] * (prime[j] - 1);
			mu[t] = -mu[i];
		}
	}
	for (register int i = 1; i <= n; i++){
		sum[i] = sum[i - 1] + phi[i];
	}
}

inline int lowbit(int x){
	return x & (-x);
}

inline void add(int n, int x, ll k, int cur_time){
	while (x <= n){
		if (tree_time[x] != cur_time){
			tree_time[x] = cur_time;
			tree[x] = 0;
		}
		tree[x] += k;
		x += lowbit(x);
	}
}

inline ll get_sum(int x, int cur_time){
	ll ans = 0;
	while (x > 0){
		if (tree_time[x] != cur_time){
			tree_time[x] = cur_time;
			tree[x] = 0;
		}
		ans += tree[x];
		x -= lowbit(x);
	}
	return ans;
}

int main(){
	int n;
	ll ans;
	scanf("%d", &n);
	init(n);
	ans = (ll)n * n - (sum[n] * 2 - 1) * 2 + (n - 1);
	for (register int i = 1; i <= n; i++){
		scanf("%d", &P[i]);
	}
	for (register int i = 1; i <= n; i++){
		for (register int j = i; j <= n; j += i){
			int t = sqrt(P[j]);
			for (register int k = 1; k <= t; k++){
				if (P[j] % k == 0){
					if (mu[k] != 0){
						if (val_time[k] != i){
							val_time[k] = i;
							val[k] = 0;
						}
						add(n, k, mu[k] * (val[k] * 2 + 1), i);
						val[k]++;
					}
					if (k * k != P[j]){
						int tp = P[j] / k;
						if (mu[tp] != 0){
							if (val_time[tp] != i){
								val_time[tp] = i;
								val[tp] = 0;
							}
							add(n, tp, mu[tp] * (val[tp] * 2 + 1), i);
							val[tp]++;
						}
					}
				}
			}
		}
		ans += mu[i] * get_sum(n, i);
	}
	printf("%lld", ans / 2);
	return 0;
}