Problem F. Flower

问题描述

Yuki 面前有一朵含 n 片花瓣的花，她会进行多轮操作：每轮先摘 a 片花瓣，再摘 b 片花瓣（若剩余不足则摘完），直到花瓣全部摘完。她离开的条件是：最后一片花瓣是在某轮的前 a 片花瓣中被摘下的；否则她会留下。

我们可以提前摘一些花瓣（不能全摘），确保她留下。求最少需要提前摘的花瓣数量；若不可能，输出 “Sayonara”。

输入

  • 第一行：整数 t（测试用例数）。

  • 每个测试用例：三个整数 n, a, b（花瓣总数、每轮先摘数量、每轮后摘数量）。

  • 1 ≤ t ≤ 100

  • 1 ≤ n ≤ 10⁹

  • 1 ≤ a, b ≤ 10⁹

输出

  • 若能让 Yuki 留下，输出最少提前摘的花瓣数。
  • 否则，输出 “Sayonara”。

题解

核心分析

Yuki 的每轮操作可视为 “先摘 a 片，再摘 b 片”，每轮最多摘 T = a + b 片（T 为单轮操作的最大花瓣数）。关键是判断最后一片花瓣的位置：

  • 若最后一片在某轮的前 a 片中 → Yuki 离开。
  • 若最后一片在某轮的后 b 片中 → Yuki 留下。

我们需要通过提前摘花瓣（设数量为 x），使剩余花瓣 m = n - x（m > 0）满足：最后一片花瓣在某轮的后 b 片中。

分情况

  1. 当 n ≤ a 时： Yuki 第一轮就会摘完所有花瓣（因 n ≤ a，最后一片在前 a 片中），她会离开。 若提前摘 x 片（x > 0，m = n - x > 0），则 m < n ≤ a，同样最后一片在前 a 片中，无法让她留下。故输出 “Sayonara”。
  2. 当 n > a 时： 计算 n 除以 T 的商 k = n // T 和余数 r = n % T（即 n = k*T + r，0 ≤ r < T）：
    • 若 r = 0：刚好 k 轮摘完，最后一片在第 k 轮的后 b 片中 → 无需提前摘，x = 0。
    • 若 r > a：最后一轮先摘 a 片，剩余 r - a 片（> 0），再摘 b 片（摘完 r - a 片），最后一片在后 b 片中 → 无需提前摘，x = 0。
    • 若 0 < r ≤ a：最后一轮仅摘 r 片（前 a 片中），Yuki 会离开。需提前摘 x = r 片，剩余 m = k*T（刚好 k 轮，最后一片在后 b 片中）→ x = r。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main() {
    int t; cin >> t;
    while (t--) {
        ll n, a, b;
        cin >> n >> a >> b;
        if (n <= a) {
            cout << "Sayonara\n";
        } else {
            ll T = a + b;
            ll r = n % T;
            if (r == 0 || r > a) {
                cout << 0 << '\n';
            } else {
                cout << r << '\n';
            }
        }
    }
    return 0;
}

时间复杂度：O(t)

Problem D. Distant Control

问题描述

有 n 个机器人排成一行，初始状态为开（1）或关（0）。你可以执行两种操作：

  1. 选择 a 个连续且全为开的机器人，将它们全关掉。
  2. 选择 a+1 个连续且全为关的机器人，将它们全打开。

目标是通过若干次操作（可零次），使最终开着的机器人数量最大化。

输入

  • 第一行：整数 t（测试用例数）。

  • 每个测试用例：

    • 第一行：整数 n（机器人数量）和 a（操作参数）。
    • 第二行：长度为 n 的字符串 s，表示初始状态（0 为关，1 为开）。

  • 1 ≤ t ≤ 4×10⁴

  • 2 ≤ n ≤ 2×10⁵

  • 1 ≤ a ≤ n-1

  • 所有测试用例的 n 之和 ≤ 4×10⁵

输出

每个测试用例输出最大可能的开着的机器人数量。

题解

两种操作的影响：

  • 操作 1（关）：减少 a 个开着的机器人（代价）。
  • 操作 2（开）：增加 a+1 个开着的机器人（收益）。

由于 a+1 > a，操作 2 的收益大于操作 1 的代价，因此策略核心是最大化操作 2 的次数，同时考虑是否通过操作 1 创造更多操作 2 的机会。

  1. 连续片段分解：将初始状态分解为连续的 “0 片段”（关）和 “1 片段”（开）。例如 “001” 分解为 (0,2)、(1,1)（类型，长度）。
  2. 基础收益：对每个 0 片段（长度 z），最多可执行 z // t 次操作 2（t = a+1），每次增加 t 个开着的机器人，总收益为 (z // t) * t。
  3. 合并收益：相邻两个 0 片段之间夹着一个 1 片段（长度 b）时：
    • 若 b ≥ a（可执行操作 1 关掉该 1 片段），则两个 0 片段合并为长度 z1 + z2 + b（原 1 片段变为 0）。
    • 合并后可能增加操作 2 的次数，额外收益为：(合并后0片段的操作2收益) - (原两个0片段的操作2收益) - b（关掉 1 片段损失的数量）。
    • 若额外收益为正，则值得合并。

思路

  1. 分解初始状态为连续片段，计算初始开着的机器人数量 ini。
  2. 计算所有 0 片段的基础操作 2 收益 base。
  3. 计算所有可能合并相邻 0 片段的额外收益，取最大值 max_merge（若为正则加入总收益）。
  4. 最终结果为 ini + base + max(max_merge, 0)。

