题目顺序按开题顺序排列

# I - The Easiest 问题

# 题目大意

给定一行字符串，问其中有多少个小写字母

# 题解

1
2
3
4
5
6
7
8
9

void solve() {
    string s;
    getline(cin, s);
    int cnt = 0;
    for (char c : s)
        if (islower(c))
            cnt++;
    cout << cnt << endl;
}

# L - Recharge

# 题目大意

你现在有一个电池，这块电池有 $k$ 格电，现在，有两种充电站

• $x$ 个第一种充电站，可以加 $1$ 格电
• $y$ 个第二种充电站，可以加 $2$ 格电

若你现在有 $k-1$ 格电，那么使用第二种充电站的话，则会充满这块电池但是就浪费了一格电
问：最多能充满多少块这样的电池？

# 数据范围

• $t$ 组数据，$1 \le t \le 2 \times 10^5$
• $1 \le k \le 10^9$
• $0 \le x,y \le 10^9$

# 题解

尽量先用加 $2$ 格电的充电站先充，针对 $k$ 的奇偶性进行分类讨论

• $k$ 是偶数
  • 那么需要消耗 t = k / 2 个 $2$ 即可拼成一个 $k$
  • 所以，只用 $2$ 的话，可以凑出 a = y / t 个，还剩下 y = y - a * t 个 $2$
  • 那么剩下的就可以直接散着拼了，也就是有 (x + 2 * y) / k 个
  • 最终答案为 a + (x + 2 * y) / k ，此处 $y$ 为减之后的 $y$
• $k$ 是奇数
  • 那么需要消耗 t = (k - 1) / 2 个 $2$ 和一个 $1$ 即可拼成一个 $k$
  • 所以可以先拼出 a = min(y / t, x) 个，还剩下 y = y - a * t 个 $2$ 和 x = x - t 个 $1$
  • 剩下的散着拼，但是这里还要考虑到浪费电的那种充电情况
    • 如果 $1$ 的还有剩余，那么和前面的情况，也就是有 (x + 2 * y) / k 个
      • 那么最后答案就是 a + (x + 2 * y) / k ，此处的 $x$ 和 $y$ 均为减之后的 $x$ 和 $y$
    • 如果 $1$ 的没有剩余，那么就全部用 $2$ 拼，只能考虑浪费，也就是有 y / ((k + 1) / 2) 个
      • 那么最后答案就是 a + y / ((k + 1) / 2) ，此处的 $x$ 和 $y$ 均为减之后的 $x$ 和 $y$

这题还有一个坑是，$k$ 的范围是 $1 \le k \le 10^9$，那么当 $k = 1$ 时，我们前面讨论中的除 $k - 1$ 就会 $RE$
再添加一个特判，当 $k=1$ 时，答案是 $x+y$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

void solve () {
    int k, x, y;
    cin >> k >> x >> y;
    
    if (k & 1) {
        int t = (k - 1) / 2;
        int a1 = min(y / t, x);
        y -= a1 * t, x -= a1;
        if (x == 0)
            cout << a1 + y / ((k + 1) / 2) << endl;
        else
            cout << a1 + (x + 2 * y) / k << endl;
    }
    else {
        int t = k / 2, a1 = y / t;
        y -= a1 * t;
        cout << a1 + (x + 2 * y) / k << endl;
    }
}