CSP-J复习

[CSP-J 2024] 扑克牌
问：最少还需要向小 S 借几张牌才能凑成一副完整的扑克牌？
第一步：看范围，预测一下是什么算法？
因为 n = 52 ，且题目特别简单，大概率是个模拟
第二步：是其他算法，再计算一下时间复杂度是否足够
第三步：梳理逻辑，写代码
从题目问题出发，反推需要哪些条件才能计算出问题。
需要知道：已经有几张扑克，完整扑克的条件
完整扑克：4花色 * 13点数 = 52张
比对，已经有的扑克，和完整的扑克还差多少 ========> 还需要借多少张
用 bool vis[4][13] 标记哪些牌出现过
代码实现：

1. 输入已有的牌，将 vis 数组标记为1
2. 遍历 4 行 13 列的 vis 数组，用 cnt 统计有哪些是 0
3. 输出 cnt

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

bool has[4][13];
int main() {

    int n;

    cin >> n;

    string points = "A23456789TJQK"; // 13种点数

    for (int i = 0; i < n; i++) {
        string card;
        cin >> card;

        // 解析花色
        int suit = 0;
        if (card[0] == 'D') suit = 0;
        else if (card[0] == 'C') suit = 1;
        else if (card[0] == 'H') suit = 2;
        else suit = 3;

        // 解析点数：在 points 中找到对应位置
        int rank = 0;
        for (int j = 0; j < 13; j++) {
            if (card[1] == points[j]) {
                rank = j;
                break;
            }
        }

        has[suit][rank] = true; // 标记这种牌已有
    }

    // 统计已有多少种不同的牌
    int cnt = 0;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 13; j++)
            if (has[i][j]) cnt++;

    cout << 52 - cnt << endl;
    return 0;
}

[CSP-J 2024] 地图探险
问：执行完 k 步操作后，机器人经过的不同位置有多少个（含起点）
需求知道：起点位置，每次操作的过程
k 次操作：

• 若前方下一步再地图内 && 为空地，前进一步
• 否则，原地右转（d' = (d + 1) mod 4）

纯模拟。用一个 bool 数组记录哪些位置被走过。
代码实现：

1. 读入数据。
2. 模拟 k 次操作，注意判断下一步是否能走。
3. 用 vis 数组标记不同位置是否经过。
4. 遍历 vis 数组，统计有哪些位置经过了，输出。

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

const int MAXN = 1005;

int n, m, k;
string grid[MAXN];  // 用 string 存每一行
bool vis[MAXN][MAXN];

// 方向偏移：0=东, 1=南, 2=西, 3=北
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

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

    while (T--) {
        cin >> n >> m >> k;
        int x, y, d;
        cin >> x >> y >> d;

        for (int i = 1; i <= n; i++) {
            cin >> grid[i];
            grid[i] = " " + grid[i]; // 前面加空格，让下标从1开始
        }

        // 清空 vis 数组
        memset(vis, false, sizeof(vis));
        vis[x][y] = true; // 起点算经过

        // 模拟 k 步操作
        for (int step = 0; step < k; step++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            // 判断下一步是否可以走
            // 能不能重复走？ 
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && grid[nx][ny] == '.') {
                x = nx;
                y = ny;
                vis[x][y] = true;
            }
            else {
                d = (d + 1) % 4; // 右转
            }
        }

        // 统计经过的不同位置数
        int cnt = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (vis[i][j]) cnt++;

        cout << cnt << endl;
    }
    return 0;
}

[CSP-J 2024] 小木棍
问：是否存在满足题意的正整数，即，没有前导0，用 n 根木棍，的最小正整数。
如果要用 n 根木棍拼出正整数，怎么拼会最少？
很明显，观察到，数字 8 用的木棍最多 7 根，性价比最低。
注意：能凑 8 尽量凑，但是也要考虑特殊情况。
例如：n = 6，输出 6。n = 5，输出 2.
因此，容易想到，能凑 8 尽量凑，当n % 7 == 0时，用 8 凑。当 n % 7 = 1,2,3,4,5,6 时，特殊讨论。
如果 n % 7 == 0：全用 8
如果n % 7 == 1：1 / 8 / 15 / 22。如果 n = 1，非法。如果 n = 8，19（2 + 6）10（2 + 6）。如果n = 15，22.......，先抽一个‘10’出来，再放一个88888888。
如果n % 7 == 2：如果 n = 2，1。如果 n = 9，16........，抽‘1’，再放888888888。
如果n % 7 == 3：如果 n = 3，7。如果 n = 10，22。如果 n = 17.........，200，再放88888888。
如果n % 7 == 4：如果 n = 4，4。如果 n = 11，20。如果 n = 18........，20，再8888888888。
如果 n % 7 == 5：如果 n = 5，2。如果 n = 12，2 8888888888
如果 n % 7 == 6：如果 n = 6，6。如果 n = 13，6 8888888888

