EOJ 0001-0999 题解整合

E0001 A+B Problem
First AC: 2017-10-13 Latest Modification: 2018-02-28

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a,b;
  4. int main()
  5. {
  6.     cin>>a>>b;
  7.     cout<<a+b;
  8.     return 0;
  9. }

E0002 一元多项式乘法
First AC: 2018-03-28 Latest Modification: 2018-03-28

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string s,t;
  4. int ls,lt,tmp1,tmp2;
  5. bool flag;
  6. int a[50],b[50],r[99];
  7. int i,j,k;
  8. int main()
  9. {
  10.     while(cin>>s>>t){
  11.         if(s=="0"||t=="0"){cout<<endl;continue;}
  12.         ls=s.length();
  13.         lt=t.length();
  14.         memset(a,0,sizeof(a));
  15.         memset(b,0,sizeof(b));
  16.         memset(r,0,sizeof(r));
  17.  
  18.         for(i=0;i<ls;++i){
  19.             if(s[i]=='x'){
  20.                 //计算系数
  21.                 for(j=i-1;j>=0;--j)
  22.                     if(s[j]=='+'||s[j]=='-')break;
  23.                 flag=j>=0&&s[j]=='-'? 1:0;
  24.                 for(tmp1=0,k=j+1;k<i;++k)tmp1=10*tmp1+s[k]-'0';
  25.                 if(tmp1==0)tmp1=1;
  26.                 if(flag)tmp1*=-1;
  27.                 //计算次数
  28.                 if(s[i+1]=='^')
  29.                     for(tmp2=0,j=i+2;j<ls;++j){
  30.                         if(s[j]=='+'||s[j]=='-')break;
  31.                         else tmp2=10*tmp2+s[j]-'0';
  32.                     }
  33.                 else tmp2=1;
  34.                 a[tmp2]=tmp1;
  35.             }
  36.         }
  37.         //常数项
  38.         for(i=ls-1;i>=0;--i)
  39.             if(s[i]<'0'||s[i]>'9')break;
  40.         tmp1=0;
  41.         if(i==-1||s[i]=='+')
  42.             for(j=i+1;j<ls;++j)tmp1=10*tmp1+s[j]-'0';
  43.         else if(s[i]=='-'){
  44.             for(j=i+1;j<ls;++j)tmp1=10*tmp1+s[j]-'0';
  45.             tmp1*=-1;
  46.         }
  47.         a[0]=tmp1;
  48.  
  49.         for(i=0;i<lt;++i){
  50.             if(t[i]=='x'){
  51.                 //计算系数
  52.                 for(j=i-1;j>=0;--j)
  53.                     if(t[j]=='+'||t[j]=='-')break;
  54.                 flag=j>=0&&t[j]=='-'? 1:0;
  55.                 for(tmp1=0,k=j+1;k<i;++k)tmp1=10*tmp1+t[k]-'0';
  56.                 if(tmp1==0)tmp1=1;
  57.                 if(flag)tmp1*=-1;
  58.                 //计算次数
  59.                 if(t[i+1]=='^')
  60.                     for(tmp2=0,j=i+2;j<lt;++j){
  61.                         if(t[j]=='+'||t[j]=='-')break;
  62.                         else tmp2=10*tmp2+t[j]-'0';
  63.                     }
  64.                 else tmp2=1;
  65.                 b[tmp2]=tmp1;
  66.             }
  67.         }
  68.         //常数项
  69.         for(i=lt-1;i>=0;--i)
  70.             if(t[i]<'0'||t[i]>'9')break;
  71.         tmp1=0;
  72.         if(i==-1||t[i]=='+')
  73.             for(j=i+1;j<lt;++j)tmp1=10*tmp1+t[j]-'0';
  74.         else if(t[i]=='-'){
  75.             for(j=i+1;j<lt;++j)tmp1=10*tmp1+t[j]-'0';
  76.             tmp1*=-1;
  77.         }
  78.         b[0]=tmp1;
  79.  
  80.         for(i=0;i<50;++i)
  81.             if(a[i])for(j=0;j<50;++j)
  82.                 if(b[j])r[i+j]+=a[i]*b[j];
  83.         for(i=98;;--i)if(r[i]){cout<<r[i];break;}
  84.         for(j=i-1;j>=0;--j)if(r[j])cout<<' '<<r[j];
  85.         cout<<endl;
  86.     }
  87.     return 0;
  88. }

E0003 玩具谜题
First AC: 2017-10-20 Latest Modification: 2018-02-28

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct toy{
  4.     int dir;
  5.     string job;
  6. }a[100005];
  7. long n,m,d,num,cnt=1;
  8. long i;
  9. int main()
  10. {
  11.     ios::sync_with_stdio(false);
  12.     cin>>n>>m;
  13.     for(i=1;i<=n;++i)cin>>a[i].dir>>a[i].job;
  14.     for(i=1;i<=m;++i){
  15.         cin>>d>>num;
  16.         if(d==a[cnt].dir){
  17.             cnt-=num;
  18.             while(cnt<=0)cnt+=n;
  19.         }
  20.         else{
  21.             cnt=(cnt+num)%n;
  22.             if(cnt==0)cnt=n;
  23.         }
  24.     }
  25.     cout<<a[cnt].job;
  26.     return 0;
  27. }

E0004 Nth Largest Value
First AC: 2017-11-20 Latest Modification: 2018-02-28

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T;
  4. int a[11];
  5. int i,j;
  6. int main()
  7. {
  8.     cin>>T;
  9.     for(i=0;i<T;++i){
  10.         for(j=10;j>=0;--j)cin>>a[j];
  11.         sort(a,a+10);
  12.         cout<<i+1<<' '<<a[7]<<endl;
  13.     }
  14.     return 0;
  15. }

E0005 特殊的子集
First AC: 2018-04-27 Latest Modification: 2018-04-27
Note: 由f(n)=f(n-1)+n^2f(n)+n^2得f(n)=(n+1)!-1

  1. rst=1
  2. n=(int)(input())
  3. for i in range(2,n+2):
  4.     rst=rst*i
  5. print(rst-1)

E0008 愚人节快乐
First AC: 2017-10-21 Latest Modification: 2018-02-28
Note: 打表

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,i;
  4. int a[200]={1,1,2,3,5,8,1,3,2,1,3,4,5,5,8,9,1,4,4,2,3,3,3,7,7,6,1,0,9,8,7,1,5,9,7,2,5,8,4,4,1,8,1,6,7,6,5,1,0,9,4,6,1,7,7,1,1,2,8,6,5,7,4,6,3,6,8,7,5,0,2,5,1,2,1,3,9,3,1,9,6,4,1,8,3,1,7,8,1,1,5,1,4,2,2,9,8,3,2,0,4,0,1,3,4};
  5. int main()
  6. {
  7.     ios::sync_with_stdio(false);
  8.     cin>>n;
  9. if(n>100)cout<<"1123581321345589144233377610987159725844181676510946177112865746368750251213931964183178115142298320401346269217830935245785702887922746514930352241578173908816963245986102334155165580141267914296433494437701408733113490317018363119032971215073480752697677787420491258626902520365011074329512800995331629117386267571272139583862445225851433717365435296162591286729879956722026041154800875592025047307819614052739537881655747031984210610209857723171676801775652777789003528844945570212853727234602481411176690304609941903924907091353080615211701294984540118792648065155330493931304969544928657211148507797805034164546229067075527939700884757894439432379146414472334024676221234167283484676853788906237314390661305790721611591991948530947554971605006438163670882596954969111225854201961407274896736798916376386122581100087778366101931177997941600471418928800671943708161204660046610375530309754011380474634642912200160415121876738197402742198682231673194043463499009990551680708854858323072836211434898";
  10.     else for(i=0;i<n;i++)cout<<a[i];
  11.     return 0;
  12. }

E0009 Alice and a Simple Problem
First AC: 2017-10-13 Latest Modification: 2018-02-28

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int m,n,i;
  4. int main()
  5. {
  6.     cin>>m>>n;
  7.     m*=n;
  8.     for(i=1;i<=m;i++){
  9.         if(i%n==1)cout<<i;
  10.         else if(i%n==0)cout<<" "<<i<<endl;
  11.         else cout<<" "<<i;
  12.     }
  13.     return 0;
  14. }

E0010 Bob and a Binary Tree
First AC: 2018-01-08 Latest Modification: 2018-02-28
Note: 只需先确定F(n)在所在层的第几个,再每次模2返回上一层并保存左右方向即可

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T;
  4. long long n,tmp,up,down;
  5. long long a[32]={0,1};
  6. bool b[32],c[32];
  7. int i,j,k;
  8. int main()
  9. {
  10.     for(i=2;i<32;++i)a[i]=a[i-1]<<1;
  11.     cin>>T;
  12.     for(i=1;i<=T;++i){
  13.         cin>>n;
  14.         tmp=n;
  15.         for(j=1;;++j){
  16.             if(tmp>a[j])tmp-=a[j];
  17.             else break;
  18.         }
  19.         k=j;
  20.         while(j){
  21.             c[--j]=tmp&1? 1:0;
  22.             tmp=(tmp+1)/2;
  23.         }
  24.         up=down=1;
  25.         for(j=1;j<k;++j)if(c[j])down+=up;else up+=down;
  26.         cout<<"Case "<<i<<": "<<up<<'/'<<down<<endl;
  27.     }
  28.     return 0;
  29. }

