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;
}