Day 29 · 模拟赛

题意：给一个一元 n 次多项式从高次到低次的 n+1 个系数，按竞赛规定的格式把它输出成一行字符串。

思路

这题没有算法，只有一个循环加一堆特判。核心是把题面 5 条规则翻译成一张清单（见第 2 节）， 然后逐条实现。最关键的技巧是用一个 first 标记区分「第一项」和「后面的项」——

然后按次数分三种情况输出后半截：

5 
100 -1 1 -3 0 10

100x^5-x^4+x^3-3x^2+10

3 
-50 0 0 1

-50x^3+1

样例 1 一次性考了 4 个特判：系数 1 省掉（x^4、x^3）、系数 0 整项跳过（x 那一项没了）、 常数项只写系数（+10）、以及正负号切换。这就是它被叫做「特判地狱」的原因。

完整代码

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;

    bool first = true;              // 还没有输出过任何一项

    for(int i = n; i >= 0; i--){    // i 就是当前这一项的次数
        int a;
        cin >> a;

        if(a == 0) continue;        // ★ 系数为 0 的项直接不输出

        // ---------- 1. 符号 ----------
        if(first){
            if(a < 0) cout << '-';      // 开头只有负数才输出负号
        }else{
            cout << (a < 0 ? '-' : '+'); // ★ 后面每项都要带符号
        }

        // ---------- 2. 系数 + 字母 + 指数 ----------
        int ab = (a < 0 ? -a : a);      // 系数的绝对值

        if(i == 0){
            cout << ab;                 // 常数项：只输出系数
        }else if(i == 1){
            if(ab != 1) cout << ab;     // ★ 一次项：|系数|=1 时省略 1
            cout << 'x';                //           指数 1 不写
        }else{
            if(ab != 1) cout << ab;     // ★ 高次项：|系数|=1 时省略 1
            cout << "x^" << i;
        }

        first = false;
    }

    cout << endl;
    return 0;
}

易错点

• 符号和系数要分开处理。负系数输出 - 之后，后面只能输出 |a|。 如果直接 cout << a，就会出现 --3x^2 这种两个负号叠在一起的东西。
• 省略 1 只针对 |系数| = 1 的非常数项。常数项 1 是要老老实实输出 1 的， 别顺手也省掉（那就什么都不剩了）。
• 「省略 1」和「省略指数 1」是两条独立规则。x（系数 1、次数 1）会同时触发两条； -x 同理。别只写一条。
• 输出末尾不能有空格。本题的合法输出里根本没有空格， 所以千万不要用「每项后面补一个空格再删掉最后一个」这种写法，容易出错。
• 题面没明说「最高次项系数为 0」怎么办。用 first 标记的写法会自然处理成「谁最先被输出，谁就是第一项」， 这是社区通行做法，我也按这个实现了。

题意：石头剪刀布的升级版，共 5 种手势（0 剪刀、1 石头、2 布、3 蜥蜴人、4 斯波克）。 小 A 和小 B 各有自己的周期出拳规律，一共比 N 局，赢的加 1 分，问两人各得几分。

思路

5 种手势两两组合共 25 种，用 if 写就是 25 个分支。正确的做法是把胜负关系存成一张二维表， 用的时候只需要 r[a][b] 查一下。

升级版的 10 条胜负规则（每句记一半，反过来就是输）是：

整理成 5×5 的表（行是甲、列是乙）：

然后模拟 N 局，第 i 局两人出的是 a[i % na] 和 b[i % nb] —— 取模就实现了循环。

10 5 6
0 1 2 3 4
0 3 4 2 1 0

6 2

9 5 5
0 1 2 3 4
1 0 3 2 4

4 4

完整代码

#include <iostream>
using namespace std;

// 手势编号：0 剪刀  1 石头  2 布  3 蜥蜴人  4 斯波克
// r[a][b] = 甲出 a、乙出 b 时甲的结果： 1 甲赢  0 平  -1 甲输
int r[5][5] = {
    { 0, -1,  1,  1, -1},   // 剪刀  vs 剪/石/布/蜥/斯
    { 1,  0, -1,  1, -1},   // 石头
    {-1,  1,  0, -1,  1},   // 布
    {-1, -1,  1,  0,  1},   // 蜥蜴人
    { 1,  1, -1, -1,  0}    // 斯波克
};

int main(){
    int n, na, nb;
    cin >> n >> na >> nb;

    int a[205], b[205];
    for(int i = 0; i < na; i++) cin >> a[i];
    for(int i = 0; i < nb; i++) cin >> b[i];

    int sa = 0, sb = 0;
    for(int i = 0; i < n; i++){
        int res = r[a[i % na]][b[i % nb]];   // ★ 取模实现无限循环
        if(res == 1)       sa++;
        else if(res == -1) sb++;
    }

    cout << sa << ' ' << sb << endl;
    return 0;
}

易错点

• 编号记反：0 是剪刀，1 才是石头。写表之前先把这句话抄在草稿纸上。
• 表的反对称性写错：比如 r[0][3] 填了 1（剪刀斩首蜥蜴人）， 那 r[3][0] 必须是 −1。手写表很容易两边都填成 1，一定要回头查一遍。
• 取模写错：是 i % na 不是 (i + 1) % na。这里的周期序列本来就从下标 0 开始存， 直接取模就对。
• 数组开小：N_A、N_B 都是 ≤ 200，我开了 [205]。开成 [200] 就是越界。
• 用 if 硬写 25 个分支：能过，但改一个规则就要重看一遍，极容易漏。 这类「两两关系」的题，打表永远比 if 稳。