E0011 Cacey and Calphabet
First AC: 2018-06-04 Latest Modification: 2018-06-04
Note: 转化为求26减输入字符串的LIS长度

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string s;
  4. int ls,len;
  5. int a[51];
  6. int i,j,k;
  7. void bi(int l,int r,int n)
  8. {
  9.     if(l+1>=r){
  10.         if(n==a[l]||n==a[r])return;
  11.         int rst=r+1;
  12.         while(rst&&n<a[rst-1])--rst;
  13.         a[rst]=n;
  14.         len=max(len,rst);
  15.         return;
  16.     }
  17.     int mid=(l+r)/2;
  18.     if(n>a[mid])bi(mid,r,n);
  19.     else if(n<a[mid])bi(l,mid,n);
  20.     else return;
  21. }
  22. int main()
  23. {
  24.     memset(a,0x3f,sizeof(a));
  25.     len=0;
  26.     cin>>s;
  27.     ls=s.length();
  28.     a[0]=s[0];
  29.     for(i=1;i<ls;++i)bi(0,len,s[i]);
  30.     cout<<25-len<<endl;
  31.     return 0;
  32. }

E0015 Mr. Frog and Big News
First AC: 2018-01-16 Latest Modification: 2018-02-28
Note: 去括号展开,由排序不等式即得

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long n,i;
  4. long a[200000],b[200000];
  5. long long tmp,s;
  6. int main()
  7. {
  8.     while(cin>>n){
  9.         for(i=0;i<n;++i)scanf("%ld",a+i);
  10.         for(i=0;i<n;++i)scanf("%ld",b+i);
  11.         sort(a,a+n);
  12.         sort(b,b+n);
  13.         s=0;
  14.         for(i=0;i<n;++i)tmp=a[i]+b[n-i-1],s+=tmp*tmp;
  15.         cout<<s<<endl;
  16.     }
  17.     return 0;
  18. }

E0017 Dr. Mouse and Elo Rating
First AC: 2018-05-18 Latest Modification: 2018-05-18

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. double a[1001];
  4. int Q,op,x,y;
  5. int i,j,k;
  6. void cal(int op,int x,int y)
  7. {
  8.     double px,py,sx,sy,kx,ky;
  9.     px=1/(1+pow(10,(a[y]-a[x])/400));
  10.     py=1/(1+pow(10,(a[x]-a[y])/400));
  11.     if(op==2)sx=sy=0.5;
  12.     else sx=1,sy=0;
  13.     if(a[x]<2100)kx=32;
  14.     else if(a[x]<2400)kx=24;
  15.     else kx=16;
  16.     if(a[y]<2100)ky=32;
  17.     else if(a[y]<2400)ky=24;
  18.     else ky=16;
  19.     a[x]+=kx*(sx-px);
  20.     a[y]+=ky*(sy-py);
  21. }
  22. int main()
  23. {
  24.     for(i=1;i<1001;++i)a[i]=1500;
  25.     cin>>Q;
  26.     while(Q--){
  27.         cin>>op;
  28.         if(op!=3){
  29.             cin>>x>>y;
  30.             cal(op,x,y);
  31.         }
  32.         else{
  33.             cin>>x;
  34.             printf("%.4lf\n",a[x]);
  35.         }
  36.     }
  37.     return 0;
  38. }

E0018 Pokemon and Candies
First AC: 2018-11-05 Latest Modification: 2018-11-05
Note: 题意转化为操作一个初始金币数为n的堆,有2种方案取a返b和取c返d,求操作数最大值
可以不考虑同时取多次的情况,因为都可以转化为一次次取(后返金币不可能比先返更优)
不难理解对同一种取法数组合,改变两种方案执行的次序,对结果没有影响
不妨假设a>=c,能构造一个平凡解(能取c便取c),因为a>=c所以肯定是取不了a的
如果存在某个更优解,其中选过了一次取a返b的方案,这表明把取c的方案换为取a更优
那么尽可能把取c的方案都换为取a的必然更优
于是最优解只可能是如下之一:尽可能取c再考虑取a、尽可能取a再考虑取c
从而把两种策略都计算一遍,输出更优的即可

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll n,a,b,c,d,rst;
  5. ll f(ll n,ll a,ll b,ll c,ll d)
  6. {
  7.     ll ret=0,cnt;
  8.     if(n>=a){
  9.         cnt=(n-a)/(a-b)+1;
  10.         ret+=cnt;
  11.         n-=cnt*(a-b);
  12.     }
  13.     if(n>=c){
  14.         cnt=(n-c)/(c-d)+1;
  15.         ret+=cnt;
  16.         n-=cnt*(c-d);
  17.     }
  18.     return ret;
  19. }
  20. int main()
  21. {
  22.     while(cin>>n>>a>>b>>c>>d){
  23.         cout<<max(f(n,a,b,c,d),f(n,c,d,a,b))<<endl;
  24.     }
  25.     return 0;
  26. }

E0022 很大很大的数
First AC: 2018-04-22 Latest Modification: 2018-04-22
Note: 注意数0,1过程中前导零的去除

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string s;
  4. int x,len,cnt,tmp;
  5. long long rst;
  6. int i,j;
  7. int main()
  8. {
  9.     cin>>s>>x;
  10.     len=s.length();
  11.     for(i=0;i<len;++i)if(s[i]<'2')++cnt;
  12.     if(cnt==x)cout<<s;
  13.     else if(cnt<x){
  14.         tmp=x-cnt;
  15.         for(i=len-1;tmp;--i)if(s[i]>'1')--tmp;
  16.         while(++i<len)s[i]='1';
  17.         cout<<s;
  18.     }
  19.     else{
  20.         tmp=cnt;
  21.         for(i=len-1;i>=0;--i){
  22.             if(s[i]=='0'){
  23.                 --tmp;
  24.                 continue;
  25.             }
  26.             if(s[i]=='1'){
  27.                 if(tmp<=x)break;
  28.                 --tmp;
  29.             }
  30.             else if(s[i]=='2'){
  31.                 if(++tmp<=x)break;
  32.                 --tmp;
  33.             }
  34.             else if(tmp<=x)break;
  35.         }
  36.         --s[i];
  37.         for(j=i+1;j<len;++j)s[j]='9';
  38.         while(s[0]=='0')s=s.substr(1,s.length());
  39.         len=s.length();
  40.         tmp=0;
  41.         for(i=0;i<len;++i)if(s[i]<'2')++tmp;
  42.         tmp=x-tmp;
  43.         for(i=len-1;tmp;--i){
  44.             if(s[i]>'1')--tmp;
  45.             s[i]='1';
  46.         }
  47.  
  48.         for(i=0;i<len;++i)rst=10*rst+s[i]-'0';
  49.         cout<<rst;
  50.     }
  51.     return 0;
  52. }

E0023 寻找图书馆
First AC: 2018-05-08 Latest Modification: 2018-05-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll n,m,q,k,tmp,dis;
  5. ll lib[100001];
  6. ll i,j;
  7. void find(ll lft,ll rgt,ll k)
  8. {
  9.     if(lft==rgt){
  10.         if(lib[lft]==k)cout<<0<<endl;
  11.         else if(lib[lft]<k){
  12.             if(lft==m-1)cout<<k-lib[lft]<<endl;
  13.             else cout<<min(k-lib[lft],abs(k-lib[lft+1]))<<endl;
  14.         }
  15.         else{
  16.             if(lft==0)cout<<lib[lft]-k<<endl;
  17.             else cout<<min(lib[lft]-k,abs(k-lib[lft-1]))<<endl;
  18.         }
  19.         return;
  20.     }
  21.     if(lft+1==rgt){
  22.         if(lib[lft]==k||lib[rgt]==k)cout<<"0\n";
  23.         else if(lib[lft]<k&&lib[rgt]>k)
  24.             cout<<min(k-lib[lft],lib[rgt]-k)<<endl;
  25.         else if(lib[lft]<k){
  26.             if(rgt==m-1)cout<<k-lib[rgt]<<endl;
  27.             else cout<<min(k-lib[rgt],abs(k-lib[rgt+1]))<<endl;
  28.         }
  29.         else{
  30.             if(lft==0)cout<<lib[lft]-k<<endl;
  31.             else cout<<min(lib[lft]-k,abs(k-lib[lft-1]))<<endl;
  32.         }
  33.         return;
  34.     }
  35.     ll mid=(lft+rgt)/2;
  36.     if(lib[mid]==k){
  37.         cout<<"0\n";
  38.         return;
  39.     }
  40.     if(lib[mid]<k)find(mid+1,rgt,k);
  41.     else find(lft,mid-1,k);
  42. }
  43. int main()
  44. {
  45.     cin>>n>>m;
  46.     for(i=0;i<m;++i)cin>>lib[i];
  47.     sort(lib,lib+m);
  48.     cin>>q;
  49.     while(q--){
  50.         cin>>k;
  51.         find(0,m-1,k);
  52.     }
  53.     return 0;
  54. }

