2024睿抗编程赛国赛-题解

2024睿抗编程赛国赛题解

RC-u1 大家一起查作弊

题目重述

我们需要从给定的多行字符串中提取出所有的关键词，并计算这些关键词的可疑分数总和、总长度以及关键词的数量。具体步骤如下：

1. 关键词定义：由大写字母、小写字母、数字组成的字符串，并且前后均为非大小写字母及数字（即关键词的边界是非字母数字字符或字符串的开头/结尾）。
2. 可疑分数计算：
   • 同时包含大写字母、小写字母、数字：+5 分
   • 同时包含（大写字母和数字）或（小写字母和数字）：+3 分
   • 同时包含大写字母和小写字母：+1 分
   • 其他情况：+0 分
3. 输出要求：
   • 第一行：可疑分数的总和
   • 第二行：关键词的总长度和关键词的数量（用空格隔开）

输入示例

static void nnmMNBkf3kfa(){
    int fefvB4=2;
    int [][]fsdk9A=new int[fefvB4][fefvB4];
    fsdk9A[0][0]=1;
    for (int gfdgsUB3 = 0; gfdgsUB3 < fefvB4; gfdgsUB3++) {
        for (int fdnbXZ8 = 0; fdnbXZ8<fefvB4-gfdgsUB3-1; fdnbXZ8++) {
            fsdk9A[gfdgsUB3][fdnbXZ8+1]=fsdk9A[gfdgsUB3][fdnbXZ8]+gfdgsUB3+fdnbXZ8+2;
            fsdk9A[gfdgsUB3+1][fdnbXZ8]=fsdk9A[gfdgsUB3][fdnbXZ8]+gfdgsUB3+fdnbXZ8+1;
            break;
        }
        break;
    }
}

输出示例

155
276 54

算法思路

主要是要学会getline读取字符串；

code

#include <bits/stdc++.h>
using namespace std;
#define int long long 
bool check1(char ch)
{
	if (ch >= 'a' && ch <= 'z') return true;
	else if(ch >= 'A' && ch <= 'Z') return true;
	else if (ch >= '0' && ch <= '9') return true;
	return false;
}
int sc = 0, le = 0, cnt = 0;
signed main()
{
	string s;
	while (getline(cin, s))
	{
		for (int i = 0; i < s.size(); i ++)
		{
			if (check1(s[i]))
			{
				bool f1 = 0, f2 = 0, f3 = 0;
				int r = i;
				for (int j = i; j < s.size(); j ++)
					if (check1(s[j]))				
						r = j;
					else 
						break;
				for (int j = i; j <= r; j ++)
				{
					if (s[j] >= 'a' && s[j] <= 'z') f1 = 1;
					else if (s[j] >= 'A' && s[j] <= 'Z') f2 = 1;
					else if (s[j] >= '0' && s[j] <= '9')f3 = 1; 
				}
				cnt ++;
				if (f1 && f2 && f3) sc += 5;
				else if ((f1 && f3) || (f2 && f3)) sc += 3;
				else if (f1 && f2) sc++;
				le += r - i + 1;
				i = r + 1;
			}
		}
	}
	cout << sc << endl;
	cout << le << " " << cnt ;
	return 0;
 } 

RC-u3 势均力敌

题目描述

给定一个整数 $n$（$2<n\le 4$）和 $n$ 个不同的个位数字（数字在 [1, 9] 范围内），用这些数字组成的所有 $n!$ 个不同的 $n$ 位数。需要将这些数字分成两组，满足以下条件：

1. 两组的数字个数相等（即每组有 $n!/2$ 个数字）。
2. 两组的数字的平方和相等。

题目要求输出其中一组的数字，每个数字占一行。

输入格式

• 第一行：正整数 $n$（$2<n\le 4$）。
• 第二行：$n$ 个不同的个位数字，用空格分隔。

输出格式

• 输出其中一组的 $n!/2$ 个数字，每个数字占一行。解不唯一时，输出任意一组均可。

示例

输入：

3
5 2 1

输出：

125
512
251

算法思路

因为 n 最大取4， 换算过来就是 24 中排列情况， 这期间又不是全部需要枚举，所以直接dfs深搜即可

第一个 dfs 把所有组合情况加在 v 中

第二个 dfs2 则枚举所有组合情况分成数量相同的两堆

code

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, sum;
int a[30];
vector<int> v, x;
bool st[30], st2[30], flag;
void dfs(int u, int x) {
	if (u == n) {
		v.push_back(x);
		return ;
	}
	for (int i = 0; i < n; i ++) {
		if (st[i]) continue;
		st[i] = 1;
		dfs(u + 1, x * 10 + a[i]);
		st[i] = 0;
	}
}

