ABC457#

Tasks - Polaris.AI Programming Contest 2026（AtCoder Beginner Contest 457）

首次破D且运气很好做过类似的G，排名最高的一把（~~差点被关在空教室回不来~~）我终于会折叠标题了！！！

A - 模拟

简单模拟.

1
n = int(input())
2
a = list(map(int,input().split()))
3
x = int(input())
4
print(a[x-1])

B - 模拟

比A好理解的模拟（我是不会告诉你赛时A我看了2分钟不知道没看出来要求属什么，甚至以为是递增序列的）

1
n = int(input())
2
g = []
3
for _ in range(n):
4
    t = list(map(int,input().split()))
5
    g.extend([t[1:]])
6
x,y = map(int,input().split())
7
print(g[x-1][y-1])

C - 模拟

简单模拟，值得注意的是k的取值会非常大，因此直接存会RE

判断k是否大于当前序列ai在b中的总长度，如果小于，说明要找的目标在后面的序列，k-cur

否则，目标值在当前ai的重复块中，(k-1) % L即可求得目标

1
n, k = map(int, input().split())
2
g = []
3
for _ in range(n):
4
    t = list(map(int, input().split()))
5
    g.append(t[1:])
6
c = list(map(int, input().split()))
7
for i in range(n):
8
    cur = len(g[i]) * c[i]
9
    if k > cur:
10
        k -= cur
11
    else:
12
        print(g[i][(k - 1) % len(g[i])])
13
        break

D - 二分答案

二分答案是一中求最小的最大可能值的很有效的方法

check()函数的作用用于判断经操作后数组中的所有值能否大于mid

c++在处理本题时要注意数据的范围非常大

1
n, k = map(int, input().split())
2
a = list(map(int, input().split()))
3
def check(mid):
4
    ops = 0
5
    for i, x in enumerate(a):
6
        if x < mid:
7
            t = (mid - x + i) // (i + 1)
8
            ops += t
9
            if ops > k:
10
                return False
11
    return True
12

13
left = min(a) - 1
14
right = max(a) + k * n + 1
15
while left + 1 < right:
16
    mid = (left + right) // 2
17
    if check(mid):
18
        left = mid
19
    else:
20
        right = mid
21
print(left)

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
using i64 = long long;
5
using u64 = unsigned long long;
6
using u32 = unsigned;
7
using i128 = __int128;
8
using u128 = unsigned __int128;
9
#include <iostream>
10
#include <string>
11
#include <algorithm>
12
using namespace std;
13

14
void print_i128(__int128 x) {
15
    if (x == 0) {
16
        cout << '0';
17
        return;
18
    }
19
    if (x < 0) {
20
        cout << '-';
21
        x = -x;
22
    }
23
    string s;
24
    while (x) {
25
        s += char('0' + (int)(x % 10));
26
        x /= 10;
27
    }
28
    reverse(s.begin(), s.end());
29
    cout << s;
30
}
31
int main(){
32
    i64 n,k;
33
    cin >> n >> k;
34
    vector<i64> a(n);
35
    for(int i = 0;i < n ;i++){
36
        cin >> a[i];
37
    }
38

39

40
    auto check = [&](i128 mid){
41
        i128 pos = 0;
42
        for(int i = 0;i < n;i++){
43
            if(mid > a[i]){
44
                i128 t = (mid - a[i] + i)/(i+1);
45
                pos += t;
46
                if(pos > k){
47
                    return false;
48
                }
49
            }
50
        }
51
        return true;
52
    };
53

54
    i128 l = *min_element(a.begin(),a.end()) - 1;
55
    i128 r = *max_element(a.begin(),a.end()) + (i128)k*n + 1;
56
    while (l + 1 < r){
57
        i128 mid = (l + r)/2;
58
        if (check(mid)){
59
            l = mid;
60
        }
61
        else{
62
            r = mid;
63
        }
64
    }
65
    print_i128(l);
66
    cout << endl;
67
    return 0;
68
}

G - 偏序集 + 最长上升子序列

题意：

我们有 $N$ 个事件 $(t_i, x_i)$ 。

一个机器人可以先后收集两个事件 $(t_1, x_1)$ 和 $(t_2, x_2)$ （假设 $t_1 \le t_2$ ）当且仅当它们满足“速度约束”：

|x_1 - x_2| \le t_2 - t_1

也就是说，机器人在时间差内最多移动距离不超过时间差。

把这一条件改写，引入变量

u = x + t, \quad v = x - t

则上述条件等价于（设 $t_1 \le t_2$ ）：

u_1 \le u_2 \quad \text{且} \quad v_1 \le v_2

因此，能被同一个机器人收集的事件，在 $(u, v)$ 坐标系下，必须具有两维都不减小的偏序关系。

