【比赛】 AtCoder Beginner Contest 171

题意/题解

A Calc

• 题意：给你 \(a\) 输出 \(a + a * a + a * a * a\)。
• 题解：直接输出，不会爆int

B Minor Change

• 题意：给你两个字符串 \(s\) 和 \(t\) 可以进行选择 \(t\) 中的一个字符替换成另一个字符的操作， 问你最少多少次把 \(t\) 变成 \(s\)
• 题解：答案就是不同之处的数量。

C Tsundoku

• 题意：两个桌子，每个桌子上都有一摞书，上面的必须读完才能读下面的，给你时间 \(k\)，问在 \(k\) 的时间内最多读几本书。
• 题解：前缀和 + 二分。先用前缀和记录每个桌子上读前 \(i\) 本要花的时间，然后枚举第一个桌子上读几本，可知剩下多少时间，然后二分找第二个桌子上读几本即可。

D Sum of Divisors

• 题意：\(f(x)\) 表示 \(x\) 的约数个数，求 \(\sum_{i = 0}^{n} i * f(i)\)
• 题解：线性筛约数个数。

E NEQ

• 题意：咕咕咕
• 题解：咕咕咕

F Unfair Nim

• 题意：咕咕咕
• 题解：咕咕咕

代码

A Calc

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>

int main() {
	int a;
	scanf("%d", &a);
	printf("%d\n", a + a * a + a * a * a);
	return 0;
}

B Minor Change

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>

std:: string s1, s2;

int main() {
	std::cin >> s1 >> s2;
	int len = s1.length(), ans = 0;
	for (int i = 0; i < len; ++i) {
		if (s1[i] != s2[i]) ++ans;
	}
	printf("%d\n", ans);
	return 0;
}

C Tsundoku

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define MAXN 200001

int n, m, k, ans, a[MAXN], b[MAXN];
long long suma[MAXN], sumb[MAXN];

int max(int a, int b) { return a > b ? a : b; }

int main() {
	scanf("%d %d %d", &n, &m, &k);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		suma[i] = suma[i - 1] + a[i];
	}
	for (int i = 1; i <= m; ++i) {
		scanf("%d", &b[i]);
		sumb[i] = sumb[i - 1] + b[i];
	}
	for (int i = 0; i <= n; ++i) {
		int temp = k - suma[i];
		if (temp == 0) ans = max(ans, i);
		if(temp < 0) break;
		int pos = std::upper_bound(sumb + 1, sumb + m +1, temp) - sumb;
		ans = max(ans, i + pos - 1);
	}
	printf("%d\n", ans);
	return 0;
}

D Sum of Divisors

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define MAXN 10000001

typedef long long ll;
ll n, d[MAXN], num[MAXN];
ll ans, cnt, prime[MAXN];
bool vis[MAXN];

void getd(int N) {
    d[1] = 1, num[1] = 1;
    for (int i = 2; i <= N; ++i) {
        if (!vis[i]) {
            prime[++cnt] = i;
            d[i] = 2, num[i] = 1;
        }
        for (int j = 1; j <= cnt; ++j) {
            if (i * prime[j] > n) break;
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
            	d[i * prime[j]] = d[i] / (num[i] + 1) * (num[i] + 2);
            	num[i * prime[j]] = num[i] + 1;
            	break;
            }
            else {
            	d[i * prime[j]] = d[i] * 2;
            	num[i * prime[j]] = 1;
            }
        }
    }
}

int main() {
	scanf("%lld", &n);
	getd(n);
	for (int i = 1; i <= n; ++i) {
		ans += 1ll * i * d[i];
	}
	printf("%lld\n", ans);
	return 0;
}

rating

反思：

• 太菜了。
• 数论不行，\(D\) 题花了太长时间

【比赛】 AtCoder Beginner Contest 171

原文：https://www.cnblogs.com/poi-bolg-poi/p/13200116.html