题意：给一个只含 + 和 * 的表达式（没有括号、没有空格），算出它的值， 但只输出最后 4 位。

思路

用第 4 节讲的「加法切项」思路：维护 ans（已结算总和）和 term（当前正在累乘的项）。

• 读到数字 → 往 num 里攒，并且边攒边取模 10000。
• 读到一个数字结束（遇到运算符或到行尾）时，看上一个运算符 op：
  • op 还没记过 → 这是第一个数，直接 term = num
  • op == '*' → term *= num（乘法优先，并进当前项，不结算）
  • op == '+' → 把 term 结算进 ans，然后 term = num 开新项
• 循环结束后补一句把最后一项结算掉。

整个过程中所有变量都小于 10000，不会有任何溢出风险。

1+1*3+4

8

1+1234567890*1

7891

1+1000000003*1

4

样例 2 说明：1234567890 的后四位是 7890，1 + 7890 = 7891。
样例 3 说明：1000000003 的后四位是 0003 = 3，1 + 3 = 4。 注意这里不能先把 1000000003 当完整数字算完再取模——虽然这题数字没超 int，但读进来就取模更省心。

完整代码

#include <iostream>
#include <string>
#include <cctype>
using namespace std;

int main(){
    string s;
    cin >> s;                       // 这一行只含 0123456789+*

    long long ans  = 0;             // 已经算完的所有项的和
    long long term = 1;             // 当前正在累乘的这一项
    long long num  = 0;             // 正在读的这个数
    char op = 0;                    // 上一个读到的运算符，0 表示还没读到

    for(int i = 0; i <= (int)s.size(); i++){
        if(i < (int)s.size() && isdigit(s[i])){
            num = (num * 10 + (s[i] - '0')) % 10000;   // ★ 只留后四位就够
        }else{
            // 走到这里说明一个数字读完了，用 op 决定怎么合并它
            if(op == 0)        term = num;                          // 第一个数
            else if(op == '*') term = term * num % 10000;           // ★ 乘法优先，先并到本项
            else { ans = (ans + term) % 10000; term = num; }        // ★ 遇到加号：本项结算，开新项

            if(i < (int)s.size()) op = s[i];   // 记下这个运算符
            num = 0;
        }
    }

    ans = (ans + term) % 10000;      // ★ 别忘了最后一项
    cout << ans << endl;
    return 0;
}

易错点

• 忘了结算最后一项——详见第 4 节的红色警示框。这是本题第一大坑。
• 把数字当成单个字符读：数字可以有多位（最多 10 位），必须用 num = num*10 + (c-'0') 攒起来。
• 从左往右直接算：1+2*3 会算成 9。乘法的优先级必须处理。
• 用 cin >> n 一个个读：这题没有空格分隔，cin >> int 读 1+1*3+4 会在 1 后面直接失败。要么整行读成字符串自己拆，要么用 cin >> char 逐个读字符。
• 只对最终答案取模：中间过程会爆 long long（100000 个 2³¹ 量级的数连乘，天文数字）。 必须每一步都取模。

题意：n 个人围成一圈，从第 1 个人开始报数，数到 m 的人出圈，然后从下一个人重新从 1 报数， 直到所有人都出圈。按顺序输出每个出圈人的编号。

思路

题目描述本身就已经是算法了：「数到 m 的出圈 → 下一个人重新从 1 开始报数」。 这正是队列的操作方式：

把队头拿到队尾，循环 n 轮，每个人都恰好被取出并处理到出圈为止。

10 3

3 6 9 2 7 1 8 5 10 4

10 个人数到 3 出圈：先出 3、6、9，然后从 10 后面的 1 继续数，出 2、7、1、8、5、10，最后剩 4。

完整代码

#include <iostream>
#include <queue>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;

    queue<int> q;
    for(int i = 1; i <= n; i++) q.push(i);   // 所有人排队，队头是 1 号

    int cnt = 0;                             // 当前报数报到几了
    bool first = true;

    while(!q.empty()){
        int x = q.front();
        q.pop();
        cnt++;

        if(cnt == m){                        // ★ 数到 m，出圈
            if(!first) cout << ' ';
            cout << x;
            first = false;
            cnt = 0;                         // ★ 下一个人重新从 1 开始报
        }else{
            q.push(x);                       // ★ 没数到 m，回到队尾接着排
        }
    }

    cout << endl;
    return 0;
}

易错点

• 输出格式：n 个数用空格隔开，最后一个后面不要多打空格。 用 if(!first) cout << ' '; 这种「先判断再输出」的写法最稳。
• 报数计数器要清零：出圈时 cnt = 0，等于下一次循环 cnt++ 后正好是 1。 如果忘了清零，报数就错位了。
• 循环条件用 while(!q.empty())，不要用 for(i = 1; i < n; i++)—— 那样只会淘汰 n−1 个人，少输出一个数（正是题面提醒的那个坑）。
• 别把「出圈的人」又 push 回去：出圈的分支里不能再 q.push(x)，否则死循环。
• 数据只有 100，队列法 O(n·m) = 10⁴ 次操作，实际上是瞬时完成的， 不需要任何优化（真正的数学做法是递推公式，Day 17 已经见过类似思想，但这里完全不必）。