[关闭]
@Asuna 2016-10-28T15:24:27.000000Z 字数 8033 阅读 815

题目1：Hometask

题意：字符串给一串母串，给n个子串，每个子串两个字母而且字母不重复，问要让每个子串正拟序都不在母串中出现需要在母串中删除几个字符。

题解：每读入一个子串就在母串中进行匹配，sum1和sum2分别代表子串中第一个和第二个字母出现的次数（可能有aaaabbbb这种串）然后每次取min加到ans上就可以了。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cmath>
  5. #include<algorithm>
  6. using namespace std;
  7. string s,c;
  8. int l,k,ans,sum1,sum2,sum;
  9. int main()
  10. {
  11.     cin>>s;
  12.     cin>>k;
  13.     l=s.size();
  14.     while(k>0)
  15.     {
  16.         cin>>c;
  17.         sum1=0;
  18.         sum2=0;
  19.         for(int i=0; i<l; i++)
  20.         {
  21.             if (s[i]==c[0]) sum1++;
  22.             else
  23.             if(s[i]==c[1]) sum2++;
  24.             else
  25.             {
  26.                 cout<<sum1<<endl;
  27.                 cout<<sum2<<endl;
  28.                 sum=min(sum1,sum2);
  29.                 ans+=sum;
  30.                 sum1=0;
  31.                 sum2=0;
  32.             }
  33.             sum=min(sum1,sum2);
  34.         }
  35.         ans+=sum;
  36.         k--;
  37.     }
  38.     cout<<ans<<endl;
  39.     return 0;
  40. }

题目2：Colliders

题意：有n个电子碰撞机，编号为1~n，初始状态所有的碰撞机都没有激活。然后需要你编写程序对下面的m次操作进行判断。’+’操作代表激活，’-’操作代表关闭激活，后面跟的数字就是操作的机器号。
    1.当操作为’+’时：
        1) 当i号机器已经激活时，则输出 Already on
        2) 当i号机器没有激活时，则如果有一个已经激活的j号机器，并且i与j不互质的话即gcd(i,j)!=1时，那么提示 Conflict with j。
        3) 否则机器正常激活，输出Success
    2.当操作为’-’时：
        1) 当i号机器已经激活时，则关闭激活成功，输出Success
        2) 当i号机器没有激活时，则不需要关闭，则输出Already off

