语法周赛round19

T1

知识点

• 数学比较运算
• 条件判断

思路

题目要求统计「神秘事件」发生的次数。定义：如果某个人射中的环数严格大于另外两个人环数的和，就算一次。 因此只需要依次判断三种情况：

1. $x > y + z$
2. $y > x + z$
3. $z > x + y$

满足一次就加一。因为输入范围很小（$1 \leq x,y,z \leq 10$），直接枚举判断即可，时间复杂度为 $O(1)$。

参考代码

int cnt = 0;
if (x > y + z) 
    cnt++;
if (y > x + z) 
    cnt++;
if (z > x + y) 
    cnt++;
cout << cnt;

---

T2

知识点

• 浮点数运算
• 条件判断与比较
• 格式化输出

---

思路

分别算出三个人的喝酒量：

• 李白 1：$a \times x + b \times y$
• 李白 2：$c \times y$
• 李白 3：$d \times y + e$

然后用变量 maxWine 保存当前最大量，用 ans 保存编号。依次比较更新即可。

参考代码

double wine1 = a * x + b * y;
double wine2 = c * y;
double wine3 = d * y + e;

int ans = 1;
double maxWine = wine1;

if (wine2 > maxWine) 
{
    maxWine = wine2;
    ans = 2;
}
if (wine3 > maxWine) 
{
    maxWine = wine3;
    ans = 3;
}
cout << ans << " " << fixed << setprecision(2) << maxWine;

---

T3

知识点

• 比例分配（按权重分配总和）
• 浮点数计算
• 高效输入输出（大数据量场景）

---

思路

• 确定工资总分配方式：

每道题的工资占总工资 $m$ 的比例是 $\dfrac{b_i}{sum_b}$，其中 $sum_b = b_1 + b_2 + \dots + b_n$。

• 卷王的工资：

只对出题人 $a_i=1$ 的题，把对应的权重 $b_i$ 加起来。设卷王权重和为 $B_w$，则卷王获得的工资为：

$$ \text{wage} = m \times \frac{B_w}{sum_b} $$

• 实现细节：
  • 遍历一遍输入，累加权重总和 sumB 和卷王的权重和 sumWang。
  • 最终输出 m * sumWang / sumB，保留小数点后三位。

时间复杂度 $O(n)$，只需一次遍历即可。

参考代码

long long sumB = 0;    // 全部题目的权重和
long long sumWang = 0; // 卷王题目的权重和
for (int i = 0; i < n; i++)
{
    int a, b;
    cin >> a >> b;
    sumB += b;
    if (a == 1)
        sumWang += b;
}
double ans = (double)m * sumWang / sumB;
cout << fixed << setprecision(3) << ans;

---

T4

知识点

• 枚举
• 整除判定
• 输出控制

---

思路

题目要求找出所有满足条件的三位数：

• 枚举所有三位数 $abc$：
  • $a \in [1,9]$，$b \in [0,9]$，$c \in [0,9]$。
  • 总共有 $9 \times 10 \times 10 = 900$ 种情况，可以直接暴力枚举。
• 对每个数检查三个条件：
  • $a \times 10 + b$ 是 $k$ 的倍数；
  • $b \times 10 + c$ 是 $k$ 的倍数；
  • $a \times 100 + b \times 10 + c$ 是 $k$ 的倍数。
• 若条件成立，输出该三位数。
• 如果遍历结束后没有输出任何数，则输出 None!。

参考代码

bool ok = false;
for (int a = 1; a <= 9; a++)
{
    for (int b = 0; b <= 9; b++)
    {
        for (int c = 0; c <= 9; c++)
        {
            int ab = a * 10 + b;
            int bc = b * 10 + c;
            int num = a * 100 + b * 10 + c;
            if (ab % k == 0 && bc % k == 0 && num % k == 0)
            {
                cout << num;
                ok = true;
            }
        }
    }
}
if (!ok)
    cout << "None!";

---

T5

知识点

• 二维数组
• 枚举，模拟

思路讲解

• 输入部分
  • 先读入每个朋友的初始身高 a[i]；
  • 再用二维数组 b[i][j] 存储：第 i 年第 j 个朋友的身高增长。
• 处理询问，每次询问 (x, y, z) 表示：
  • 问第 y 个朋友 经过 x 年的身高
  • 和第 z 个朋友 经过 x 年的身高
  • 再输出二者的差。

在代码里：

• height1 从 a[y] 开始，每一年加上 b[i][y]，得到第 y 个朋友 x 年后的身高；
• height2 从 a[z] 开始，每一年加上 b[i][z]，得到第 z 个朋友 x 年后的身高；
• 两者相减输出即可。

复杂度

• 每次查询都要循环加上 x 年的增长。
• 最坏情况下，$q = 1000, m = 1000$，每次查询都要扫 1000 年，整体 $O(q \times m)$，大约 $10^6$，还能接受。
• 但如果 $n,m,q$ 更大，就会不够快。

参考代码