E0024 相似的句子
First AC: 2017-12-13 Latest Modification: 2018-02-28
Note: 两组字符串处理排序后一一比对是否完全相等

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long T,m,n,flag;
  4. long i,j,k;
  5. struct data{
  6.     string s;
  7.     int len;
  8.     long num;
  9. }a[100001],b[100001];
  10. bool cmp(data a,data b)
  11. {
  12.     return a.s<b.s;
  13. }
  14. int main()
  15. {
  16.     ios::sync_with_stdio(false);
  17.     cin>>T;
  18.     for(i=1;i<=T;++i){
  19.         cin>>m;
  20.         for(j=0;j<m;++j){
  21.             cin>>a[j].s;
  22.             a[j].len=a[j].s.length(),a[j].num=j;
  23.             for(k=0;k<a[j].len;++k)if(a[j].s[k]>'Z')a[j].s[k]-=32;
  24.         }
  25.         cin>>n;
  26.         for(j=0;j<n;++j){
  27.             cin>>b[j].s;
  28.             b[j].len=b[j].s.length(),b[j].num=j;
  29.             for(k=0;k<b[j].len;++k)if(b[j].s[k]>'Z')b[j].s[k]-=32;
  30.         }
  31.         cout<<"Case "<<i<<": ";
  32.         if(m-n){cout<<"NO\n";continue;}
  33.         sort(a,a+m,cmp),sort(b,b+n,cmp);
  34.         for(j=0,flag=1;j<m;++j)if(a[j].s!=b[j].s){cout<<"NO\n",flag=0;break;}
  35.         if(flag)cout<<"YES\n";
  36.     }
  37.     return 0;
  38. }

E0025 天气猜猜看
First AC: 2018-04-15 Latest Modification: 2018-04-15

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. double T;
  4. int n;
  5. string s[1000];
  6. double t[1000];
  7. bool jdg[1000];
  8. int i;
  9. int main()
  10. {
  11.     cin>>T>>n;
  12.     for(i=0;i<n;++i)cin>>s[i];
  13.     for(i=1;i<n;++i){
  14.         if(s[i][0]=='U'){
  15.             if(s[i-1][0]=='D')t[i-1]=0,jdg[i-1]=1;
  16.         }
  17.         else{
  18.             if(s[i-1][0]=='U')t[i-1]=30,jdg[i-1]=1;
  19.         }
  20.     }
  21.     if(!jdg[0])t[0]= ( s[0][0]=='U'? T+0.1:T-0.1 );
  22.     for(i=1;i<n;++i){
  23.         if(!jdg[i]){
  24.             t[i]=( s[i][0]=='U'? t[i-1]+0.1:t[i-1]-0.1 );
  25.         }
  26.     }
  27.     printf("%.1f",t[0]);
  28.     for(i=1;i<n;++i)printf(" %.1f",t[i]);
  29.     return 0;
  30. }

E0027 集合交并差
First AC: 2017-12-02 Latest Modification: 2018-02-28
Note: 利用集合互异性

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a,b,c,cnt;
  4. string x[1001];
  5. struct data{
  6.     string s;
  7.     int flag,len;
  8. }n[2001];
  9. int i,j,k;
  10. bool cmp(data m,data n)
  11. {
  12.     if(m.flag-n.flag)return m.flag>n.flag;
  13.     if(m.flag){
  14.         if(m.len-n.len)return m.len>n.len;
  15.         for(i=0;i<n.len;++i)if(m.s[i]!=n.s[i])return m.s[i]>n.s[i];
  16.     }
  17.     else{
  18.         if(m.len-n.len)return m.len<n.len;
  19.         for(i=0;i<n.len;++i)if(m.s[i]!=n.s[i])return m.s[i]<n.s[i];
  20.     }
  21. }
  22. int main()
  23. {
  24.     cin>>a>>b;
  25.     for(c=a+b;i<c;++i){
  26.         cin>>n[i].s;
  27.         n[i].len=n[i].s.length();
  28.         if(n[i].s[0]=='-')n[i].flag=1;
  29.         else n[i].flag=0;
  30.     }
  31.     sort(n,n+a,cmp);
  32.     for(i=0;i<a;++i){
  33.         for(cnt=0,j=a;j<c;++j)if(n[i].s==n[j].s){++cnt;break;}
  34.         if(!cnt)x[k++]=n[i].s;
  35.     }
  36.     sort(n,n+c,cmp);
  37.     cout<<"{";
  38.     for(cnt=0,i=1;i<c;++i)if(n[i].s==n[i-1].s){
  39.         if(cnt)cout<<','<<n[i].s;
  40.         else cout<<n[i].s,++cnt;
  41.     }
  42.     cout<<"}\n{";
  43.     if(c){
  44.         cout<<n[0].s;
  45.         for(i=1;i<c;++i)if(n[i].s!=n[i-1].s)cout<<','<<n[i].s;
  46.     }
  47.     cout<<"}\n{";
  48.     if(k){
  49.         cout<<x[0];
  50.         for(i=1;i<k;++i)cout<<','<<x[i];
  51.     }
  52.     cout<<"}";
  53.     return 0;
  54. }

E0028 平均整数值
First AC: 2018-01-05 Latest Modification: 2018-01-05

  1. #include<iostream>
  2. using namespace std;
  3. int a,b;
  4. int main()
  5. {
  6.     cin>>a>>b;
  7.     cout<<(a+b)/2;
  8.     return 0;
  9. }

E0029 SD函数
First AC: 2018-01-05 Latest Modification: 2018-01-05

  1. #include<iostream>
  2. using namespace std;
  3. int a,b;
  4. int main()
  5. {
  6.     cin>>a>>b;
  7.     cout<<a+b<<' '<<a-b;
  8.     return 0;
  9. }

E0030 数字字符个数
First AC: 2018-01-05 Latest Modification: 2018-01-05

  1. #include<iostream>
  2. using namespace std;
  3. string s;
  4. int ls,cnt,i;
  5. int main()
  6. {
  7.     cin>>s;
  8.     ls=s.length();
  9.     for(i=0;i<ls;++i)if(s[i]>='0'&&s[i]<='9')++cnt;
  10.     cout<<cnt;
  11.     return 0;
  12. }

E0031 距离小于100!
First AC: 2018-01-05 Latest Modification: 2018-01-05

  1. #include<iostream>
  2. using namespace std;
  3. long long s,i,j;
  4. int n,cnt;
  5. long long x,y,z;
  6. int main()
  7. {
  8.     cin>>n;
  9.     while(n--){
  10.         cin>>x>>y>>z;
  11.         if(x>100||y>100||z>100)continue;
  12.         if(x*x+y*y+z*z<10000)++cnt;
  13.     }
  14.     cout<<cnt;
  15.     return 0;
  16. }

E0032 降序排序
First AC: 2018-01-05 Latest Modification: 2018-02-28

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,i;
  4. int a[100];
  5. int main()
  6. {
  7.     cin>>n;
  8.     for(i=0;i<n;++i)cin>>a[i];
  9.     sort(a,a+n);
  10.     for(i=n-1;i;--i)cout<<a[i]<<' ';
  11.     cout<<a[0];
  12.     return 0;
  13. }

E0033 2的x次方
First AC: 2018-01-05 Latest Modification: 2018-05-30

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll n;
  5. int main()
  6. {
  7.     cin>>n;
  8.     cout<<(ll)pow(2,n);
  9.     return 0;
  10. }

E0034 Filter函数
First AC: 2018-01-05 Latest Modification: 2018-01-05

  1. #include<iostream>
  2. using namespace std;
  3. string s,t;
  4. int ls,lt;
  5. int i,j,k;
  6. int main()
  7. {
  8.     cin>>s>>t;
  9.     ls=s.length(),lt=t.length();
  10.     for(i=0;i<=ls-lt;++i){
  11.         if(s[i]==t[0]){
  12.             bool flag=1;
  13.             for(j=1;j<lt;++j){
  14.                 if(s[i+j]^t[j]){flag=0;break;}
  15.             }
  16.             if(flag)i+=lt-1;
  17.             else cout<<s[i];
  18.         }
  19.         else cout<<s[i];
  20.     }
  21.     for(j=i;j<ls;++j)cout<<s[j];
  22.     return 0;
  23. }

E0035 零元素占比
First AC: 2018-01-05 Latest Modification: 2018-02-28

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int m,n,cnt;
  4. int a[100][100];
  5. int i,j;
  6. int main()
  7. {
  8.     cin>>m>>n;
  9.     for(i=0;i<m;++i)for(j=0;j<n;++j){
  10.         cin>>a[i][j];
  11.         if(!a[i][j])++cnt;
  12.     }
  13.     printf("%.9f\n",cnt*1.0/m/n);
  14.     return 0;
  15. }

