GPLT团体程序设计天梯赛模拟：2025年分组赛
摘要
相对分子质量
字符串模拟
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
| #include<bits/stdc++.h>
using namespace std;
string s;
double sum;
unordered_map<string, double> mp;
void init_mp(){
mp["H"] = 1;
mp["C"] = 12;
mp["N"] = 14;
mp["O"] = 16;
mp["F"] = 19;
mp["Na"] = 23;
mp["Mg"] = 24;
mp["Al"] = 27;
mp["Si"] = 28;
mp["P"] = 31;
mp["S"] = 32;
mp["Cl"] = 35.5;
mp["K"] = 39;
mp["Ca"] = 40;
mp["Mn"] = 55;
mp["Fe"] = 56;
mp["Cu"] = 64;
mp["Zn"] = 65;
mp["Ag"] = 108;
mp["I"] = 127;
mp["Ba"] = 137;
mp["Hf"] = 178.5;
mp["Pt"] = 195;
mp["Au"] = 197;
mp["Hg"] = 201;
}
int read_num(int & i){
int res = 0;
for(;s[i] >= '0' && s[i] <= '9' ; i++){
res = (s[i] - '0') + res*10;
}
return res;
}
double read_elem(int & i){
string t = "";
int num = 1;
if(s[i] >= 'A' && s[i] <= 'Z'){
t += s[i]; i++;
if(i < s.length() && s[i] >= 'a' && s[i] <= 'z'){
t += s[i]; i++;
}
}
if(s[i] == '_'){
i += 2;
num = read_num(i);
i ++;
}
return mp[t]*num;
}
int main(void){
cin>>s;
init_mp();
for(int i = 0 ; i < s.length(); ){
if(s[i] >= 'A' && s[i] <= 'Z'){
sum += read_elem(i);
}else if(s[i] == '('){
double k = 0; i++;
while(s[i] != ')') k += read_elem(i);
i += 3;
sum += k*read_num(i);
i++;
}else if(s[i] == '~'){
i++;
int num = (s[i] == 'H' ? 1: read_num(i));
sum += num*(mp["H"]*2 + mp["O"]);
i += 6;
}else{
i++;
}
}
if(sum == int(sum)) cout<<int(sum);
else cout<<fixed<<setprecision(1)<<sum;
return 0;
}
|
女仆咖啡厅桌游吧
给一棵树，要对树的节点进行涂色，允许涂两种颜色，要求每个子树的两种颜色数相同，求单一颜色的最大个数。
我们设 红色为1，蓝色为-1，即每个子树的总和为0；
假设节点x的每个子节点已经合法涂色，因为每个子节点代表的子树总和都为0，现在可以考虑的只有叶子节点和父节点。
那么x代表的子树对总和的贡献为 （叶子节点个数 + 1）/ 2。
由此可以得到递推关系： \[
dp[i] = \sum_{j}^{son[i]}dp[j] + cnt/2
\] 这里的son[i]表示非叶子节点，cnt 表示 叶子节点 + 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int n,dp[maxn],d[maxn];
vector<int > e[maxn];
void dfs(int x, int f){
int cnt = 1;
for(auto it : e[x]){
if(it != f){
dfs(it, x);
dp[x] += dp[it];
if(d[it] == 1) cnt++;
}
}
dp[x] += cnt/2;
}
int main(void){
cin>>n;
for(int i = 1 ; i <= n-1 ; i ++){
int u, v; cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
d[v]++;d[u]++;
}
dfs(1, -1);
cout<<dp[1];
return 0;
}
|
数学作业
给定一个数字n，求 < n 的斐波那契数中，能构成n的组合有几种。
题目给定n的最大值为10^12，斐波那契数最多有58个，而朴素遍历的时间复杂度为O(2^n)。一定会超时。
我们考虑使用前缀和进行优化：
若当前和 + 此后所有数的和 < n，退出循环；
若当前和 > n，退出循环；
注意，对于合法的斐波那契数，我们要从大到小进行遍历，可以极大优化剪枝过程。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n,l,ans;
ll dp[100],pre[100];
void dfs(ll d, ll sum){
if(sum + pre[d] < n) return;
if(sum > n) return;
if(d == 0){
if(sum == n) ans++;
return;
}
dfs(d-1, sum + dp[d]);
dfs(d-1, sum);
}
int main(void){
cin>>n;
dp[0] = dp[1] = 1;
pre[1] = 1;
for(int i = 2 ; dp[i-1] <= n ; i ++){
dp[i] = dp[i-1] + dp[i-2];
pre[i] += pre[i-1] + dp[i];
l = i;
}
dfs(l-1, 0);
cout<<ans;
return 0;
}
|
买礼物
Kruskal最小生成树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| #include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3;
struct edge{
int w;
int x,y;
bool operator<(const edge & rhs){
return w < rhs.w;
}
};
vector<edge> v;
int p, n;
int fa[maxn];
int find(int x){
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int main(void){
cin>>p>>n;
for(int i = 1 ; i <= n ; i ++) fa[i] = i;
for(int i = 1 ; i <= n ; i ++){
for(int j = 1 ; j <= n ; j ++){
edge e; e.x = i; e.y = j;
cin>>e.w;
if(e.w == 0 || e.w > p) e.w = p;
v.push_back(e);
}
}
sort(v.begin(), v.end());
int cnt = 0;
int sum = 0;
for(int i = 0 ; i < v.size() && cnt < n-1 ; i ++){
int fx = find(v[i].x);
int fy = find(v[i].y);
if(fx == fy) continue;
fa[fx] = fy;
sum += v[i].w;
cnt++;
}
cout<<sum+p;
return 0;
}
|