题解：考虑到时间复杂度，这道题必须控制在nlogn了吧。。。然后就是考虑到n<=10^5，我们可以用一个筛法筛出10^5以内的数的质因数作为预处理。然后开一个f数组保存n的质因数，w数组表示一个数x的质因数（起指向作用），之后对于每一个操作，假设是“＋”，读入的是x，我们就处理出x的质因数有哪些，然后判断这些质因数是否已经出现，出现的话就输出Conflict With w数组指向的那个数，否则就把x加入进来并且把它的所有质因数都打上标记。假设是“－”，读入的是y，我们就把和y有关的质因数去掉（和y有关的w清零）。这样我们可以说严格控制了时间复杂度（真的严格么。。。。whatever反正本萌妹没t）。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cmath>
  5. #include<algorithm>
  6. using namespace std;
  7. int p[100005],w[100005],nfp[100005],f[100005][25],sum,x,k,j,n,m,y;
  8. char c;
  9. bool a[100005],bo[100005];
  11. bool cprime(int x)
  12. {
  13.     for (int i=2; i*i<=x; i++)
  14.         if (x%i==0) return false;
  15.     return true;
  16. }
  18. int main()
  19. {
  20.     int i;
  21.     sum=0;
  22.     memset(bo,false,sizeof(bo));
  23.     for (int i=2; i<=100000; i++)
  24.         if (cprime(i))
  25.         {
  26.             sum++;
  27.             p[sum]=i;
  28.             bo[i]=true;
  29.         }
  30.     for (int i=2; i<=100000; i++)
  31.     {
  32.         k=i;
  33.         j=1;
  34.         while (p[j]*p[j]<=k)
  35.         {
  36.             // cout<<p[j]<<" !";
  37.             if (k%p[j]==0)
  38.             {
  39.                 nfp[i]++;
  40.                 f[i][nfp[i]]=p[j];
  41.                 while (k%p[j]==0) k/=p[j];
  42.             }
  43.             j++;
  44.         }
  45.         if (bo[k])
  46.         {
  47.             // cout<<f[i][nfp[i]]<<endl;
  48.             nfp[i]++;
  49.             f[i][nfp[i]]=k;
  50.         }
  51.     }
  52.     cin>>n>>m;
  53.     //for (int i=1; i<=10000; i++)
  54.     //    cout<<N[i]<<" ";
  55.     memset(a,false,sizeof(a));
  56.     while (m>0)
  57.     {
  58.         cin>>c;
  59.         cin>>x;
  60.         if (c=='+')
  61.         {
  62.             if (a[x]) cout<<"Already on"<<endl;
  63.             else
  64.             {
  65.                 for (i=1; i<=nfp[x]; i++)
  66.                 {
  67.                     //cout<<w[f[x][i]]<<endl;
  68.                     if (w[f[x][i]])
  69.                     {
  70.                        // cout<<i<<"!!!"<<endl;
  71.                         break;
  72.                     }
  73.                     else
  74.                     {
  75.                        // cout<<i<<"!!!!"<<endl;
  76.                     }
  77.                 //cout<<y<<endl;
  79.                 }
  80.                 if (i<=nfp[x]) cout<<"Conflict with "<<w[f[x][i]]<<endl;
  81.                     else
  82.                     {
  83.                         cout<<"Success"<<endl;
  84.                         a[x]=true;
  85.                         for (int i=1; i<=nfp[x]; i++) w[f[x][i]]=x;
  86.                     }
  87.                 //y=1;
  88.             }
  89.         }
  90.         else
  91.         {
  92.             if (!a[x]) cout<<"Already off"<<endl;
  93.             else
  94.             {
  95.                 cout<<"Success"<<endl;
  96.                 for (int i=1; i<=nfp[x]; i++) w[f[x][i]]=0;
  97.             }
  98.             a[x]=false;
  99.         }
  100.         m--;
  101.     }
  102.     return 0;
  103. }

题目3:不会做！！！！

题目4:I_love_%username%

题意：判断下一个数是否位于之前的最大最小值之外.

题解：维护一个max和一个min，之后每读入就判断并改变范围。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cmath>
  5. using namespace std;
  6. int a[1005],n,maxx,minn,sum;
  7. int main()
  8. {
  9.     cin>>n;
  10.     cin>>a[1];
  11.     maxx=a[1];
  12.     minn=a[1];
  13.     for (int i=2; i<=n; i++)
  14.     {
  15.         cin>>a[i];
  16.         if (a[i]>maxx)
  17.         {
  18.             maxx=a[i];
  19.             sum++;
  20.         }
  21.         if (a[i]<minn)
  22.         {
  23.             minn=a[i];
  24.             sum++;
  25.         }
  27.     }
  28.     cout<<sum<<endl;
  29.     return 0;
  30. }

题目5:Combination

题意：给你n张牌，每张牌有a[i]、b[i]，分别表示可以获得的分数和可以获得的取牌次数，问在一开始只能取一次的情况下能获得的最大分数是多少。

题解：取牌越多分一定越大，先按b从大到小排，若b一样则a大的先排。

参考代码：

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<algorithm>
  7. using namespace std;
  8. struct node
  9. {
  10.     int a,b;
  11. }f[10005];
  12. int a[10005],n,ans,sum;
  13. bool cmp(node x,node y)
  14. {
  15.     if(x.b!=y.b) return x.b>y.b;
  16.     else return x.a>y.a;
  17. }
  18. int main()
  19. {
  20.     cin>>n;
  21.     for (int i=1; i<=n; i++)
  22.         cin>>f[i].a>>f[i].b;
  23.     sort(f+1,f+n+1,cmp);
  24.     ans=f[1].a;
  25.     sum=f[1].b;
  26.     for (int i=2; i<=n; i++)
  27.     {
  28.         if (sum==0) break;
  29.         ans+=f[i].a;
  30.         sum+=f[i].b-1;
  31.     }
  32.     cout<<ans<<endl;
  33.     return 0;
  34. }

