题目可以去pta教育超市找
写第一题还很清醒。（耗时15分钟）
#include<bits/stdc++.h>
using namespace std;
string s;
int sum = 0,len = 0;
int cnt = 0;int check(char c){if(c >= 'a' && c <= 'z'){return 1;}else if(c <= 'Z' && c >= 'A'){return 2;}else if(c <= '9' && c >= '0'){return 3;}else{return 0;}
}void f(string t){len += t.size();if(t.size()){cnt ++;}bool f1 = false, f2 = false, f3 = false;for(int i = 0;i < t.size();i ++){if(check(t[i]) == 1){f1 = true;}else if(check(t[i]) == 2){f2 = true;}else{f3 = true;}}if(f1 && f2 && f3){sum += 5;}else if((f1 && f3) || (f2 && f3)){sum += 3;}else if(f1 && f2){sum += 1;}
}void solve(){while(cin >> s){string t = "";for(int i = 0;i < s.size();i ++){if(check(s[i])){t += s[i]; }else{f(t);t = "";}}if(t.size()){f(t);}}cout << sum << endl << len << ' ' << cnt << endl;
}int main(){int t = 1;while(t --){solve();}
}
第二题就开始犯迷糊了，题面太恶心了，val数组少写了一个半天没找到，无语了。。。（耗时25分钟）
#include<bits/stdc++.h>
using namespace std;
int val[] = {0, 25, 21, 18, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};struct d{int first;int second;
}a[40];bool cmp(d x, d y){if(x.first != y.first){return x.first > y.first;}else{return x.second < y.second;}
}void solve(){int n;cin >> n;map<int,int>mp;while(n --){for(int i = 0;i < 20;i ++){int x, y;cin >> x >> y;mp[x] = 1;a[x] = {a[x].first + val[y], x};}}sort(a + 1, a + 31, cmp);for(int i = 1;i <= 30;i ++){if(mp[a[i].second])cout << a[i].second << ' ' << a[i].first << endl;}
}int main(){int t = 1;while(t --){solve();}
}
第三题，一开始忘了如何dfs求排列，求完排列果断暴力，最后就14分，当时想的是dp，没想到就是一个简单数学问题。每个数可以拆个十百千来算，就是个排序
#include<bits/stdc++.h>
using namespace std;int a[5], st[5];
map<int,int>mp;
int n;
vector<int>b;
set<int>s;
vector<int>ans;void dfs1(int val, int cnt){if(cnt >= n){s.insert(val);return;}for(int i = 1;i <= n;i ++){if(!st[i]){st[i] = 1;dfs1(val * 10 + a[i], cnt + 1);st[i] = 0;}}
}void solve(){cin >> n;for(int i = 1;i <= n;i ++){cin >> a[i];} dfs1(0, 0);long long sum = 0;for(auto x : s){b.push_back(x);sum += x * x;}int f = 1;for(int i = 0;i < b.size();i += 2){int c = b[i], d = b[i + 1];if(f == 1)cout << c << endl;elsecout << d << endl;f *= -1;}
}int main(){int t = 1;while(t --){solve();}
}
第四题，当时写最短路，然后写的很对就是过不去，最后没办法，只能二分答案，
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>int n, m, s, t;
vector<pair<int,int>>e[1010];
int val[1010], st[1010], dist[1010], pre[1010];bool dij(int mid){priority_queue<pii, vector<pii>, greater<pii>>q;memset(pre, -1, sizeof pre);memset(st, 0, sizeof st);memset(dist, 0x3f, sizeof dist);q.push({0, s});while(q.size()){auto k = q.top();q.pop();int d = k.first;int id = k.second;if(st[id]){continue;}st[id] = 1;for(auto [x, y] : e[id]){if(val[x] > mid && x != t){continue;}else{if(y + d < dist[x]){dist[x] = y + d;q.push({dist[x], x});}}}}if(dist[t] == 0x3f3f3f3f){return false;}return true;
}void solve(){cin >> n >> m;cin >> s >> t;int ma = -1, mi = 0x3f3f3f3f;for(int i = 1;i <= n;i ++){cin >> val[i];ma = max(ma, val[i]);mi = min(mi, val[i]);}for(int i = 0;i < m;i ++){int x, y, z;cin >> x >> y >> z;e[x].push_back({y, z});e[y].push_back({x, z});}int l = mi - 1, r = ma + 1;while(l + 1 != r){int mid = l + r >> 1;if(dij(mid)){r = mid;} else{l = mid;}}if(!dij(r)){cout << "Impossible";}else{cout << dist[t] << ' ' << r << endl;}
}int main(){int t = 1;while(t --){solve();}
}
赛后秒出正解，服了啊，错误原因是我建边建错了
#include<bits/stdc++.h>
using namespace std;
#define pii pair<pair<int,int>,int>int n, m, s, t;
vector<pair<int,int>>e[1010];
int val[1010], st[1010], dist[1010], pre[1010];
int res[1010];bool dij(){priority_queue<pii, vector<pii>, greater<pii>>q;memset(pre, -1, sizeof pre);memset(st, 0, sizeof st);memset(dist, 0x3f, sizeof dist);q.push({{0, 0}, s});while(q.size()){auto k = q.top();q.pop();int d = k.first.first;int v = k.first.second;int id = k.second;if(st[id]){continue;}st[id] = 1;for(auto [x, y] : e[id]){if(dist[x] > y + d){dist[x] = y + d;pre[x] = id;res[x] = max(v, val[x]);q.push({{dist[x], res[x]}, x});}else if(dist[x] == y + d && res[x] > v){res[x] = max(val[x], v);pre[x] = id;q.push({{dist[x], res[x]}, x});}}}if(dist[t] == 0x3f3f3f3f){return false;}return true;
}void solve(){cin >> n >> m;cin >> s >> t;for(int i = 1;i <= n;i ++){cin >> val[i];}val[s] = 0;val[t] = 0;for(int i = 0;i < m;i ++){int x, y, z;cin >> x >> y >> z;e[x].push_back({y, z});e[y].push_back({x, z});}if(!dij()){cout << "Impossible";}else{cout << dist[t] << ' ' << res[t];}
}int main(){int t = 1;while(t --){solve();}
}
这次比赛很糟糕，但是也学到了不少东西。下次注意