void dfs2(int u)
{
	if (u == sum || flag) return ;
	if (x.size () == sum / 2)
	{
		int s1 = 0, s2 = 0;
		for (int i = 0; i < sum; i ++) {
			if (st2[i]) s1 += v[i] * v[i];
			else s2 += v[i] * v[i];
		}
		if (s1 == s2) {
			flag = 1;
			for (auto c : x) {
				cout << c << endl;
			} 
			return;
		}
	}
	x.push_back(v[u]);
	st2[u] = 1;
	dfs2(u + 1);
	st2[u] = 0;
	x.pop_back();
	dfs2(u + 1);
}


signed main() {
	cin >> n;
	for (int i = 0 ; i < n; i ++ )
		cin >> a[i];
	dfs(0, 0);
	sum = v.size();
	dfs2(0);
	return 0;
}

RC-u4 City 不 City

题目描述

“City 不 City”是一个网络热梗，源于一位外国友人保保熊在直播旅游时用奇怪的腔调说“好 city，啊！”。现在，一些叛逆的年轻人喜欢在旅行时避开网红打卡点，选择一些小众的特色地方小城镇，不追求“city”，而是喜欢说“好 country，啊”。

给定各个城镇的旅游热度和城镇间的旅行花销，请为旅行者规划一条最经济的路线，并尽可能避开热度很高的网红点。

输入格式：

• 第一行：4 个正整数 n（城镇数量，1 < n ≤ 10^3）、m（通路条数，1 ≤ m ≤ 5n）、s（出发地）、t（目的地）。
• 第二行：n 个不超过 100 的正整数，表示 n 个城镇的旅游热度。
• 接下来的 m 行：每行给出 u、v、cost，表示城镇 u 和 v 之间有一条双向通路，花销为 cost（不超过 10^3 的正整数）。

输出格式：

• 从 s 到 t 的最小花销路线；若有多条相同最小花销的路线，选择途经城镇的最高旅游热度值最小的那条。
• 输出格式：最小花销 最高热度值（若没有途经城镇，最高热度为 0）。
• 如果无法从 s 走到 t，输出 Impossible。

输入样例 1：

8 14 7 8
100 20 30 10 50 80 100 100
7 1 1
7 2 2
7 3 1
7 4 2
1 2 1
1 5 2
2 5 1
3 4 1
3 5 3
3 6 2
4 6 1
5 6 1
5 8 1
6 8 2

输出样例 1：

4 50

解释：

从 7 到 8 的最短路径有 3 条：

1. 7->1->5->8（最高热度：max(100, 50) = 100）
2. 7->2->5->8（最高热度：max(20, 50) = 50）
3. 7->3->6->8（最高热度：max(30, 80) = 80）

选择最高热度最小的路径 7->2->5->8，输出 4 50。

输入样例 2：

3 1 1 2
10 20 30
1 3 1

输出样例 2：

Impossible

算法思路

Dijstra() 标准模板题，主要是要处理好best数组，best数组用来记录路上的最高热度

code

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e3 + 10, M = N * 10;
int h[N], e[M], ne[M], idx, w[M];
void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int p[N], dist[N];
int best[N];  // 记录最高热度 
int n, m, s, t;
bool st[N];
void Dijstra() {
	memset(dist, 0x3f, sizeof dist);
	memset(best, 0x3f, sizeof best);
	dist[s] = 0;
	best[s] = 0;
	for (int i = 1; i <= n; i ++) {
		int v = -1;
		for (int j = 1; j <= n; j ++) {
			if (!st[j] && (v == -1 || dist[j] < dist[v] || (dist[j] == dist[v] && best[j] < best[v]))) v = j;

		}
		st[v] = 1;
		for (int i = h[v]; i != -1; i = ne[i]) {
			int j = e[i];
			int d = dist[v] + w[i];
			int be = max(best[v], j == t ? 0 : p[j]); // 如果不是终点，就把热度考虑进去 
			if ( d < dist[j] || (d == dist[j] && be < best[j])) {
				dist[j] = d;
				best[j] = be;
			}
		}
	}
}

int main() {
	memset(h, -1,sizeof h);
	cin >> n >> m >> s >> t;
	for (int i = 1; i <= n; i ++) {
		cin >> p[i];
	}
	for (int i = 1; i <= m; i ++) {
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b, c), add(b, a, c);
	}

	Dijstra();
	if (dist[t] == 0x3f3f3f3f)
		cout << "Impossible";
	else {
		cout << dist[t] << " " << best[t];
	}
	cout << endl;
	return 0;
}