开学第三测
（题目分析摘自dalao博客
https://blog.csdn.net/todobe/article/details/54617259
https://blog.csdn.net/cdqzgxxqdql/article/details/53085481）
P71
竞赛时间：???? 年?? 月?? 日??:??-??:??
| 题目名称 | 智乃 | 麻耶 | 惠 |
| 名称 | kahuucino | zyougamaya | nacumegu |
| 输入 | kahuucino.in | zyougamaya.in | nacumegu.in |
| 输出 | kahuucino.out | zyougamaya.out | nacumegu.out |
| 每个测试点时限 | 1秒 | 1秒 | 1秒 |
| 内存限制 | 512MB | 512MB | 512MB |
| 测试点数目 | 20 | 10 | 10 |
| 每个测试点分值 | 5 | 10 | 10 |
| 是否有部分分 | 无 | 无 | 无 |
| 题目类型 | 传统 | 传统 | 传统 |
T1
智乃
【题目描述】
给你N个字符串，你每次可以选择其中一个字符串的一段前缀进行翻转，但是你必须保证这个前缀的长度是偶数。你可以进行无限次这样的操作，并且如果
两个字符串变得相同的时候，你就可以把这两个字符串都删除掉，问最后最少剩下多少个字符串？
【输入格式】
第一行一个整数T代表数据组数。
对于每组数据，第一行一个整数N代表字符串个数。
接下来N行每行一个字符串。
【输出格式】
对于每组数据，一行一个整数代表答案。
【样例输入】
2
5
esprit
god
redotopc
odcpoter
dog
14
rats
live
stressed
to
act
as
star
desserts
of
evil
cat
sa
fo
ot
【样例输出】
3
0
【样例解释】
无。
【数据范围与规定】
40%的数据，字符串长度不超过8。
对于100%的数据，1 ≤ T≤ 11，字符串长度不超过50，1 ≤ N ≤ 50。
思路：很容易证明：将这个字符串分成两个字符+两个字符+……，两个字符为一组，将一组作为基础，每组可以出现在任何位置，且每组的两个字符可以互换。那么直接排序每组，每组内再排序，就行。要注意：字符串的长度为奇数时，最后一组的第二个设为0。
#include <algorithm> #include <iostream> #include <vector> #include <cstdio> #include <string> #include <set> using namespace std; set<string> h; string a[55]; int getMin(vector<string> words) { int n = words.size(), ans = n; h.clear(); //清空操作 for (int i = 0; i < n; i++) { int m = words[i].size(); string s = ""; for (int j = 0; j*2 < m; j++) { char x = words[i][j*2], y = words[i][j*2+1]; if (x > y) swap(x, y); a[j] = x, a[j] += y; } sort(a, a+m/2); for (int j = 0; j*2 < m; j++) s += a[j]; if (m & 1) s += words[i][m-1]; //位运算符 & //http://www.runoob.com/cplusplus/cpp-operators.html if (h.find(s) == h.end()) h.insert(s); else h.erase(s), ans -= 2; } return ans; } int main() { // freopen("kahuucino.in","r",stdin); // freopen("kahuucino.out","w",stdout); int T, n, m; char ch; string s; vector<string> w; scanf("%d", &T); while (T--) { scanf("%d%d", &n, &m); w.clear(); //初始化，将vector数组清空 for(int i = 0; i < n; i++) cin >> s, w.push_back(s); //尾部插入刚输入的字符串 s printf("%d\n", getMin(w)); //调用函数 } return 0; }
#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; struct node { int fi, se; } gg[55][55]; int judge[55], num[55], ans; int cmp(const node &a, const node &b) { if(a.fi != b.fi) return a.fi < b.fi; return a.se < b.se; } void search(int k) { int bbbb = 0; for(int i = 1; i < k; i++) if(!judge[i] && num[i] == num[k]) { int q = num[i]>>1; if((num[i] & 1) == 1) q++; for(int j = 1; j <= q; j++) { if(gg[i][j].fi != gg[k][j].fi || gg[i][j].se != gg[k][j].se) break; if(j == q) bbbb = 1; } if(bbbb) { ans -= 2; judge[i] = judge[k] = 1; return ; } } } int main() { // freopen("kahuucino.in","r",stdin); // freopen("kahuucino.out","w",stdout); int T; scanf("%d", &T); while(T--) { memset(judge, 0, sizeof(judge)); memset(gg, 0, sizeof(gg)); int n; scanf("%d", &n); ans = n; for(int i = 1; i <= n; i++) { int tot = 0; char s[55]; scanf("%s", s+1); num[i] = strlen(s+1); if((num[i] & 1) == 0) for(int j = 1; j <= num[i]; j += 2) { int x1 = s[j]-'a'+1, x2 = s[j+1]-'a'+1; gg[i][++tot].fi = min(x1,x2); gg[i][tot].se = max(x1,x2); } else { for(int j = 1; j <= num[i]-1; j += 2) { int x1 = s[j]-'a'+1, x2 = s[j+1]-'a'+1; gg[i][++tot].fi = min(x1,x2); gg[i][tot].se = max(x1,x2); } gg[i][++tot].fi = s[num[i]]-'a'+1; } sort(gg[i]+1, gg[i]+1+tot, cmp); search(i); } printf("%d\n", ans); } return 0; }
T2
麻耶
【问题描述】
油库里是幻想乡特有的一种生物。每只油库里都有一个战斗力值和一个能量值。当两只油库里战斗时，总是战斗力值高的一位获胜。获胜者的战斗力值将变
成(自己的原战斗力值-对手的战斗力值+对手的能量值)。败者将死去。若两者战斗力值一样，则同归于尽。（这句漏下了qwq）
思考熊发现了很多油库里，他想知道通过互相战斗之后油库里中战斗力值+能量值最高的一个可能到达多少。你能帮他们求出来吗？（假设除了考察的那只
油库里之外，其他油库里之间不会发生战斗）
【输入格式】
第一行是一个整数N，代表当前有多少油库里。
接下来的N行， 每一行有两个整数u，v， 代表这只油库里的战斗力值和能量值。
【输出格式】
输出一个整数，代表油库里中战斗力值+能量值最高的一个能达到多少。
【样例输入】
2
1 2
2 1
【样例输出】
4
【样例解释】
无。
【数据规模与约定】
| 数据点编号 | N = | 数据点编号 | N = |
| 1 | 2 | 6 | 14989 |
| 2 | 984 | 7 | 21726 |
| 3 | 6168 | 8 | 100000 |
| 4 | 10470 | 9 | 100000 |
| 5 | 19168 | 10 | 100000 |
思路：简单贪心。将每只油库里按战斗力从大到小排序，枚举。每枚举到一只油库里进行三个判断：
1、打这只油库里。
2、不打这只油库里。
3、从这只油库里重新开始。
这里解释一下第三个判断。如果之前的油库里打到当前这只油库里，并且如果打这只或不打这只的战斗力+能量还没有直接选当前这只油库里的战斗力+能量大的话，选当前这只。
#include<algorithm> #include<cstdio> #define N 100005 using namespace std; int n; int x[N], y[N]; int sum[N]; int ans[N]; int main() { freopen("zyougamaya.in","r",stdin); freopen("zyougamaya.out","w",stdout); int maxn = -1; scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d%d", &x[i], &y[i]); sum[i] = y[i]-x[i]; ans[i] = x[i]+y[i]; } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(i == j) continue; ans[i] = max(ans[i], ans[i]+sum[j]); } maxn = max(maxn, ans[i]); } printf("%d", maxn); fclose(stdin); fclose(stdout); return 0; }
（dalao们就不要看我的了 捂脸）
#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #ifdef unix #define LL "%lld" #else #define LL "%I64d" #endif const int maxn = 100010; int n; struct Yukkuri { int f, e; void init() { scanf("%d%d", &f, &e); } bool operator<(const Yukkuri &a)const { if (f == a.f) return e>a.e; else return f<a.f; } } yukkuri[maxn]; int main() { // freopen("zyougamaya.in","r",stdin); // freopen("zyougamaya.out","w",stdout); scanf("%d",&n); int cnt=0; long long ans=0; for (int a=1; a<=n; a++) { yukkuri[++cnt].init(); ans=max(ans,(long long)yukkuri[cnt].f+yukkuri[cnt].e); } sort(yukkuri+1,yukkuri+cnt+1); long long sum=0; for (int a=1; a<=cnt;) if (a==1) { int b=a; while (b<=cnt && yukkuri[b].f==yukkuri[a].f) sum+=yukkuri[b].e-yukkuri[b].f,b++; a=b; } else { ans=max(ans,sum+yukkuri[a].f+yukkuri[a].e); if (yukkuri[a].f<yukkuri[a].e) sum+=yukkuri[a].e-yukkuri[a].f; a++; } printf(LL "\n",ans); return 0; }
#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; struct node{ long long fight,power,give,sum; }gg[100005]; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int cmp(const node&a,const node&b) { if(a.fight>b.fight)return true; else if(a.fight<b.fight)return false; if(a.fight==b.fight&&a.power>b.power)return true; else return false; } int main() { freopen("zyougamaya.in","r",stdin); freopen("zyougamaya.out","w",stdout); int n=read(); for(int i=1;i<=n;i++) { scanf("%I64d%I64d",&gg[i].fight,&gg[i].power); gg[i].give=gg[i].power-gg[i].fight; gg[i].sum=gg[i].power+gg[i].fight; } sort(gg+1,gg+n+1,cmp); for(int i=2;i<=n;i++) if(gg[i].fight!=gg[i-1].fight&&gg[i-1].fight+gg[i].give+gg[i-1].power>gg[i-1].sum&&gg[i-1].fight+gg[i].give+gg[i-1].power>gg[i].sum) { gg[i].fight=gg[i-1].fight+gg[i].give; gg[i].power=gg[i-1].power; gg[i].give=gg[i].power-gg[i].fight; gg[i].sum=gg[i].power+gg[i].fight; } else if(gg[i-1].sum>gg[i].sum||(gg[i-1].sum==gg[i].sum&&gg[i-1].power>gg[i].power)) { gg[i].fight=gg[i-1].fight; gg[i].power=gg[i-1].power; gg[i].give=gg[i].power-gg[i].fight; gg[i].sum=gg[i].power+gg[i].fight; } printf("%I64d",gg[n].sum); return 0; }
T1
惠
【问题描述】
现在你要实现一个文件系统，支持以下操作
cd Directory_Name
如果当前路径下有名为 Directory_Name 的文件夹，则进入该文件夹所对应的路径，否则输出“No such directory!” 。
cd ..
如果当前路径存在父路径， 则返回父路径， 否则输出 “No parent directory!” 。
touch File_Name
如果当前目录下存在名为 File_Name 的文件则输出“File already exists!” ，否则创建这样一个文件。
rm File_Name
如果当前目录下存在名为 File_Name 的文件则删除它，否则输出“No suchfile!” 。
mkdir Directory_Nam e
如果在当前路径下存在名为 Directory_Name 的文件夹，则输出“Directoryalready exists!” ，否则创建这样一个文件夹（当前路径不变） 。
rmdir Directory_Name
如果在当前路径下存在名为 Directory_Name 的文件夹，则删除之，否则输出“No such directory!” 。
ls
列出当前路径下所有的文件和文件夹，每一项占一行，按创建的先后顺序给出。采用以下形式输：
“Item_Name Type” （Type 为 <D>（文件夹）或<F>（文件））
注意：同一路径下文件与文件夹可以同名，但同一路径下文件与文件、文件夹与文件夹不能同名。
初始时当前路径处于根路径下，无父路径。
【输入格式】
第一行为Q，表示有Q个操作。
接下来是Q行，每行输入为以上描述的操作之一。
【输出格式】
输出答案。
【样例输入】
3
mkdir standy
touch totalfrank
ls
【样例输出】
standy <D>
totalfrank <F>
【样例解释】
无。
【数据规模与约定】
对于100%的数据，1 ≤ Q ≤ 100，所有文件名字长度不超过200且均为小写字母。
思路：炒鸡大模拟啊。。。
（因为标程太长（200多行呢qwq）所以我选择只把dalao的程序拿上来 不要说我懒 我只是特别懒而已 哈哈）
我是不会告诉你们我没有看懂题目滴。。。
#include<map> #include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int tot=1,fa[3005],now=1,judge[3005]; string que[3005]; void touch() { string s2; cin>>s2; for(int i = 1; i <= tot; i++) if(que[i]==s2 && fa[i]==now && judge[i]==1) { printf("File already exists!\n"); return ; } fa[++tot] = now; que[tot] = s2; judge[tot] = 1; } void mkdir() { string s2; cin>>s2; for(int i = 1; i <= tot; i++) if(que[i] == s2 && fa[i]==now && judge[i]==2) { printf("Directory already exists!\n"); return ; } fa[++tot] = now; que[tot] = s2; judge[tot] = 2; } void rmdir() { string s2; cin>>s2; for(int i = 1; i <= tot; i++) if(que[i]==s2 && fa[i]==now && judge[i]==2) { fa[i] = -1; return ; } printf("No such directory!\n"); } void rm() { string s2; cin>>s2; for(int i = 1; i <= tot; i++) if(que[i]==s2 && fa[i]==now && judge[i]==1) fa[i]=-1;return ; printf("No such file!\n"); } void sd() { string s2; cin>>s2; if(s2[0] == '.') { if(fa[now]) { now = fa[now]; return ; } else { printf("No parent directory!\n");return ; } } for(int i = 1; i <= tot; i++) if(que[i]==s2 && fa[i]==now && judge[i]==2) { now = i; return ; } printf("No such directory!\n"); } void ls() { for(int i = 1; i <= tot; i++) if(fa[i]==now) { cout<<que[i]; if(judge[i] == 1) printf(" <F>\n"); else printf(" <D>\n"); } } int main() { // freopen("nacumegu.in","r",stdin); // freopen("nacumegu.out","w",stdout); int q; scanf("%d", &q); judge[now] = 2; while(q--) { string s1; cin>>s1; int len = s1.size(); if(len == 5) { if(s1[len-1] == 'h') touch(); else if(s1[0]=='m') mkdir(); else rmdir(); } else { if(s1[len-1]=='s') ls(); else if(s1[len-1]=='m') rm(); else sd(); } } return 0; }
PS：某些人不要在下边乱评论了。。。
