csp-j2024题解

T1 模拟题意这题需要在输入小P拥有的扑克牌后，统计最少还差几张可以凑够52张不同花色不同点数的牌。一种方法是将输入的牌转化为[1,52]中的一个数字，然后计算有几个数字没出现过；也可以直接从字符串入手，统计有几个本质不同的字符串，即可得到小P有几张不同的扑克牌，用52减去结果即可。

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

int n, ans, cnt[56 + 5], res;

int check1(char u)
{
    if (u == 'D')
        return 0;
    if (u == 'C')
        return 1;
    if (u == 'H')
        return 2;
    if (u == 'S')
        return 3;
}

int check2(char u)
{
    if (u == 'A')
        return 1;
    if (u == 'T')
        return 10;
    if (u == 'J')
        return 11;
    if (u == 'Q')
        return 12;
    if (u == 'K')
        return 13;
    return u - '0';
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        res = check1(s[0]) * 13 + check2(s[1]);
        cnt[res]++;
    }
    for (int i = 1; i <= 52; i++)
        if (!cnt[i])
            ans++;
    cout << ans;
    return 0;
}

T2 模拟需要根据题中描述，记录下机器人的实时位置与朝向后，执行k次题中操作： ①根据朝向判断出机器人的目标移动位置 ②判断机器人的目标移动位置是否超出地图或碰到障碍若目标移动位置合法，则向目标位置移动反之，改变机器人朝向在移动的同时，可以用一个数组记录下机器人到过哪些位置，最后遍历每个位置统计机器人去过多少个点即可。

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

int T, m, n, K, x, y, d;
int dir[4][2] = {{0, 1},{1, 0},{0, -1},{-1, 0}};
char g[N][N];
bool st[N][N];

bool check(int u, int v) // 检验位置合法 
{
    if (u < 1 || u > m || v < 1 || v > n)
        return 0;
    if (g[u][v] != '.')
        return 0;
    return 1;
}

int main()
{
    cin >> T;
    while (T--)
    {
        memset(st, 0, sizeof(st));
        scanf("%d%d%d", &m, &n, &K);
        scanf("%d%d%d", &x, &y, &d);
        for (int i = 1; i <= m; i++)
            scanf("%s", g[i] + 1);
        st[x][y] = 1;
        while (K--)
        {
            int nx, ny;
            nx = x + dir[d][0];
            ny = y + dir[d][1];
            if (!check(nx, ny))
            {
                d = (d + 1) % 4;
                continue;
            }
            x = nx, y = ny;
            st[x][y] = 1;
        }
        int ans = 0;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (st[i][j])
                    ans++;
        printf("%d\n", ans);
    }
}

T3 这题需要用贪心的思想来逐位确定答案。观察发现，0-9这10个数字分别需要6,2,5,5,4,5,6,3,7,6根火柴，也就意味着组成一个数字需要2-7根火柴棒。因而不难发现，只有在 n=1 时，无解输出 -1。而对于其他情况，为让组成的数字尽可能小，首先需要这个数字的长度（位数）尽可能短，这个长度可以直接计算： [] 除此之外，我们还需要让数位高的数尽可能小，因而可以采用逐位确定的方法，从大到小依次遍历各个数位，每个数位从小到大（注意最高位不能是 0），依次尝试填入数字。若此时还剩下 n 个火柴棒，需要组成 len 个数位，当且仅当满足 2*(len-1)≤n-cnt[x]≤7*(len-1) 时，最高位才可以填入数字 x。式中的 cnt[x] 表示拼成数字 x 需要的火柴棒数。只需贪心地让高数位上的数字尽可能小即可。

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

int T, n, len;
int cnt[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

bool judge(int u, int v) // 判断用v个火柴棒拼成u个数位是否合法
{
    if (v > u * 7)
        return 0;
    if (v < u * 2)
        return 0;
    return 1;
}

void work(int u, int sum) // 目前在填第u位，火柴棒还有sum个
{
    if (!u)
        return;
    int st = 0;
    if (u == len) // 注意不能有前导零
        st = 1;
    for (int i = st; i <= 9; i++) // 尝试将i填到第u位
    {
        if (judge(u - 1, sum - cnt[i]))
        {
            printf("%d", i);
            work(u - 1, sum - cnt[i]);
            break;
        }
    }
}

int main()
{
    cin >> T;
    while (T--)
    {
        scanf("%d", &n);
        if (n == 1)
        {
            puts("-1");
            continue;
        }
        len = (n + 6) / 7; // 计算最终的数位个数
        work(len, n);
        puts("");
    }
    return 0;
}

共 2 条回复