题目#

给你一个长度为 $N$ 的字符串 $S$ ，由 o 和 x 组成。 $N$ 个袋子排成一行，每个袋子里有一个甜点。 在第 $i$ 个袋子上，如果 $S$ 的第 $i$ 个字符是 “o”，则写下 “命中”；如果是 “x”，则写下 “未中”。 针对每个 $k=1,2,\dots,N$ 求解下面的问题。

高桥从排头的 $k$ 个袋子中取出第一个袋子，吃掉里面的糖果，并保留袋子。 然后，他尽可能多次重复下面的操作。

- 他扔掉手中一个标有 “击中 “的袋子，接过排在最前面的袋子，吃掉里面的糖果，并保留这个袋子。这个动作只能在该行还有一个袋子且他拿着一个标有 “中 “的袋子时进行。

找出他能吃掉的糖果数量。 注意，当他收到一个袋子时，该袋子就会从这一行中移除。

贪心#

初始拿 m 个袋子，最多吃到第 m 个 x 的位置。如果没有第 m 个 x，就全吃完。

1
n = int(input())
2
s = input().strip()
3
res = [n] * (n + 1)
4
cnt = 0
5
for i in range(1, n + 1):
6
    if s[i - 1] == 'x':
7
        cnt += 1
8
    v = cnt
9
    if v <= n and res[v] == n and i >= v:
10
        res[v] = i
11
for k in range(1, n + 1):
12
    print(res[k])

题目#

有一盘有 $N$ 名棋手 $1,2,\dots,N$ 的棋局。 这盘棋采用两位棋手一对一对弈的形式。 在 $N$ 名棋手中举行了 $M$ 次比赛， $A_m$ 和 $B_m$ 两名棋手进入了 $m$ -次比赛的决赛。 求满足以下条件的整数 $x$ 和 $y$ 对的个数。

• $1 \leq x \lt y \leq N$
• 在每次比赛中， $x$ 和 $y$ 中至少有一名棋手晋级决赛。

度数桶#

设 deg[i] = 玩家 i 参加的场次数。

对于一对 (x, y)，它们覆盖的比赛数 = deg[x] + deg[y] - cnt_xy

其中 cnt_xy = x 和 y 共同参加的比赛数。

合法条件：覆盖所有 M 场 → deg[x] + deg[y] - cnt_xy = M

移项：deg[y] - cnt_xy = M - deg[x]

令 need = M - deg[x]，则要求 deg[y] - cnt_xy = need。

对于每个 x：

• need = M - deg[x]

• 如果 0 <= need <= max_deg：

  非邻居：从 by_deg[need] 中找 y，检查 y > x 且 y 不是 x 的邻居。

  邻居：遍历 adj[x]，对每个邻居 y，检查 deg[y] - cnt_xy == need。

1
from collections import defaultdict
2
n, m = map(int, input().split())
3
d = [0] * (n + 1)
4
ad = [defaultdict(int) for _ in range(n + 1)]
5
for _ in range(m):
6
    u, v = map(int, input().split())
7
    d[u] += 1
8
    d[v] += 1
9
    ad[u][v] += 1
10
    ad[v][u] += 1
11
max_d = max(d)
12
by_d = [[] for _ in range(max_d + 1)]
13
for i in range(1, n + 1):
14
    by_d[d[i]].append(i)
15
# print(by_d)
16
ans = 0
17
for x in range(1, n + 1):
18
    need = m - d[x]
19
    if 0 <= need <= max_d:
20
        for y in by_d[need]:
21
            if y > x and y not in ad[x]:
22
                ans += 1
23
        for y, cnt in ad[x].items():
24
            if y > x and d[y] - cnt == need:
25
                ans += 1
26
print(ans)

题目#

给你一个长度为 $N$ 的字符串 $S$ ，它由 o 和 x 组成。 保证 $S$ 中至少有 $K$ 次出现 o。 高桥玩了某个游戏 $N$ 次。 在第 $i$ 次对局中，如果 $S$ 的第 $i$ 个字符是 “o”，他就赢了，如果是 “x”，他就输了。

高桥选择了一对满足以下条件的整数 $l$ 和 $r$ 。

• $1 \leq l \leq r \leq N$
• 他在从 $l$ 之三到 $r$ 之三的对局中至少赢了 $K$ 次。

求从 $l$ （之三）到 $r$ （之三）的对局中胜率的最大可能值。

01分数规划#

问题等价于：选区间 [l, r]，要求 o 的数量 ≥ K，最大化 o的数量 / 区间长度

二分胜率 mid，判定是否存在满足条件的区间。

条件：o的数量 / 区间长度 ≥ mid

⟺ o的数量 - mid × 区间长度 ≥ 0

每个位置：

• o → 1 - mid
• x → -mid

sum[i] = 前 i 个位置的权值和。

条件变为：存在 l < r，使得 sum[r] - sum[l-1] ≥ 0 且 cnt[r] - cnt[l-1] ≥ K。

遍历右端点 r，维护满足 cnt 条件的最小 sum[l-1]。

用数组 mn[t] 记录 cnt = t 时的最小 sum 值。

对于每个 r：

• 如果 cnt[r] ≥ K，可以取 t = cnt[r] - K 对应的最小 sum
• 维护 now = min(mn[0..cnt[r]-K])

判断 sum[r] ≥ now。

mn[cnt[i]] 只在遇到 o 时才可能更新（因为 cnt 变化），所以可以用滚动维护最小值。

1
n, k = map(int, input().split())
2
s = input().strip()
3
s = ' ' + s  # 1-indexed
4

5
cnt = [0] * (n + 1)
6
for i in range(1, n + 1):
7
    cnt[i] = cnt[i - 1] + (1 if s[i] == 'o' else 0)
8

9
def check(mid: float) -> bool:
10
    sum_val = 0.0
11
    now = 1e18
12
    mn = [1e18] * (n + 1)
13
    mn[0] = 0.0
14

15
    for i in range(1, n + 1):
16
        if s[i] == 'o':
17
            sum_val += 1.0 - mid
18
            if cnt[i] >= k:
19
                now = min(now, mn[cnt[i] - k])
20
        else:
21
            sum_val -= mid
22

23
        if sum_val >= now:
24
            return True
25

26
        mn[cnt[i]] = min(mn[cnt[i]], sum_val)
27

28
    return False
29

30
l, r = -0.1, 1.1
31
for _ in range(50):
32
    mid = (l + r) / 2.0
33
    if check(mid):
34
        l = mid
35
    else:
36
        r = mid
37

38
print(f"{l:.8f}")