26江苏省赛

发表于 分类于 ， 阅读次数： 作者 Pomelorin

B. 梦中星河

给定非负整数 \(x\)，求三个非负整数 \(a,b,c\) 满足 \(a\times b+c=x\)，并使得 \(\max(a,b,c)−\min(a,b,c)\) 尽可能小。输出该最小值。要求约 \(O(\sqrt x)\)。

点击查看题解

最佳答案可在 \(x=k(k+1)\) 时取到，形如这样的数间隔为 \(2k\)，约为 \(\sqrt x\)，即枚举答案期望复杂度 \(O(\sqrt x)\)。

\((k+1)^2=k^2+2k+1>k(k+1)\)，也就是说取 \(a=b=\lfloor \sqrt x \rfloor\)，不会错过最佳答案。

从 \(0\) 开始枚举答案 \(i\)，令 \(a=\lfloor \sqrt x \rfloor,b=a+i,c=x-ab\)，如果 \(ab>x\) 则调整为 \(a\gets a-1,b\gets b-1\)，计算此时答案并记录历史最小答案。如果记录的答案小于等于 \(i\)，则输出 \(i\) 即可。

官方题解证明枚举次数为 \(O(x^{1/4})\)。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 0, inf = 1e17;

void solve() {
    ll x, ans = inf;
    cin >> x;
    ll a = sqrt(x), b = a - 1;
    for (ll i = 0;; i++) {
        b++;
        if (a * b > x) {
            a--, b--;
        }
        ll c = x - a * b;
        ans = min(ans, max({a, b, c}) - min({a, b, c}));
        if (ans <= i) {
            cout << ans << endl;
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

A. 舞者僵尸

有 \(n\) 个初始僵尸，第 \(i\) 个在时刻 \(a_i\) 出现在位置 \(b_i\)。每个僵尸出现后，每秒向左右相邻整数点各召唤一个僵尸（新僵尸同理）。求最少秒数，使得数轴上整数区间 \([0,k]\) 内每个点都至少有一个僵尸。要求 \(O(n\log n)\)。

点击查看题解

二分答案 二分秒数，求出每只僵尸的区间，按左端点排序，从 \(-1\) 开始往右端点合并，最后看有没有超过 \(k\) 即可。

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
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define PII pair<ll, ll>

const ll inf = 1e17, N = 1e5 + 10;

ll n, k, a[N], b[N];

bool cmp(PII a, PII b) { return a.first < b.first; }

ll check(ll t) {
	PII s[n + 10];
	for (ll i = 1; i <= n; i++) {
		if (t < a[i]) {
			continue;
		}
		s[i].first = b[i] - (t - a[i]);
		s[i].second = b[i] + (t - a[i]);
	}
	sort(s + 1, s + 1 + n, cmp);
	ll tar = -1;
	for (ll i = 1; i <= n; i++) {
		if (s[i].first <= tar + 1) {
			tar = max(tar, s[i].second);
		}
	}
	if (tar >= k) {
		return 1;
	}
	return 0;
}

void __() {
	cin >> n >> k;
	for (ll i = 1; i <= n; i++) {
		cin >> a[i] >> b[i];
	}

	ll l = 0, r = 3e12 + 100, ans = inf;
	while (l <= r) {
		ll mid = (l + r) / 2;
		if (check(mid)) {
			ans = mid;
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	cout << ans << endl;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	__();
	return 0;
}

F. 进行一个数的数

给定一个长度为 \(n\) 的数组 \(b\)（由原数组 \(a\) 对某个正整数 \(m\) 取模得到），求所有可能的原数组 \(a\) 的 \(\text{mex}\) 值的个数。\(a\) 是非负整数数组，\(m\) 是未知正整数且 \(b_i=a_i \pmod m\)。

点击查看题解

思维题 如果 \(x\) 可以是 \(\text{mex}\)，那么比 \(x\) 小的非负整数都可以。所以问题转化为求最大可能 \(\text{mex}\)。

最优的 \(m\) 应当取 \((\max b)+1\)，这样的话类似于把 \(b\) 放入值域 \([0,m-1]\) 的桶里，答案为桶最小值乘以 \(m\)，再加上最左边的最小值的下标。

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
50
51
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long

const ll inf = 1e17;

void __() {
	ll n, len = -inf;
	cin >> n;
	map<ll, ll> b;
	for (ll i = 1, a; i <= n; i++) {
		cin >> a;
		b[a]++;
		len = max(len, a);
	}
	ll base = inf, mex = 0;
	for (ll i = 0; i <= n; i++) {
		if (b.count(i)) {
			mex++;
		} else {
			break;
		}
	}
	if (len >= mex) {
		base = 0;
	}
	for (ll i = 0; i <= mex - 1; i++) {
		base = min(base, b[i]);
	}
	ll ans = 0;
	for (ll i = 0; i <= len - 1; i++) {
		b[i] -= base;
		if (b[i] >= 1) {
			ans++;
		} else {
			break;
		}
	}
	cout << ans + base * mex + 1 << endl;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	while (t--) {
		__();
	}
	return 0;
}