NOTE
比赛链接：Codeforces Round 1093 (Div. 2)

A - Blocked#

关键词：构造

思路#

注意到数组中不能出现两个相同的元素，因为总有一个位置会被阻塞。

Code#

1
// Problem: CF 2220 A
2
// Contest: Codeforces - Codeforces Round 1093 (Div. 2)
3
// URL: https://codeforces.com/contest/2220/problem/A
4
// Time: 2026-05-23 10:53:51
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    int n;
29
    cin >> n;
30

31
    vector<int> a(n);
32
    for (int i = 0; i < n; i++)
33
        cin >> a[i];
34

35
    sort(all(a));
36

37
    for (int i = 1; i < n; i++)
38
    {
39
        if (a[i] == a[i - 1])
40
        {
41
            cout << -1 << endl;
42
            return;
43
        }
44
    }
45

46
    for (int i = n - 1; i >= 0; i--)
47
        cout << a[i] << " ";
48
    cout << endl;
49
}
50

51
int main()
52
{
53
    fastio();
54

55
    int T = 1;
56
    cin >> T;
57

58
    while (T--)
59
        solve();
60

61
    return 0;
62
}

B -OIE Excursion#

关键词：思维，贪心

思路#

考虑什么情况下他无论如何也过不去：考虑一段计时器相同的监视者。设这一段有 $l$ 个，由于每次只能移动 $1$ 格，所以至少需要 $l$ 秒来通过，故当周期小于 $l+1$ （有一秒是被监视的，不能通过）秒时不能通过该段。

Code#

1
// Problem: CF 2220 B
2
// Contest: Codeforces - Codeforces Round 1093 (Div. 2)
3
// URL: https://codeforces.com/contest/2220/problem/B
4
// Time: 2026-05-23 10:59:20
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    int n, m;
29
    cin >> n >> m;
30

31
    vector<int> a(n);
32
    for (int i = 0; i < n; i++)
33
        cin >> a[i];
34

35
    int mx = 1;
36

37
    for (int i = 0; i < n;)
38
    {
39
        int j = i;
40

41
        while (j < n && a[j] == a[i])
42
            j++;
43

44
        mx = max(mx, j - i);
45
        i = j;
46
    }
47

48
    if (mx < m)
49
        cout << "YES" << endl;
50
    else
51
        cout << "NO" << endl;
52
}
53

54
int main()
55
{
56
    fastio();
57

58
    int T = 1;
59
    cin >> T;
60

61
    while (T--)
62
        solve();
63

64
    return 0;
65
}

C - Grid L#

关键词：数学

思路#

一个 $n \times m$ 网格有： $(n+1) \times m$ 个横向单位边， $n \times (m+1)$ 个纵向单位边，则总边数为 $2nm+n+m$ 。

则第一个必要条件为： $p+2q=2nm+n+m$ 。

不妨设 $n \le m$ ，纵向边数为 $V=n(m+1)$ ，横向边数为 $H=(n+1)m$ ，差值为 $H-V=(n+1)m-n(m+1)=m-n$ 。每个 L 形块都会同时消耗一条横边和一条竖边，所以它无法消除横竖数量的差异，因此，最后至少有 $m-n$ 条多出来的横边必须用单独线段覆盖。

则第二个必要条件为： $p \ge m-n$ 。

关于充分性的证明：当 $n \le m$ 时，较少的是纵边，数量为： $V=n(m+1)$

可以证明所有纵边都能各自配到一条不同的相邻横边，形成 L 形块。

也就是说，一个 $n \times m$ 网格最多能放： $n(m+1)$ 个 L 形块。

而条件 $p \ge m-n$ 等价于： $q \le n(m+1)$ 。

所以只要满足总边数和 $p \ge m-n$ ，就一定可以放下 $q$ 个 L 形块，剩下的边全部用 $p$ 个单独线段补上。

下面我们考虑，如何找到 $n, m$ ，使得 $2nm+n+m=p+2q$ ，就是数学方法了。

直接暴力枚举因子 $a$ ，通过 $S / a$ 计算 $b$ ，再算出 $n, m$ ，检查 $|n-m| \le p$ 即可。

Code#

1
// Problem: CF 2220 C
2
// Contest: Codeforces - Codeforces Round 1093 (Div. 2)
3
// URL: https://codeforces.com/contest/2220/problem/C
4
// Time: 2026-05-23 12:07:18
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    ll p, q;
29
    cin >> p >> q;
30

31
    ll S = 2 * (p + 2 * q) + 1;
32
    for (ll a = 3; a * a <= S; a += 2)
33
    {
34
        if (S % a != 0)
35
            continue;
36

37
        ll b = S / a, n = (a - 1) / 2, m = (b - 1) / 2;
38

39
        if (n >= 1 && m >= 1 && abs(n - m) <= p)
40
        {
41
            cout << n << " " << m << endl;
42
            return;
43
        }
44
    }
45
    cout << -1 << endl;
46
}
47

48
int main()
49
{
50
    fastio();
51

52
    int T = 1;
53
    cin >> T;
54

55
    while (T--)
56
        solve();
57

58
    return 0;
59
}