题目6:Message

题意：给两串字符，去第一个字符串的某一子串，经过若干次变换之后，变成子串二。允许的变换是：从任意一个末尾删去、或增加一个字符，置换一个字符。设计最优方案，求出最少的变换次数。

题解：似乎。。直接暴力解决就行了呢。。

参考代码：

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdlib>
  4. #include<algorithm>
  5. #include<cmath>
  6. #include<cstdio>
  7. using namespace std;
  8. string s1,s2;
  9. int l,l1,l2,l3,sum,ans=10000000,j,k;
  10. int main()
  11. {
  12.     cin>>s1>>s2;
  13.     l1=s1.size();
  14.     l2=s2.size();
  15.     l=l2;
  16.     if (l1<l2)
  17.     {
  18.         swap(s1,s2);
  19.         swap(l1,l2);
  20.     }
  21.     for (int i=1; i<l2; i++)
  22.     {
  23.         sum=0;
  24.         k=i;
  25.         j=0;
  26.         while((k<l2) && (j<l1))
  27.         {
  28.             if (s2[k]==s1[j]) sum++;
  29.             k++;
  30.             j++;
  31.         }
  32.         //cout<<sum<<" !!!"<<endl;
  33.         ans=min(ans,l-sum);
  34.         //cout<<ans<<" !!!"<<endl;
  35.     }
  36.     for (int i=0; i<l1; i++)
  37.     {
  38.         sum=0;
  39.         k=i;
  40.         j=0;
  41.         while((j<l2) && (k<l1))
  42.         {
  43.             if (s2[j]==s1[k]) sum++;
  44.             k++;
  45.             j++;
  46.         }
  47.         //cout<<sum<<" !!!!!"<<endl;
  48.         ans=min(ans,l-sum);
  49.         //cout<<ans<<" !!!!"<<endl;
  50.     }
  51.     cout<<ans<<endl;
  52.     return 0;
  53. }

题目7:Suspects

题意：给你n表示嫌疑人说的话，+i表示第i个人说i是犯人，-i表示第i个人说i不是犯人。m表示这n个人中有m个人说真话。现在让你判断每个人说的是真话还是假话，或者不确定。

题解：我们知道当一个人说的话和另外超过n-m个人说的话发生冲突的时候，这个人说的一定是假话（因为要有m个人说真话），而当一个人说的话的相反一定是假话的时候，这个人说的话就一定是真话，剩下的都是不确定的。问题就剩下如何判断一个人说的话有多少和他冲突。我们假设这个人指认了第i个人，那么说第i个人不是犯人的人和说别人是犯人的人就和他发生了冲突（因为只有一个犯人）。假设这个人为第i个人开脱了，那么说第i个人是犯人的人就和他冲突了。因此我们只需要多开几个数组求出每一个人和他冲突的话的个数就可以得出哪些话是必假的，从而推出哪些话是必真的。为了防止复杂度达到n^2，我们要用O1复杂度算出第i个人的冲突数，所以我们要预处理出共有多少人指认了别人，设为kk，那么说别人是犯人的个数就是kk－说第i个人是犯人的个数。至此就求出了冲突数。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<cstring>
  5. #include<cmath>
  6. using namespace std;
  7. int a[100005],b[100005],c[100005],d[100005],e[100005],n,m,sum,sum1,t;
  8. int main()
  9. {
  10.     cin>>n>>m;
  11.     for (int i=1; i<=n; i++)
  12.     {
  13.         cin>>a[i];
  14.         if (a[i]>0) b[a[i]]++;
  15.         else
  16.         {
  17.             c[abs(a[i])]++;
  18.             sum++;
  19.         }
  20.     }
  21.     for (int i=1; i<=n; i++)
  22.     {
  23.         sum1=b[i]+sum-c[i];
  24.         if (sum1==m)
  25.         {
  26.             e[t]=i;
  27.             d[i]=1;
  28.             t++;
  29.         }
  30.     }
  31.    // cout<<t<<endl;
  32.     if (t==1)
  33.     {
  34.         for (int i=1; i<=n; i++)
  35.         {
  36.             if (a[i]>0)
  37.             {
  38.                 if (d[a[i]]) cout<<"Truth"<<endl;
  39.                 else cout<<"Lie"<<endl;
  40.             }
  41.             else
  42.             {
  43.                 if (d[abs(a[i])]) cout<<"Lie"<<endl;
  44.                 else cout<<"Truth"<<endl;
  45.             }
  46.         }
  47.     }
  48.     else
  49.     {
  50.         for (int i=1; i<=n; i++)
  51.         {
  52.             if (a[i]>0)
  53.             {
  54.                 if (d[a[i]]) cout<<"Not Defined"<<endl;
  55.                 else cout<<"Lie"<<endl;
  56.             }
  57.             else
  58.             {
  59.                 if (d[abs(a[i])]) cout<<"Not Defined"<<endl;
  60.                 else cout<<"Truth"<<endl;
  61.             }
  62.         }
  63.     }
  64.     return 0;
  65. }

