2019年华南理工大学程序设计竞赛（春季赛）题解

本文主要是介绍2019年华南理工大学程序设计竞赛（春季赛）题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目在牛客上有https://ac.nowcoder.com/acm/contest/625#question

C    六数学家的困惑

题意：就是给你两串数字，每次只能从其中一串数字的左侧或右侧取出一个数字，然后组成一串最大的字典序最大的串。做法是把两串数字翻转一下，变成四串数字，每次从字典序最大的那串数取数。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 5;int main()
{int n, Case = 0;string a, b, t;cin >> n;while(n--){cin >> a >> b;cout << "Case #" << ++Case << ": ";while(a.length() || b.length()){t = a;reverse(a.begin(), a.end());a = max(a, t);t = b;reverse(b.begin(), b.end());b = max(b, t);if(a < b) swap(a, b);cout << a[0];a.erase(0, 1);}cout << endl;}return 0;
}

 

E    数独挑战

暴力搜索题，每次判断填的数在行列中和小九宫格中是否出现过。

#include <bits/stdc++.h>
using namespace std;
int num[9][9], flag;
int col[10][10], row[10][10];//列 行标记
int nine[3][3][10];
void print(){for(int i = 0; i < 9; i++){for(int j = 0; j < 9; j++){cout << num[i][j];if(j != 8) cout << " ";}cout << endl;}
}void dfs(int x, int y){if(flag) return ;if(y == 9){flag = 1;print();return ;}if(num[y][x] == 0){for(int i = 1; i <= 9; i++){if(!col[x][i] && !row[y][i] && !nine[y / 3][x / 3][i]){col[x][i] = 1;row[y][i] = 1;nine[y / 3][x / 3][i] = 1;num[y][x] = i;dfs((x + 1) % 9, y + (x + 1) / 9);col[x][i] = 0;row[y][i] = 0;nine[y / 3][x / 3][i] = 0;}}num[y][x] = 0;}else{dfs((x + 1) % 9, y + (x + 1) / 9);}
}int main()
{flag = 0;memset(col, 0, sizeof(col));memset(row, 0, sizeof(row));memset(nine, 0, sizeof(nine));for(int i = 0; i < 9; i++){for(int j = 0; j < 9; j++){cin >> num[i][j];col[j][num[i][j]] = 1;row[i][num[i][j]] = 1;nine[i / 3][j / 3][num[i][j]] = 1;}}dfs(0, 0);return 0;
}

 

F    翻牌游戏

概率DP。但是可从后面的样例推出规律 2n-1

#include <cstdio>
int main() {int t;double n;scanf("%d", &t);while(t--){scanf("%lf", &n); printf("%.2lf\n", 2*n-1);}return 0;
}

 

H    Parco_Love_GCD

先把n个数的公共gcd求出来。然后对每个子序列的起点往后求gcd，有和公共gcd相同的可用直接计算ans = (ans + (n - 1 - j) * com) % MOD然后跳过这轮循环。数据比较水，到后面有许多相同的数QAQ

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define MOD 1000000007
const int maxn = 5e5 + 5;
LL a[maxn];
LL gcd(LL a, LL b){return b == 0 ? a : gcd(b, a % b);
}
int main() {LL ans = 0, com, res, n;//com公共公约数cin >> n;for(int i = 0; i < n; i++){cin >> a[i];if(i == 0) com = a[i];else com = gcd(a[i], com);}/*16 4 7 21 3
res 16 4 1  1 1*///cout << com << endl;for(int i = 0; i < n; i++){res = a[i];for(int j = i; j < n; j++){res = gcd(res, a[j]);ans = (ans + res) % MOD;if(res == com){//如果这里的公共公约数=com，那后面的公共公约数肯定也是com，直接加起来ans = (ans + (n - 1 - j) * com) % MOD;break;//后面不用计算了}}}cout << ans << endl;return 0;
}

I     炒股

贪心题，每次加上两数差为正数

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 5;int main()
{std::ios::sync_with_stdio(false);LL ans = 0, n, last, a;cin >> n;for(int i = 0; i < n; i++){cin >> a;if(i >= 1 && last < a) ans += a - last;last = a;}cout << ans << endl;return 0;
}

L    石头剪刀布

签到题

#include <bits/stdc++.h>
using namespace std;
int main()
{int n;char a[10];cin >> n;while(n--){cin >> a;if(a[0] == 'S') cout << "Rock" << endl;else if(a[0] == 'R') cout << "Paper" << endl;else cout << "Scissors" << endl;}return 0;
}

 

这篇关于2019年华南理工大学程序设计竞赛（春季赛）题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---