CSP-J2 2024 题解

T1 扑克牌 入门

思路

本题核心是统计不重复的牌有多少张，可使用 set 或 map 进行统计

set 参考程序

#include<bits/stdc++.h>
using namespace std;
int main(){
    set<string> card;
    int n;
    cin>>n;
    for(int i=1; i<=n; i++){
        string s;
        cin>>s;
        card.insert(s);
    }
    cout<<52-card.size();
    return 0;
}

map 参考程序

#include<bits/stdc++.h>
using namespace std;
int main(){
    map<string, int> card;
    int n;
    cin>>n;
    for(int i=1; i<=n; i++){
        string s;
        cin>>s;
        card[s] = 1;
    }
    cout<<52-card.size();
    return 0;
}

T2 地图探险 普及-

思路

• 模拟题，按照题目意思操作 k 步，能走的时候就往下走，不能走的时候改变方向，改变方向也算作一次操作
• 由于题目 d 的值为 0，1，2，3 时恰好是 右，下，左，上，方向数组按照顺序存储即可
• 注意多组数据，需要 memset 重置 vis 数组

参考程序

#include <bits/stdc++.h> // 引入万能头文件，包含所有标准库
using namespace std;

const int MAXN = 1010; // 定义地图最大尺寸
char mp[MAXN][MAXN]; // 存储地图的字符数组，'.'表示空地，'x'表示障碍物
bool vis[MAXN][MAXN]; // 记录机器人是否访问过某位置的布尔数组
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 方向数组：东、南、西、北
int n, m, k, x, y, d; // 地图的行列数、操作步数、起始位置(x, y)及初始朝向d

// 检查坐标(nx, ny)是否在地图内，且是空地（即可以通过）
bool check(int nx, int ny)
{
    return nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny] != 'x';
}

// 核心算法：模拟机器人在地图上的移动
int solve()
{
    int res = 1; // 记录机器人经过的不同位置数，初始值为1（包括起始位置）
    vis[x][y] = 1; // 标记起始位置已访问

    // 模拟机器人执行k步操作
    while (k--) 
    {
        int nx = x + dir[d][0], ny = y + dir[d][1]; // 计算下一步的坐标

        // 检查下一步是否在地图内且为空地
        if (check(nx, ny)) 
        {
            // 如果下一步未被访问过，则计入结果并标记为已访问
            if (!vis[nx][ny]) 
            {
                res++; // 增加经过的不同位置数
                vis[nx][ny] = 1; // 标记该位置已访问
            }
            // 更新机器人位置为下一步的坐标
            x = nx, y = ny;
        }
        else 
        {
            // 如果下一步不可行，则右转
            d = (d + 1) % 4;
        }
    }

    return res; // 返回经过的不同位置数
}

int main()
{
    int T; // 测试数据组数
    cin >> T;

    while (T--) 
    {
        memset(vis, 0, sizeof(vis)); // 每组数据初始化访问标记数组

        // 读取地图尺寸、操作步数和初始位置及朝向
        cin >> n >> m >> k;
        cin >> x >> y >> d;

        // 读取地图信息
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) 
                cin >> mp[i][j];

        // 输出机器人在地图上经过的不同位置总数
        cout << solve() << endl;
    }

    return 0;
}

T3 小木棍 普及/提高-

思路

贪心算法，按照 n 对 7 取模后进行分类讨论即可：

• 余0: 组成 8...8
• 余1: 当 n=1 时，无解，否则组成 108...8
• 余2: 当 n=2 时，组成 1，否则组成 18...8
• 余3: 当 n=3 时，组成 7，当 n=10 时，组成 22，否则组成 2008...8
• 余4: 当 n=4 时，组成 4，否则组成 208...8
• 余5: 当 n=5 时，组成 2，否则组成 28...8
• 余6: 当 n=6 时，组成 6，否则组成 68...8

参考程序

#include <bits/stdc++.h> // 引入万能头文件，包含所有标准库
using namespace std;

