B
题目大意：Hector 正与西班牙信息学奥林匹克代表队一起在拉科鲁尼亚远足，但他非常想溜出去见他的朋友们 Gustavo、Esomer 和 Dani。为此，他需要穿过一条由 $n$ 个志愿者看守的道路，志愿者们站成一排，编号为 $1$ 到 $n$；第 $i$ 位志愿者负责看守位置 $i$。每个志愿者都有一个内部计时器。最初（第 0 秒），第 $i$ 位志愿者的计时器值为 $a_i$。每秒，所有计时器增加 1。一旦计时器达到 $m$，它会绕回到 0。具体来说，在第 $x$ 秒，第 $i$ 位志愿者的计时器显示值为 $(a_i + x) \pmod m$。第 $i$ 位志愿者只有在他们的计时器恰好为 0 时，才会看守位置 $i$。
数据范围：$1 \le t \le 10^4$，$2 \le n \le 2 \cdot 10^5$，$2 \le m \le 10^9$，$0 \le a_i < m$，$\sum n \le 2 \cdot 10^5$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| void solve() {
ll n, m;
cin >> n >> m;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
rep(i, 0, n - 1) { a[i] = m - a[i] % m; }
int tem = 0;
rep(i, 0, n - 1) {
if (i == 0 || a[i] == a[i - 1])
tem++;
else
tem = 1;
if (tem >= m) {
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
return;
}
|
C
题目大意：Roger 有 $p$ 根单位长度的线段，以及 $q$ 个 L 型拼块，每个 L 型拼块由两根单位长度的线段以直角拼接而成。 他想用所有这些线段与拼块（不能剩余）拼成一个 $n \times m$ 的网格。给定 $p$ 和 $q$，判断是否存在正整数 $n$ 和 $m$，使得用恰好 $p$ 根单位线段和 $q$ 个 L 型拼块（可以旋转）正好拼出一个 $n \times m$ 的网格。
数据范围：$1 \le t \le 100$，$1 \le p, q \le 10^8$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void solve() {
ll p, q;
cin >> p >> q;
ll tem = 2 * p + 4 * q + 1;
for (ll i = 3; i * i <= tem; i += 2) {
if (tem % i != 0) continue;
ll tem2 = tem / i;
ll n = (i - 1) / 2, m = (tem2 - 1) / 2;
if (q > min(n * (m + 1), m * (n + 1))) {
continue;
}
cout << n << ' ' << m << endl;
return;
}
cout << -1 << endl;
return;
}
|
D1
题目大意：本题的简单版与困难版的区别在于最多允许的查询次数。本题允许的查询次数为 66 次。有一个长度为 $2n+1$ 的秘密数组 $a$，其中的元素都是 $1$ 到 $n$ 的整数。每个值恰好出现两次，只有一个值恰好出现三次。你的目标是找出那个出现三次的值对应的三个位置。为此，你最多可以进行 66 次如下操作： 1. 选择一个整数 $k$ 和一个由 $1$ 到 $2n+1$ 之间的 $k$ 个不同下标组成的数组 $s$。2. 你会得到一个答案：在 $a_{s_1}, a_{s_2}, \ldots, a_{s_k}$ 中，有多少个值恰好出现一次。换句话说，就是没有重复出现的数字有多少种。3 出现了 2 次，2 出现了 3 次，这些都属于出现多次，不被计算。
数据范围：$1 \le t \le 500$，$2 \le n \le 1000$。
思路：
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
58
59
60
61
| void ask(int l, vi res) {
cout << "? " << l << ' ';
rep(i, 0, l - 1) cout << res[i] << ' ';
cout << endl;
cout.flush();
}
void report(ll x, ll y, ll z) {
cout << "! " << x << ' ' << y << ' ' << z << '\n';
cout.flush();
}
void solve() {
int n;
cin >> n;
int l = 1, r = 2 * n + 1, mid;
ll x, y, z;
int op;
auto check = [&](vi& res) -> bool {
int cnt = sz(res);
ask(cnt, res);
cin >> op;
if ((cnt - op) % 2 == 1)
return true;
else
return false;
};
while (l <= r) {
mid = (l + r) / 2;
vi tem;
rep(i, 1, mid) tem.push_back(i);
if (check(tem)) {
r = mid - 1;
x = mid;
} else
l = mid + 1;
}
l = 1, r = 2 * n + 1;
while (l <= r) {
mid = (l + r) / 2;
vi tem;
frep(i, 2 * n + 1, mid) tem.push_back(i);
if (check(tem)) {
y = mid;
l = mid + 1;
} else
r = mid - 1;
}
l = y + 1, r = x - 1;
while (l <= r) {
mid = (l + r) / 2;
vi tem;
rep(i, 1, mid) tem.push_back(i);
tem.push_back(x);
if (check(tem)) {
r = mid - 1;
z = mid;
} else
l = mid + 1;
}
report(x, y, z);
return;
}
|
D2
题目大意：简单版与困难版的区别在于允许的查询次数上限不同。本题中最多允许进行 $33$ 次查询。存在一个隐藏数组 $a$，长度为 $2n+1$，其中元素取值为 $1$ 到 $n$ 的整数。每个值恰好出现两次，但有且仅有一个值恰好出现三次。需要找出这个出现三次的值对应的三个位置。你可以进行最多 $33$ 次如下形式的查询： 1. 选择一个整数 $k$，以及一个长度为 $k$ 的数组 $s$，其中包含 $1$ 到 $2n+1$ 之间的互不相同的下标。2. 你会得到一个数值，表示在 $a_{s_1}, a_{s_2}, \ldots, a_{s_k}$ 中，恰好出现一次的不同数值的个数（也就是说，没有重复的数的个数）。
数据范围：$1 \le t \le 500$，$2 \le n \le 1000$，$\sum n \le 2 \times 10^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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| void ask(int l, vi res) {
cout << "? " << l << ' ';
rep(i, 0, l - 1) cout << res[i] << ' ';
cout << endl;
cout.flush();
}
void report(ll x, ll y, ll z) {
cout << "! " << x << ' ' << y << ' ' << z << '\n';
cout.flush();
}
void solve() {
int n;
cin >> n;
int l = 1, r = 2 * n + 1, mid;
ll x, y, z;
int op;
auto check = [&](vi& res) -> bool {
int cnt = sz(res);
ask(cnt, res);
cin >> op;
if ((cnt - op) % 2 == 1)
return true;
else
return false;
};
while (l <= r) {
mid = (l + r) / 2;
vi tem;
rep(i, 1, mid) tem.push_back(i);
if (check(tem)) {
r = mid - 1;
x = mid;
} else
l = mid + 1;
}
l = 1, r = 2 * n + 1;
while (l <= r) {
mid = (l + r) / 2;
vi tem;
frep(i, 2 * n + 1, mid) tem.push_back(i);
if (check(tem)) {
y = mid;
l = mid + 1;
} else
r = mid - 1;
}
l = y + 1, r = x - 1;
while (l <= r) {
mid = (l + r) / 2;
vi tem;
rep(i, 1, mid) tem.push_back(i);
tem.push_back(x);
if (check(tem)) {
r = mid - 1;
z = mid;
} else
l = mid + 1;
}
report(x, y, z);
return;
}
|