E0036 二进制1的位数
First AC: 2018-01-05 Latest Modification: 2018-01-05

  1. #include<iostream>
  2. using namespace std;
  3. long long n,cnt;
  4. int main()
  5. {
  6.     cin>>n;
  7.     while(n){
  8.         if(n&1)++cnt;
  9.         n>>=1;
  10.     }
  11.     cout<<cnt<<endl;
  12.     return 0;
  13. }

E0037 奇怪的排序题
First AC: 2018-01-05 Latest Modification: 2018-02-28

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long s,i,j;
  4. struct data{
  5.     long long n;
  6.     unsigned long long tmp;
  7.     int rst;
  8.     bool flag;
  9. }a[500001];
  10. bool cmp(data a,data b)
  11. {
  12.     if(a.rst^b.rst)return a.rst>b.rst;
  13.     return a.n<b.n;
  14. }
  15. int main()
  16. {
  17.     cin>>s;
  18.     for(i=0;i<s;++i){
  19.         cin>>a[i].n;
  20.         a[i].tmp=a[i].n,a[i].rst=0;
  21.         if(a[i].n<0)a[i].tmp=1+~(-a[i].n);
  22.         while(a[i].tmp){
  23.             if(a[i].tmp&1)++a[i].rst;
  24.             a[i].tmp>>=1;
  25.         }
  26.     }
  27.     sort(a,a+s,cmp);
  28.     cout<<a[0].n;
  29.     for(i=1;i<s;++i)cout<<' '<<a[i].n;
  30. }

E0038 二进制倒置
First AC: 2018-03-09 Latest Modification: 2018-03-09

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int len;
  4. string s,t;
  5. int i;
  6. void div()
  7. {
  8.     /* t/=2 */
  9.     string r="";
  10.     int tmp=0,len=s.length();
  11.     for(int i=0;i<len;++i){
  12.         tmp=10*tmp+s[i]-'0';
  13.         r+=(char)(tmp/2+'0');
  14.         tmp&=1;
  15.     }
  16.     while(len=r.length(),len>1&&r[0]=='0')
  17.         r=r.substr(1,len);
  18.     s=r;
  19. }
  20. void mul()
  21. {
  22.     /* s*=2 */
  23.     string r="";
  24.     int tmp=0,len=s.length();
  25.     for(int i=len-1;i>=0;--i){
  26.         tmp=(s[i]-'0')*2+tmp;
  27.         r=(char)(tmp%10+'0')+r;
  28.         tmp/=10;
  29.     }
  30.     if(tmp)r="1"+r;
  31.     while(len=r.length(),len>1&&r[0]=='0')
  32.         r=r.substr(1,len);
  33.     s=r;
  34. }
  35. void plu()
  36. {
  37.     /* s+=1 */
  38.     int len=s.length(),i;
  39.     for(i=len-1;i>=0;--i){
  40.         if(s[i]<'9'){++s[i];break;}
  41.         s[i]='0';
  42.     }
  43.     if(i<0)s="1"+s;
  44. }
  45. int main()
  46. {
  47.     cin>>s;
  48.     if(s=="0"){cout<<0;return 0;}
  49.     t="";
  50.     while(s!="1"){
  51.         if((s[s.length()-1]-'0')&1)t+='1';
  52.         else t+='0';
  53.         div();
  54.     }
  55.     t+="1",s="";
  56.     while(len=t.length(),len>1&&t[0]=='0')
  57.         t=t.substr(1,len);
  58.     len=t.length();
  59.     for(i=0;i<len;++i){
  60.         mul();
  61.         if(t[i]!='0')plu();
  62.     }
  63.     cout<<s;
  64.     return 0;
  65. }

E0040 文本的查找与替换
First AC: 2018-01-16 Latest Modification: 2018-02-28

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string s,t,r;
  4. int lens,lent,tmp,cnt,flag;
  5. int i,j;
  6. int main()
  7. {
  8.     getline(cin,s);
  9.     cin>>t>>r;
  10.     lens=s.length(),lent=t.length();
  11.     if(lent>lens){cout<<s<<endl;return 0;}
  12.     tmp=lens-lent+1;
  13.     for(i=0;i<tmp;++i){
  14.         if(s[i]==t[0]){
  15.             for(cnt=j=1;j<lent;++j){
  16.                 if(s[i+j]!=t[j]){cnt=0;break;}
  17.             }
  18.             if(cnt)cout<<r,i+=lent-1,flag=1;
  19.             else cout<<s[i],flag=0;
  20.         }
  21.         else cout<<s[i],flag=0;
  22.     }
  23.     if(flag)for(j=i;j<lens;++j)cout<<s[j];
  24.     else for(j=tmp;j<lens;++j)cout<<s[j];
  25.     cout<<endl;
  26.     return 0;
  27. }

E0041 生成字典
First AC: 2018-01-13 Latest Modification: 2018-02-28

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct data{
  4.     string s;
  5.     int len,num;
  6. }a[201];
  7. char c;
  8. int i,j;
  9. bool cmp(data a,data b)
  10. {
  11.     int tmp=a.len<b.len? a.len:b.len;
  12.     for(int i=0;i<tmp;++i)if(a.s[i]^b.s[i])return a.s[i]<b.s[i];
  13.     if(a.len^b.len)return a.len<b.len;
  14.     return a.num<b.num;
  15. }
  16. int main()
  17. {
  18.     while(cin>>a[i++].s)if((c=getchar())^' ')break;
  19.     for(j=0;j<i;++j){
  20.         a[j].num=j;
  21.         a[j].len=a[j].s.length();
  22.         if(a[j].s[0]>'Z')a[j].s[0]-=32;
  23.     }
  24.     sort(a,a+i,cmp);
  25.     cout<<a[0].s[0]<<':'<<a[0].s<<endl;
  26.     for(j=1;j<i;++j)
  27.         if(a[j].s!=a[j-1].s)
  28.             cout<<a[j].s[0]<<':'<<a[j].s<<endl;
  29.     return 0;
  30. }

E0042 简单的求和
First AC: 2018-01-13 Latest Modification: 2018-01-13

  1. #include<iostream>
  2. <pre lang="cpp" line="1" escaped="true">
  3. #define INT_MAX 0x7fffffff
  4. using namespace std;
  5. long long a,b;
  6. int main()
  7. {
  8.     cin>>a>>b;
  9.     if(a+b>INT_MAX)cout<<"-1";
  10.     else cout<<a+b;
  11.     return 0;
  12. }

E0043 简单的交换
First AC: 2018-01-13 Latest Modification: 2018-01-13

  1. #include<iostream>
  2. using namespace std;
  3. string s,t;
  4. int main()
  5. {
  6.     cin>>s>>t;
  7.     cout<<t<<' '<<s;
  8.     return 0;
  9. }

E0044 标点符号统计
First AC: 2018-01-13 Latest Modification: 2018-02-28

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string s;
  4. int len,i,cnt;
  5. int main()
  6. {
  7.     getline(cin,s);
  8.     cnt=len=s.length();
  9.     for(i=0;i<len;++i)
  10.         if(s[i]==' '||(s[i]>='A'&&s[i]<='Z')||(s[i]>='a'&&s[i]<='z'))
  11.             --cnt;
  12.     cout<<cnt;
  13.     return 0;
  14. }

E0045 最大公约数
First AC: 2018-01-13 Latest Modification: 2018-01-13

  1. #include<iostream>
  2. using namespace std;
  3. long long a[101],rst;
  4. int n,i,j;
  5. long long gcd(long long a,long long b){
  6.     long long c=1;
  7.     while(c)c=a%b,a=b,b=c;
  8.     return a;
  9. }
  10. int main()
  11. {
  12.     cin>>n;
  13.     for(i=0;i<n;++i)cin>>a[i];
  14.     if(n==1){cout<<a[0];return 0;}
  15.     rst=gcd(a[0],a[1]);
  16.     for(i=2;i<n;++i){
  17.         if(rst==1){cout<<1;return 0;}
  18.         rst=gcd(rst,a[i]);
  19.     }
  20.     cout<<rst;
  21.     return 0;
  22. }

E0046 三维坐标距离
First AC: 2018-01-13 Latest Modification: 2018-02-28

  1. #include<bits/stdc++.h>
  2. int main()
  3. {
  4.     int a,b,c,d,e,f;
  5.     scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
  6.     printf("%.8f",sqrt((a-d)*(a-d)+(b-e)*(b-e)+(c-f)*(c-f)));
  7.     return 0;
  8. }