#include <iostream>
using namespace std;
int main() {

        int t, n;
        cin >> t;
        while (t--) {
                cin >> n;
                if (n % 7 == 0) {
                        for (int i = 1; i <= n / 7; i++) {
                                cout << "8";
                        }
                }
                else if (n % 7 == 1) {
                        if (n == 1) {
                                cout << "-1";
                        }
                        else {//先拿出1 + 7根，剩下的7根一组
                                cout << "10";
                                for (int i = 1; i <= (n - 8) / 7; i++) {
                                        cout << "8";
                                }
                        }
                }
                else if (n % 7 == 2) {
                        if (n == 2) {
                                cout << "1";
                        }
                        else{//先拿出2 + 7根，剩下的7根一组
                                cout << "18";
                                for (int i = 1; i <= (n - 9) / 7; i++) {
                                        cout << "8";
                                }
                        }
                }
                else if (n % 7 == 3) {
                        if (n == 3) {
                                cout << "7";
                        }
                        else if(n == 10){
                                cout << "22";
                        }
                        else {//先拿出3 + 7 + 7根，剩下的7根一组
                                cout << "200";
                                for (int i = 1; i <= (n - 17) / 7; i++) {
                                        cout << "8";
                                }
                        }
                }
                else if (n % 7 == 4) {
                        if (n == 4) {
                                cout << "4";
                        }
                        else {
                                cout << "20";
                                for (int i = 1; i <= (n - 11) / 7; i++) {
                                        cout << "8";
                                }
                        }
                }
                else if (n % 7 == 5) {
                        cout << "2";
                        for (int i = 1; i <= (n - 5) / 7; i++) {
                                cout << "8";
                        }
                }
                else if (n % 7 == 6) {
                        cout << "6";
                        for (int i = 1; i <= (n - 6) / 7; i++) {
                                cout <<"8";
                        }
                }
                cout << endl;
        }

        return 0;
}

[CSP-J 2021] 插入排序
给定长度为 n 的数组，支持两种操作：

• 操作1：将 a[x] 修改为 v
• 操作2：询问 a[x] 在插入排序后的位置。排序结果是不保留的。
  查询次数2e5，n 是 8000，修改次数是 5000
  先考虑，要快速的实现这两个操作，需要哪些条件。
  修改之后每次排序，太慢了，不如一开始就排好序，后续修改的时候，考虑”微调“就好了。
  要怎么让调整一个数字在有序数组中的位置呢？
• 做两次冒泡，假设这个元素变大了，就可以后移，假设变小，就可以前移。

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

struct node {
    int val; // 值
    int id;  // 原始下标
} a[8005];

int ans[8005]; // ans[x] = 原数组第x个元素在排序后的位置
int n, q;

// 比较函数：先按值升序，值相同按原始下标升序（稳定性）
bool cmp(node x, node y) {
    if (x.val != y.val) return x.val < y.val;
    return x.id < y.id;
}

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].val;
        a[i].id = i; // 记录原始编号
    }

    // 初始排序
    sort(a + 1, a + 1 + n, cmp);
    for (int i = 1; i <= n; i++) {
        ans[a[i].id] = i; // 记录每个元素排序后的位置
    }

    while (q--) {
        int op, x, v;
        cin >> op;

        if (op == 1) { // 单点修改
            cin >> x >> v;
            a[ans[x]].val = v; // 在排序数组中找到原数组第x个数，修改值

            // 值变大了可能需要往后移：从前往后扫一遍
            for (int i = 2; i <= n; i++) {
                if (cmp(a[i], a[i - 1])) {
                    node tmp = a[i];
                    a[i] = a[i - 1];
                    a[i - 1] = tmp;
                }
            }
            // 值变小了可能需要往前移：从后往前扫一遍
            for (int i = n; i >= 2; i--) {
                if (cmp(a[i], a[i - 1])) {
                    node tmp = a[i];
                    a[i] = a[i - 1];
                    a[i - 1] = tmp;
                }
            }

            // 更新 ans 数组
            for (int i = 1; i <= n; i++)
                ans[a[i].id] = i;
        }
        else if (op == 2) { // 单点查询
            cin >> x;
            cout << ans[x] << endl;
        }
    }

    return 0;
}