题目8：不会做！！！！

题目9:Game Outcome

题意：矩形列的和大于行的和就是成功的，判断有多少个数成功了。

题解：暴力枚举每个数。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. using namespace std;
  7. int a[35][35],n,ans,sum1,sum2,b[35][35],c[35][35];
  8. int main()
  9. {
  10.     cin>>n;
  11.     for (int i=1; i<=n; i++)
  12.         for (int j=1; j<=n; j++)
  13.             cin>>a[i][j];
  14.     for (int i=1; i<=n; i++)
  15.         for (int j=1; j<=n; j++)
  16.         {
  17.             for (int k=1; k<=n; k++) b[i][j]+=a[i][k];
  18.             //cout<<b[i][j]<<" !!!"<<endl;
  19.             for (int p=1; p<=n; p++) c[i][j]+=a[p][j];
  20.             //cout<<b[i][j]<<" !!!!"<<endl;
  21.             if (b[i][j]<c[i][j]) ans++;
  22.         }
  23.     cout<<ans<<endl;
  24.     return 0;
  25. }

题目10:Trace

**题意：**n个同心圆有不同半径，两个相邻的圆之间颜色要不同，只有两种颜色红和蓝，问最后涂红色的面积。

题解：按半径排序，把能多涂一个的用红的涂，剩下的蓝。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. int a[105],n,sum;
  7. double ans;
  8. bool bo=true;
  9. bool cmp(int a,int b)
  10. {
  11.     return a>b;
  12. }
  13. int main()
  14. {
  15.     cin>>n;
  16.     for (int i=1; i<=n; i++)
  17.         cin>>a[i];
  18.     sort(a+1,a+n+1,cmp);
  19.     for (int i=1; i<=n; i++)
  20.     {
  21.         if (bo==true)
  22.         {
  23.             sum+=a[i]*a[i];
  24.             bo=false;
  25.         }
  26.         else
  27.         {
  28.             sum-=a[i]*a[i];
  29.             bo=true;
  30.         }
  31.     }
  32.     ans=sum*3.141592653589793;
  33.     cout<<ans<<endl;
  34.     return 0;
  35. }

题目11:Next Round

题意：前k大的数有几个（不包含0）

题解：不知该说些什么。

参考代码：

  1. #include<iostream>
  2. using namespace std;
  3. int a[105],n,k,ans;
  4. int main()
  5. {
  6.     cin>>n>>k;
  7.     for (int i=1; i<=n; i++)
  8.         cin>>a[i];
  9.     for (int i=1; i<=n; i++)
  10.         if (a[i]>=a[k] && a[i]!=0)
  11.             ans++;
  12.     cout<<ans<<endl;
  13.     return 0;
  14. }

题目12:Taxi

题意：有n组人，每组都是1到4人，准备做出租车去参加Party。一个出租车只能坐4个人，每个组的人不能拆分，求需要出租车的数量。

