2020“游族杯”全国高校程序设计网络挑战赛部分题解数据结构与算法rwbyblake的博客-

题目PDF

A – Amateur Chess Players

水题，题面写了一大堆，实际上有用的就几句话，输入也是，实际上有用的就只有n和m，就是比较n和m的大小

#include <iostream> #include <cstring> #include <cstdio> #include <string> #include <algorithm> #include <cmath> #include <stack> #include <queue> #include <vector> #include <map> using namespace std; int main() {     ios::sync_with_stdio(false); long long r = 1e9; long long l = -r; int n,m;     cin>>n;     string s; for(int i = 0;i<n;i++){         cin>>s; }     cin>>m; for(int i = 0;i<m;i++){         cin>>s; } if(n==m){         cout<<"Quber CC"; }else if(n>m){         cout<<"Cuber QQ"; }else{         cout<<"Quber CC"; } return 0; } 

F – Find / -type f -or -type d

近似模板题的字典树，写出来之后觉得非常简单，但是其中也有好几个坑。

题意就是说给一个原本输入命令后给出的目录及文件列表的乱序版本，让你找到一共有几个带有.eoj后缀的文件，因为是要找文件，所以如果在一个名字后面还有/文件名，那么这个就是名字里有.eoj的文件夹名，所以需要判断一下这个是不是文件夹，如果不全部插入后再查找，需要排序后从后往前进行插入并查找，同时还需要判断插入的字符串符不符合带有.eoj的文件这一属性。还有一种方法就是全部插入树后，再对每一个字符串进行查找，看遍历到最后的时候是否只出现过一次这个字符串。

#include <iostream> #include <cstring> #include <cstdio> #include <string> #include <algorithm> #include <cmath> #include <stack> #include <queue> #include <vector> #include <map> using namespace std; const int N = 5e6 + 10; string s[100005]; int tree[N][28]; int flag[N]; int cnt = 0; map<string, int> q; bool cmp(string s) { int a = s.size(); return s[a - 1] == 'j' && s[a - 2] == 'o' && s[a - 3] == 'e' && s[a - 4] == '.' && a > 5 && s[a - 5] != '/'; } int add(string s) { int root = 0; for (int i = 0; i < s.size(); i++) { int id; if (s[i] == '/') {             id = 26; } else if (s[i] == '.') {             id = 27; } else {             id = s[i] - 'a'; } if (!tree[root][id]) {             tree[root][id] = ++cnt; }         root = tree[root][id];         flag[root]++; } if (cmp(s) && flag[root] == 1) { return 1; } else { return 0; } } int main() {     ios::sync_with_stdio(false); int n; //solve();     cin >> n; int ans = 0; for(int i = 0;i<n;i++) {         cin >> s[i]; } sort(s,s+n); for(int i = n-1;i>=0;i--){         ans += add(s[i]); }     cout << ans; return 0; } 

I – Find / -type f -or -type d

也算是比较水的一道题，就是构造一个全部后缀子串按照字典序排序后，主串恰好排在k的字符串。这道题一开始想了好久，试了好多种构造方式，最后发现这种方法就可以了，有点崩溃。

#include <iostream> #include <cstring> #include <cstdio> #include <string> #include <algorithm> #include <cmath> #include <stack> #include <queue> #include <vector> #include <map> using namespace std; void builds(){ int n,k;     string s;     cin>>n>>k; for(int i = 1;i<=n;i++){ if(i==n-k+1){             s+='z'; }else{             s+='a'; } }     cout<<s; } int main() {     ios::sync_with_stdio(false); builds(); return 0; }