题解：

**偏序集与 **Dilworth 定理

我们把每个事件抽象成一个点 $(u, v)$ ，并定义偏序关系：

P_1 \le P_2 \iff u_1 \le u_2 \ \text{且}\ v_1 \le v_2

我们要找的是最少的单调链，这种链中元素全都可以被同一个机器人按照时间顺序收集

Dilworth 定理：

最小链划分的大小 = 最长反链的大小

反链是集合中任意两点不可比较的集合，即对于任意两点 $P_1, P_2$ ，不能同时满足 $u_1 \le u_2 \ \text{且}\ v_1 \le v_2$ 。

在二维平面上按 $u$ 坐标排序后，反链在 $v$ 坐标上一定是严格递减的。

如果 $u_1 < u_2$ 且 $v_1 \le v_2$ ，那么它们就是可比较的（自然可以放在同一条链中），这就不属于反链。

因此，要构成反链，当 $u$ 递增时， $v$ 必须严格递减。

最长反链的长度 = 最长严格递减子序列（ $v$ ** 坐标）的长度**

如果 $u_1 = u_2$ ，那么除非 $v_1 = v_2$ （不可能，因为 $(t,x)$ 不同），否则它们 $v_1 \neq v_2$ 。

如果 $x + t$ 相同且 $x - t$ 不同，那么它们的 $(t, x)$ 不同，但无论如何，它们的时间 $t = (u - v)/2$ 不一定相同。

因此，当 $u$ 相同时，先按 $v$ 降序排序，可使相同 $u$ 的点不会错误地构成一条链，因为这时 $v$ 递减，不会满足 $v_1 \le v_2$ 的要求。

由此得出求最大反链 = 最长严格递减子序列

按 $u$ 升序、 $u$ 相同时按 $v$ 降序排序后，原偏序关系变成：

要两点可比，必须同时满足 $u$ 递增且 $v$ 递增（因为相同的 $u$ 我们已经按 $v$ 降序安排，它们之间无法再形成 $v$ 递增）。

于是，任何一个反链在这样的排序下就是 $v$ 严格递减的子序列。

1
import sys
2
import bisect
3
input = sys.stdin.readline
4
n = int(input())
5
a = []
6
for _ in range(n):
7
    t, x = map(int, input().split())
8
    a.append((x + t, x - t))
9
a.sort(key=lambda p: (p[0], -p[1]))
10
b = [p[1] for p in a]
11
res = []
12
for b in b:
13
    pos = bisect.bisect_left(res, b)
14
    if pos == len(res):
15
        res.append(b)
16
    else:
17
        res[pos] = b
18
print(len(res))

E - 数据结构 + 二分查找

一道数据结构题，难点在于高效的存储和查询数据(暂未补)

1
import sys
2
from bisect import bisect_right, bisect_left
3
from collections import defaultdict
4
input = sys.stdin.readline
5
N, M = map(int, input().split())
6
by_l = [[] for _ in range(N + 1)]
7
by_r = [[] for _ in range(N + 1)]
8
cnt = defaultdict(int)
9
INF = 10**9
10
min_r_at_l = [INF] * (N + 2)
11
for _ in range(M):
12
    L, R = map(int, input().split())
13
    by_l[L].append(R)
14
    by_r[R].append(L)
15
    cnt[(L, R)] += 1
16
    if R < min_r_at_l[L]:
17
        min_r_at_l[L] = R
18

19
for i in range(1, N + 1):
20
    by_l[i].sort()
21
    by_r[i].sort()
22

23
suf_min_r = [INF] * (N + 3)
24
for i in range(N, 0, -1):
25
    suf_min_r[i] = min(suf_min_r[i + 1], min_r_at_l[i])
26

27
Q = int(input())
28
ans = []
29

30
for _ in range(Q):
31
    S, T = map(int, input().split())
32

33
    if cnt[(S, T)] > 0:
34
        ok = False
35
        ok |= cnt[(S, T)] >= 2
36
        ok |= suf_min_r[S + 1] <= T
37
        ok |= suf_min_r[S] <= T - 1
38
        print("Yes" if ok else "No")
39
        continue
40

41
    ok = False
42

43
    rs = by_l[S]
44
    pos_r = bisect_right(rs, T) - 1
45

46
    ls = by_r[T]
47
    pos_l = bisect_left(ls, S)
48

49
    if pos_r >= 0 and pos_l < len(ls):
50
        r1 = rs[pos_r]
51
        l2 = ls[pos_l]
52
        ok |= l2 <= r1 + 1
53
    print("Yes" if ok else "No")

音乐

音乐

ABC457#

音乐

目录

音乐

音乐

ABC457-二分答案/偏序集+最长上升子序列/数据结构+二分查找

ABC457#

音乐

目录