代码

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n, a;
        string s;
        cin >> n >> a >> s;
        int t_val = a + 1;  // 开操作需要的连续0数量
        
        // 分解为连续的0/1片段 (类型, 长度)
        vector<pair<char, int>> segments;
        if (!s.empty()) {
            char cur = s[0];
            int cnt = 1;
            for (int i = 1; i < n; ++i) {
                if (s[i] == cur) cnt++;
                else {
                    segments.emplace_back(cur, cnt);
                    cur = s[i];
                    cnt = 1;
                }
            }
            segments.emplace_back(cur, cnt);
        }
        
        int ini = 0;  // 初始开着的数量
        vector<int> zero_lengths;  // 所有0片段的长度
        vector<int> between_ones;  // 相邻0片段之间的1片段长度
        
        for (int i = 0; i < segments.size(); ++i) {
            auto [type, len] = segments[i];
            if (type == '1') {
                ini += len;
                // 若该1片段在两个0片段之间，则记录长度
                if (i > 0 && i < segments.size() - 1 && segments[i-1].first == '0' && segments[i+1].first == '0') {
                    between_ones.push_back(len);
                }
            } else {
                zero_lengths.push_back(len);
            }
        }
        
        // 计算基础收益
        long long base = 0;
        for (int z : zero_lengths) {
            base += (1LL * z / t_val) * t_val;
        }
        
        // 计算最大合并收益
        long long max_merge = 0;
        int m = zero_lengths.size();
        for (int i = 0; i < (int)between_ones.size(); ++i) {
            int b = between_ones[i];
            if (b < a) continue;  // 无法执行关操作
            
            int z1 = zero_lengths[i];
            int z2 = zero_lengths[i+1];
            long long original = (1LL * z1 / t_val) * t_val + (1LL * z2 / t_val) * t_val;
            long long merged_z = z1 + z2 + b;
            long long merged = (1LL * merged_z / t_val) * t_val;
            long long gain = merged - original - b;  // 额外收益
            
            if (gain > max_merge) {
                max_merge = gain;
            }
        }
        
        long long ans = ini + base + max(max_merge, 0LL);
        cout << ans << '\n';
    }
    return 0;
}

时间复杂度：O(t * n)

Problem J. Jetton

问题描述

Yuki 和 Ena 玩回合制扑克牌游戏：

  • 初始时，Yuki 有 x 筹码，Ena 有 y 筹码。
  • 每轮胜负规则：
    • 若筹码数不同，筹码少的玩家获胜。
    • 若筹码数相同，Yuki 获胜。
  • 输家需支付给赢家与赢家当前筹码数相等的金额。
  • 当任一玩家筹码数为 0 时，游戏结束。

求游戏是否会在有限轮内结束，若是则输出轮数，否则输出 -1。

输入

  • 第一行：整数 t（测试用例数）。
  • 后续 t 行：每行两个整数 x 和 y（初始筹码数）。

约束

  • 1 ≤ t ≤ 10⁵
  • 1 ≤ x, y ≤ 10⁹

输出

  • 若游戏在有限轮内结束，输出轮数。
  • 否则，输出 -1。

题解

  1. 游戏规则转化：
    • 若 x ≠ y，设 m = min(x, y)，则下一轮筹码变为 (x + m, y - m) 或 (x - m, y + m)。
    • 若 x = y，则 Yuki 获胜，Ena 支付 x，游戏结束（1 轮）。
  2. 终止条件：
    • 每轮后总筹码 S = x + y 保持不变。
    • 若 S 为奇数，游戏无法结束（因无法通过操作使任一筹码为 0）。
    • 若 S 为偶数，需进一步分析是否能通过有限次操作使某玩家筹码为 0。

二进制分解：

  • 总筹码 S 的二进制中最低位 1 的位置 k（即 S 能被 2^k 整除但不能被 2^(k+1) 整除）。

  • 初始时较小的筹码

    1
    u = min(x, y)

    必须满足：

    • u 是 S / 2^k 的倍数。
    • u 的二进制中最低位 1 的位置 r ≤ k-1。

轮数计算：

  • 若满足上述条件，轮数为 k - r，即 S 和 u 的最低位 1 位置之差。

实现方法

  1. 特殊情况处理：
    • 若 x == y，直接输出 1 轮。
    • 若 S = x + y 为奇数，输出 -1。
  2. **计算 k 和 r**：
    • k：S 的二进制中最低位 1 的位置。
    • r：u = min(x, y) 的二进制中最低位 1 的位置。
  3. 验证条件：
    • 检查 u 是否为 S / 2^k 的倍数。
    • 检查 r ≤ k-1。
  4. 输出结果：
    • 若条件满足，输出 k - r。
    • 否则，输出 -1。

代码

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
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long

// 计算n的二进制中最低位1的位置（即log2(n & -n)）
int f(int n) {
    if (!n) return -1;
    int len = 0;
    int t = (n & -n);
    while (t > 0) {
        len++;
        t >>= 1;
    }
    return len - 1;
}

void solve() {
    int x, y;
    cin >> x >> y;
    int a = x + y;  // 总筹码数不变
    
    // 特殊情况：x == y，直接结束
    if (x == y) { cout << 1 << endl; return; }
    
    // 总筹码为奇数，无法结束
    if (a % 2) { cout << -1 << endl; return; }
    
    int k = f(a);           // S的最低位1位置
    int u = min(x, y);      // 初始较小的筹码
    int r = f(u);           // u的最低位1位置
    int m = a >> k;         // S / 2^k
    
    // 验证条件并输出轮数
    if (u % m != 0 || r > k - 1) cout << -1 << endl;
    else cout << k - r << endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    cin >> _;
    while (_--) solve();
    return 0;
}

时间复杂度：O(t)