题解：记录每种一组人数的个数，4个人一组的就直接一辆了。分类讨论在于1人一组和3人一组的个数谁大，如果3人一组的个数多，就拿一人的都填上，然后就需要3人一组的车数，两人一组的就2组一辆车。如果一个人一组的组数多，就先把3人一组的填满，然后再拿1人一组的去补二人一组的。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. using namespace std;
  6. int n,ans,a[100005],b[11];
  7. int main()
  8. {
  9.     cin>>n;
  10.     memset(b,0,sizeof(b));
  11.     for (int i=1; i<=n; i++)
  12.     {
  13.         cin>>a[i];
  14.         b[a[i]]++;
  15.     }
  16.     ans=b[4]+b[3]+b[2]/2;
  17.     if (b[1]>b[3]) b[1]-=b[3];
  18.     else b[1]=0;
  19.     b[2]=b[2]%2;
  20.     if (b[2]==1)
  21.     {
  22.         ans++;
  23.         if (b[1]>2) b[1]-=2;
  24.         else b[1]=0;
  25.     }
  26.     ans+=b[1]/4;
  27.     if (b[1]%4!=0) ans++;
  28.     cout<<ans<<endl;
  29.     return 0;
  30. }

题目13:Cd and pwd commands

题意：模拟目录？题目中总共有三种情况:以"/"开头是指新建一个根目录,以前清空就行了,".."是返回上一层的文件夹,"单词开头"就是在停在的文件夹处建立这个单词所描述的文件夹。

题解：按照题目要求来进行字符串操作就好了。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cmath>
  5. using namespace std;
  6. string s,ans,p,s1;
  7. int n,k,t;
  8. int main()
  9. {
  10.     ans="/";
  11.     cin>>n;
  12.     for (int i=1; i<=n; i++)
  13.     {
  14.         cin>>s;
  15.         if (s=="cd")
  16.         {
  17.             cin>>s1;
  18.             s1+='/';
  19.             //cout<<s1<<endl;
  20.             for (int j=0; j<s1.length(); j++)
  21.             {
  22.                 p+=s1[j];
  23.                 if(s1[j]=='/')
  24.                 {
  25.                     if(p=="/") ans=p;
  26.                     else if (p=="../")
  27.                     {
  28.                         t=1;
  29.                         k=ans.size()-1;
  30.                         while (k>0)
  31.                         {
  32.                             if (ans[k-1]=='/') break;
  33.                             k--;
  34.                             t++;
  35.                         }
  36.                        // cout<<t<<endl;
  37.                         ans.erase(ans.size()-t,t);
  38.                     }
  39.                     else ans+=p;
  40.                     p="";
  41.                 }
  42.             }
  43.         }
  44.         if (s=="pwd")
  45.         {
  46.             cout<<ans<<endl;
  47.         }
  49.     }
  50.     return 0;
  51. }

题目14:Ice Sculptures

题意：有n个冰雕等距地站成一个圈，每个冰雕都有自己的价值，现在你可以融化掉其中的一些，但必须使得剩余的冰雕围城的是正多边形，求价值总和的最大值。

题解：我们只要计算需要剩下多少个冰雕即可，但是要注意的是因为要组成多边形，所以最小一定是三角形，所以只能去掉n／3个冰雕最多。然后就是暴力枚举每一种情况求最大值了。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. using namespace std;
  7. int a[20005],ans,n,sum;
  8. int main()
  9. {
  10.     cin>>n;
  11.     for (int i=1; i<=n; i++)
  12.     {
  13.         cin>>a[i];
  14.         ans+=a[i];
  15.     }
  16.     for (int i=2; i<=n/3; i++)
  17.     {
  18.         if (n%i==0)
  19.         {
  20.             for (int j=1; j<=i; j++)
  21.             {
  22.                 sum=0;
  23.                 for (int k=j; k<=n; k+=i)
  24.                     sum+=a[k];
  25.                 if (sum>ans) ans=sum;
  26.             }
  27.         }
  28.     }
  29.     cout<<ans<<endl;
  30.     return 0;
  31. }

题目15:不会做！！！！

祝各菊苣校赛AK...

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注