for (int i = 1; i <= n; i++)
{
    cin >> a[i];
}
for (int i = 1; i <= m; i++)
{
    for (int j = 1; j <= n; j++)
    {
        cin >> b[i][j];
    }
}
while (q--)
{
    int x, y, z;
    cin >> x >> y >> z;
    long long height1 = a[y], height2 = a[z];
    for (int i = 1; i <= x; i++)
    {
        height1 += b[i][y];
    }
    for (int i = 1; i <= x; i++)
    {
        height2 += b[i][z];
    }
    cout << height1 - height2 << endl;
}

---

拓展：用前缀和优化

注意到 每次查询时，我们都要「重复加一遍增长量」。

实际上，可以提前把「每个人在前 i 年的总增长」算好，存在数组里。

具体做法

• 定义 grow[i][j] = b[1][j] + b[2][j] + ... + b[i][j]。
• 也就是：第 j 个朋友在前 i 年一共长高多少。
• 构造方式：

grow[i][j] = grow[i-1][j] + b[i][j];

• 查询时直接用：
  • height1 = a[y] + grow[x][y]
  • height2 = a[z] + grow[x][z]
• 差值：height1 - height2。

优势

• 每次查询复杂度 $O(1)$，而不是 $O(x)$。
• 总复杂度：$O(n \times m + q)$，比原来的 $O(q \times m)$ 更快。

---

前缀和优化代码

for (int i = 1; i <= n; i++)
    cin >> a[i];
for (int i = 1; i <= m; i++)
{
    for (int j = 1; j <= n; j++)
    {
        int b;
        cin >> b;
        grow[i][j] = grow[i - 1][j] + b;
    }
}
while (q--)
{
    int x, y, z;
    cin >> x >> y >> z;
    long long height1 = a[y] + grow[x][y];
    long long height2 = a[z] + grow[x][z];
    cout << height1 - height2 << "\n";
}

---

T6

题意解析

你有一个 $01$ 串 $s$，长度为 $n$。要执行 $q$ 次操作，每次操作是：

• 操作 1（翻转）：把字符串颠倒，比如 "10010" → "01001"。
• 操作 2（反转）：逐位取反，0→1, 1→0。

问最终得到的字符串。

---

直观做法（会超时）

最直接的方法是：每次真的去翻转或反转字符串。

• 翻转需要 $O(n)$。利用 reverse 函数。
• 反转也需要 $O(n)$。遍历字符串修改所有位置。
• 如果 $q$ 和 $n$ 都是 $10^5$，最坏复杂度就是 $10^{10}$，会超时。

所以我们必须 优化。

---

关键观察

• 操作是可合并的
  • 连续两次翻转（操作 1）等于没做；
  • 连续两次反转（操作 2）等于没做；
  • 所以我们只需要关心 操作 1 和操作 2 的次数的奇偶性。
• 操作顺序的影响
  • 翻转和反转其实是 可交换的：
  • 举例：s = "10"
    • 先翻转再反转： "10" → "01" → "10"
    • 先反转再翻转： "10" → "01" → "10"
  • 结果一样。
  • 所以我们只要统计最终“需要不要翻转一次”和“需要不要反转一次”。

---

算法流程

• 遍历操作字符串 $w$，统计：
  • cnt1 = 翻转操作的个数
  • cnt2 = 反转操作的个数
• 最终：
  • 如果 cnt1 % 2 == 1 → 需要翻转一次；
  • 如果 cnt2 % 2 == 1 → 需要反转一次。
• 按顺序执行（先翻转再反转也行，反过来也行，结果一样）。
• 输出结果。

---

复杂度分析

• 统计操作次数：$O(q)$
• 最终只做最多一次翻转和一次反转：$O(n)$
• 总复杂度：$O(n+q)$，可以轻松通过 $10^5$ 的数据规模。

参考代码

int cnt1 = 0, cnt2 = 0;
for (int i = 0; i < s2.size(); i++)
{
    if (s2[i] == '1')
        cnt1++;
    else
        cnt2++;
}
// 需要翻转
if (cnt1 % 2 == 1)
    reverse(s1.begin(), s1.end());
// 需要反转
if (cnt2 % 2 == 1)
{
    for (int i = 0; i < s1.size(); i++)
    {
        if (s1[i] == '1')
            s1[i] = '0';
        else
            s1[i] = '1';
    }
}
cout << s1;

---

T7

思路

设把串逐个字符读入，记录所有为 1 的下标到数组 a[1..cnt]。

没有 1（cnt == 0）

• 全是 0。要能从某个“间距为 $k-1$”的零段里截取出长度为 $m$ 的全零串，需要 $k-1 \ge m$。
• 因为最大可选 $k = n+1$，条件等价为 $m \le n$。
• 代码等价判断：if (m > n) No else Yes。

---

只有一个 1（cnt == 1）

• 记这个 1 的位置为 a[1]。
• 左边前缀零段长度 L = a[1] - 1，右边后缀零段长度 R = m - a[1]。
• 只要存在某个 $k$ 使得两侧都装得下，即 L <= n 且 R <= n。
• 代码判断：if (L > n || R > n) No else Yes。

