https://codeforces.com/contest/1359

C. Mixing Water

 

题意：给定热水和冷水的温度分别是h，c，按照一杯热水，一杯冷水，一杯热水，一杯冷水······的顺序倒入一个桶里，温度为平均值，问最少倒多少杯后温度与给定温度差值最小。

有两种情况：冷水数=热水数；热水数=冷水数+1。

先考虑第二种，冷水数为0时，温度就是热水，随着冷水数增加，温度逐渐趋近两者的平均值，把式子列出来就可以证明是单调递减的了，类似双曲线。

第一种情况，温度就是两者的平均值，也就是双曲线的渐进线。

所以温度随着杯数递减，趋近平均值，且杯数为1和杯数为2是两个极端，极端外的结果就是极端的值。

而对于范围内的，由于单调，所以可以直接求出给定温度所在位置的杯数，可能在坐标中间，有两个整点，比较一下大小即可。

还要注意精度，最好要把分数比较化成整数比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
int T;
ll h, c, t;
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%lld%lld%lld", &h, &c, &t);
		if (t == h) { puts("1"); continue; }
		if (2 * t <= h + c) { puts("2"); continue; }
		ll x1 = (t - c) / (2 * t - h - c);
		ll x2 = x1 + 1;
		if ((h*x1 + c * (x1 - 1) - t * (2 * x1 - 1))*(2 * x2 - 1) > (t*(2 * x2 - 1) - (h*x2 + c * (x2 - 1)))*(2 * x1 - 1))
			printf("%lld\n", 2 * x2 - 1);
		else printf("%lld\n", 2 * x1 - 1);
	}
	return 0;
}

 

D. Yet Another Yet Another Task

 

题意：给定一个数组 −30≤ai≤30-30\le a_i\le 30，Alice选一个区间，Bob把区间内最大值拿掉，要使得区间剩下的数和最大。问Alice选哪个区间，求最大值。

dp

发现数组里的数很小，所以考虑加入作为dp的一维。

dp[i][j]dp[i][j] 表示选择右端点为 i，区间最大值为 j 的区间的结果。

dp[i]dp[i] 由 dp[i−1]dp[i-1] 转移得到。枚举 dp[i−1]dp[i-1] 的 j ，如果 j 小于等于 aia_i，则加入 aia_i 后，区间最大值变为 aia_i，如果 j 大于 aia_i，加入后最大值仍为 j。

要考虑 j=aij=a_i 时，作为两种转移方式的交叉点额外关注，注意如果 j 等于 aia_i，应该作为第一种转移，因为这里第二种转移直接指定结果了，而不是取最大值。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
int n;
int a[N], ans;
map<int, int>dp[N];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) {
		dp[i][a[i]] = 0;
		for (int j = -30; j <= a[i]; j++) {
			if (dp[i - 1].count(j)) {
				dp[i][a[i]] = max(dp[i][a[i]], dp[i - 1][j] + j);
				ans = max(ans, dp[i][a[i]]);
			}
		}
		for (int j = a[i] + 1; j <= 30; j++) {
			if (dp[i - 1].count(j)) { 
				dp[i][j] = dp[i - 1][j] + a[i];
				ans = max(ans, dp[i][j]);
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

 

E. Modular Stability

 

题意：已知数组的长度和正整数n，要求构造一个递增的数组，1≤a1<a2<⋯<ak≤n1 \le a_1 < a_2 < \dots < a_k \le n，且对于任意非负整数x，不论怎么改变数组元素顺序，(((x mod a1) mod a2)… mod ak−1) mod ak(((x \bmod a_1) \bmod a_2) \dots \bmod a_{k - 1}) \bmod a_k 始终不变，问这样的数组个数。

考虑数组长度为2，且 x=a2x=a_2，则 x%a2%a1=0x\%a_2\%a_1=0，需要 x%a1%a2=0x\%a_1\%a_2=0，由于 a1<a2a_1<a_2，所以 x%a1%a2=x%a1x\%a_1\%a_2=x\%a_1，所以 a2%a1=0a_2\%a_1=0，即 a1a_1 是 a2a_2 的因子。

这时候就可以开始猜结论了，多试几次就能发现只要 a1a_1 是所有数的因子，这个数组一定满足条件，反之也是。

要证明的话，就是要证不论顺序怎么变，结果都等于 x%a1x\%a_1，然而并不会证。

所以只要枚举 a1a_1，让其他数都是它的倍数，求这样的数组个数。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 5e5 + 10;
const ll mod = 998244353;
ll n, k, ans;
ll fac[N], inv[N];
ll power(ll a, int x) {
	ll ans = 1;
	while (x) {
		if (x & 1) ans = (ans * a) % mod;
		a = (a * a) % mod;
		x >>= 1;
	}
	return ans;
}
void init() {
	fac[0] = 1;
	for (int i = 1; i < N; i++) {
		fac[i] = fac[i - 1] * i %mod;
	}
	inv[N - 1] = power(fac[N - 1], mod - 2);
	for (int i = N - 2; i >= 0; i--) {
		inv[i] = inv[i + 1] * (i + 1) % mod;
	}
}
ll C(ll n, ll k) {
	return fac[n] * inv[n - k] % mod*inv[k] % mod;
}
int main() {
	init();
	scanf("%lld%lld", &n, &k);
	for (int a1 = 1; n / a1 >= k; a1++) {
		ans = (ans + C(n / a1 - 1, k - 1)) % mod;
	}
	printf("%lld\n", ans);
	return 0;
}