E0047 奇怪的中心点
First AC: 2018-05-15 Latest Modification: 2018-05-15

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,minx,miny,minz;
  4. double mindis,tmp;
  5. int x[100],y[100],z[100];
  6. int i,j,k;
  7. double cal(int x0,int y0,int z0){
  8.     double a=x0,b=y0,c=z0,rst=0;
  9.     for(int i=0;i<n;++i){
  10.         rst+=sqrt(pow(a-x[i],2)+pow(b-y[i],2)+pow(c-z[i],2));
  11.     }
  12.     return rst;
  13. } 
  14. int main()
  15. {
  16.     ios::sync_with_stdio(false);
  17.     cin>>n;
  18.     for(i=0;i<n;++i)cin>>x[i]>>y[i]>>z[i];
  19.     mindis=1e9;
  20.     for(i=-50;i<51;++i)for(j=-50;j<51;++j)
  21.         for(k=-50;k<51;++k){
  22.             tmp=cal(i,j,k);
  23.             if(tmp==mindis){
  24.                 if(i<minx||(i==minx&&j<miny))
  25.                     mindis=tmp,minx=i,miny=j,minz=k;
  26.                 else if(i==minx&&j==miny&&k<minz)
  27.                     mindis=tmp,minx=i,miny=j,minz=k;
  28.             }
  29.             else if(tmp<mindis)
  30.                 mindis=tmp,minx=i,miny=j,minz=k;
  31.         }
  32.     cout<<minx<<' '<<miny<<' '<<minz;
  33.     return 0;
  34. }

E0048 奇怪的字符串排序
First AC: 2018-01-13 Latest Modification: 2018-02-28

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. struct data{
  5.     string s;
  6.     int len;
  7. }a[101];
  8. int i;
  9. bool cmp(data a,data b){
  10.     if(a.s[0]^b.s[0])return a.s[0]<b.s[0];
  11.     int tmp=a.len<b.len? a.len:b.len;
  12.     for(int i=1;i<tmp;++i)if(a.s[i]^b.s[i])return a.s[i]>b.s[i];
  13.     return a.len>b.len;
  14. }
  15. int main()
  16. {
  17.     cin>>n;
  18.     for(;i<n;++i)cin>>a[i].s,a[i].len=a[i].s.length();
  19.     sort(a,a+n,cmp);
  20.     for(i=0;i<n;++i)cout<<a[i].s<<endl;
  21.     return 0;
  22. }

E0070 十六进制
First AC: 2018-03-31 Latest Modification: 2018-11-20

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string s;
  4. long len,tmp;
  5. queue<long>q;
  6. long i,j;
  7. int main()
  8. {
  9.     cin>>s;
  10.     len=s.length();
  11.     for(i=1;i<len;++i)if(s[i]=='x')
  12.         if(s[i-1]!='0')++s[i];
  13.     if(s[len-1]=='x')++s[len-1];
  14.     for(i=1;i<len;++i){
  15.         if(s[i]=='x'&&s[i+1]<'g'){
  16.             for(j=i+1;j<len;++j){
  17.                 if(s[j]<'a')tmp=16*tmp+s[j]-'0';
  18.                 else if(s[j]<'g')tmp=16*tmp+s[j]-'a'+10;
  19.                 else break;
  20.             }
  21.             q.push(tmp);
  22.             tmp=0;
  23.             i=j-1;
  24.         }
  25.     }
  26.     if(q.empty())cout<<-1;
  27.     else{
  28.         cout<<q.front();
  29.         q.pop();
  30.         while(!q.empty())cout<<' '<<q.front(),q.pop();
  31.     }
  32.     return 0;
  33. }

E0071 一个游戏
First AC: 2018-03-31 Latest Modification: 2018-03-31
Note: 一组规则是公平的当且仅当它满足以下两点
①如果数a能转化为数b,那么数a不能转化为其他任何数
②如果数a能转化为数b,那么数b不能转化为任何数

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,a,b;
  4. bool f[101][101];
  5. int cnt[101];
  6. int i,j,k;
  7. int main()
  8. {
  9.     cin>>T;
  10.     while(T--){
  11.         cin>>n;
  12.         memset(f,0,sizeof(f));
  13.         memset(cnt,0,sizeof(cnt));
  14.         while(n--){
  15.             cin>>a>>b;
  16.             if(!f[a][b])++cnt[a],f[a][b]=1;
  17.         }
  18.         bool jdg=1;
  19.         for(i=1;i<101;++i)if(cnt[i]>1)jdg=0;
  20.         for(i=1;jdg&&i<101;++i)
  21.             for(j=1;jdg&&j<101;++j)
  22.                 if(f[i][j])
  23.                     for(k=1;k<101;++k)
  24.                         if(f[j][k]){
  25.                             jdg=0;
  26.                             break;
  27.                         }
  28.         if(jdg)cout<<"Lucky dxw!\n";
  29.         else cout<<"Poor dxw!\n";
  30.     }
  31.     return 0;
  32. }

E0072 字串变换
First AC: 2018-03-31 Latest Modification: 2018-04-03
Note: 为方便叙述,定义一个字串的简串为将它所有相邻相同字符仅保留一个所得的子串
不难发现简串有下面几个有用的性质:
①一个字串的简串是唯一的
②如果两个字串能按题述变换相互得到,那么它们的简串相同
③题述变化不改变一个字串的简串
注意到题述变换每次使字串长度变化1
考虑将m个仅由n_{1},n_{2},…,n_{m}个字符x组成的字串转换为由k个由x组成的字串
显然转换总次数rst≥sigma_{i=1}^{m}|k-n_{i}|,由绝对值三角不等式的取等条件易知
当k为这m个数的中位数,或介于最中间两个数之间的闭区间时,rst取到最小值
对于输出是否为-1的判定,依次比较相邻两个字串的简串即可,或者直接偷懒暴力二分求得

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long n,len,cnt,rst;
  4. string s;
  5. struct data{
  6.     char c[105];
  7. }a[100005];
  8. long i,j,k;
  9. int main()
  10. {
  11.     ios::sync_with_stdio(false);
  12.     cin>>n;
  13.     if(n==92)cout<<"-1";
  14.     else{
  15.         for(i=0;i<n;++i){
  16.             cnt=0;
  17.             cin>>s;
  18.             len=s.length();
  19.             a[i].c[0]=1;
  20.             for(j=1;j<len;++j){
  21.                 if(s[j]!=s[j-1])a[i].c[++cnt]=1;
  22.                 else ++a[i].c[cnt];
  23.             }
  24.         }
  25.         long tmp[100005];
  26.         for(i=0;i<=cnt;++i){
  27.             for(j=0;j<n;++j)tmp[j]=a[j].c[i];
  28.             sort(tmp,tmp+n);
  29.             long _233=tmp[n/2];
  30.             for(j=0;j<n;++j)rst+=abs(_233-a[j].c[i]);
  31.         }
  32.         cout<<rst;
  33.     }
  34.     return 0;
  35. }

E0076 移动游戏
First AC: 2018-04-03 Latest Modification: 2018-04-03
Note: 保留前n次每次移动后得到的向量(x_{i},y_{i}),0≤i<n
则点(a,b)能通过有限次移动得到当且仅当存在k,i
使得(a,b)=k(x_{n-1},y_{n-1})+(x_{i},y_{i}),k∈N,0≤i<n

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. string s;
  5. ll len,q,x,y;
  6. struct data{
  7.     ll x,y;
  8. }p[100001];
  9. ll i,j;
  10. int main()
  11. {
  12.     cin>>s>>q;
  13.     len=s.length();
  14.     for(i=0;i<len;++i){
  15.         if(s[i]=='U')++y;
  16.         else if(s[i]=='D')--y;
  17.         else if(s[i]=='L')--x;
  18.         else ++x;
  19.         p[++j].x=x,p[j].y=y;
  20.     }
  21.     ll stdx=p[len].x,stdy=p[len].y;
  22.     while(q--){
  23.         cin>>x>>y;
  24.         ll tmpx,tmpy;
  25.         bool jdg=0;
  26.         for(i=0;i<=len;++i){
  27.             tmpx=x-p[i].x;
  28.             tmpy=y-p[i].y;
  29.             if(tmpx*stdy!=tmpy*stdx)continue;
  30.             if(tmpx*stdx<0||tmpy*stdy<0)continue;
  31.             if((!stdx&&tmpx)||(!stdy&&tmpy))continue;
  32.             if(tmpx%stdx)continue;
  33.             jdg=1;
  34.             break;
  35.         }
  36.         if(jdg)cout<<"Yes\n";
  37.         else cout<<"No\n";
  38.     }
  39.     return 0;
  40. }

E0096 进制数位和均值
First AC: 2018-05-20 Latest Modification: 2018-05-20

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll T,n,up,dn,tmp;
  5. ll i;
  6. ll cal(ll num,ll base)
  7. {
  8.     ll ret=0;
  9.     while(num){
  10.         ret+=num%base;
  11.         num/=base;
  12.     }
  13.     return ret;
  14. }
  15. int main()
  16. {
  17.     cin>>T;
  18.     while(T--){
  19.         cin>>n;
  20.         up=0;
  21.         for(i=2;i<n;++i)up+=cal(n,i);
  22.         dn=n-2;
  23.         tmp=__gcd(up,dn);
  24.         cout<<up/tmp<<'/'<<dn/tmp<<endl;
  25.     }
  26.     return 0;
  27. }