int n; // 表示小木棍的数量
int d[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; // 每个数字所需的小木棍数，例如d[0]表示数字0需要6根小木棍
int ans[11] = {-1, -1, 1, 7, 4, 2, 6, 8, 10, 18, 22}; // 特殊情况下的答案，前10个小木棍数量下的最小整数

// 打印函数：用于输出最小整数，由若干个数字8组成
void print(int n)
{
    // 当 n 为 7 的倍数时，拼出最小数的方案是尽可能多地使用数字8
    for (int i = 1; i <= n / 7; i++) 
        cout << 8;
}

int main() {
    int T; // 测试数据组数
    cin >> T;

    while (T--) {
        int n; // 本组数据的小木棍数量
        cin >> n;

        int r = n % 7; // 计算 n 除以 7 的余数，用于判断拼接方式

        // 如果 n 小于或等于10，直接输出预先计算好的答案
        if (n <= 10) 
            cout << ans[n];
        else if (r == 0) 
            // 当 n 是 7 的倍数，直接调用 print 函数输出尽量多的 8
            print(n);
        else if (r == 1) {
            // 当余数为 1 时，用数字10开头，然后用剩下的木棍尽量多拼接数字8
            cout << 10;
            print(n - d[1] - d[0]); // 剩余的小木棍数量为 n - d[1] - d[0]
        }
        else if (r == 2) {
            // 当余数为 2 时，用数字1开头，然后用剩下的木棍尽量多拼接数字8
            cout << 1;
            print(n - d[1]); // 剩余的小木棍数量为 n - d[1]
        }
        else if (r == 3) {
            // 当余数为 3 时，用数字200开头，然后用剩下的木棍尽量多拼接数字8
            cout << 200;
            print(n - d[2] - d[0] - d[0]); // 剩余的小木棍数量为 n - d[2] - 2*d[0]
        }
        else if (r == 4) {
            // 当余数为 4 时，用数字20开头，然后用剩下的木棍尽量多拼接数字8
            cout << 20;
            print(n - d[2] - d[0]); // 剩余的小木棍数量为 n - d[2] - d[0]
        }
        else if (r == 5) {
            // 当余数为 5 时，用数字2开头，然后用剩下的木棍尽量多拼接数字8
            cout << 2;
            print(n - d[2]); // 剩余的小木棍数量为 n - d[2]
        }
        else if (r == 6) {
            // 当余数为 6 时，用数字6开头，然后用剩下的木棍尽量多拼接数字8
            cout << 6;
            print(n - d[6]); // 剩余的小木棍数量为 n - d[6]
        }
        
        cout << endl; // 输出换行以分隔每组数据的结果
    }

    return 0;
}

T4 接龙普及+/提高

思路

动态规划：

• $dp[i][x]$ 表示前 $i$ 轮接龙之后，第 $i$ 轮的接龙序列的最后一项是 $x$ 时可能参与第 $i$ 轮接龙的人有几个（0个，1个，>=2个），如果只有一个人，记录是哪个人
• $dp[i][x]=0$ 表示有 $0$ 个人，即不可能达到这样的状态
• $dp[i][x]=-p$ 表示参与第 $i$ 轮的人只能是 $p$，$1<=p<=n$
• $dp[i][x]=2$ 表示能参与第 $i$ 轮的人至少有2个。
• 边界条件：
  • $dp[0][1]=2$，代表任何人都可以进行第一轮接龙
  • $dp[0][x]=0,x\ne 1$

参考程序

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

// 设置常量
const int maxs = 2e5; // 最大的值空间（假设元素最大值不会超过 2e5）
const int maxr = 100; // 最大的轮数限制

// 主解决函数
void solve() {
    int n, k, q; // n为玩家人数，k为子序列最大长度，q为任务数量
    cin >> n >> k >> q;

    vector<vector<int>> s(n + 1); // s[i] 存储第i个人的词库
    for (int i = 1; i <= n; i++) {
        int l; // l为词库长度
        cin >> l;
        while (l--) {
            int x;
            cin >> x; // 读入每个词库中的数字
            s[i].push_back(x);
        }
    }

    // 定义 dp 数组，dp[i][x] 表示第 i 轮接龙的最后一个元素是 x 的状态
    // dp[i][x] = 0 表示无法通过该接龙得到该状态
    // dp[i][x] = -p 表示只由玩家 p 可以达成该状态
    // dp[i][x] = 2 表示至少两个玩家可以达成该状态
    vector<vector<int>> dp(maxr + 1, vector<int>(maxs + 1));
    dp[0][1] = 2; // 初始化，第 0 轮默认初始状态设置为 2，表示初始状态可以由任意人开始

    // 动态规划进行状态转移
    for (int i = 1; i <= maxr; i++) { // 遍历每一轮
        for (int p = 1; p <= n; p++) { // 遍历每个玩家
            int cnt = 0; // 当前可以参与接龙的子序列计数
            for (int j = 0; j < s[p].size(); j++) { // 遍历玩家 p 的词库
                int x = s[p][j];
                // 如果前面有子序列满足条件，则标记当前状态
                if (cnt > 0) {
                    if (dp[i][x] == 0) {
                        dp[i][x] = -p; // 如果当前状态没有任何人到达，则由 p 到达
                    } else if (dp[i][x] < 0 && dp[i][x] != -p) {
                        dp[i][x] = 2; // 如果已经有其他人到达，则标记为至少有两个玩家可以到达
                    }
                }

                // 如果当前长度已经超过 k，开始从前面缩短子序列
                if (j >= k - 1) {
                    int y = s[p][j - (k - 1)]; // 获取子序列的起始元素
                    // 如果前一轮某人可以到达 y 并且不是当前玩家 p，则减少之前记录的有效子序列数量
                    if (dp[i - 1][y] != 0 && dp[i - 1][y] != -p) {
                        cnt--; // 当前窗口内有效子序列数量减少
                    }
                }

                // 检查当前元素是否可以作为接龙的起点
                int y = s[p][j];
                if (dp[i - 1][y] != 0 && dp[i - 1][y] != -p) {
                    cnt++; // 当前窗口内有效子序列数量增加
                }
            }
        }
    }

    // 处理每一个查询任务
    while (q--) {
        int r, c;
        cin >> r >> c; // 读取查询的轮数 r 和目标元素 c
        cout << (bool)dp[r][c] << '\n'; // 输出该状态是否可达，1 表示可达，0 表示不可达
    }
}

int main() {
    int T;
    cin >> T; // 读取测试案例数量
    while (T--) solve(); // 每个测试案例调用一次 solve 函数
    return 0;
}