语法周赛round24

T1

知识点：顺序结构，数学表达式化简。

由于题目只要求对给定的一个 $a$ 分别执行两段固定顺序的操作，因此可以直接按照步骤模拟计算即可。

算法步骤

1. 小 Y 的程序

   • 先令 $a \leftarrow a + 5$；
   • 再令 $a \leftarrow 3a$；
   • 最终结果为 $a_y = 3(a + 5)$。

2. 小 L 的程序

   • 先令 $a \leftarrow 3a$；
   • 再令 $a \leftarrow a + 5$；
   • 最终结果为 $a_l = 3a + 5$。

3. 输出两个计算结果 $a_y, a_l$。

注意具体实现时，把 $a$ 先分别储存到两个变量 $a_y,a_l$ 后在进行计算。

本题关键在于理解“顺序不同 → 结果不同”，直接按要求模拟或写出公式都能轻松完成。

代码

int a;
cin >> a;
int ay = a, al = a;
ay += 5;
ay *= 3;
cout << ay << " ";
al *= 3;
al += 5;
cout << al;

---

T2

知识点：枚举，绝对值判断，数学。

循环方法

刻度尺上共有刻度 $0,1,\ldots,n$，最多 $101$ 个，因此直接枚举所有刻度并判断是否满足与 $a$ 的距离为 $b$，完全可行。

算法步骤

1. 从小到大枚举所有刻度 $i = 0, 1, \dots, n$。
2. 对每个刻度 $i$：
   • 判断是否满足 $|i - a| = b$。
3. 若满足，将 $i$ 加入答案列表。
4. 全部枚举完成后：
   • 若答案列表非空，按从小到大输出所有刻度；
   • 否则输出 No solution。

代码

bool ok = 0;
for (int i = 0; i <= n; i++)
{
    if (abs(i - a) == b)
    { 
        cout << i << ' ';
        ok = 1; // 打标记
    }
}
if (ok == 0)
{
    cout << "No solution";
}

数学做法

假设这个刻度尺无限延伸的话，那么和 $a$ 厘米刻度距离恰好为 $b$ 厘米的刻度应该有两个：$a−b$ 和 $a+b$。

如果 $a\geq b$，那么 $a−b$ 这个刻度确实出现在刻度尺上（并且一定是更小的），输出这个解即可；

如果 $a+b\leq n$，那么 $a+b$ 这个刻度也出现在刻度尺上，如果 $b\not =0$ 的话（否则 $a−b,a+b$ 是同一个刻度），那么还要输出这个解。

那么什么时候无解呢？无解就是 $a < b$ 并且 $a+b>n$，此时输出 No solution 即可。

代码

bool ok = 0;
// a - b
if (a >= b)
{
    cout << a - b << " ";
    ok = 1;
}
// a + b
if (a + b <= n)
{
    if (b != 0)
    {
        cout << a + b;
        ok = 1;
    }
}
if (!ok)
{
    cout << "No solution";
}

---

T3

知识点：枚举，最值。

已知当前是 第一周周六（星期 6）。每门课给定开课星期 $w$ 和开课间隔 $d$，我们需要计算它的 下一次需要交作业的时间，即第二次上课的到来时间。

对某门课：

• 第二次上课发生在第 $d$ 周的星期 $w$。
• 从现在（第一周周六）到第 $d$ 周周 $w$ 需经过 $(d-1)\times 7$ 天。
• 从周六到这一周的星期 $w$ 还需额外 $w+1$ 天。

因此，这门课距离现在的天数为：

\[ (d-1)\times 7 + (w+1) = 7d + w - 6. \]

题目要求的，就是所有课程中该数值的最小值，即最早需要交作业的天数。

代码

int n;
cin >> n;
int ans = 1e9;
for (int i = 1; i <= n; i++)
{
    int w, d;
    cin >> w >> d;
    int dist = 7 * d + w - 6;
    ans = min(ans, dist);
}
cout << ans;

---

T4

知识点：数组。

题目分析

• 有 $2n$ 个小朋友，编号 $1$ 到 $2n$；
• $n$ 张桌子，每张桌坐 $2$ 人；
• 每个小朋友 $i$ 希望和 $p_i$ 做同桌；
• 要判断是否存在一种配对，使得每对同桌 $(i, j)$ 满足：
• $p_i = j$ 且 $p_j = i$；
• 同桌不能是自己。

