2024CSP-J题解附源码T1-T3

T1

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

///T1题解
///输入行数n
///输入n行，每行一个字符串，字符串只有两个字母组成，第一个字母是花色，第二个字母是点数。
///一副牌只有52种组合，因为map能去重，所以用map进行统计不同组合数即mp.size()
///结果为52-mp.size()

map<string,bool>mp;
int main() {
    int n;
    cin>>n;
    string s;
    for(int i = 0;i < n;i++) {
        cin>>s;
        mp[s] = true;
    }
    int ret = 52-mp.size();
    cout<<ret<<endl;
    return 0;
}
/*
4
DQ
H3
DQ
DT
49

1
SA
51
*/

T2

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

///T2题解
///有一张n*m的地图，地图上的位置要么是空地、要么是障碍物。
///有一个机器人，一开始机器人在某一个空地位置（x,y）
///机器人需要按照给定的方向d开始走路具体规则（规则看题目描述），求操作k次后机器人走过的不同空地位置数量
///机器人的每次操作有可能是走一步，有可能是右转。只要机器人能往这个方向走则走一步操作，否则机器人需要右转一次操作
///时间复杂度是O（k）,k最大1e6，即O(n)
const int N = 1e3+5;
struct node {
    int x,y;
};
int n,m,k;
string s[N];
int dx[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; ///顺序要根据题目写
int vis[N][N]; ///标记走过的点，统计时能去掉重复走的点

bool check(int x,int y) {
    if(x >= 0 && x < n && y >= 0 && y < m && s[x][y]=='.'){ ///检查要走的点在地图上并且为空地
        return true;
    }
    return false;
}
int bfs(int x,int y,int d) {
    queue<node>qu;
    while(!qu.empty()) qu.pop(); ///清空队列
    qu.push({x,y});
    fill(vis[0],vis[0]+N*N,0); ///多组数据，清空vis数组
    vis[x][y] = 1;              ///起点标记
    int cnt =1;     ///包括起始位置；数据范围k>=1
    while(!qu.empty()) {
        node now = qu.front();
        qu.pop();
        x = now.x;
        y = now.y;
        ///cout<<"goto "<<x<<" "<<y<<endl; ///输出按题目要求走过的所有点，包括重复走的
        if(k==0) {          ///机器人操作完k次就可以返回答案了
            return cnt;
        }
        while(k) {  ///机器人只能操作k次
            k--;
            int xx = x+dx[d][0];    ///机器人下一步要走的位置是（xx,yy）
            int yy = y+dx[d][1];
            if(check(xx,yy)) {  ///检查机器人想走的位置（xx,yy）能走
                qu.push({xx,yy});   ///位置（xx，yy）在地图上并且为空地机器人就能走，需要入队作为机器人下一步的位置
                if(vis[xx][yy] == 0) {  ///cnt统计机器人走过的不同位置数量，通过vis标记数组能去掉机器人重复走过的位置
                    vis[xx][yy] = 1;
                    cnt++;
                }
                break;  ///只要机器人能走位置（xx，yy）就可以直接跳出循环，从队列中获取机器人的最新位置信息即位置（xx，yy）。
            }
            else {
                ///cout<<"t r\n"; ///打印机器人右转
                d = (d+1)%4;    ///机器人进行右转
            }
        }
    }
    return cnt;  ///返回结果：机器人走过的不同位置数量（题目中说了包括起点）
}
void solve() {
    int x,y,d;
    cin>>n>>m>>k;   ///输入地图大小n*m和机器人操作次数k
    cin>>x>>y>>d;   ///输入机器人起始位置（x,y）和方向d
    for(int i = 0;i < n;i++) {
        cin>>s[i];          ///输入地图
    }
    int ret = bfs(x-1,y-1,d);   ///调用bfs函数让机器人进行k次操作并返回结果。
    cout<<ret<<"\n";        ///输出结果
}
int main() {
    int T;
    cin>>T; ///输入T
    while(T--) {///T组数据的出来
        solve();    ///调用solve函数处理每一组数据
    }
    return 0;
}
/*
样例 1 输入

2
1 5 4
1 1 2
....x
5 5 20
1 1 0
.....
.xxx.
.x.x.
..xx.
x....

样例 1 输出
3
13
*/

T3

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

///T3题解
///题目要求火柴组成的数字是最小的，那就尽可能把火柴组合成8，因为8使用的火柴数量最多
///特殊性质 A：保证 n 是 7 的倍数且 n ≥ 100。 20分
///特殊性质 B：保证存在整数 k 使得 n = 7k + 1，且 n ≥ 100。 30分
///送的50分，性质A的数据输出全是数字8，8的数量为n/7；性质B的数据输出：先输出10之后全是8,输出8的具体数量为(n-1-7)/7个。
///根据特殊性质数据提示，可以知道，组成的数字最小的方案：第一二位需要考虑，之后每一位只能是8
const int N = 1e3+5;
int a[40] = {-1,-1,1,7,4,2,6,8,10,18,22,20,28,68}; ///打表
void print8(int m) {
    for(int i = 0;i < m;i++) {
        cout<<8;
    }
    cout<<"\n";
    return;
}
void solve() {
    a[1] = -1; ///打表
    a[2] = 1;
    a[3] = 7;
    a[4] = 4;
    a[5] = 2;
    a[6] = 6; ///数字0也是用6根火柴，但不能有前导0，包括数字0
    a[7] = 8;
    int n;
    cin>>n;   ///输入火柴数量n
    if(n < 7 ) { ///火柴数量小于7要打表。
        cout<<a[n]<<"\n";
    }
    else {
        switch(n%7) {
            case 0:                 ///火柴数量是7的倍数，
                print8(n/7);        ///全打印8并打印换行。
                break;
            case 1:                 ///火柴数量是7的倍数+1，
                cout<<10;           ///8根火柴组成的最小数是10，先打印10
                print8((n-1-7)/7);  ///打印8并打印换行
                break;
            case 2:                 ///火柴数量是7的倍数+2，
                cout<<18;           ///9根火柴组成的最小数是18，先打印18
                print8((n-2-7)/7);    ///全打印8并打印换行。
                break;
            case 3:                 ///火柴数量是7的倍数+3，
                if((n-10)/7) {   ///只考虑先输出22，再输出8个数。
                                    ///仔细观察，2需要5根火柴，8需要7根火柴，0需要6根火柴
                    cout<<200;       ///2变0、8变0火柴数量是+1、-1，刚好抵消掉且可以使数字更小。
                    print8((n-10)/7-1);///因为把最前面的8换成了0，所以实数需要-1，打印8并打印换行
                }
                else {
                    cout<<22<<"\n"; ///10根火柴组成的最小数是22
                }
                break;
            case 4:                 ///火柴数量是7的倍数+4，
                cout<<20;            ///11根火柴组成的最小数是20，先打印20
                print8((n-4-7)/7);    ///全打印8并打印换行。
                break;
            case 5:                 ///火柴数量是7的倍数+5，
                cout<<28;           ///12根火柴组成的最小数是28，先打印28
                print8((n-5-7)/7);  ///打印8并打印换行
                break;
            case 6:                 ///火柴数量是7的倍数+6，
                cout<<68;           ///13根火柴组成的最小数是68，先打印68
                print8((n-6-7)/7);   ///全打印8并打印换行。
                break;
            default:
                break;
        }
    }
    return;
}

void st();
void bfs(int n,bool v,long long ans);
int main() {
    st();
    int T;
    cin>>T; ///输入T
    while(T--) {///T组数据的出来
        solve();    ///调用solve函数处理每一组数据
    }
    return 0;
}
/*
【样例 1 输入】
5
1
2
3
6
18
【样例 1 输出】
-1
1
7
6
208
*/
/*
///打表check一下
int b[] = {-1,-1,1,7,4,2,0,8};
long long ret;
void dfs(int n,bool v,long long ans) {
    if(n==0) {
        ret = min(ans,ret);
        return;
    }
    if(n < 2) return;
    for(int i = 2;i <= 7;i++) {
        if(i > n) continue;
        if(i!=6) {
            dfs(n-i,1,ans*10+b[i]);
        }
        else {
            if(v) {
                dfs(n-i,v,ans*10);
            }
            else {
                dfs(n-i,1,ans*10+6);
            }
        }
    }
}
void st() {
    long long a = 1;
    for(int i = 1;i < 40;i++) {
        ret = 0x7fffffffffffffff;
        dfs(i,0,0);
        cout<<ret<<" "<<i<<" "<<i%7<<"\n";
    }
}
*/