---

至少两个 1（cnt >= 2）

• 令 len = a[2] - a[1] - 1（两 1 中间的零的个数），这就确定了相邻 1 的固定间距。
• 先判 len <= n（否则该间距不可能）。
• 还要检查所有相邻 1 的零段都等于 len：对 i = 3..cnt，要求 a[i]-a[i-1]-1 == len。
• 边界零段也不能超过 len：
  • 前缀零段：a[1] - 1 <= len
  • 后缀零段：m - a[cnt] <= len
• 以上都满足则 Yes，否则 No。

---

参考代码

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 5;
int a[N];
void solve()
{
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    s = " " + s;
    int cnt = 0;
    for (int i = 1; i <= m; i++)
    {
        if (s[i] == '1')
        {
            a[++cnt] = i;
        }
    }
    if (cnt == 0)
    {
        if (m > n) cout << "No\n";
        else cout << "Yes\n";
        return ;
    }
    if (cnt == 1)
    {
        int L = a[1] - 1; // 左边有 L 个 0
        int R = m - a[1]; // 右边有 R 个 0
        if (L > n || R > n) cout << "No\n";
        else cout << "Yes\n";
        return ;
    }
    // cnt >= 2
    int len = a[2] - a[1] - 1;
    if (len > n) // 固定间隔超过 n 不合法
    {
        cout << "No\n";
        return ;
    }
    int L = a[1] - 1; // 左边有 L 个 0
    int R = m - a[cnt]; // 右边有 R 个 0
    if (L > len || R > len) // 左右边界零段超过 len 不合法
    {
        cout << "No\n";
        return ;
    }
    for (int i = 3; i <= cnt; i++)
    {
        if (a[i] - a[i - 1] - 1 != len) // 中间零段不等于 len 不合法
        {
            cout << "No\n";
            return ;
        }
    }
    cout << "Yes\n";
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

---

T8

题意重述

• 有 $n$ 个牛棚，每个牛棚初始防御值 $a_i$。
• $m$ 块陨石会砸下来，第 $j$ 块陨石落在牛棚 $x_j$。每次命中，牛棚防御值减少 2。
• 在陨石雨到来之前，翁老师有 $t$ 秒。每秒可以给某个牛棚防御值 +1（补给），可以任意选择牛棚。
• 目标：让被破坏的牛棚数尽量少，问最多能保下多少牛棚。

---

关键分析

• 最终损伤量 对于牛棚 $i$，它被陨石击中 $c_i$ 次，则总伤害 = $2c_i$。 于是最终防御 = $a_i + \text{补给}_i - 2c_i$。

若要不被摧毁：

$$ a_i + \text{补给}_i - 2c_i > 0 \quad\Longleftrightarrow\quad \text{补给}_i \ge \max(0, 2c_i - a_i + 1) $$

• 这里的 $\max(0, \cdot)$ 表示如果初始就够用，就不必补。

定义：

$$ \text{need}_i = \max(0, 2c_i - a_i + 1) $$

表示想要救活牛棚 $i$，至少需要的补给量。

贪心思想

总共可补给时间是 $t$。

为了最大化救下的牛棚数，显然应该 优先救补给需求小的牛棚。所以：

• 把所有 $\text{need}_i$ 算出来。
• 排序，从小到大依次尝试救。
• 当剩余时间不够救下一个需要时，就停。

---

算法流程

1. 统计每个牛棚被陨石击中的次数 $c_i$。
2. 计算每个牛棚的需求量 $\text{need}_i = \max(0, 2c_i - a_i + 1)$。
3. 将所有 $\text{need}_i$ 排序。
4. 从小到大累加，直到用光 $t$。累加了多少个，就是能保下的牛棚数。

---

复杂度分析

• 统计 $c_i$：$O(m)$
• 计算 $\text{need}_i$：$O(n)$
• 排序：$O(n \log n)$
• 贪心挑选：$O(n)$

数据范围内完全可行（所有测试点 $\sum n \leq 5\times 10^4$，$\sum m \leq 3\times 10^6$）。

---

参考代码

#include <bits/stdc++.h>
using namespace std;
int a[5005];    // 每个牛棚的初始防御
int cnt[5005];        // 每个牛棚被击中次数
int need[5005]; // 每个牛棚需要的补给量
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        int n, m;
        int t;
        cin >> n >> t >> m;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            cnt[i] = 0; // 初始化击中次数
        }
        for (int i = 0; i < m; i++)
        {
            int x;
            cin >> x;
            cnt[x]++;
        }
        for (int i = 1; i <= n; i++)
        {
            int dmg = 2 * cnt[i];   // 总伤害
            int req = dmg - a[i] + 1; // 至少需要的补给
            if (req < 0)
                req = 0; // 不需要补给时置0
            need[i] = req;
        }
        sort(need + 1, need + n + 1);
        int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            if (t >= need[i])
            {
                t -= need[i];
                ans++;
            }
            else
            {
                break;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}