解题思路

• 将问题转化为检查每个同桌关系是否互相匹配；
• 遍历每个小朋友 $i$，检查：
  • $p_i \neq i$，自己不能是同桌；
  • $p_{p_i} = i$，对方也想和自己做同桌；
• 若所有小朋友均满足上述条件，则输出 Yes，否则输出 No。

处理流程

• 读入整数 $n$；
• 读入长度为 $2n$ 的数组 $p$；
• 对每个 $i$ 从 $1$ 到 $2n$：
  • 如果 $p_i = i$，直接输出 No 并结束；
  • 否则判断 $p_{p_i}$ 是否等于 $i$，不等则输出 No 并结束；
    • 解析：$p_i$ 是 $i$ 希望的同桌。那么 $p_{p_i}$ 就是 $p_i$ 希望的同桌。
• 如果全部检查通过，输出 Yes。

代码

cin >> n;
for (int i = 1; i <= 2 * n; i++)
{
    cin >> p[i];
}
for (int i = 1; i <= 2 * n; i++)
{
    if (p[i] == i)
    {
        cout << "No";
        return 0;
    }
    else
    {
        int x = p[i];
        if (p[x] != i)
        {
            cout << "No";
            return 0;
        }
    }
}
cout << "Yes";

---

T5

知识点：枚举，质数判定。

由于 $n $最多只有一万，因此直接从 $1 $到 $n$ 枚举判断每个数是否为孤独数是完全可行的。

算法步骤

1. 从大到小枚举 $i=n,n-1,\dots,1$（这样在找到第 $k$ 个时即可立即返回）。
2. 对每个 $i$：
   • 判断是否为质数；
   • 判断是否满足 $i \equiv r \pmod m$。
3. 若两者均满足，则计数器加一。
4. 当计数器等于 $k$ 时，输出当前的 $i$。

如果循环结束仍未找到第 $k$ 个孤独数，则输出 $-1$。

代码

#include <bits/stdc++.h>
using namespace std;

bool check(int x)
{
    if (x < 2) 
    {
        return false;
    }
    for (int i = 2; i <= sqrt(x); i++)
    {
        if (x % i == 0)
        {
            return false;
        }
    }
    return true;
}
int main()
{
    int n, m, r, k;
    cin >> n >> m >> r >> k;
    int cnt = 0;
    for (int i = n; i >= 1; i--)
    {
        if (check(i) && i % m == r)
        {
            cnt++;
            if (cnt == k)
            {
                cout << i;
                return 0;
            }
        }
    }
    cout << -1;
    return 0;
}

时间复杂度：$O(n\sqrt{n})$

---

T6

知识点：字符串。

思路分析

题目允许的操作是：

选择一个位置 $i$（$1 \leq i < n$），将 $s_i$ 修改为 $s_{i+1}$。

也就是说，你只能把某个字符变成它右边那个字符，不能随便改成任意字符。

因此，如果我们把操作不断向左传播：

• $s_{n-1}$ 可以变成 $s_n$
• $s_{n-2}$ 可以变成 $s_{n-1}$，也可以进一步经过传播变成 $s_n$
• ...
• 最终，每个字符都可以被修改成 最终靠右传递而来的一连串值

从这个传播链可以看到：

最终字符串中所有字符的值必定等于 $s_n$

原因：

• 因为最右端的字符 $s_n$ 无法被改变；
• 左边的位置只能被“推”成右边已有的值；
• 所以最后所有字符只能变成 $s_n$。

因此不需要尝试任何其他目标字符，最终形态完全确定。

---

如何计算最少操作次数？

我们希望把所有字符都变成 $s_n$。

• 若某个字符位置的值已经是 $s_n$，则无需操作。
• 若不是 $s_n$，就必须通过一系列传播操作使它变成 $s_n$。

结论：

只需要数出有多少个字符已经等于 $s_n$，其余的都需要改变。

因此答案为 $n-cnt[s_n]$。其中 $cnt[s_n]$ 表示字符 $s_n$ 的个数。

时间复杂度：$O(n)$。

代码

int t;
cin >> t;
while (t--)
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == s[n - 1])
        {
            cnt++;
        }
    }
    cout << n - cnt << "\n";
}

---