AtCoder Beginner Contest 230
以后不准备把打的每一场比赛的题解都挂在 cnblogs 上了因为我懒。
但这次还是想写写。
A
显然，当 \(n < 42\) 时输出 AGC+str(n)；否则，输出 AGC+str(n+1)。时间复杂度为 \(O(1)\)。
注意需要补足 \(3\) 位。
代码：
#include
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
#include
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
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
#include
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
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
#include 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} \ln n)\)。
赛后看了一下大家的代码，发现直接暴力可过。我赛时居然还写了树状数组。我真是个 zz。
代码：
#include
#include
typedef long long ll;
const int N = 2e5 + 7;
int prime[N], phi[N], mu[N], P[N], tm[N], val[N];
ll sum[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];
}
}
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 (tm[k] != i){
tm[k] = i;
val[k] = 0;
}
ans += mu[i] * mu[k] * ((val[k]++) * 2 + 1);
}
if (k * k != P[j]){
int tp = P[j] / k;
if (mu[tp] != 0){
if (tm[tp] != i){
tm[tp] = i;
val[tp] = 0;
}
ans += mu[i] * mu[tp] * ((val[tp]++) * 2 + 1);
}
}
}
}
}
}
printf("%lld", ans / 2);
return 0;
}