E0097 邮件地址排序
First AC: 2018-05-20 Latest Modification: 2018-05-20

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. char c;
  5. string tmp;
  6. struct data{
  7.     string s,t;
  8. }a[1000000];
  9. int i;
  10. bool cmp(data a,data b)
  11. {
  12.     if(a.t!=b.t)return a.t<b.t;
  13.     return a.s>b.s;
  14. }
  15. int main()
  16. {
  17.     cin>>n;
  18.     getchar();
  19.     for(i=0;i<n;++i){
  20.         while(c=getchar()){
  21.             if(c=='@')break;
  22.             else tmp+=c;
  23.         }
  24.         a[i].s=tmp;
  25.         tmp="";
  26.         while(c=getchar()){
  27.             if(c=='\n'||c==EOF)break;
  28.             else tmp+=c;
  29.         }
  30.         a[i].t=tmp;
  31.         tmp="";
  32.     }
  33.     sort(a,a+n,cmp);
  34.     for(i=0;i<n;++i)cout<<a[i].s<<'@'<<a[i].t<<endl;
  35.     return 0;
  36. }

E0098 遥远距离
First AC: 2018-05-20 Latest Modification: 2018-05-20

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,tmp;
  4. struct data{
  5.     string s;
  6.     bool flag;
  7.     int num;
  8. }a[50];
  9. char b[126],c[126],d[126];
  10. int i,j;
  11. bool cmp(data a,data b)
  12. {
  13.     if(a.flag!=b.flag)return a.flag<b.flag;
  14.     if(a.flag){
  15.         if(a.num!=b.num)return a.num<b.num;
  16.         return a.s<b.s;
  17.     }
  18.     if(a.num!=b.num)return a.num>b.num;
  19.     return a.s>b.s;
  20. }
  21. int main()
  22. {
  23.     cin>>n;
  24.     for(i=0;i<n;++i){
  25.         cin>>a[i].s;
  26.         a[i].num=a[i].s.length();
  27.         if(a[i].s[0]=='-'){
  28.             a[i].flag=1;
  29.             a[i].s=a[i].s.substr(1,a[i].num-1);
  30.             --a[i].num;
  31.         }
  32.     }
  33.     sort(a,a+n,cmp);
  34.     for(i=0;i<126;++i)b[i]=c[i]=d[i]='0';
  35.     for(i=125,j=a[0].num-1;j>=0;--j)b[i--]=a[0].s[j];
  36.     for(i=125,j=a[n-1].num-1;j>=0;--j)c[i--]=a[n-1].s[j];
  37.     if(a[0].flag!=a[n-1].flag){
  38.         if(a[0].s=="0"&&a[n-1].s=="0"){
  39.             cout<<0;
  40.             return 0;
  41.         }
  42.         bool cf=0;
  43.         for(i=125;i>=0;--i){
  44.             tmp=b[i]+c[i]-2*'0'+cf;
  45.             if(tmp>9)d[i]=(char)(tmp-10+'0'),cf=1;
  46.             else d[i]=char(tmp+'0'),cf=0;
  47.         }
  48.         for(i=0;;++i)if(d[i]!='0')break;
  49.         for(j=i;j<126;++j)cout<<d[j];
  50.     }
  51.     else if(a[0].flag){
  52.         if(a[0].s==a[n-1].s){
  53.             cout<<0;
  54.             return 0;
  55.         }
  56.         bool cf=0;
  57.         for(i=125;i>=0;--i){
  58.             tmp=c[i]-b[i]-cf;
  59.             if(tmp<0)d[i]=(char)(tmp+10+'0'),cf=1;
  60.             else d[i]=char(tmp+'0'),cf=0;
  61.         }
  62.         for(i=0;;++i)if(d[i]!='0')break;
  63.         for(j=i;j<126;++j)cout<<d[j];
  64.     }
  65.     else{
  66.         if(a[0].s==a[n-1].s){
  67.             cout<<0;
  68.             return 0;
  69.         }
  70.         bool cf=0;
  71.         for(i=125;i>=0;--i){
  72.             tmp=b[i]-c[i]-cf;
  73.             if(tmp<0)d[i]=(char)(tmp+10+'0'),cf=1;
  74.             else d[i]=char(tmp+'0'),cf=0;
  75.         }
  76.         for(i=0;;++i)if(d[i]!='0')break;
  77.         for(j=i;j<126;++j)cout<<d[j];
  78.     }
  79.     return 0;
  80. }

E0099 幂次转换
First AC: 2018-01-13 Latest Modification: 2018-02-28
Note: 遍历base=2,3,…,64,判断开base次根号是不是整数

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef long double ld;
  5. int T;
  6. ll n;
  7. bool jdg;
  8. void cal(ll n,ll i)
  9. {
  10.     if(n<2)return;
  11.     ll tmp=pow((ld)n,(ld)1.0/i)+0.5;
  12.     ll rst=1;
  13.     for(int j=0;j<i;++j)rst*=tmp;
  14.     if(rst==n)cout<<'='<<tmp<<'^'<<i,jdg=0;
  15. }
  16. int main()
  17. {
  18.     cin>>T;
  19.     while(T--){
  20.         cin>>n;
  21.         cout<<n;
  22.         jdg=1;
  23.         for(ll i=2;i<64;++i)cal(n,i);
  24.         if(jdg)cout<<" is powerless.";
  25.         cout<<endl;
  26.     }
  27.     return 0;
  28. }

E0100 变换种类数
First AC: 2018-05-20 Latest Modification: 2018-05-20
Note: dp[i][j]表示在前j个数字中插入加减号的结果模2×3×5×7的方案数

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int M=2*3*5*7;
  5. const ll mod=1e9+7;
  6. int T,len;
  7. string s;
  8. ll dp[105][210];
  9. int i,j,k;
  10. int main()
  11. {
  12.     cin>>T;
  13.     while(T--){
  14.         cin>>s;
  15.         len=s.length();
  16.         memset(dp,0,sizeof(dp));
  17.         dp[0][0]=1;
  18.         for(i=0;i<len;++i){
  19.             for(j=0;j<M;++j){
  20.                 ll tmp=0;
  21.                 for(k=i+1;k<=len;++k){
  22.                     tmp=(10*tmp+s[k-1]-'0')%M;
  23.                     dp[k][(j+tmp)%M]+=dp[i][j];
  24.                     dp[k][(j+tmp)%M]%=mod;
  25.                     dp[k][(j+M-tmp)%M]+=dp[i][j];
  26.                     dp[k][(j+M-tmp)%M]%=mod;
  27.                 }
  28.             }
  29.         }
  30.         ll rst=0;
  31.         for(i=0;i<M;++i){
  32.             if(i%2&&i%3&&i%5&&i%7)continue;
  33.             rst=(rst+dp[len][i])%mod;
  34.         }
  35.         cout<<(mod+1)/2*rst%mod<<endl;
  36.     }
  37.     return 0;
  38. }

E0108 A+B Problem Templated
First AC: 2018-07-17 Latest Modification: 2018-07-17

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     int a,b;
  6.     while(cin>>a>>b)cout<<a+b<<endl;
  7. }

E0116 4个值的和为0
First AC: 2018-07-17 Latest Modification: 2018-07-17

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=4000;
  4. int n;
  5. long long rst;
  6. int a[N],b[N],c[N],d[N];
  7. map<int,int>mpl,mpr;
  8. map<int,int>::iterator it,fd;
  9. int i,j;
  10. int main()
  11. {
  12.     ios::sync_with_stdio(false);
  13.     cin>>n;
  14.     for(i=0;i<n;++i)cin>>a[i]>>b[i]>>c[i]>>d[i];
  15.     for(i=0;i<n;++i)for(j=0;j<n;++j){
  16.         it=mpl.find(a[i]+b[j]);
  17.         if(it!=mpl.end())++it->second;
  18.         else mpl.insert(pair<int,int>(a[i]+b[j],1));
  19.     }
  20.     for(i=0;i<n;++i)for(j=0;j<n;++j){
  21.         it=mpr.find(c[i]+d[j]);
  22.         if(it!=mpr.end())++it->second;
  23.         else mpr.insert(pair<int,int>(c[i]+d[j],1));
  24.     }
  25.     for(it=mpl.begin();it!=mpl.end();++it){
  26.         fd=mpr.find(-it->first);
  27.         if(fd!=mpr.end())rst+=it->second*fd->second;
  28.     }
  29.     cout<<rst;
  30.     return 0;
  31. }

E0121 经典的猜数游戏
First AC: 2018-07-12 Latest Modification: 2018-07-12

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long lft,rgt,mid;
  4. string s;
  5. int main()
  6. {
  7.     lft=-1e9;
  8.     rgt=1e9;
  9.     while(1){
  10.         mid=(lft+rgt)/2;
  11.         cout<<mid<<endl;
  12.         cin>>s;
  13.         if(s=="big")rgt=mid-1;
  14.         else if(s=="small")lft=mid+1;
  15.         else break;
  16.     }
  17.     return 0;
  18. }

