ABC341A-D题解

A

题目

这个没什么好说的，就先输出一个 1，再输出 $n$ 个 01就大功告成了。

AC Code：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int n;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	cout << 1;
	for (int i = 1; i <= n; i ++) cout << "01";
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

B

题目

要获取更多 $x$ 国货币，只能用 $x-1$ 国货币换。
所以我们可以从 $1$ 国一直换到 $n$ 国，输出，结束。

AC Code：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int n;
long long a[200100];
int s[200100], t[200100];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	for (int i = 1; i < n; i ++) cin >> s[i] >> t[i];
	for (int i = 1; i < n; i ++) {
		a[i + 1] += t[i] * (a[i] / s[i]);
	}
	cout << a[n];
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

C

题目

你会发现，$500^3<2\cdot 10^8$，所以可以暴力枚举高桥所在的位置，如果他行进的过程中没有经过海洋就将答案加一。如果经过海洋了就直接枚举下一个点。

AC Code：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int h, w, n;
char m[510][510];
string s;
map<char, int> dir;
int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
int ans;
bool check(int x, int y) {
	for (int i = 0; i < n; i ++) {
		int nx = x + dx[dir[s[i]]], ny = y + dy[dir[s[i]]];
		if (nx > 0 && nx <= h && ny > 0 && ny <= w && m[nx][ny] == '.') {
			x = nx;
			y = ny;
		}
		else return 0;
	}
	return 1;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> h >> w >> n;
	cin >> s;
	for (int i = 1; i <= h; i ++) {
		for (int j = 1; j <= w; j ++) cin >> m[i][j];
	}
	dir['L'] = 0, dir['R'] = 1, dir['U'] = 2, dir['D'] = 3;
	for (int i = 1; i <= h; i ++) {
		for (int j = 1; j <= w; j ++) {
			if (m[i][j] == '.') {
				ans += check(i, j);
			}
		}
	}
	cout << ans;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

D

题目

这个题并不难，但是细节很多，仔细看！我因为一些零碎的细节卡了 40min！

首先，我们先讨论那些“有规律”的部分。我们发现，对于两个数 $n$ 和 $m$，在 $nm$ 范围内有 $n+m-2\times \gcd (n,m)$ 个数满足只被 $n$ 和 $m$ 中的一个数字整除。

这个结论怎么来的呢？

首先，对于可以被 $n$ 整除的一共有 $\frac{nm}{n}$ 共 $m$ 个，可以被 $m$ 整除的一共有 $\frac{nm}{m}$ 共 $n$ 个。

那么 $-2\times \gcd (n,m)$ 又是怎么来的呢？

首先，$nm$ 范围内有 $\frac{nm}{\frac{nm}{\gcd (n,m)}}$ 个数即 $\gcd (n,m)$ 个数可以被 $n$ 和 $m$ 整除。我们要在可以被 $n$ 整除的部分减去它，还要在可以被 $m$ 整除的部分减去它。所以是 $-2\times \gcd (n,m)$。

然后我们就可以将答案直接跳到 $nm(k/(n+m-2\gcd (n,m)))$，此时 $k$ 变成 $k\mathrm{mod}(n+m-2\gcd (n,m))$。

我们继续讨论，可以枚举，用 $k1$ 和 $k2$ 两个变量依次跳到答案。如果 $k1$ 跳的远就跳 $k2$，否则跳 $k1$。如果两个跳的一样远就都跳依次，这两次不算在跳的次数内。一共跳 $k$ 次后，较大的就是满足条件的，加到答案上即可。

你以为这就完了？

如果减掉前面“有规律”的部分后，发现 $k$ 等于 $0$ 时，不加任何特判会输出一个 $nm$ 的倍数的数。但是我们要的是最大的比上述不合法答案小的答案。此时如果我们把 $k$ 设为 $n+m-2\gcd (n,m)$，答案减去 $nm$ 就可以解决这个问题。

还有一个很重要的东西：long long！

时间复杂度分析：

按最坏情况来说，$\gcd (n,m)=1$，此时时间复杂度就是 $n+m$，而且跑不到这么多，所以执行次数不会超过 $2\cdot 10^8$，合格。

AC Code：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
long long n, m, k;
long long gcd(long long x, long long y) {
	return x % y == 0ll ? y : gcd(y, x % y);
}
long long ans;
long long cnt;
long long cnt1;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> k;
	long long g = gcd(n, m);
	ans = n * m * (k / (n + m - g * 2));
	k = k % (n + m - g * 2);
	if (k == 0) {
		ans -= n * m;
		k += n + m - g * 2;
	}
	long long k1 = 0ll, k2 = 0ll;
	cnt1 = 0ll;
	for (long long i = 1; i <= k; i ++) {
		if (k1 + n < k2 + m) {
			k1 += n;
		}
		else if (k1 + n > k2 + m) {
			k2 += m;
		}
		else {
			k1 += n;
			k2 += m;
			i--;
		}
	}
	ans += max(k1, k2);
	cout << ans;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

E

什么，不是 A-D题解吗？怎么还有 E？

我才不会给出详细的解法的，我只给一个小小的提示：懒标线段树！