T1
【题目描述】
给你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
#include <cstdio> #include <cstring> char s[51][51]; int t,n,ans,len[51]; bool vis[51][1001],del[51];inline void work(int x) {len[x]=strlen(s[x]);--len[x];//长度若是单数，那么下面枚举到最后时会出现vis[负数]=true for(int i=0;i<len[x];i+=2)vis[x][s[x][i]-'a'+s[x][i+1]-'a']=true;++len[x]; }inline bool judge(int i,int j) {for(int k=0;k<1001;++k)if(vis[i][k]!=vis[j][k])return false; // printf("\n%s %s\n",s[i],s[j]);if(len[i]&1)return s[i][len[i]-1]==s[j][len[j]-1];return true; }inline void clear() {ans=0;memset(vis,false,sizeof vis);memset(del,false,sizeof del); }int main() {freopen("kahuucino.in","r",stdin);freopen("kahuucino.out","w",stdout);scanf("%d",&t);while(t--){clear();scanf("%d",&n);for(int i=1;i<=n;++i)scanf("%s",s[i]);for(int i=1;i<=n;++i)work(i);//处理每个字符串的情况 /*printf("\n");for(int i=1;i<=n;++i)printf("%d ",len[i]);printf("\n"); */for(int l,i=1;i<=n;++i){if(del[i])continue;for(int j=i+1;j<=n;++j){if(del[j]||len[i]!=len[j])continue;if(judge(i,j)){ // printf("\n%d %d\n",i,j);del[j]=true;ans+=2;break;}}}printf("%d\n",n-ans);}fclose(stdin);fclose(stdout);return 0; } /* 5 esprit god redotopc odcpoter dog样例第一组数据解释： redotopc -> cpot oder -> topcod er -> do cpoter -> odcpoter 最后剩3个 以连续两个字符为一个单位 */
/* 把字符串拆成有两个字母的组合 然后将这些组合按照字典序排起来，合到一起形成一个新的字符串 最后判断这个字符串有没有出现过 */ #include <algorithm> #include <iostream> #include <string> #include <cstdio> #include <vector> #include <set>std::set<std::string> h; std::string a[55]; int getMin(std::vector<std::string> words) {int n=words.size(),ans=n;h.clear();for(int i=0;i<n;++i){int m=words[i].size();std::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)std::swap(x,y);a[j]=x,a[j]+=y;}std::sort(a,a+m/2);for(int j=0;j*2<m;++j)s+=a[j];if(m&1)s+=words[i][m-1];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;std::string s;std::vector<std::string> w;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);w.clear();for(int i=0;i<n;++i){std::cin>>s;w.push_back(s);}printf("%d\n",getMin(w));}fclose(stdin);fclose(stdout);return 0; }
T2
麻耶
【问题描述】
油库里是幻想乡特有的一种生物。每只油库里都有一个战斗力值和一个能量值。当两只油库里战斗时，总是战斗力值高的一位获胜。获胜者的战斗力值将变成(自己的原战斗力值-对手的战斗力值+对手的能量值)。败者将死去。若两者战斗力值一样，则同归于尽。
思考熊发现了很多油库里，他想知道通过互相战斗之后油库里中战斗力值+能量值最高的一个可能到达多少。你能帮他们求出来吗？
（假设除了考察的那只油库里之外，其他油库里之间不会发生战斗）
【输入格式】
第一行是一个整数N，代表当前有多少油库里。
接下来的N行， 每一行有两个整数u,v， 代表这只油库里的战斗力值和能量值。
【输出格式】
输出一个整数，代表油库里中战斗力值+能量值最高的一个能达到多少。
【样例输入】
2
1 2
2 1
【样例输出】
4
【样例解释】
无。
不是所有油库里都要打一遍！！！
本来自信满满能拿10分……………………
正解是贪心
题意描述不清……
以为是所有油库里都要打一遍
但是实际是可以随意选着搞，想和哪个打和哪个打……
#include <algorithm> #include <complex> #include <cstdio> const int N=1e5+7; #ifdef Win32 #define LL "%I64d" #else #define LL "%lld" #endif struct node{int u,v; }peo[N]; int n; long long ans; int read() {int n=0,w=1;register char c=getchar();while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}while(c>='0'&&c<='9')n=n*10+c-'0',c=getchar();return n*w; } bool cmp(const node &a,const node &b) {if(a.u==b.u)return a.v>b.v;return a.u<b.u; } inline long long max(long long x,long long y) {return x>y?x:y;} int main() {freopen("zyougamaya.in","r",stdin);freopen("zyougamaya.out","w",stdout);n=read();for(int i=1;i<=n;++i){peo[i].u=read();peo[i].v=read();ans=max(ans,(long long)peo[i].u+peo[i].v);}std::sort(peo+1,peo+n+1,cmp);long long sum=0;for(int i=1;i<=n;++i){ans=max(ans,sum+peo[i].u+peo[i].v);if(peo[i].u<peo[i].v)sum+=peo[i].v-peo[i].u;}printf("%I64d",ans);//不能用define的LL，只能得10分 fclose(stdin);fclose(stdout);return 0; }
T3
思路：大模拟
注意细节！！！！！
#include <cstdio> #include <string> #include <cstring> #include <iostream> char cmd[20]; struct Node{int son[101],now,fa,type; //儿子有哪些，现在到了第几个儿子，父亲是谁，是文件还是文件夹(1是文件，2是文件夹) std::string s;Node(){now=0,fa=0;} }a[201];inline void del_file(int x) {a[x].fa=0;a[x].type=0;a[x].s=' '; }void del_directory(int x) {a[x].fa=0;a[x].s=' ';a[x].type=0;for(int i=1;i<=a[x].now;++i){if(a[a[x].son[i]].type==1)del_file(a[x].son[i]);else del_directory(a[x].son[i]);a[x].son[i]=0;}a[x].now=0; }int main() {freopen("nacumegu.in","r",stdin);freopen("nacumegu.out","w",stdout);int n,now=-1;//now:现在在哪个里面 scanf("%d",&n);for(int i=1;i<=n;++i){ // printf("\nGG\n");scanf("%s",cmd);switch(cmd[0]){case 'c'://转换目录 std::cin>>a[i].s;if(a[i].s[0]=='.'){//向上一级 if(a[now].fa!=0)now=a[now].fa;else printf("No parent directory!\n");}else{//向下一级 for(int j=1;j<=a[now].now;++j)if(a[a[now].son[j]].s==a[i].s&&a[a[now].son[j]].type==2){now=a[now].son[j];goto S;}printf("No such directory!\n");} // --i,--n;//没必要 continue;case 't'://新建文件 std::cin>>a[i].s;for(int j=1;j<=a[now].now;++j)if(a[a[now].son[j]].s==a[i].s&&a[a[now].son[j]].type==1){//已经有了 printf("File already exists!\n");goto S;}a[now].son[++a[now].now]=i;a[i].now=0;a[i].fa=now;a[i].type=1;continue;case 'r'://删除 std::cin>>a[i].s;if(strlen(cmd)<3){//删除文件 for(int j=1;j<=a[now].now;++j)if(a[a[now].son[j]].s==a[i].s&&a[a[now].son[j]].type==1){//有 del_file(a[now].son[j]);a[now].son[j]=0;goto S;}printf("No such file!\n");}else{//删除文件夹for(int j=1;j<=a[now].now;++j)if(a[a[now].son[j]].s==a[i].s&&a[a[now].son[j]].type==2){//有 del_directory(a[now].son[j]);a[now].son[j]=0;goto S;}printf("No such directory!\n");}goto S;case 'm'://新建文件夹 std::cin>>a[i].s;for(int j=1;j<=a[now].now;++j)if(a[a[now].son[j]].s==a[i].s&&a[a[now].son[j]].type==2){//已经有了 printf("Directory already exists!\n");goto S;}a[now].son[++a[now].now]=i;a[i].now=0;a[i].fa=now;a[i].type=2;continue;case 'l'://输出目录下的文件及文件夹 for(int j=1;j<=a[now].now;++j){if(a[a[now].son[j]].s[0]==' ')continue;std::cout<<a[a[now].son[j]].s;if(a[a[now].son[j]].type==1)printf(" <F>\n");else printf(" <D>\n");}} S: ;}fclose(stdin);fclose(stdout);return 0; }