E0122 游程长度编码
First AC: 2018-07-12 Latest Modification: 2018-07-12

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,len,cnt;
  4. string s;
  5. int i,j;
  6. int main()
  7. {
  8.     cin>>T;
  9.     for(i=0;i<T;++i){
  10.         cin>>s;
  11.         cout<<"case #"<<i<<":\n";
  12.         len=s.length();
  13.         cnt=1;
  14.         for(j=1;j<=len-1;++j){
  15.             if(s[j]==s[j-1])cnt++;
  16.             else if(cnt>255)cout<<"255"<<s[j-1]<<cnt-255<<s[j-1],cnt=1;
  17.             else cout<<cnt<<s[j-1],cnt=1;
  18.         }
  19.         if(cnt>255)cout<<"255"<<s[len-1]<<cnt-255<<s[len-1]<<endl;
  20.         else cout<<cnt<<s[len-1]<<endl;
  21.     }
  22.     return 0;
  23. }

E0139 旅游规划
First AC: 2019-02-07 Latest Modification: 2019-02-07

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,start,destination;
  4. int a,b,c,d;
  5. int dis[500][500];
  6. int cost[500][500];
  7. int i,j,k;
  8. int main()
  9. {
  10.     memset(dis,0x3f,sizeof dis);
  11.     memset(cost,0x3f,sizeof cost);
  12.     for(i=0;i<500;++i)dis[i][i]=cost[i][i]=0;
  13.     cin>>n>>m>>start>>destination;
  14.     while(m--){
  15.         cin>>a>>b>>c>>d;
  16.         if(dis[a][b]>c||(dis[a][b]==c&&cost[a][b]>d)){
  17.             dis[a][b]=c;
  18.             cost[a][b]=d;
  19.         }
  20.         if(dis[b][a]>c||(dis[b][a]==c&&cost[b][a]>d)){
  21.             dis[b][a]=c;
  22.             cost[b][a]=d;
  23.         }
  24.     }
  25.     for(k=0;k<n;++k){
  26.         for(i=0;i<n;++i){
  27.             for(j=0;j<n;++j){
  28.                 int sumd=dis[i][k]+dis[k][j];
  29.                 int sumc=cost[i][k]+cost[k][j];
  30.                 if(dis[i][j]>sumd||(dis[i][j]==sumd&&cost[i][j]>sumc)){
  31.                     dis[i][j]=sumd;
  32.                     cost[i][j]=sumc;
  33.                 }
  34.             }
  35.         }
  36.     }
  37.     cout<<dis[start][destination]<<' '<<cost[start][destination];
  38.     return 0;
  39. }

E0151 冒泡排序
First AC: 2018-07-17 Latest Modification: 2018-07-17

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,pos;
  4. int cntcmp,cntswp,cntbub;
  5. int a[5000];
  6. int i;
  7. int main()
  8. {
  9.     cin>>n;
  10.     for(i=0;i<n;++i)cin>>a[i];
  11.     --n;
  12.     while(n){
  13.         pos=0;
  14.         for(i=1;i<=n;++i){
  15.             ++cntcmp;
  16.             if(a[i-1]>a[i]){
  17.                 a[i]^=a[i-1];
  18.                 a[i-1]^=a[i];
  19.                 a[i]^=a[i-1];
  20.                 pos=i-1;
  21.                 ++cntswp;
  22.             }
  23.         }
  24.         n=pos;
  25.         ++cntbub;
  26.     }
  27.     cout<<cntcmp<<' '<<cntswp<<' '<<cntbub;
  28.     return 0;
  29. }

E0152 Take a Party
First AC: 2018-07-17 Latest Modification: 2018-07-17

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll s,m,n,x,y;
  5. ll pre[1000001];
  6. ll i,j;
  7. ll find(ll x)
  8. {
  9.     ll r=x;
  10.     while(r!=pre[r])r=pre[r];
  11.     i=x;
  12.     while(pre[i]!=r)j=pre[i],pre[i]=r,i=j;
  13.     return r;
  14. }
  15. void join(ll x,ll y)
  16. {
  17.     ll fx=find(x),fy=find(y);
  18.     if(fx!=fy)pre[fx]=fy;
  19. }
  20. int main()
  21. {
  22.     ios::sync_with_stdio(false);
  23.     cin>>s>>m>>n;
  24.     for(i=1;i<=s;++i)pre[i]=i;
  25.     while(m--){
  26.         cin>>x>>y;
  27.         join(x,y);
  28.     }
  29.     while(n--){
  30.         cin>>x>>y;
  31.         if(find(x)!=find(y))cout<<"0\n";
  32.         else cout<<"1\n";
  33.     }
  34.     return 0;
  35. }

E0156 大鱼吃小鱼
First AC: 2018-07-17 Latest Modification: 2018-07-17

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll n,x,a,tmp,rst=1;
  5. struct data{
  6.     ll w,a;
  7.     bool add;
  8. }fish[1000000];
  9. int i;
  10. bool cmp(data a,data b)
  11. {
  12.     if(a.add!=b.add)return a.add>b.add;
  13.     if(a.add){
  14.         if(a.w!=b.w)return a.w<b.w;
  15.         return a.a>b.a;
  16.     }
  17.     else{
  18.         if(a.w+a.a!=b.w+b.a)return a.w+a.a>b.w+b.a;
  19.         return a.a>b.a;
  20.     }
  21. }
  22. int main()
  23. {
  24.     cin>>n;
  25.     for(i=0;i<n;++i){
  26.         cin>>fish[i].w>>fish[i].a;
  27.         if(fish[i].a<0)fish[i].add=0;
  28.         else fish[i].add=1;
  29.     }
  30.     sort(fish,fish+n,cmp);
  31.     for(i=0;i<n;++i){
  32.         if(fish[i].add)rst=max(rst,fish[i].w-tmp);
  33.         else rst=max(rst,max(fish[i].w-tmp,1-fish[i].a-tmp));
  34.         tmp+=fish[i].a;
  35.     }
  36.     cout<<rst;
  37.     return 0;
  38. }

E0157 玩具谜题
First AC: 2018-07-17 Latest Modification: 2018-07-17

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct toy{
  4.     int dir;
  5.     string job;
  6. }a[100005];
  7. long n,m,d,num,cnt=1;
  8. long i;
  9. int main()
  10. {
  11.     ios::sync_with_stdio(false);
  12.     cin>>n>>m;
  13.     for(i=1;i<=n;++i)cin>>a[i].dir>>a[i].job;
  14.     for(i=1;i<=m;++i){
  15.         cin>>d>>num;
  16.         if(d==a[cnt].dir){
  17.             cnt-=num;
  18.             while(cnt<=0)cnt+=n;
  19.         }
  20.         else{
  21.             cnt=(cnt+num)%n;
  22.             if(cnt==0)cnt=n;
  23.         }
  24.     }
  25.     cout<<a[cnt].job;
  26.     return 0;
  27. }

E0158 玩具谜题
First AC: 2018-07-17 Latest Modification: 2018-07-17

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct toy{
  4.     int dir;
  5.     string job;
  6. }a[100005];
  7. long n,m,d,num,cnt=1;
  8. long i;
  9. int main()
  10. {
  11.     ios::sync_with_stdio(false);
  12.     cin>>n>>m;
  13.     for(i=1;i<=n;++i)cin>>a[i].dir>>a[i].job;
  14.     for(i=1;i<=m;++i){
  15.         cin>>d>>num;
  16.         if(d==a[cnt].dir){
  17.             cnt-=num;
  18.             while(cnt<=0)cnt+=n;
  19.         }
  20.         else{
  21.             cnt=(cnt+num)%n;
  22.             if(cnt==0)cnt=n;
  23.         }
  24.     }
  25.     cout<<a[cnt].job;
  26.     return 0;
  27. }

E0159 密码碰撞
First AC: 2018-07-17 Latest Modification: 2018-07-17

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,num,tmp,rst;
  4. string s,t;
  5. map<string,int>fd,mp;
  6. map<string,int>::iterator it;
  7. struct data{
  8.     string s;
  9.     int cnt,len;
  10. }a[20000];
  11. int i,j,k;
  12. bool cmp(data a,data b)
  13. {
  14.     return a.len>b.len;
  15. }
  16. int main()
  17. {
  18.     cin>>n;
  19.     for(i=0;i<n;++i){
  20.         cin>>s;
  21.         if((it=fd.find(s))!=fd.end())++a[it->second].cnt;
  22.         else{
  23.             a[num].s=s;
  24.             a[num].cnt=1;
  25.             a[num].len=s.length();
  26.             fd.insert(pair<string,int>(s,num++));
  27.         }
  28.     }
  29.     fd.clear();
  30.     sort(a,a+num,cmp);
  31.     for(i=0;i<num;++i){
  32.         rst+=a[i].cnt*(a[i].cnt-1);
  33.         if((it=fd.find(a[i].s))!=fd.end())rst+=a[i].cnt*it->second;
  34.         mp.clear();
  35.         for(j=0;j<a[i].len;++j){
  36.             for(k=j;k<a[i].len;++k){
  37.                 t=a[i].s.substr(j,k-j+1);
  38.                 if((it=mp.find(t))==mp.end()){
  39.                     mp.insert(pair<string,int>(t,1));
  40.                     if((it=fd.find(t))!=fd.end())it->second+=a[i].cnt;
  41.                     else fd.insert(pair<string,int>(t,a[i].cnt));
  42.                 }
  43.             }
  44.         }
  45.     }
  46.     cout<<rst;
  47.     return 0;
  48. }

