CSP-J2024复赛T1-T3题解

‮队团加不）ด้้童帅_者仇复

2024-10-26 21:20:05

发布于：广东

372阅读

0回复

0点赞

T1

缺啥牌补啥就行了，用set记录最后判断长度

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
set <string> s;
int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        string str;
        cin >> str;
        s.insert(str);//加入集合
    }
    cout << 52 - s.size();

	return 0;
}

T2

按题意模拟即可.
注意方向应该怎么加

#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
char a[1005][1005];
bool vis[1005][1005];
const int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
void solve(){
	memset(a, 0, sizeof(a));
	memset(vis, 0, sizeof(vis));
	int n, m, k, x, y, cur;
	cin >> n >> m >> k >> x >> y >> cur;
	for(int i = 1; i <= n; i++){
		cin >> a[i] + 1;
	}
	vis[x][y] = 1;
	while(k--){
		int xx = x + dir[cur][0], yy = y + dir[cur][1];
		if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && a[xx][yy] == '.') vis[x = xx][y = yy] = 1;//移动
		else cur = (cur + 1) % 4;//转向
	}
	int ct = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++) ct += vis[i][j];
	}
	cout << ct << endl;
}
int main(){
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

T3

我们可以发现，真正可能在数字里面的只有0124678这7个数，我们贪心求出组成的最小值，再DP就行了
比较不能先转string，这样时间复杂度就会退化成 $O(n^2)$ .
注意比较中最后的判断，比如两个数去掉首位后的记录情况如下：

1 2 3 4 5 6 7
7 6 5 4 3 2 1

那他们所对应的数（不含首位）为

0112224444666667777778888888
0000000111111222224444666778

很明显第二个数小.

#include <iostream>
#include <cstdio>
using namespace std;
struct node{
	int a[7];//用桶记录
}dp[100005];
const int turn[7] = {0, 1, 2, 4, 6, 7, 8}, number[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
int get_head(node &n){//获取开头的数，因为首位不能为0
	for(int i = 1; i <= 6; i++){
		if(n.a[i]){
			n.a[i]--;
			return turn[i];
		}
	}
}
string get(node n){//转换为字符串
	string s;
	s = get_head(n) + '0';
	for(int i = 0; i <= 6; i++){
		while(n.a[i]){
			s += turn[i] + '0';
			n.a[i]--;
		}
	}
	return s;
}
bool cmp(node a, node b){//比较，是不是更小
	int lena = 0, lenb = 0;
	for(int i = 0; i <= 6; i++){
		lena += a.a[i], lenb += b.a[i];
	}
	if(lena == 0) return 0;
	if(lenb == 0) return 1;//如果是空的就要加入
	if(lena < lenb) return 1;
	if(lena > lenb) return 0;
	int tmp1 = get_head(a), tmp2 = get_head(b);
	if(tmp1 < tmp2) return 1;//判断首位
	if(tmp1 > tmp2) return 0;
	for(int i = 0; i <= 6; i++){
		if(a.a[i] < b.a[i]) return 0;//注意这个要反过来判断
		if(a.a[i] > b.a[i]) return 1;
	}
	return 0;
}
int main(){
	dp[2].a[1] = 1, dp[3].a[5] = 1, dp[4].a[3] = 1, dp[5].a[2] = 1, dp[6].a[4] = 1, dp[7].a[6] = 1;//初始化
	for(int i = 8; i <= 100000; i++){
		for(int j = 0; j <= 6; j++){
			if(i - number[turn[j]] <= 1) continue;//1不能算
			node n = dp[i - number[turn[j]]];
			n.a[j]++;
			if(cmp(n, dp[i])) dp[i] = n;
		}
	}
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		cout << (n == 1 ? "-1\n" : get(dp[n]) + '\n');//1不能拼任何数
	}

	return 0;
}