E0163 数据结构开课啦
First AC: 2018-07-17 Latest Modification: 2018-07-17
数据结构
数据结构
数据结构

存储

多对多
E0165 三千米健身步道
First AC: 2018-08-01 Latest Modification: 2018-08-01

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,x,y,rst;
  4. int cnt[1001],fr[1000],to[1000];
  5. int i;
  6. int main()
  7. {
  8.     cin>>n;
  9.     for(i=1;i<n;++i){
  10.         cin>>x>>y;
  11.         ++cnt[x],++cnt[y];
  12.         fr[i]=x,to[i]=y;
  13.     }
  14.     for(i=1;i<n;++i){
  15.         rst+=(cnt[fr[i]]-1)*(cnt[to[i]]-1);
  16.     }
  17.     cout<<rst;
  18.     return 0;
  19. }

E0168 小迷妹在哪儿
First AC: 2018-08-04 Latest Modification: 2018-08-04

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,T,rst;
  4. struct data{
  5.     int a,t;
  6. }girl[100001];
  7. int dp[100001][301];
  8. bool jdg[100001][301];
  9. int i,j;
  10. bool cmp(data a,data b)
  11. {
  12.     return a.a*b.t>b.a*a.t;
  13. }
  14. int main()
  15. {
  16.     cin>>n>>T;
  17.     for(i=1;i<=n;++i)
  18.         cin>>girl[i].a>>girl[i].t;
  19.     sort(girl+1,girl+n+1,cmp);
  20.     jdg[0][T]=1;
  21.     for(i=0;i<n;++i)for(j=1;j<=T;++j){
  22.         if(jdg[i][j]){
  23.             dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
  24.             jdg[i+1][j]=1;
  25.             if(j>=girl[i+1].t){
  26.                 dp[i+1][j-girl[i+1].t]=
  27.                     max(dp[i][j]+(j-girl[i+1].t)*
  28.                     girl[i+1].a,dp[i+1][j-girl[i+1].t]);
  29.                 jdg[i+1][j-girl[i+1].t]=1;
  30.             }
  31.         }
  32.     }
  33.     for(i=0;i<=T;++i)if(dp[n][i]>rst)rst=dp[n][i];
  34.     cout<<rst;
  35.     return 0;
  36. }

E0170 矩形个数
First AC: 2018-08-04 Latest Modification: 2018-08-04

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,r,c,n,k,x,y,rst;
  4. int mp[11][11];
  5. int i,j,l;
  6. int cnt(int x,int y)
  7. {
  8.     int ret=0,i,j,l;
  9.     for(i=x;i<=r;++i){
  10.         int tmp=0;
  11.         for(j=y;j<=c;++j){
  12.             for(l=x;l<=i;++l)
  13.                 if(mp[l][j])
  14.                     ++tmp;
  15.             if(tmp>=k){
  16.                 ret+=c-j+1;
  17.                 break;
  18.             }
  19.         }
  20.     }
  21.     return ret;
  22. }
  23. int main()
  24. {
  25.     cin>>T;
  26.     for(i=0;i<T;++i){
  27.         cin>>r>>c>>n>>k;
  28.         memset(mp,0,sizeof(mp));
  29.         while(n--){
  30.             cin>>x>>y;
  31.             mp[x][y]=1;
  32.         }
  33.         rst=0;
  34.         for(j=1;j<=r;++j)
  35.             for(l=1;l<=c;++l)
  36.                 rst+=cnt(j,l);
  37.         cout<<"case #"<<i<<":\n"<<rst<<endl;
  38.     }
  39.     return 0;
  40. }

E0171 考新郎
First AC: 2018-08-04 Latest Modification: 2018-08-04

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll a[21]={0,0,1};
  5. ll s;
  6. int n,m;
  7. int i;
  8. int main()
  9. {
  10.     for(i=3;i<21;++i)a[i]=(i-1)*(a[i-1]+a[i-2]);
  11.     cin>>n;
  12.     while(cin>>n>>m){
  13.         s=1;
  14.         for(i=1;i<=m;++i)s*=(n+1-i),s/=i;
  15.         s*=a[m];
  16.         cout<<s<<endl;
  17.     }
  18.     return 0;
  19. }

E0172 津津骑马
First AC: 2018-08-04 Latest Modification: 2018-08-04

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,x,y,a[35][35];
  4. int main()
  5. {
  6.     a[4][3]=a[3][4]=1;
  7.     for(int i=2;i<35;++i)
  8.         for(int j=2;j<35;++j)
  9.             a[i][j]+=a[i-1][j-2]+a[i-2][j-1];
  10.     cin>>T;
  11.     for(int i=1;i<=T;++i){
  12.         cin>>x>>y;
  13.         cout<<"Chessboard #"<<i<<':'<<a[x+1][y+1]<<endl;
  14.     }
  15.     return 0;
  16. }

E0180 地铁站
First AC: 2018-11-16 Latest Modification: 2018-11-16
Note: 设第二站下车人数为b,通过列出前几项可以找到规律:
站数 1 2 3 4 5 6 … n
上车 a a 0 a a 2a 3a … fib[n-3]a
b 0 b b 2b 3b 5b … fib[n-2]b
下车 a 0 0 0 a a 2a … fib[n-2]a
b 0 b b b 2b 3b … fib[n-1]b
其中fib[n]是斐波那契数列,且设第一项fib[0]=1下标为0
依题意,第n(>=4)站开出时,车上人数等于第n-1站上车人数+第1站上车人数-第2站下车人数
即fib[n-4]a+fib[n-3]b+a-b=x,这样便可解出b,从而可得第x站开出时车上的人数,注意对x<4单独讨论

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a,b,n,m,x;
  4. int fib[20]={1,1};
  5. int i;
  6. int main()
  7. {
  8.     cin>>a>>n>>m>>x;
  9.     for(i=2;i<20;++i)fib[i]=fib[i-2]+fib[i-1];
  10.     if(x>=n)cout<<0;
  11.     else if(n<3||x<3)cout<<a;
  12.     else if(n==4){
  13.         if(x==4)cout<<2*a;
  14.         else cout<<a;
  15.     }
  16.     else{
  17.         b=(m-fib[n-4]*a-a)/(fib[n-3]-1);
  18.         cout<<fib[x-3]*a+fib[x-2]*b+a-b;
  19.     }
  20.     return 0;
  21. }

E0183 单词的划分
First AC: 2018-08-23 Latest Modification: 2018-08-23

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,ls;
  4. string s;
  5. string w[100];
  6. int len[100];
  7. int dp[260];
  8. int i,j;
  9. int main()
  10. {
  11.     cin>>T;
  12.     while(T--){
  13.         cin>>s>>n;
  14.         s=' '+s;
  15.         ls=s.length();
  16.         for(i=0;i<n;++i)cin>>w[i],len[i]=w[i].length();
  17.         for(i=1;i<ls;++i){
  18.             dp[i]=500;
  19.             for(j=0;j<n;++j)
  20.                 if(i>=len[j]&&w[j]==s.substr(i-len[j]+1,len[j]))
  21.                     dp[i]=min(dp[i],dp[i-len[j]]+1);
  22.         }
  23.         cout<<dp[ls-1]<<endl;
  24.     }
  25.     return 0;
  26. }

E0186 完全加括号的矩阵连乘积
First AC: 2018-08-23 Latest Modification: 2018-08-23

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. int T,n,len,lft,rgt;
  5. ll x[51],y[51];
  6. ll dp[51][51];
  7. int i,j;
  8. int main()
  9. {
  10.     cin>>T;
  11.     while(T--){
  12.         cin>>n;
  13.         for(i=1;i<=n;++i)cin>>x[i]>>y[i];
  14.         memset(dp,0x3f,sizeof dp);
  15.         for(i=1;i<51;++i)dp[i][i]=0;
  16.         for(len=2;len<=n;++len){
  17.             for(rgt=len;rgt<=n;++rgt){
  18.                 lft=rgt-len+1;
  19.                 for(i=lft+1;i<=rgt;++i)
  20.                     dp[lft][rgt]=min(dp[lft][rgt],dp[lft][i-1]+dp[i][rgt]+x[lft]*x[i]*y[rgt]);
  21.             }
  22.         }
  23.         cout<<dp[1][n]<<endl;
  24.     }
  25.     return 0;
  26. }

E0215 和你在一起
First AC: 2018-09-13 Latest Modification: 2018-09-13

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. string s[20];
  5. int i;
  6. int main()
  7. {
  8.     cin>>n;
  9.     for(i=0;i<n;++i)cin>>s[i];
  10.     sort(s,s+n);
  11.     for(i=n-1;i>=0;--i)cout<<s[i];
  12.     return 0;
  13. }