EOJ 3000-3999 题解集合

E3000 ROT13加密和解密
First AC: 2017-10-30 Latest Modification: 2018-03-15

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,i,j,len;
  4. string s;
  5. int main()
  6. {
  7.     cin>>T;
  8.     getchar();
  9.     for(i=0;i<T;i++){
  10.         cout<<"case #"<<i<<":\n";
  11.         getline(cin,s,'\n');
  12.         len=s.length();
  13.         for(j=0;j<len;++j){ if(s[j]>='A'&&s[j]<'N')cout<<(char)(s[j]+13); else if(s[j]>'M'&&s[j]<='Z')cout<<(char)(s[j]-13); else if(s[j]>='a'&&s[j]<'n')cout<<(char)(s[j]+13); else if(s[j]>'m'&&s[j]<='z')cout<<(char)(s[j]-13);
  14.             else cout<<s[j];
  15.         }
  16.         cout<<endl;
  17.     }
  18.     return 0;
  19. }

E3001 计算a的n次方的大整数
First AC: 2017-12-21 Latest Modification: 2018-04-11

  1. n=input()
  2. i=0
  3. while True:
  4.     try:
  5.         a,b=input().split()
  6.         print('case #%d:'%i)
  7.         print((int)(a)**(int)(b))
  8.         i=i+1
  9.     except:
  10.         break

E3002 泰波那契数列的前74项
First AC: 2017-09-28 Latest Modification: 2018-06-04

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long tib[75]={0,1,1};
  4. int T,n;
  5. int i;
  6. int main()
  7. {
  8.     for(i=3;i<75;++i)tib[i]=tib[i-1]+tib[i-2]+tib[i-3]; cin>>T;
  9.     for(i=0;i<T;++i){ cin>>n;
  10.         cout<<"case #"<<i<<":\n"<<tib[n]<<endl;
  11.     }
  12.     return 0;
  13. }

E3003 最小向量点积
First AC: 2017-12-14 Latest Modification: 2018-03-22

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n;
  4. long a[1001],b[1001],rst;
  5. int i,j;
  6. int main()
  7. {
  8.     cin>>T;
  9.     for(i=0;i<T;++i){ cin>>n;
  10.         for(j=0;j<n;++j)cin>>a[j];
  11.         for(j=0;j<n;++j)cin>>b[j];
  12.         sort(a,a+n),sort(b,b+n);
  13.         for(j=rst=0;j<n;++j)rst+=a[j]*b[n-1-j];
  14.         cout<<"case #"<<i<<":\n"<<rst<<endl;
  15.     }
  16.     return 0;
  17. }

E3004 生理高峰
First AC: 2017-10-22 Latest Modification: 2018-03-22

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,p,e,i,d,rst;
  4. int j;
  5. int main()
  6. {
  7.     cin>>T;
  8.     for(j=0;j<T;++j){ cin>>p>>e>>i>>d;
  9.         for(rst=d+1;;++rst){
  10.             if((rst-p)%23==0&&(rst-e)%28==0&&(rst-i)%33==0){
  11.                 printf("case #%d:\nthe next triple ",j);
  12.                 printf("peak occurs in %d days.\n",rst-d);
  13.                 break;
  14.             }
  15.         }
  16.     }
  17.     return 0;
  18. }

E3005 小型组合数
First AC: 2017-10-24 Latest Modification: 2018-04-11

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

E3007 A*B II
First AC: 2017-12-17 Latest Modification: 2017-12-17

  1. n=(int)(input())
  2. while n>0:
  3.     a,b=(input().split())
  4.     print((int)(a)*(int)(b))
  5.     n=n-1

E3008 Coins (I)
First AC: 2018-04-24 Latest Modification: 2018-06-06
Note: 因为每个硬币面额至少为1,所以K次的限制是多余的,那么就转化为完全背包

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const ll M=1e8+7;
  5. ll T,n,K,m;
  6. ll dp[100001];
  7. ll i,j;
  8. int main()
  9. {
  10.     ios::sync_with_stdio(false);
  11.     cin>>T;
  12.     for(i=1;i<=T;++i){ cin>>n>>K;
  13.         memset(dp,0,sizeof(dp));
  14.         dp[0]=1;
  15.         while(n--){
  16.             cin>>m;
  17.                 for(j=m;j<=K;++j)
  18.                     (dp[j]+=dp[j-m])%=M;
  19.         }
  20.         cout<<"Case "<<i<<": "<<dp[K]<<endl;
  21.     }
  22.     return 0;
  23. }

E3009 Coins (II)
First AC: 2018-06-06 Latest Modification: 2018-06-06
Note: 多重背包

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const ll M=1e8+7;
  5. ll T,n,K,m;
  6. ll a[101],dp[10001];
  7. ll i,j,k,l;
  8. int main()
  9. {
  10.     ios::sync_with_stdio(false);
  11.     cin>>T;
  12.     for(i=1;i<=T;++i){ cin>>n>>K;
  13.         for(j=0;j<n;++j)cin>>a[j];
  14.         memset(dp,0,sizeof(dp));
  15.         dp[0]=1;
  16.         for(j=0;j<n;++j){ cin>>m;
  17.             for(k=K;k>=0;--k)
  18.                 for(l=1;l<=m;++l) if(k-l*a[j]>=0)
  19.                         (dp[k]+=dp[k-l*a[j]])%=M;
  20.         }
  21.         cout<<"Case "<<i<<": "<<dp[K]<<endl;
  22.     }
  23.     return 0;
  24. }

E3010 Coins (III)
First AC: 2018-06-07 Latest Modification: 2018-06-07
Note: 多重背包的二进制优化

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll T,n,K,m,cnt;
  5. ll a[101];
  6. bool dp[100001];
  7. ll i,j,k,l;
  8. int main()
  9. {
  10.     ios::sync_with_stdio(false);
  11.     cin>>T;
  12.     for(i=1;i<=T;++i){ cin>>n>>K;
  13.         for(j=0;j<n;++j)cin>>a[j];
  14.         memset(dp,0,sizeof(dp));
  15.         dp[0]=1;
  16.         for(j=0;j<n;++j){ cin>>m;
  17.             ll sum=0,tmp;
  18.             bool jdg=1;
  19.             for(k=1;jdg;k*=2){
  20.                 if(sum+k<=m)sum+=k,tmp=k*a[j]; else jdg=0,tmp=(m-sum)*a[j]; for(l=K-tmp;l>=0;--l)
  21.                     dp[l+tmp]|=dp[l];
  22.             }
  23.         }
  24.         cnt=0;
  25.         for(j=1;j<=K;++j)if(dp[j])++cnt;
  26.         cout<<"Case "<<i<<": "<<cnt<<endl;
  27.     }
  28.     return 0;
  29. }

E3012 Coins (V)
First AC: 2018-04-24 Latest Modification: 2018-04-24

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long T,n,i;
  4. int main()
  5. {
  6.     cin>>T;
  7.     for(i=1;i<=T;++i){ cin>>n;
  8.         cout<<"Case "<<i<<": "<<(long long)(log(n)/log(2))+1<<endl;
  9.     }
  10.     return 0;
  11. }

E3013 Coins (VI)
First AC: 2018-04-24 Latest Modification: 2018-04-24

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long T,n,i;
  4. int main()
  5. {
  6.     cin>>T;
  7.     for(i=1;i<=T;++i){ cin>>n;
  8.         cout<<"Case "<<i<<": "<<ceil(log(2*n+1)/log(3))<<endl;
  9.     }
  10.     return 0;
  11. }

E3014 小高斯和小欧几里得(I)
First AC: 2018-06-08 Latest Modification: 2018-06-08
Note: 数据范围很大,很多方法都会超时
注意到(1+60000)×60000/2>2000000000
这表明符合条件的连续正整数个数不超过60000
而每个连续正整数的个数最多只能有一组解满足题设
所以对整数个数遍历即可

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll T,n,rst;
  5. ll i,j;
  6. int main()
  7. {
  8.     cin>>T;
  9.     for(i=0;i<T;i++){ cin>>n;
  10.         rst=0;
  11.         for(j=1;j*(j+1)<=2*n;++j)
  12.             if(!((n-j*(j+1)/2)%j))
  13.                 ++rst;
  14.         cout<<"case #"<<i<<": "<<rst<<endl;
  15.     }
  16.     return 0;
  17. }

E3015 小高斯和小欧几里得(II)
First AC: 2018-06-08 Latest Modification: 2018-06-08
Note: 将所有程序按写的时间和调的贡献大小分为总体写bug和总体debug两类
注意到首尾两个程序计算时写bug和debug的时间都要计算在内
所以应该尽可能让第一个程序写的时间和最后一个程序调的时间尽可能少
同时中间的程序尽可能先写bug
因为写的时间里可以调前面程序的bug,贪心的做法是先写bug再调bug
所以可以排序,凡是写bug的都排在调bug前面
在写bug内部,让第一个程序的写bug时间最小
在debug内部,让最后一个程序不得不遗留的debug时间最小
但这个算法我没法证明正确性的一点是
在写bug和debug差异较大的数据中,是否最优解的首末程序仍是首写bug末debug
虽然测试数据中没有这种可能存在的反例
有大佬写的cmp函数是这样的:return min(a.bug,b.debug)<min(a.debug,b.bug);
试了一下可以过,但我也不知道怎么证明正确性

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. int T,n;
  5. ll bug,debug,tmp,rst;
  6. struct data{
  7.     ll bug,debug;
  8. }a[100000],b;
  9. int i,j;
  10. bool cmp(data a,data b)
  11. {
  12.     bool jdga=a.bug<a.debug? 1:0;
  13.     bool jdgb=b.bug<b.debug? 1:0; if(jdga!=jdgb)return jdga>jdgb;
  14.     if(jdga){
  15.         if(a.bug!=b.bug)return a.bug<b.bug;
  16.         return a.bug-a.debug<b.bug-b.debug; } else{ if(a.debug!=b.debug)return a.debug>b.debug;
  17.         return a.bug-a.debug<b.bug-b.debug; } } int main() { cin>>T;
  18.     for(i=0;i<T;i++){ cin>>n;
  19.         for(j=0;j<n;++j)cin>>a[j].bug>>a[j].debug;
  20.         sort(a,a+n,cmp);
  21.         bug=debug=rst=0;
  22.         for(j=0;j<n;++j){
  23.             rst+=a[j].bug;
  24.             if(debug<a[j].bug)debug=a[j].debug;
  25.             else debug=debug-a[j].bug+a[j].debug;
  26.         }
  27.         cout<<"case #"<<i<<": "<<rst+debug<<endl;
  28.     }
  29.     return 0;
  30. }

E3016 Blue Forehead
First AC: 2018-06-08 Latest Modification: 2018-06-08

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

E3017 计算n阶乘右端0的个数(I)
First AC: 2017-10-22 Latest Modification: 2018-04-11

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,T,i;
  4. int main()
  5. {
  6.     cin>>T;
  7.     for(;i<T;i++){ cin>>n;
  8.         cout<<"case #"<<i<<":\n"<<n/5+n/25+n/125+n/625<<endl;
  9.     }
  10.     return 0;
  11. }

E3018 查找单词
First AC: 2017-11-07 Latest Modification: 2018-03-15

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,i,j,k,ls,lt,mx,num,cnt;
  4. string s,t;
  5. int main()
  6. {
  7.     cin>>T;getchar();
  8.     for(i=0;i<T;++i){
  9.         getline(cin,t),getline(cin,s);
  10.         cout<<"case #"<<i<<":\n";
  11.         ls=s.length(),lt=t.length();
  12.         for(j=0;j<ls;++j)if(s[j]>64&&s[j]<91)s[j]+=32;
  13.         for(j=0;j<lt;++j)if(t[j]>64&&t[j]<91)t[j]+=32;
  14.         mx=ls-lt,cnt=0;
  15.         for(j=0;j<mx;++j){
  16.             if((j==0||s[j-1]==' ')&&s[j]==t[0]
  17.                 &&(lt+j==ls||s[j+lt]==' ')){
  18.                 num=0;
  19.                 for(k=1;k<lt;++k){
  20.                     if(s[j+k]!=t[k]){
  21.                         num++;
  22.                         break;
  23.                     }
  24.                 }
  25.                 if(num==0){cout<<j+1<<endl;cnt++;break;}
  26.             }
  27.         }
  28.         if(cnt==0)cout<<"None\n";
  29.     }
  30.     return 0;
  31. }

E3020 数字猜想问题
First AC: 2017-11-05 Latest Modification: 2018-06-08

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

E3021 字符排序
First AC: 2017-12-13 Latest Modification: 2018-03-07

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

E3022 计算n阶乘右端0的个数(II)
First AC: 2017-10-15 Latest Modification: 2018-04-11

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,i;
  4. int main()
  5. {
  6.     cin>>T;
  7.     for(i=0;i<T;i++){ cin>>n;
  8.         cout<<"case #"<<i<<":\n"<<n/5+n/25+n/125+n/625<<endl;
  9.     }
  10.     return 0;
  11. }

E3023 字符组合
First AC: 2018-03-15 Latest Modification: 2018-03-15

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long T,len,tmp,cnt;
  4. string s,t,r;
  5. bool a[26],b[26];
  6. string str[66000];
  7. long i,j,k;
  8. int main()
  9. {
  10.     cin>>T;
  11.     for(i=0;i<T;++i){ cin>>s;
  12.         len=s.length();
  13.         for(j=0;j<len;++j) if(s[j]>='A'&&s[j]<='Z')a[s[j]-'A']=1; else if(s[j]>='a'&&s[j]<='z')b[s[j]-'a']=1;
  14.         t="";
  15.         for(j=0;j<26;++j)if(a[j])t+=(char)(j+'A'),a[j]=0;
  16.         for(j=0;j<26;++j)if(b[j])t+=(char)(j+'a'),b[j]=0;
  17.         k=0;
  18.         for(j=(1<<t.length())-1;j;--j){ r=""; tmp=j,cnt=0; while(tmp){ if(tmp&1)r+=t[cnt]; tmp>>=1;
  19.                 ++cnt;
  20.             }
  21.             str[k++]=r;
  22.         }
  23.         sort(str,str+k);
  24.         cout<<"case #"<<i<<":\n";
  25.         for(j=0;j<k;++j)cout<<str[j]<<endl;
  26.     }
  27.     return 0;
  28. }

E3024 八进制小数
First AC: 2018-03-10 Latest Modification: 2018-03-10

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,len;
  4. string s,t;
  5. int i,j;
  6. void div()
  7. {
  8.     string r="";
  9.     int tmp=0,len=t.length();
  10.     for(int i=0;i<len;++i){ tmp=10*tmp+t[i]-'0'; r+=(char)(tmp/8+'0'); tmp%=8; } while(tmp){ tmp*=10; r+=(char)(tmp/8+'0'); tmp%=8; } t=r.substr(1,r.length()); } int main() { cin>>T;
  11.     for(i=0;i<T;++i){ cin>>s;
  12.         len=s.length();
  13.         t="";
  14.         for(j=len-1;j>1;--j)t=s[j]+t,div();
  15.         len=t.length();
  16.         while(t[len-1]=='0')t=t.substr(0,--len);
  17.         cout<<"case #"<<i<<":\n0."<<t<<endl;
  18.     }
  19.     return 0;
  20. }

E3025 连续正整数之和
First AC: 2017-10-18 Latest Modification: 2018-09-14
Note: 对加数个数j分奇偶
奇数j可以是加数个数,当且仅当平均数n÷j为整数且最小数>0
偶数j可以是加数个数,当且仅当平均数n÷j小数部分为0.5且最小数>0
对给定的n,满足前述的j唯一确定一种连加方法,故j的种数cnt即为所求

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

E3026 排版
First AC: 2018-02-17 Latest Modification: 2018-03-15

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,M,len,tmp,suml,cnt;
  4. char c;
  5. queueq,r;
  6. string s,t;
  7. int i,j,k;
  8. int main()
  9. {
  10.     cin>>T;
  11.     for(i=0;i<T;++i){ cin>>M;
  12.         getchar();
  13.         getline(cin,s);
  14.         len=s.length();
  15.         for(j=0;j<len;++j){
  16.             if(s[j]!=' ')t+=s[j];
  17.             else if(t.length())q.push(t),t="";
  18.         }
  19.         if(t.length())q.push(t),t="";
  20.         tmp=cnt=suml=0;
  21.         cout<<"case #"<<i<<":\n"; while(1){ if(q.empty()||tmp+q.front().length()>M){
  22.                 if(q.empty()){
  23.                     cout<<r.front(),r.pop();
  24.                     while(!r.empty())cout<<' '<<r.front(),r.pop();
  25.                     cout<<endl;
  26.                     break;
  27.                 }
  28.                 else{
  29.                     cout<<r.front(),r.pop();
  30.                     --cnt,suml=M-suml;
  31.                     int tmp1=suml/cnt,tmp2=suml%cnt,tmp3=cnt-tmp2;
  32.                     for(j=0;j<tmp3;++j){
  33.                         for(k=0;k<tmp1;++k)cout<<' ';
  34.                         cout<<r.front(),r.pop();
  35.                     }
  36.                     for(j=0;j<tmp2;++j){
  37.                         for(k=0;k<=tmp1;++k)cout<<' ';
  38.                         cout<<r.front(),r.pop();
  39.                     }
  40.                     cout<<endl;
  41.                 }
  42.                 tmp=cnt=suml=0;
  43.             }
  44.             else{
  45.                 ++cnt;
  46.                 suml+=q.front().length();
  47.                 tmp+=q.front().length()+1;
  48.                 r.push(q.front()),q.pop();
  49.             }
  50.         }
  51.     }
  52.     return 0;
  53. }

E3027 抽奖
First AC: 2017-12-09 Latest Modification: 2017-12-09

  1. #include
  2. using namespace std;
  3. int T,m,n,cnt;
  4. int a[50001];
  5. int i,j;
  6. int gcdj(int m,int n)
  7. {
  8.     int q=1;
  9.     while(q)q=m%n,m=n,n=q;
  10.     if(m==1)return 1;
  11.     return 0;
  12. }
  13. int main()
  14. {
  15.     cin>>T;
  16.     for(i=0;i<T;++i){ cin>>m>>n;
  17.         for(cnt=0,j=1;j<=m;++j)if(gcdj(m,j))a[++cnt]=j;
  18.         a[0]=a[cnt];
  19.         cout<<"case #"<<i<<":\n"<<a[n%cnt]+n/cnt*m<<endl;
  20.     }
  21.     return 0;
  22. }

E3028 构造多项式
First AC: 2017-11-14 Latest Modification: 2018-06-08

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

E3029 不重复正整数
First AC: 2018-04-12 Latest Modification: 2018-04-12

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,m;
  4. int i;
  5. int find(int n,int m)
  6. {
  7.     if(n<0)return 0;
  8.     if(n<1)return 1;
  9.     if(n<2&&m>0)return 1;
  10.     if(m<1)return 0; int rst=0; for(int i=m;i;--i)rst+=find(n-i,i-1); return rst; } int main() { cin>>T;
  11.     for(i=0;i<T;++i){ cin>>n>>m;
  12.         cout<<"case #"<<i<<":\n"<<find(n,m)<<endl;
  13.     }
  14.     return 0;
  15. }

E3030 天黑请闭眼
First AC: 2017-10-31 Latest Modification: 2018-06-08

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

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

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,len;
  4. string s,t;
  5. int i,j,k;
  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){ tmp=10*tmp+s[i]-'0'; r+=(char)(tmp/2+'0'); tmp&=1; } while(len=r.length(),len>1&&r[0]=='0')
  12.         r=r.substr(1,len);
  13.     s=r;
  14. }
  15. void mul()
  16. {
  17.     /* s*=2 */
  18.     string r="";
  19.     int tmp=0,len=s.length();
  20.     for(int i=len-1;i>=0;--i){
  21.         tmp=(s[i]-'0')*2+tmp;
  22.         r=(char)(tmp%10+'0')+r;
  23.         tmp/=10;
  24.     }
  25.     if(tmp)r="1"+r;
  26.     while(len=r.length(),len>1&&r[0]=='0')
  27.         r=r.substr(1,len);
  28.     s=r;
  29. }
  30. void plu()
  31. {
  32.     /* s+=1 */
  33.     int len=s.length(),i;
  34.     for(i=len-1;i>=0;--i){
  35.         if(s[i]<'9'){++s[i];break;}
  36.         s[i]='0';
  37.     }
  38.     if(i<0)s="1"+s; } int main() { cin>>T;
  39.     for(i=0;i<T;++i){ cin>>s;
  40.         cout<<"case #"<<i<<":\n";
  41.         if(s=="0"){cout<<"0\n";continue;} t=""; while(s!="1"){ if((s[s.length()-1]-'0')&1)t+='1'; else t+='0'; div(); } t+="1",s=""; while(len=t.length(),len>1&&t[0]=='0')
  42.             t=t.substr(1,len);
  43.         len=t.length();
  44.         for(j=0;j<len;++j){
  45.             mul();
  46.             if(t[j]!='0')plu();
  47.         }
  48.         cout<<s<<endl;
  49.     }
  50.     return 0;
  51. }

E3032 是坚挺数吗?
First AC: 2017-12-11 Latest Modification: 2017-12-11

  1. #include
  2. using namespace std;
  3. int a[10001];
  4. int T,cnt,n;
  5. int i;
  6. void del(int n)
  7. {
  8.     int cnt=0;
  9.     for(int i=1;i<10001;++i){
  10.         if(a[i]&&++cnt==n)cnt=0,a[i]=0;
  11.     }
  12. }
  13. int main()
  14. {
  15.     for(i=1;i<10001;++i)a[i]=i;
  16.     for(i=2;i<2000;++i)del(i);
  17.     for(cnt=i=1;i<10001;++i)if(a[i])a[i]=cnt++; cin>>T;
  18.     for(i=0;i<T;++i){ cin>>n;
  19.         cout<<"case #"<<i<<":\n";
  20.         if(a[n])cout<<"Yes "<<a[n]<<endl;
  21.         else cout<<"No\n";
  22.     }
  23.     return 0;
  24. }

E3033 删除子串
First AC: 2017-12-24 Latest Modification: 2018-06-08

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

E3034 数字拆分
First AC: 2017-12-11 Latest Modification: 2017-12-11

  1. #include
  2. using namespace std;
  3. long long f[1000001]={0,1,2};
  4. long long i,n;
  5. int T;
  6. int main()
  7. {
  8.     for(i=3;i<1000001;++i){ if(i&1)f[i]=f[i-1]; else f[i]=(f[i-2]+f[i>>1])%1000000000;
  9.     }
  10.     cin>>T;
  11.     for(i=0;i<T;++i)cin>>n,cout<<"case #"<<i<<":\n"<<f[n]<<endl;
  12.     return 0;
  13. }

E3035 次大黑区域
First AC: 2017-12-26 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,w,h,r,l,tmp,maxn,maxm,i,j,k;
  4. char a[105][105];
  5. int cnt(int l,int r)
  6. {
  7.     if(a[l][r]=='0'||l==0||r==0||l>h||r>w)return 0;
  8.     if(a[l-1][r]-'0'||a[l][r-1]-'0'||a[l][r+1]-'0'||a[l+1][r]-'0'){
  9.         a[l][r]='0';
  10.         return cnt(l-1,r)+cnt(l,r-1)+cnt(l,r+1)+cnt(l+1,r)+1;
  11.     }
  12.     a[l][r]='0';
  13.     return 1;
  14. }
  15. int main()
  16. {
  17.     cin>>T;
  18.     for(k=0;k<T;++k){ memset(a,'0',sizeof(a)); maxn=maxm=0; cin>>h>>w;
  19.         for(i=1;i<=h;++i)for(j=1;j<=w;++j)cin>>a[i][j];
  20.         for(i=1;i<=h;++i)for(j=1;j<=w;++j){ tmp=cnt(i,j); if(tmp>maxn)maxm=maxn,maxn=tmp;
  21.             else if(tmp>maxm&&tmp<maxn)maxm=tmp;
  22.         }
  23.         cout<<"case #"<<k<<":\n"<<maxm<<endl;
  24.     }
  25.     return 0;
  26. }

E3036 按数据中1的位数排序
First AC: 2017-12-06 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,cnt,tmp,flag;
  4. int i,j,k;
  5. struct data{
  6.     long long sum,sum0;
  7.     int num;
  8. }a[10001];
  9. bool cmp(data a,data b)
  10. {
  11.     if(a.num-b.num)return a.num>b.num;
  12.     return a.sum0<b.sum0; } int main() { cin>>T;
  13.     for(i=0;i<T;++i){ cin>>n;
  14.         for(j=0;j<n;++j){ cin>>a[j].sum;
  15.             a[j].sum0=a[j].sum;
  16.             if(a[j].sum>0){
  17.                 cnt=0;
  18.                 for(k=0;k<64;++k){
  19.                     tmp=a[j].sum%2;
  20.                     if(tmp)++cnt;
  21.                     a[j].sum/=2;
  22.                 }
  23.                 a[j].num=cnt;
  24.             }
  25.             else if(a[j].sum<0){
  26.                 a[j].sum*=-1,cnt=1,flag=1;
  27.                 for(k=0;k<63;++k){
  28.                     tmp=a[j].sum%2;
  29.                     if(flag){if(tmp)flag=0,++cnt;}
  30.                     else if(!tmp)++cnt;
  31.                     a[j].sum/=2;
  32.                 }
  33.                 a[j].num=cnt;
  34.             }
  35.             else if(a[j].sum==0){a[j].num=0;continue;}
  36.         }
  37.         sort(a,a+n,cmp);
  38.         cout<<"case #"<<i<<":\n";
  39.         for(j=0;j<n-1;++j)cout<<a[j].sum0<<' ';
  40.         cout<<a[n-1].sum0<<endl;
  41.     }
  42.     return 0;
  43. }

E3037 十六进制加法
First AC: 2017-11-11 Latest Modification: 2018-03-09

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,c[501],d[501],e[501];
  4. string a,b;
  5. int lena,lenb,num;
  6. int i,j,k;
  7. int main()
  8. {
  9.     cin>>T; 
  10.     for(k=0;k<T;++k){ cin>>a>>b;
  11.         if(a=="0"&&b=="0"){cout<<"case #"<<k<<":\n0\n";continue;}
  12.         cout<<"case #"<<k<<":\n";
  13.         for(i=0;i<501;++i)c[i]=d[i]=e[i]=0; num=0,lena=a.length(),lenb=b.length(); for(i=lena-1,j=499;i>=0;--i,--j)
  14.             if(a[i]>='0'&&a[i]<='9')c[j]=(int)(a[i]-'0'); else c[j]=(int)(a[i]-'A'+10); for(i=lenb-1,j=499;i>=0;--i,--j)
  15.             if(b[i]>='0'&&b[i]<='9')d[j]=(int)(b[i]-'0'); else d[j]=(int)(b[i]-'A'+10); for(i=499;i>=0;--i)
  16.             if(c[i]+d[i]+num>15)e[i+1]=c[i]+d[i]+num-16,num=1;
  17.             else e[i+1]=c[i]+d[i]+num,num=0;
  18.         for(i=0;i<501;++i)if(e[i]!=0)break;
  19.         for(j=i;j<501;++j) if(e[j]>=0&&e[j]<=9)cout<<e[j];
  20.             else cout<<(char)(e[j]-10+'A');
  21.         cout<<endl;
  22.     }
  23.     return 0;
  24. }

E3038 构造字典序最小字符串
First AC: 2017-12-31 Latest Modification: 2018-03-15

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,l,r;
  4. char a[2001],b[2001];
  5. int i,j,k;
  6. int main()
  7. {
  8.     cin>>T;
  9.     for(k=0;k<T;++k){ cin>>n;
  10.         scanf("%s",a);
  11.         j=l=0,r=n-1;
  12.         while(j<n){
  13.             if(a[l]<a[r])b[j]=a[l],++l; else if(a[l]>a[r])b[j]=a[r],--r;
  14.             else for(i=1;;++i){
  15.                 if(l+i>=r-i){b[j]=a[l],++l;break;}
  16.                 if(a[l+i]>a[r-i]){b[j]=a[r],--r;break;}
  17.                 else if(a[l+i]<a[r-i]){b[j]=a[l],++l;break;}
  18.             }
  19.             ++j;
  20.         }
  21.         cout<<"case #"<<k<<":\n";
  22.         for(i=0;i<n;++i)cout<<b[i];
  23.         cout<<endl;
  24.     }
  25.     return 0;
  26. }

E3039 按整数最高位的值排序
First AC: 2017-12-05 Latest Modification: 2018-03-07

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

E3040 非重复二进制串
First AC: 2018-01-01 Latest Modification: 2018-03-09

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,cnt,tmp,rst;
  4. int a[32];
  5. int i,j,k;
  6. int main()
  7. {
  8.     cin>>T;
  9.     for(i=0;i<T;++i){ cin>>n;
  10.         cnt=rst=0;
  11.         while(n)a[cnt++]=n&1,n>>=1;
  12.         for(j=0;j<cnt;++j){
  13.             for(tmp=k=1;j+k<cnt;++k){ if(a[j+k]!=a[j+k-1])++tmp; else break; } if(tmp>rst)rst=tmp;
  14.         }
  15.         cout<<"case #"<<i<<":\n"<<rst<<endl;
  16.     }
  17.     return 0;
  18. }

E3041 分数的加减运算
First AC: 2018-02-19 Latest Modification: 2018-02-19

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,len;
  4. string s;
  5. long long tmp;
  6. long long up,dn,flag;
  7. long long tup,tdn,tflag;
  8. int i,j;
  9. long long gcd(long long a,long long b)
  10. {
  11.     long long c=1;
  12.     while(c)c=a%b,a=b,b=c;
  13.     return a;
  14. }
  15. int main()
  16. {
  17.     cin>>T;
  18.     for(i=0;i<T;++i){ cin>>n>>s;
  19.         s='+'+s;
  20.         len=s.length();
  21.         j=0,up=0,dn=1,flag=1;
  22.         while(n--){
  23.             tup=tdn=0;
  24.             for(;;++j){
  25.                 if(s[j]=='+')tflag=1;
  26.                 else if(s[j]=='-')tflag=0;
  27.                 else if(s[j]=='/'){++j;break;}
  28.                 else tup=10*tup+s[j]-'0';
  29.             }
  30.             for(;;++j){
  31.                 if(j==len)break;
  32.                 else if(s[j]=='+')break;
  33.                 else if(s[j]=='-')break;
  34.                 else tdn=10*tdn+s[j]-'0';
  35.             }
  36.             tmp=gcd(tup,tdn);
  37.             tup/=tmp,tdn/=tmp;
  38.             if(flag){
  39.                 if(tflag)up=up*tdn+dn*tup;
  40.                 else{
  41.                     up=up*tdn-dn*tup;
  42.                     if(up<0)up*=-1,flag=0;
  43.                 }
  44.             }
  45.             else{
  46.                 if(tflag){
  47.                     up=tup*dn-tdn*up;
  48.                     if(up<0)up*=-1;
  49.                     else flag=1;
  50.                 }
  51.                 else up=up*tdn+dn*tup;
  52.             }
  53.             dn*=tdn,tmp=gcd(up,dn),up/=tmp,dn/=tmp;
  54.         }
  55.         cout<<"case #"<<i<<":\n";
  56.         if(!flag)cout<<'-';
  57.         cout<<up;
  58.         if(dn!=1)cout<<'/'<<dn;
  59.         cout<<endl;
  60.     }
  61.     return 0;
  62. }

E3042 4个值的和为0 (II)
First AC: 2018-07-17 Latest Modification: 2018-07-17

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,s,tmp,rst;
  4. int a[1000];
  5. vector< pair<int,int> >v[200000];
  6. vector< pair<int,int> >::iterator it;
  7. int i,j;
  8. int main()
  9. {
  10.     cin>>n>>s;
  11.     for(i=0;i<n;++i)cin>>a[i];
  12.     for(i=0;i<n;++i){
  13.         for(j=i+1;j<n;++j)
  14.             v[a[i]+a[j]].push_back(pair<int,int>(i,j));
  15.     }
  16.     for(i=0;i<n;++i){
  17.         for(j=i+1;j<n;++j){ tmp=s-a[i]-a[j]; for(it=v[tmp].begin();it!=v[tmp].end();++it){ if(it->first>j)++rst;
  18.             }
  19.         }
  20.     }
  21.     cout<<rst;
  22.     return 0;
  23. }

E3043 最大公约数
First AC: 2017-10-17 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,a,b;
  4. int i;
  5. int main()
  6. {
  7.     cin>>T;
  8.     for(i=0;i<T;++i){ cin>>a>>b;
  9.         cout<<"case #"<<i<<":\n"<<__gcd(a,b)<<endl;
  10.     }
  11.     return 0;
  12. }

E3044 字符串的幂
First AC: 2017-11-20 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n;
  4. string s;
  5. int i;
  6. int main()
  7. {
  8.     cin>>T;
  9.     for(i=0;i<T;++i){ cin>>s>>n;
  10.         cout<<"case #"<<i<<":\n";
  11.         while(n--)cout<<s;
  12.         cout<<endl;
  13.     }
  14.     return 0;
  15. }

E3045 学生信息处理
First AC: 2017-12-05 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n;
  4. int i,j;
  5. struct data{
  6.     long long num;
  7.     string name;
  8.     int score1,score2,score3,score;
  9. }a[10001];
  10. bool cmp(data a,data b)
  11. {
  12.     if(a.score-b.score)return a.score>b.score;
  13.     return a.num<b.num; } int main() { cin>>T;
  14.     for(i=0;i<T;++i){ cin>>n;
  15.         for(j=0;j<n;++j){ cin>>a[j].num>>a[j].name>>a[j].score1
  16.                >>a[j].score2>>a[j].score3;
  17.             a[j].score=a[j].score1+a[j].score2+a[j].score3;
  18.         }
  19.         sort(a,a+n,cmp);
  20.         cout<<"case #"<<i<<":\n";
  21.         for(j=0;j<n;++j)
  22.             cout<<a[j].num<<' '<<a[j].name<<' '<<a[j].score1
  23.                 <<' '<<a[j].score2<<' '<<a[j].score3<<endl;
  24.     }
  25.     return 0;
  26. }

E3046 单向链表中的节点删除
First AC: 2018-04-05 Latest Modification: 2018-04-05

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,m;
  4. struct node{
  5.     int n;
  6.     node *next;
  7. };
  8. node *head;
  9. int i;
  10. void ins(int n)
  11. {
  12.     if(!head){
  13.         head=new node;
  14.         head->n=n;
  15.         head->next=0;
  16.         return;
  17.     }
  18.     node *tmp=head;
  19.     while(tmp->next)tmp=tmp->next;
  20.     tmp->next=new node;
  21.     tmp=tmp->next;
  22.     tmp->n=n;
  23.     tmp->next=0;
  24. }
  25. void del(int n)
  26. {
  27.     while(head&&head->n==n)head=head->next;
  28. }
  29. void pri(int n)
  30. {
  31.     if(head){
  32.         cout<n;
  33.         head=head->next;
  34.         while(head){
  35.             if(head->n!=n)cout<<' '<n;
  36.             head=head->next;
  37.         }
  38.     }
  39.     cout<<endl; } int main() { cin>>T;
  40.     for(i=0;i<T;++i){ cin>>n;
  41.         head=0;
  42.         while(n--)cin>>m,ins(m);
  43.         cin>>m;
  44.         del(m);
  45.         cout<<"case #"<<i<<":\n";
  46.         pri(m);
  47.     }
  48.     return 0;
  49. }

E3047 最小公倍数
First AC: 2017-11-11 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll T,a,b;
  5. ll i;
  6. int main()
  7. {
  8.     cin>>T;
  9.     for(i=0;i<T;++i){ cin>>a>>b;
  10.         cout<<"case #"<<i<<":\n"<<a*b/__gcd(a,b)<<endl;
  11.     }
  12.     return 0;
  13. }

E3048 单词出现次数
First AC: 2017-12-03 Latest Modification: 2019-03-20

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

E3049 Hosts排序
First AC: 2018-01-02 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n;
  4. struct data{
  5.     int a,b,c,d;
  6.     string s;
  7. }f[1001];
  8. int i,j,k;
  9. bool cmp(data m,data n)
  10. {
  11.     if(m.a!=n.a)return m.a>n.a;
  12.     if(m.b!=n.b)return m.b>n.b;
  13.     if(m.c!=n.c)return m.c>n.c;
  14.     if(m.d!=n.d)return m.d>n.d;
  15.     return m.s<n.s; } int main() { cin>>T;
  16.     for(i=0;i<T;++i){ cin>>n;
  17.         for(j=0;j<n;++j){ scanf("%d.%d.%d.%d",&f[j].a,&f[j].b,&f[j].c,&f[j].d); cin>>f[j].s;
  18.         }
  19.         sort(f,f+n,cmp);
  20.         cout<<"case #"<<i<<":\n";
  21.         for(j=0;j<n;++j){
  22.             printf("%d.%d.%d.%d ",f[j].a,f[j].b,f[j].c,f[j].d);
  23.             cout<<f[j].s<<endl;
  24.         }
  25.     }
  26.     return 0;
  27. }

E3050 链表整理
First AC: 2018-04-05 Latest Modification: 2018-04-05

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n1,n2,tmp;
  4. int a[1000];
  5. int i,j,k;
  6. int main()
  7. {
  8.     cin>>T;
  9.     for(i=0;i<T;++i){ cin>>n1>>n2;
  10.         for(j=0;j<n1;++j)cin>>a[j];
  11.         for(j=0;j<n2;++j){ cin>>tmp;
  12.             for(k=0;k<n1;++k)if(a[k]==tmp)a[k]=9876;
  13.         }
  14.         cout<<"case #"<<i<<":\n";
  15.         for(j=0;j<n1;++j)
  16.             if(a[j]!=9876){
  17.                 cout<<a[j];
  18.                 break;
  19.             }
  20.         for(k=j+1;k<n1;++k)
  21.             if(a[k]!=9876)cout<<' '<<a[k];
  22.         cout<<endl;
  23.     }
  24.     return 0;
  25. }

E3051 台阶走法数
First AC: 2017-11-25 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long a[51]={0,1,2,4,8};
  4. int T,n,i;
  5. int main()
  6. {
  7.     for(i=5;i<51;++i){ a[i]=a[i-1]+a[i-2]+a[i-3]+a[i-4]; } for(cin>>T,i=0;i<T;++i){ cin>>n;
  8.         cout<<"case #"<<i<<":\n"<<a[n]<<endl;
  9.     }
  10.     return 0;
  11. }

E3052 最小不重复数
First AC: 2017-11-23 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string s;
  4. char a[105];
  5. int T,len,cnt,flag,num,n,circle;
  6. int i,j,k,r;
  7. int main()
  8. {
  9.     cin>>T;
  10.     for(i=0;i<T;++i){ cin>>s;
  11.         cout<<"case #"<<i<<":\n"; memset(a,'0',sizeof(a)); len=s.length(),cnt=105,flag=1,n=0; for(j=len;j>0;)a[--cnt]=s[--j];
  12.         for(j=104;flag;--j){
  13.             if(a[j]=='9')a[j]='0';
  14.             else ++a[j],--flag;
  15.         }
  16.         for(circle=1;circle;){
  17.             circle=num=0;
  18.             for(j=cnt;j<104;++j){ if(a[j]==a[j+1]){ ++circle; if(a[j]=='9'){ ++n; for(k=j,flag=-1;k>cnt;--k){
  19.                             if(a[k]+a[k-1]-2*'0'!=17){flag=k;break;}
  20.                         }
  21.                         if(flag==-1){
  22.                             if(a[cnt]=='9'){
  23.                                 for(k=cnt-1,num=1;k<105;++k){
  24.                                     if(num)a[k]='1',--num;
  25.                                     else a[k]='0',++num;
  26.                                 }
  27.                             }
  28.                             else{
  29.                                 a[cnt]='9';
  30.                                 for(k=cnt+1;k<105;++k){
  31.                                     if(num)a[k]='1',--num;
  32.                                     else a[k]='0',++num;
  33.                                 }
  34.                             }
  35.                         }
  36.                         else{ 
  37.                             if(a[flag]=='9')++a[flag-1],k=flag;
  38.                             else ++a[flag],k=flag+1;
  39.                             for(;k<105;++k){
  40.                                 if(num)a[k]='1',--num;
  41.                                 else a[k]='0',++num;
  42.                             }
  43.                         }
  44.                     }
  45.                     else{
  46.                         ++n,++a[j+1];
  47.                         for(k=j+2;k<105;++k){
  48.                             if(num)a[k]='1',--num;
  49.                             else a[k]='0',++num;
  50.                         }
  51.                     }
  52.                     break;
  53.                 }
  54.             }
  55.         }
  56.         for(j=num=0;j<105;++j){
  57.             if(num)cout<<a[j];
  58.             else if(a[j]!='0')cout<<a[j],++num;
  59.         }
  60.         cout<<endl;
  61.     }
  62.     return 0;
  63. }

E3053 神秘信息
First AC: 2017-12-24 Latest Modification: 2018-03-09

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,len,cnt,num;
  4. char tmp;
  5. long long rst,base;
  6. string s;
  7. bool a[125];
  8. int i,j,k;
  9. int jdg(char c)
  10. {
  11.     if((c>='0'&&c<='9')||(c>='a'&&c<='z')||(c>='A'&&c<='Z'))return 1; return 0; } int main() { cin>>T;
  12.     for(i=0;i<T;++i){ cin>>s;
  13.         len=s.length();
  14.         memset(a,1,sizeof(a));
  15.         for(cnt=j=0;j<len;++j)if(a[s[j]])a[s[j]]=0,++cnt;
  16.         cout<<"case #"<<i<<":\n";
  17.         if(cnt==1)cout<<pow(2,len)-1<<endl;
  18.         else{
  19.             memset(a,1,sizeof(a));
  20.             tmp=s[0],s[0]=1,a[tmp]=0;
  21.             for(j=1;j<len;++j)if(s[j]==tmp)s[j]=1;
  22.             for(j=1;j<len;++j){
  23.                 if(a[s[j]]&&jdg(s[j])){
  24.                     tmp=s[j],s[j]=0,a[tmp]=0;
  25.                     for(k=j+1;k<len;++k)if(s[k]==tmp)s[k]=0;
  26.                     break;
  27.                 }
  28.             }
  29.             for(num=j=2;j<len;++j){
  30.                 if(a[s[j]]&&jdg(s[j])){
  31.                     tmp=s[j],s[j]=num,a[tmp]=0;
  32.                     for(k=j+1;k<len;++k)if(s[k]==tmp)s[k]=num; ++num; } } for(j=len-1,rst=1,base=1;j>=0;--j){
  33.                 rst+=base*s[j],base*=cnt;
  34.             }
  35.             cout<<rst-1<<endl;
  36.         }
  37.     }
  38.     return 0;
  39. }

E3054 波兰表达式
First AC: 2017-12-16 Latest Modification: 2018-04-01

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,len,flag,i,cnt;
  4. char a[15],c;
  5. double num,tmp1,tmp2;
  6. int sig[50];
  7. stackm;
  8. stackn;
  9. int main()
  10. {
  11.     cin>>T;
  12.     for(i=0;i<T;++i){ while(1){ cin>>a;
  13.             len=strlen(a);
  14.             flag=1;
  15.             if(len==1){
  16.                 switch(a[0]){
  17.                     case '+':case '-': case '*':case '/':
  18.                     m.push(a[0]);flag=0;++cnt;break;
  19.                 }
  20.             }
  21.             if(flag){
  22.                 num=atof(a);
  23.                 n.push(num);
  24.                 ++sig[cnt];
  25.             }
  26.             while(sig[cnt]>1&&m.size()&&n.size()>1){
  27.                 tmp2=n.top();
  28.                 n.pop();
  29.                 tmp1=n.top();
  30.                 n.pop();
  31.                 c=m.top();
  32.                 m.pop();
  33.                 switch(c){
  34.                     case '+':n.push(tmp1+tmp2);break;
  35.                     case '-':n.push(tmp1-tmp2);break;
  36.                     case '*':n.push(tmp1*tmp2);break;
  37.                     case '/':n.push(tmp1/tmp2);break;
  38.                 }
  39.                 sig[cnt]=0,++sig[--cnt];
  40.             }
  41.             c=getchar();
  42.             if(c=='\n'){
  43.                 num=n.top();
  44.                 n.pop();
  45.                 printf("case #%d:\n%.6f\n",i,num);
  46.                 cnt=0;
  47.                 break;
  48.             }
  49.         }
  50. }
  51. return 0;
  52. }

E3055 字符频率
First AC: 2017-12-01 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,len;
  4. string s;
  5. int i,j;
  6. double p[26];
  7. struct data{
  8.     char c,d;
  9.     double pos;
  10.     int cap;
  11. }a[101];
  12. bool cmp(data a,data b)
  13. {
  14.     if(a.pos!=b.pos)return a.pos>b.pos;
  15.     if(a.d!=b.d)return a.d<b.d; return a.c>b.c;
  16. }
  17. int main()
  18. {
  19.     cin>>T;
  20.     for(i=0;i<T;++i){
  21.         for(j=0;j<26;++j)cin>>p[j];
  22.         cin>>s;
  23.         len=s.length();
  24.         for(j=0;j<len;++j){ a[j].c=a[j].d=s[j]; if(s[j]>='a')a[j].pos=p[s[j]-'a'],a[j].cap=0;
  25.             else a[j].pos=p[s[j]-'A'],a[j].cap=1,a[j].d+=32;
  26.         }
  27.         sort(a,a+len,cmp);
  28.         cout<<"case #"<<i<<":\n";
  29.         for(j=0;j<len;++j)cout<<a[j].c;
  30.         cout<<endl;
  31.     }
  32.     return 0;
  33. }

E3056 链表查询
First AC: 2018-04-05 Latest Modification: 2018-04-05

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef struct Node
  4. {
  5.     int value;
  6.     struct Node *next;
  7. }NODE;
  8. NODE *FindLastNthNode(NODE *h,int n)
  9. {
  10.     NODE *tmp=h;
  11.     int cnt=1;
  12.     while(tmp->next)tmp=tmp->next,++cnt;
  13.     if(cnt<n)return NULL; cnt-=n; tmp=h; while(cnt--)tmp=tmp->next;
  14.     return tmp;
  15. }
  16. static unsigned long next=1;
  17. int RND()
  18. {
  19.     next=next*1103515245+12345;
  20.     return (unsigned)(next/65536)%32768;
  21. }
  22. void SETSEED(unsigned seed)
  23. {
  24.     next = seed;
  25. }
  26. void solve()
  27. {
  28.     int i,s,n,m,t;
  29.     NODE *head=0,*p,*tail;
  30.     scanf("%d%d%d%d",&s,&t,&m,&n);
  31.     SETSEED(s);
  32.     for(i=0;i<t;i++){ p=(NODE*)malloc(sizeof(NODE)); p->value=RND()%m;
  33.         p->next=0;
  34.         if(head==0)head=p;
  35.         else tail->next=p;
  36.         tail=p;
  37.     }
  38.     if(p=FindLastNthNode(head,n))
  39.         printf("%d:",p->value);
  40.     else printf("NONE:");
  41.     n=0;
  42.     while(head){
  43.         p=head;
  44.         head=head->next;
  45.         if(t<100||t>100&&n<100){ printf("%d",p->value);
  46.             if(head)printf(" ");
  47.         }
  48.         n++;
  49.         free(p);
  50.     }
  51.     printf("\n");
  52. }
  53. int main()
  54. {
  55.     int i,t;
  56.     scanf("%d\n",&t);
  57.     for(i=0;i<t;i++){
  58.         printf("case #%d:\n",i);
  59.         solve();
  60.     }
  61.     return 0;
  62. }

E3057 素数进制A+B
First AC: 2018-07-11 Latest Modification: 2018-07-11

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,len1,len2,cnt;
  4. char s1[100],s2[100];
  5. int num1[26],num2[26];
  6. int base[25]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
  7. int cas,i,j;
  8. int main()
  9. {
  10.     cin>>T;
  11.     for(cas=0;cas<T;++cas){ memset(num1,0,sizeof num1); memset(num2,0,sizeof num2); cin>>s1>>s2;
  12.         cnt=0;
  13.         len1=strlen(s1);
  14.         len2=strlen(s2);
  15.         for(i=len1-1,j=1;i+1;--i){
  16.             if(s1[i]==','){
  17.                 j=1;
  18.                 ++cnt;
  19.             }
  20.             else{
  21.                 num1[cnt]+=(s1[i]-'0')*j;
  22.                 j*=10;
  23.             }
  24.         }
  25.         cnt=0;
  26.         for(i=len2-1,j=1;i+1;--i){
  27.             if(s2[i]==','){
  28.                 j=1;
  29.                 ++cnt;
  30.             }
  31.             else{
  32.                 num2[cnt]+=(s2[i]-'0')*j;
  33.                 j*=10;
  34.             }
  35.         }
  36.         for(i=0;i<25;++i){ num1[i]+=num2[i]; if(num1[i]>=base[i]){
  37.                 num1[i+1]+=num1[i]/base[i];
  38.                 num1[i]%=base[i];
  39.             }
  40.         }
  41.         cout<<"case #"<<cas<<":\n";
  42.         for(i=25;i;--i)if(num1[i])break;
  43.         for(;i;--i)cout<<num1[i]<<",";
  44.         cout<<num1[0]<<endl;
  45.     }
  46.     return 0;
  47. }

E3058 链表运算
First AC: 2017-12-16 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,len,flag,i;
  4. char a[11],c;
  5. double num,tmp1,tmp2;
  6. stackm;
  7. stackn;
  8. int main()
  9. {
  10.     cin>>T;
  11.     for(i=0;i<T;++i){ while(1){ cin>>a;
  12.             len=strlen(a);
  13.             flag=1;
  14.             if(len==1){
  15.                 switch(a[0]){
  16.                     case '+':case '-': case '*':case '/':
  17.                     m.push(a[0]);flag=0;break;
  18.                 }
  19.             }
  20.             if(flag){
  21.                 num=atof(a);
  22.                 n.push(num);
  23.             }
  24.             while(m.size()&&n.size()>1){
  25.                 tmp1=n.top();
  26.                 n.pop();
  27.                 tmp2=n.top();
  28.                 n.pop();
  29.                 c=m.top();
  30.                 m.pop();
  31.                 switch(c){
  32.                     case '+':n.push(tmp1+tmp2);break;
  33.                     case '-':n.push(tmp1-tmp2);break;
  34.                     case '*':n.push(tmp1*tmp2);break;
  35.                     case '/':n.push(tmp1/tmp2);break;
  36.                 }
  37.             }
  38.             c=getchar();
  39.             if(c=='\n'){
  40.                 num=n.top();
  41.                 n.pop();
  42.                 printf("case #%d:\n%.2f\n",i,num);
  43.                 break;
  44.             }
  45.         }
  46.     }
  47.     return 0;
  48. }

E3059 极坐标排序
First AC: 2017-12-26 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct data{
  4.     double p,r;
  5. }a[1001];
  6. int T,n,i,j;
  7. double x,y,t;
  8. bool cmp(data a,data b)
  9. {
  10.     if(a.r!=b.r)return a.r<b.r; return a.p>b.p;
  11. }
  12. int main()
  13. {
  14.     cin>>T;
  15.     for(i=0;i<T;++i){ cin>>n;
  16.         for(j=0;j<n;++j){ cin>>x>>y;
  17.             a[j].p=sqrt(x*x+y*y);
  18.             t=atan2(y,x);
  19.             if(t<0)t+=2*3.14159265358979323846;
  20.             a[j].r=t;
  21.         }
  22.         sort(a,a+n,cmp);
  23.         cout<<"case #"<<i<<":\n";
  24.         for(j=0;j<n;++j)printf("(%.4f,%.4f)\n",a[j].p,a[j].r);
  25.     }
  26.     return 0;
  27. }

E3060 高次方数的尾数
First AC: 2017-10-27 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long a,c;
  4. int T,b,n,maxc,i,j;
  5. int main()
  6. {
  7.     cin>>T;
  8.     for(i=0;i<T;++i){
  9.         cout<<"case #"<<i<<":\n"; cin>>a>>b>>n;
  10.         maxc=pow(10,n),c=a;
  11.         for(j=1;j<b;++j)c=c*a%maxc; for(j=maxc;j>9;j/=10)cout<<c%j/(j/10);
  12.         cout<<endl;
  13.     }
  14.     return 0;
  15. }

E3061 莫尔斯电码
First AC: 2018-03-15 Latest Modification: 2018-03-15

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,len;
  4. string s,t;
  5. int i,j;
  6. void jdg(string s)
  7. {
  8.     if(s==".-")cout<<'A';
  9.     else if(s=="-...")cout<<'B';
  10.     else if(s=="-.-.")cout<<'C';
  11.     else if(s=="-..")cout<<'D';
  12.     else if(s==".")cout<<'E';
  13.     else if(s=="..-.")cout<<'F';
  14.     else if(s=="--.")cout<<'G';
  15.     else if(s=="....")cout<<'H';
  16.     else if(s=="..")cout<<'I';
  17.     else if(s==".---")cout<<'J';
  18.     else if(s=="-.-")cout<<'K';
  19.     else if(s==".-..")cout<<'L';
  20.     else if(s=="--")cout<<'M';
  21.     else if(s=="-.")cout<<'N';
  22.     else if(s=="---")cout<<'O';
  23.     else if(s==".--.")cout<<'P';
  24.     else if(s=="--.-")cout<<'Q';
  25.     else if(s==".-.")cout<<'R';
  26.     else if(s=="...")cout<<'S';
  27.     else if(s=="-")cout<<'T';
  28.     else if(s=="..-")cout<<'U';
  29.     else if(s=="...-")cout<<'V';
  30.     else if(s==".--")cout<<'W';
  31.     else if(s=="-..-")cout<<'X';
  32.     else if(s=="-.--")cout<<'Y';
  33.     else if(s=="--..")cout<<'Z';
  34.     else if(s=="-----")cout<<0;
  35.     else if(s==".----")cout<<1;
  36.     else if(s=="..---")cout<<2;
  37.     else if(s=="...--")cout<<3;
  38.     else if(s=="....-")cout<<4;
  39.     else if(s==".....")cout<<5;
  40.     else if(s=="-....")cout<<6;
  41.     else if(s=="--...")cout<<7;
  42.     else if(s=="---..")cout<<8;
  43.     else if(s=="----.")cout<<9; } int main() { cin>>T;
  44.     for(i=0;i<T;++i){ cin>>s;
  45.         len=s.length()+1;
  46.         s+="/    ";
  47.         cout<<"case #"<<i<<":\n";
  48.         for(j=0;j<len;++j)
  49.             if(s[j]!='/')t+=s[j];
  50.             else{
  51.                 jdg(t);
  52.                 if(s[j+1]=='/'&&s[j+2]=='/'){
  53.                     if(s[j+3]=='/'&&s[j+4]=='/')cout<<'.',j+=4;
  54.                     else cout<<' ',j+=2;
  55.                 }
  56.                 t="";
  57.             }
  58.         cout<<endl;
  59.     }
  60.     return 0;
  61. }

E3065 rxms写摘要
First AC: 2017-12-27 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,N,B,D;
  4. int i,j,k;
  5. struct data{
  6.     string s;
  7.     double b,d,tf,idf,rst;
  8. }a[1005];
  9. bool cmp(data a,data b)
  10. {
  11.     if(a.rst-b.rst<0.000001&&b.rst-a.rst<0.000001){
  12.         int tmp=a.s.length()<b.s.length()?a.s.length():b.s.length();
  13.         for(int i=0;i<tmp;++i)if(a.s[i]-b.s[i])return a.s[i]<b.s[i];
  14.         return a.s.length()<b.s.length(); } return a.rst>b.rst;
  15. }
  16. int main()
  17. {
  18.     cin>>T;
  19.     for(i=1;i<=T;++i){ cin>>N>>B>>D;
  20.         for(j=0;j<N;++j){ cin>>a[j].s>>a[j].b>>a[j].d;
  21.             a[j].tf=a[j].b/B,a[j].idf=log(D/(a[j].d+1));
  22.             a[j].rst=a[j].tf*a[j].idf;
  23.         }
  24.         int tmp=N>20?20:N;
  25.         sort(a,a+N,cmp);
  26.         cout<<"Case #"<<i<<":\n"<<a[0].s;
  27.         for(j=1;j<tmp;++j)cout<<' '<<a[j].s;
  28.         cout<<endl;
  29.     }
  30.     return 0;
  31. }

E3068 rxms换气球
First AC: 2018-02-09 Latest Modification: 2018-02-09

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,i,a,b,c,s;
  4. int main()
  5. {
  6.     cin>>T;
  7.     for(i=1;i<=T;++i){ cin>>a>>b>>c;
  8.         s=a+b+c;
  9.         a%=3,b%=3,c%=3;
  10.         if(a^b&&a+b+c==3)cout<<"Case #"<<i<<":"<<s-1<<endl;
  11.         else cout<<"Case #"<<i<<":"<<s<<endl;
  12.     }
  13.     return 0;
  14. }

E3069 简单的矩形计数
First AC: 2018-02-15 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,a,b,c,d;
  4. long rst;
  5. bool f[100][100];
  6. int i,j;
  7. int main()
  8. {
  9.     cin>>n>>m;
  10.     for(i=0;i<n;++i)for(j=0;j<m;++j)cin>>f[i][j];
  11.     for(a=1;a<n;++a)for(b=0;b<a;++b)for(c=1;c<m;++c)for(d=0;d<c;++d)
  12.         if(f[a][c]&&f[a][d]&&f[b][c]&&f[b][d])++rst;
  13.     cout<<rst;
  14.     return 0;
  15. }

E3070 简单的数学问题
First AC: 2018-12-12 Latest Modification: 2018-12-12
Note: 我的想法是可以利用标准分解将a^b统一表示成c^d,使得c尽可能小
其他人的思路包括:%p存long long、取对数存double、以及python啥都不做
本质上就是一一映射到可以存的结构中,然后去重计数

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long double ld;
  4. int n;
  5. int a,b,c,d;
  6. map<int,int>mp;
  7. int i;
  8. bool ok(int a,int b,int i)
  9. {
  10.     c=pow((ld)a,(ld)1.0/i)+0.3;
  11.     d=i*b;
  12.     int r=1;
  13.     for(int j=0;j<i;++j)r*=c; return r==a; } int main() { while(cin>>n){
  14.         mp.clear();
  15.         for(a=2;a<=100;++a){
  16.             for(b=2;b<=n;++b){
  17.                 bool flag=1;
  18.                 for(i=6;i;--i){
  19.                     if(ok(a,b,i)){
  20.                         mp.insert(pair<int,int>(1000*c+d,0));
  21.                         flag=0;
  22.                         break;
  23.                     }
  24.                 }
  25.             }
  26.         }
  27.         cout<<mp.size()<<endl;
  28.     }
  29.     return 0;
  30. }

E3072 小巴菲特买股票
First AC: 2018-01-01 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,low,m,rst;
  4. int i,j,k;
  5. int main()
  6. {
  7.     cin>>T;
  8.     for(i=0;i<T;++i){ cin>>n>>low;
  9.         rst=0;
  10.         for(j=1;j<n;++j){ cin>>m;
  11.             if(m<low)low=m; else if(m>low)rst=m-low>rst?m-low:rst;
  12.         }
  13.         cout<<"case #"<<i<<":\n"<<rst<<endl;
  14.     }
  15.     return 0;
  16. }

E3073 道路排序
First AC: 2018-01-06 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct data{
  4.     int a,b,c;
  5. }a[19901];
  6. int T,m,n,i,j;
  7. bool cmp(data a,data b)
  8. {
  9.     if(a.c^b.c)return a.c>b.c;
  10.     if(a.a^b.a)return a.a<b.a;
  11.     return a.b<b.b; } int main() { cin>>T;
  12.     for(i=0;i<T;++i){ cin>>m>>n;
  13.         for(j=0;j<n;++j)cin>>a[j].a>>a[j].b>>a[j].c;
  14.         sort(a,a+n,cmp);
  15.         cout<<"case #"<<i<<":\n";
  16.         for(j=0;j<n;++j)printf("(%d,%d,%d)\n",a[j].a,a[j].b,a[j].c);
  17.     }
  18.     return 0;
  19. }

E3074 特殊加密
First AC: 2017-11-15 Latest Modification: 2018-06-08

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

E3075 素进制链表
First AC: 2018-07-11 Latest Modification: 2018-07-11

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll base[]={1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
  5. ll rst[16];
  6. ll T,n;
  7. ll cas,i;
  8. int main()
  9. {
  10.     for(i=1;i<16;++i)base[i]*=base[i-1]; cin>>T;
  11.     for(cas=0;cas<T;++cas){ cin>>n;
  12.         memset(rst,0,sizeof(rst));
  13.         for(i=15;i;--i){
  14.             if(n>=base[i])rst[i]=n/base[i];
  15.             n%=base[i];
  16.         }
  17.         rst[0]=n;
  18.         cout<<"case #"<<cas<<":\n";
  19.         for(i=15;i;--i)if(rst[i])break;
  20.         for(;i+1;--i)cout<<rst[i]<<";";
  21.         cout<<endl;
  22.     }
  23.     return 0;
  24. }

E3076 斐波那契数列
First AC: 2018-01-08 Latest Modification: 2018-01-08

  1. #include
  2. using namespace std;
  3. int T,n;
  4. string f[125]={"0","1","1","2","3","5","8","13",
  5. "21",
  6. "34",
  7. "55",
  8. "89",
  9. "144",
  10. "233",
  11. "377",
  12. "610",
  13. "987",
  14. "1597",
  15. "2584",
  16. "4181",
  17. "6765",
  18. "10946",
  19. "17711",
  20. "28657",
  21. "46368",
  22. "75025",
  23. "121393",
  24. "196418",
  25. "317811",
  26. "514229",
  27. "832040",
  28. "1346269",
  29. "2178309",
  30. "3524578",
  31. "5702887",
  32. "9227465",
  33. "14930352",
  34. "24157817",
  35. "39088169",
  36. "63245986",
  37. "102334155",
  38. "165580141",
  39. "267914296",
  40. "433494437",
  41. "701408733",
  42. "1134903170",
  43. "1836311903",
  44. "2971215073",
  45. "4807526976",
  46. "7778742049",
  47. "12586269025",
  48. "20365011074",
  49. "32951280099",
  50. "53316291173",
  51. "86267571272",
  52. "139583862445",
  53. "225851433717",
  54. "365435296162",
  55. "591286729879",
  56. "956722026041",
  57. "1548008755920",
  58. "2504730781961",
  59. "4052739537881",
  60. "6557470319842",
  61. "10610209857723",
  62. "17167680177565",
  63. "27777890035288",
  64. "44945570212853",
  65. "72723460248141",
  66. "117669030460994",
  67. "190392490709135",
  68. "308061521170129",
  69. "498454011879264",
  70. "806515533049393",
  71. "1304969544928657",
  72. "2111485077978050",
  73. "3416454622906707",
  74. "5527939700884757",
  75. "8944394323791464",
  76. "14472334024676221",
  77. "23416728348467685",
  78. "37889062373143906",
  79. "61305790721611591",
  80. "99194853094755497",
  81. "160500643816367088",
  82. "259695496911122585",
  83. "420196140727489673",
  84. "679891637638612258",
  85. "1100087778366101931",
  86. "1779979416004714189",
  87. "2880067194370816120",
  88. "4660046610375530309",
  89. "7540113804746346429",
  90. "12200160415121876738",
  91. "19740274219868223167",
  92. "31940434634990099905",
  93. "51680708854858323072",
  94. "83621143489848422977",
  95. "135301852344706746049",
  96. "218922995834555169026",
  97. "354224848179261915075",
  98. "573147844013817084101",
  99. "927372692193078999176",
  100. "1500520536206896083277",
  101. "2427893228399975082453",
  102. "3928413764606871165730",
  103. "6356306993006846248183",
  104. "10284720757613717413913",
  105. "16641027750620563662096",
  106. "26925748508234281076009",
  107. "43566776258854844738105",
  108. "70492524767089125814114",
  109. "114059301025943970552219",
  110. "184551825793033096366333",
  111. "298611126818977066918552",
  112. "483162952612010163284885",
  113. "781774079430987230203437",
  114. "1264937032042997393488322",
  115. "2046711111473984623691759",
  116. "3311648143516982017180081",
  117. "5358359254990966640871840"};
  118. int main()
  119. {
  120.     cin>>T;
  121.     for(int i=0;i<T;++i){ cin>>n;
  122.         cout<<"case #"<<i<<":\n"<<f[n]<<endl;
  123.     }
  124.     return 0;
  125. }

E3081 购房还款
First AC: 2017-10-18 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. double d,p,r;
  4. int main()
  5. {
  6.     cin>>d>>p>>r;
  7.     cout<<(long)(0.5+log10(p/(p-d*r/100))/log10(1+r/100));
  8.     return 0;
  9. }

E3082 公式计算
First AC: 2017-10-18 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int x;
  4. int main()
  5. {
  6.     cin>>x;
  7.     if(x<1)cout<<x<<endl;
  8.     else if(x<10)cout<<2*x-1<<endl;
  9.     else cout<<3*x-11<<endl;
  10.     return 0;
  11. }

E3084 最大公约数
First AC: 2017-10-17 Latest Modification: 2018-12-20

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

E3085 统计1的个数
First AC: 2017-10-15 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,i,c;
  4. int main()
  5. {
  6.     cin>>n;
  7.     for(i=1;i<35;i++)if(n%2==1)c++,n/=2;
  8.     cout<<c;
  9.     return 0;
  10. }

E3086 水仙花数
First AC: 2018-01-05 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int i;
  4. int main()
  5. {
  6.     for(i=100;i<1000;++i)
  7.         if(pow(i/100,3)+pow(i%100/10,3)+pow(i%10,3)==i)
  8.             cout<<i<<endl;
  9.     return 0;
  10. }

E3087 牛顿法求解方程
First AC: 2017-12-16 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int cnt;
  4. double x=1.5;
  5. double k(double x){return 6*x*x-8*x+3;}
  6. double rst(double x){return (2*x*x+3)*(x-2);}
  7. int main()
  8. {
  9.     do{
  10.         ++cnt;
  11.         x-=rst(x)/k(x);
  12.     }while(rst(x)>1e-15||-rst(x)>1e-15);
  13.     printf("%.2f %d",x,cnt);
  14.     return 0;
  15. }

E3088 循环移位
First AC: 2017-11-16 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string s;
  4. int n,ls,m,cnt;
  5. int i,j;
  6. int main()
  7. {
  8.     cin>>s>>n,ls=s.length(),m=n%ls;
  9.     cout<<ls<<' ';
  10.     for(i=ls-m;i<ls;++i){
  11.         if(cnt==0&&s[i]!='0')++cnt;
  12.         if(cnt==1)cout<<s[i];
  13.     }
  14.     ls-=m;
  15.     for(i=0;i<ls;++i){
  16.         if(cnt==0&&s[i]!='0')++cnt;
  17.         if(cnt==1)cout<<s[i];
  18.     }
  19.     return 0;
  20. }

E3090 杨辉三角
First AC: 2017-10-22 Latest Modification: 2018-06-08

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

E3092 GDP
First AC: 2017-11-01 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,r;
  4. int main()
  5. {
  6.     cin>>n>>r;
  7.     printf("%.2f",pow(1+r/100.0,n));
  8.     return 0;
  9. }

E3093 最大公约数
First AC: 2017-10-17 Latest Modification: 2018-06-08

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

E3094 反序输出
First AC: 2017-11-04 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,a[20],sum;
  4. int i;
  5. int main()
  6. {
  7.     cin>>n;
  8.     for(i=0;i<n;++i)cin>>a[i],sum+=a[i];
  9.     for(i=n-1;i>0;--i)cout<<a[i]<<" ";
  10.     cout<<a[0]<<endl<<sum;
  11.     printf(" %.2f",sum*1.0/n);
  12.     return 0;
  13. }

E3096 字母数字对应
First AC: 2017-11-17 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string s;
  4. int i;
  5. int main()
  6. {
  7.     cin>>s;
  8.     for(i=0;i<8;++i)switch(s[i]){
  9.         case 'A':case 'B':case 'C':case 'a':case 'b':case 'c':
  10.             cout<<2;break;
  11.         case 'D':case 'E':case 'F':case 'd':case 'e':case 'f':
  12.             cout<<3;break;
  13.         case 'G':case 'H':case 'I':case 'g':case 'h':case 'i':
  14.             cout<<4;break;
  15.         case 'J':case 'K':case 'L':case 'j':case 'k':case 'l':
  16.             cout<<5;break;
  17.         case 'M':case 'N':case 'O':case 'm':case 'n':case 'o':
  18.             cout<<6;break;
  19.         case 'T':case 'U':case 'V':case 't':case 'u':case 'v':
  20.             cout<<8;break;
  21.         case 'P':case 'Q':case 'R':case 'S':case 'p':case 'q':
  22.         case 'r':case 's':
  23.             cout<<7;break;
  24.         default:cout<<9;
  25.     }
  26.     cout<<endl;
  27.     return 0;
  28. }

E3097 字符串排序
First AC: 2017-12-30 Latest Modification: 2018-06-08

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

E3098 字符串的交织
First AC: 2017-11-20 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string s,t;
  4. int ls,lt;
  5. int i;
  6. int main()
  7. {
  8.     cin>>s>>t;
  9.     ls=s.length(),lt=t.length();
  10.     if(ls==lt)for(i=0;i<ls;++i)cout<<s[i]<<t[i]; else if(ls>lt){
  11.         for(i=0;i<lt;++i)cout<<s[i]<<t[i];
  12.         for(;i<ls;)cout<<s[i++];
  13.     }
  14.     else{
  15.         for(i=0;i<ls;++i)cout<<s[i]<<t[i];
  16.         for(;i<lt;)cout<<t[i++];
  17.     }
  18.     return 0;
  19. }

E3101 矩阵转置
First AC: 2017-12-06 Latest Modification: 2017-12-06

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

E3106 骰子概率
First AC: 2018-01-21 Latest Modification: 2018-01-21

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m;
  4. int a[6];
  5. int succ,fail,jdg;
  6. long i,j;
  7. int main()
  8. {
  9.     cin>>n>>m;
  10.     for(i=0;i<100000;++i){
  11.         memset(a,0,sizeof(a));
  12.         for(j=0;j<n;++j)++a[rand()%6];
  13.         for(j=jdg=0;j<6;++j){ if(a[j]>=m){jdg=1;break;}
  14.         }
  15.         jdg? ++succ:++fail;
  16.     }
  17.     printf("%.2f",succ*1.0/(succ+fail));
  18.     return 0;
  19. }

E3107 数据交换
First AC: 2017-11-23 Latest Modification: 2018-06-08

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

E3119 排序
First AC: 2017-10-17 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a[1000],i,j,m,count;
  4. int main()
  5. {
  6.     for(i=0;i<3;i++){ cin>>m;
  7.         a[m]++;
  8.     }
  9.     for(i=0;i<1000;i++){
  10.         if(a[i]!=0){
  11.             count++;
  12.             if(count==3){
  13.                 for(j=0;j<a[i];j++)cout<<i;
  14.                 break;
  15.             }
  16.             else for(j=0;j<a[i];j++)cout<<i<<" ";
  17.         }
  18.     }
  19.     return 0;
  20. }

E3120 整除
First AC: 2017-10-17 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. int main()
  5. {
  6.     cin>>n;
  7.     if(n%15==0)cout<<"Yes";
  8.     else cout<<"No";
  9.     return 0;
  10. }

E3121 素数
First AC: 2017-10-17 Latest Modification: 2018-06-08
Note: 坑数据,最后一个数字后面有一个空格

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,i,count;
  4. int main()
  5. {
  6.     cout<<"101 ";
  7.     for(n=103;n<200;n+=2){
  8.         for(i=3;i<=sqrt(n);i++)if(n%i==0){count++;break;}
  9.         if(count==0)cout<<n<<" ";
  10.         count=0;
  11.     }
  12.     return 0;
  13. }

E3122 最大公约数
First AC: 2017-10-17 Latest Modification: 2018-06-08

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

E3123 二次方程的根
First AC: 2017-10-17 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     ios::sync_with_stdio(false);
  6.     double sqrtdelta,delta;
  7.     int a,b,c;
  8.     while(cin>>a>>b>>c){
  9.         if(a<0)a=-a,b=-b,c=-c;
  10.         delta=b*b-4*a*c;
  11.         if(delta==0)printf("%.6f\n",-(float)b/(2*a));
  12.         else{
  13.             sqrtdelta=sqrt(delta);
  14.             printf("%.6f %.6f\n",-(b+sqrtdelta)/(a<<1)
  15.                 ,(sqrtdelta-b)/(2*a));
  16.         }
  17.     }
  18.     return 0;
  19. }

E3124 单词表
First AC: 2018-03-15 Latest Modification: 2018-03-15

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,len,num;
  4. string s,t;
  5. struct data{
  6.     string s;
  7. }a[250];
  8. int i,j;
  9. bool cmp(data a,data b)
  10. {
  11.     return a.s<b.s; } int main() { cin>>T;
  12.     getchar();
  13.     for(i=0;i<T;i++){
  14.         getline(cin,s);
  15.         len=s.length();
  16.         num=0;
  17.         for(j=0;j<len;++j){
  18.             if(isalpha(s[j]))t+=s[j];
  19.             else if(t!="") a[num++].s=t,t="";
  20.         }
  21.         if(t!="") a[num++].s=t,t="";
  22.         sort(a,a+num,cmp);
  23.         cout<<"case #"<<i<<":\n"<<a[0].s;
  24.         for(j=1;j<num;++j)if(a[j].s!=a[j-1].s)cout<<' '<<a[j].s;
  25.         cout<<endl;
  26.     }
  27.     return 0;
  28. }

E3125 巧克力
First AC: 2017-11-06 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,cnt,num;
  4. long long s;
  5. int a[105];
  6. int i,j,k;
  7. int main()
  8. {
  9.     cin>>T;
  10.     for(i=0;i<T;++i){ s=1,num=0,memset(a,0,sizeof(a)); cin>>n;
  11.         cout<<"case #"<<i<<":\n";
  12.         for(j=0;j<n;++j){cin>>a[j];if(a[j]==1)++num;}
  13.         if(num==0){cout<<"0\n";continue;}
  14.         for(j=0;j<n;++j){
  15.             cnt=2;
  16.             if(a[j]==0){
  17.                 for(k=j+1;k<n;++k){
  18.                     if(a[j]==a[k])++cnt;
  19.                     else break;
  20.                 }
  21.                 if(k==n)break;
  22.                 if(j==0){j=k-1;continue;};
  23.                 s*=cnt,j=k-1;
  24.             }
  25.         }
  26.         cout<<s<<endl;
  27.     }
  28.     return 0;
  29. }

E3126 商品推荐
First AC: 2017-12-23 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,cnt;
  4. long samt[101],mamt;
  5. double spri[101],mpri;
  6. int i,j,k;
  7. struct data{
  8.     string num;
  9.     long amt;
  10.     double pri;
  11.     bool flag;
  12.     int rank;
  13. }a[101];
  14. bool cmp(data a,data b)
  15. {
  16.     if(a.flag-b.flag)return a.flag>b.flag;
  17.     if(a.amt^b.amt)return a.amt>b.amt;
  18.     if(a.pri-b.pri)return a.pri<b.pri;
  19.     return a.rank<b.rank; } int main() { cin>>T;
  20.     for(i=0;i<T;++i){ cin>>n;
  21.         for(j=0;j<n;++j){ a[j].rank=j; cin>>a[j].num>>a[j].amt>>a[j].pri;
  22.             samt[j]=a[j].amt;
  23.             spri[j]=a[j].pri;
  24.         }
  25.         sort(samt,samt+n);
  26.         sort(spri,spri+n);
  27.         if(n&1)mamt=samt[n/2],mpri=spri[n/2];
  28.         else{
  29.             mamt=(samt[n/2]+samt[n/2-1])/2.0;
  30.             mpri=(spri[n/2]+spri[n/2-1])/2.0;
  31.         }
  32.         for(cnt=j=0;j<n;++j){ if(a[j].amt>mamt&&a[j].pri<mpri)
  33.                 a[j].flag=1,++cnt;
  34.             else a[j].flag=0;
  35.         }
  36.         cout<<"case #"<<i<<":\n";
  37.         if(!cnt){
  38.             cout<<"no recommendation\n";
  39.             continue;
  40.         }
  41.         sort(a,a+n,cmp);
  42.         for(j=0;j<cnt;++j)
  43.             cout<<a[j].num<<' '<<a[j].amt<<' '<<a[j].pri<<endl;
  44.     }
  45.     return 0;
  46. }

E3127 字串间距
First AC: 2017-12-22 Latest Modification: 2018-03-15

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,ls,lt,lr;
  4. int ns[85],nt[85],cnts,cntt,rst;
  5. string s,t,r;
  6. bool flag,flags,flagt;
  7. int i,j,k;
  8. int main()
  9. {
  10.     cin>>T;
  11.     for(i=0;i<T;++i){ cin>>s>>t>>r;
  12.         ls=s.length(),lt=t.length(),lr=r.length();
  13.         memset(ns,0,sizeof(ns)),memset(nt,0,sizeof(nt));
  14.         flags=flagt=cnts=cntt=0;
  15.         for(j=0;j<=lr-ls;++j){
  16.             if(r[j]==s[0]){
  17.                 for(flag=k=1;k<ls;++k)if(r[j+k]!=s[k]){flag=0;break;}
  18.                 if(flag)ns[cnts++]=j,flags=1;
  19.             }
  20.         }
  21.         for(j=0;j<=lr-lt;++j){
  22.             if(r[j]==t[0]){
  23.                 for(flag=k=1;k<lt;++k)if(r[j+k]!=t[k]){flag=0;break;}
  24.                 if(flag)nt[cntt++]=j,flagt=1;
  25.             }
  26.         }
  27.         cout<<"case #"<<i<<":\n";
  28.         if(flags&&flagt){
  29.             sort(ns,ns+cnts),sort(nt,nt+cntt);
  30.             if(ns[cnts-1]<=nt[0])rst=max(0,nt[cntt-1]-ns[0]-ls);
  31.             else if(nt[cntt-1]<=ns[0])rst=max(0,ns[cnts-1]-nt[0]-lt);
  32.             else rst=max(0,max(ns[cnts-1]-nt[0]-lt,nt[cntt-1]-ns[0]-ls));
  33.             cout<<rst<<endl;
  34.         }
  35.         else cout<<"0\n";
  36.     }
  37.     return 0;
  38. }

E3128 十进制数列项
First AC: 2017-12-23 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,len,cnt,flag;
  4. string s;
  5. int a[25];
  6. int i,j;
  7. int main()
  8. {
  9.     cin>>T;
  10.     for(i=0;i<T;++i){ cin>>s;
  11.         len=s.length(),cnt=flag=0;
  12.         for(j=len-1;;--j){
  13.             a[cnt++]=s[j]-'0';
  14.             if(j==0){flag=1;break;}
  15.             if(s[j]>s[j-1])break;
  16.         }
  17.         cout<<"case #"<<i<<":\n";
  18.         if(flag){
  19.             sort(a,a+cnt);
  20.             for(j=0;;++j)if(a[j]){
  21.                 cout<<a[j]<<0;
  22.                 a[j]=0;
  23.                 break;
  24.             }
  25.             sort(a,a+cnt);
  26.             for(j=1;j<cnt;++j)cout<<a[j];
  27.             cout<<endl;
  28.             continue;
  29.         }
  30.         sort(a,a+cnt);
  31.         for(j=0;j<len-cnt-1;++j)cout<<s[j];
  32.         for(j=0;j<cnt;++j)if(a[j]>s[len-cnt-1]-'0'){
  33.             cout<<a[j];a[j]=s[len-cnt-1]-'0';
  34.             break;
  35.         }
  36.         sort(a,a+cnt);
  37.         for(j=0;j<cnt;++j)cout<<a[j];
  38.         cout<<endl;
  39.     }
  40.     return 0;
  41. }

E3129 最大最小之差
First AC: 2017-12-10 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,len,cnt,flag,tmp,num;
  4. string s;
  5. int a[10],M[106],m[106],r[106];
  6. int i,j,k;
  7. int main()
  8. {
  9.     cin>>T;
  10.     for(i=0;i<T;++i){ cin>>s;
  11.         len=s.length();
  12.         memset(a,0,40),memset(M,0,424);
  13.         memset(m,0,424),memset(r,0,424);
  14.         for(j=0;j<len;++j)a[s[j]-'0']++;
  15.         for(cnt=105,j=0;j<10;++j)for(k=0;k<a[j];++k)M[cnt--]=j; for(cnt=105,j=9;j>=0;--j)for(k=0;k<a[j];++k)m[cnt--]=j;
  16.         for(flag=num=0,j=105;j;--j){
  17.             tmp=M[j]-m[j]-flag;
  18.             if(tmp<0)r[j]=10+tmp,flag=1;
  19.             else r[j]=tmp,flag=0;
  20.             if(tmp)num=1;
  21.         }
  22.         cout<<"case #"<<i<<":\n";
  23.         if(num==0){cout<<0<<endl;continue;}
  24.         for(j=0;;++j)if(r[j])break;
  25.         for(k=j;k<106;++k)cout<<r[k];
  26.         cout<<endl;
  27.     }
  28.     return 0;
  29. }

E3130 方形码
First AC: 2017-12-23 Latest Modification: 2018-06-08

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

E3131 字母对的频率
First AC: 2017-12-23 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,len,cnt,rst,maxa;
  4. string s;
  5. int a[26][26];
  6. int i,j;
  7. int main()
  8. {
  9.     cin>>T,getchar();
  10.     for(i=0;i<T;++i){
  11.         getline(cin,s);
  12.         len=s.length();
  13.         memset(a,0,sizeof(a));
  14.         for(cnt=maxa=j=0;j<len;++j)if(s[j]>='A'&&s[j]<='Z')s[j]+=32;
  15.         for(j=1;j<len;++j) if(s[j-1]>='a'&&s[j-1]<='z'&&s[j]>='a'&&s[j]<='z'){ ++cnt,a[s[j-1]-'a'][s[j]-'a']++; if(a[s[j-1]-'a'][s[j]-'a']>maxa)
  16.                     maxa=a[s[j-1]-'a'][s[j]-'a'],rst=j;
  17.             }
  18.         cout<<"case #"<<i<<":\n"<<s[rst-1]<<s[rst];
  19.         printf(" %.2f%%\n",a[s[rst-1]-'a'][s[rst]-'a']*100.0/cnt);
  20.     }
  21.     return 0;
  22. }

E3132 寻宝
First AC: 2017-11-11 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a[6][6],b[6][6],c[25],r,q,tr,tq,cnt;
  4. int T;
  5. int i,j;
  6. int main()
  7. {
  8.     cin>>T;
  9.     for(i=0;i<T;++i){
  10.         memset(b,0,sizeof(b));
  11.         memset(c,0,sizeof(c));
  12.         for(j=1;j<6;++j) cin>>a[j][1]>>a[j][2]>>a[j][3]>>a[j][4]>>a[j][5];
  13.         cout<<"case #"<<i<<":\n";
  14.         r=q=0,a[0][0]=11,cnt=0;
  15.         while(1){
  16.             tr=a[r][q]/10,tq=a[r][q]%10;
  17.             if(r==tr&&q==tq){
  18.                 cout<<a[1][1];
  19.                 for(j=1;j<cnt;++j)cout<<' '<<c[j];
  20.                 break;
  21.             }
  22.             if(b[tr][tq]==0){
  23.                 ++b[tr][tq];
  24.                 c[cnt++]=a[tr][tq];
  25.                 r=tr;
  26.                 q=tq;
  27.             }
  28.             else{
  29.                 cout<<"-1";
  30.                 break;
  31.             }
  32.         }
  33.         cout<<endl;
  34.     }
  35.     return 0;
  36. }

E3133 最长回文子串
First AC: 2017-12-23 Latest Modification: 2018-06-08

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

E3134 短信激活码
First AC: 2017-11-04 Latest Modification: 2018-06-08

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

E3135 数据压缩
First AC: 2017-10-23 Latest Modification: 2018-06-08

  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){ cin>>s;
  10.         cout<<"case #"<<i<<":\n";
  11.         len=s.length();
  12.         cnt=1;
  13.         for(j=1;j<=len-1;++j){ if(s[j]==s[j-1])cnt++; else if(cnt>255){
  14.                 cout<<"255"<<s[j-1]<<cnt-255<<s[j-1];
  15.                 cnt=1;
  16.             }
  17.             else cout<<cnt<<s[j-1],cnt=1; } if(cnt>255)cout<<"255"<<s[len-1]<<cnt-255<<s[len-1]<<endl;
  18.         else cout<<cnt<<s[len-1]<<endl;
  19.     }
  20.     return 0;
  21. }

E3136 指数比例
First AC: 2018-01-06 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. #define e 2.71828
  3. using namespace std;
  4. int T,m,cnt;
  5. double sumn;
  6. struct data{
  7.     double n;
  8.     bool rst;
  9. }a[51];
  10. int i,j,k;
  11. bool cmp(data a,data b)
  12. {
  13.     if(a.rst!=b.rst)return a.rst>b.rst;
  14.     return a.n>b.n;
  15. }
  16. int main()
  17. {
  18.     cin>>T;
  19.     for(i=0;i<T;++i){ cin>>m;
  20.         for(sumn=cnt=j=0;j<m;++j)cin>>a[j].n,sumn+=pow(e,a[j].n);
  21.         for(j=0;j<m;++j){ if(pow(e,a[j].n)/sumn>0.5/m)a[j].rst=1,++cnt;
  22.             else a[j].rst=0;
  23.         }
  24.         sort(a,a+m,cmp);
  25.         cout<<"case #"<<i<<":\n";
  26.         for(j=0;j<cnt;++j)printf("%.2f\n",a[j].n);
  27.     }
  28.     return 0;
  29. }

E3137 矩形个数
First AC: 2018-05-11 Latest Modification: 2018-05-11

  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) if(mp[l][j]) ++tmp; if(tmp>=k){
  13.                 ret+=c-j+1;
  14.                 break;
  15.             }
  16.         }
  17.     }
  18.     return ret;
  19. }
  20. int main()
  21. {
  22.     cin>>T;
  23.     for(i=0;i<T;++i){ cin>>r>>c>>n>>k;
  24.         memset(mp,0,sizeof(mp));
  25.         while(n--){
  26.             cin>>x>>y;
  27.             mp[x][y]=1;
  28.         }
  29.         rst=0;
  30.         for(j=1;j<=r;++j)
  31.             for(l=1;l<=c;++l)
  32.                 rst+=cnt(j,l);
  33.         cout<<"case #"<<i<<":\n"<<rst<<endl;
  34.     }
  35.     return 0;
  36. }

E3138 Base64 编码
First AC: 2018-06-08 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,cnt;
  4. char s[100];
  5. int rst[150];
  6. int cas,i,j;
  7. int main()
  8. {
  9.     cin>>T;
  10.     for(cas=0;cas<T;++cas) { cin>>s;
  11.         int l=strlen(s);
  12.         cnt=0;
  13.         for(i=j=0;i<l;++i)
  14.         {
  15.             if(cnt==0)
  16.             {
  17.                 rst[j++]=s[i]/4;
  18.                 rst[j]=s[i]%4*16;
  19.             }
  20.             else if(cnt==1)
  21.             {
  22.                 rst[j++]+=s[i]/16;
  23.                 rst[j]=s[i]%16*4;
  24.             }
  25.             else
  26.             {
  27.                 rst[j++]+=s[i]/64;
  28.                 rst[j++]=s[i]%64;
  29.             }
  30.             cnt=++cnt%3;
  31.         }
  32.         if(j%4)for(j++;j%4;j++)rst[j]=64;
  33.         cout<<"case #"<<cas<<":\n";
  34.         for(i=0;i<j;++i)
  35.             if(rst[i]<26)cout<<(char)('A'+rst[i]);
  36.             else if(rst[i]<52)cout<<(char)('a'+rst[i]-26);
  37.             else if(rst[i]<62)cout<<(char)('0'+rst[i]-52);
  38.             else if(rst[i]==62)cout<<'+';
  39.             else if(rst[i]==63)cout<<'/';
  40.             else cout<<'=';
  41.         cout<<endl;;
  42.     }
  43.     return 0;
  44. }

E3139 鸡兔同笼
First AC: 2017-10-17 Latest Modification: 2018-06-08

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

E3140 另一种阶乘问题
First AC: 2017-10-17 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int i,j,k,n,s=1,R;
  4. int main()
  5. {
  6.     cin>>i;
  7.     while(cin>>n){
  8.         for(j=1;j<=n;j++){
  9.             for(k=1;k<=j;k+=2)s*=k;
  10.             R+=s;
  11.             s=1;
  12.         }
  13.         cout<<R<<endl;
  14.         R=0;
  15.     }
  16.     return 0;
  17. }

E3141 小学生算术
First AC: 2017-10-27 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string m,n;
  4. int a[1000],b[1000],cnt,num;
  5. int i,j,k;
  6. int main()
  7. {
  8.     while(cin>>m>>n,m!="0"||n!="0"){
  9.         cnt=num=0;
  10.         for(i=999,j=m.length()-1;j>=0;--j)a[i--]=(int)(m[j]-'0');
  11.         for(i=999,j=n.length()-1;j>=0;--j)b[i--]=(int)(n[j]-'0');
  12.         for(i=999;i>=0;--i){
  13.             if(a[i]+b[i]+num>9)cnt++,num=1;
  14.             else num=0;
  15.             a[i]=b[i]=0;
  16.         }
  17.         cout<<cnt<<endl;
  18.     }
  19.     return 0;
  20. }

E3142 九九乘法表
First AC: 2017-10-17 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,i,N,cnt;
  4. int main()
  5. {
  6.     cin>>T;
  7.     for(i=0;i<T;i++){ cin>>N;
  8.         if(cnt>0)cout<<endl;
  9.         ++cnt;
  10.         cout<<"1*1=1 1*2=2 1*3=3 1*4=4 1*5=5 1*6=6 1*7=7 1*8=8 1*9=9\n"; if(N>1)cout<<"2*2=4 2*3=6 2*4=8 2*5=10 2*6=12 2*7=14 2*8=16 2*9=18\n"; if(N>2)cout<<"3*3=9 3*4=12 3*5=15 3*6=18 3*7=21 3*8=24 3*9=27\n"; if(N>3)cout<<"4*4=16 4*5=20 4*6=24 4*7=28 4*8=32 4*9=36\n"; if(N>4)cout<<"5*5=25 5*6=30 5*7=35 5*8=40 5*9=45\n"; if(N>5)cout<<"6*6=36 6*7=42 6*8=48 6*9=54\n"; if(N>6)cout<<"7*7=49 7*8=56 7*9=63\n"; if(N>7)cout<<"8*8=64 8*9=72\n"; if(N>8)cout<<"9*9=81\n";
  11.     }
  12.     return 0;
  13. }

E3143 纯虚数的幂
First AC: 2018-01-17 Latest Modification: 2018-01-17

  1. n=int(input())
  2. for i in range(0,n):
  3.     print('case #%d:'%(i))
  4.     s,t=input().split()
  5.     s=(int)(s[:-1])
  6.     t=(int)(t)
  7.     if t%4==0:
  8.         print(s**t)
  9.     elif t%4==1:
  10.         print('%dj'%(s**t))
  11.     elif t%4==2:
  12.         print('-%d'%(s**t))
  13.     else:
  14.         print('-%dj'%(s**t))

E3144 问候
First AC: 2017-10-31 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,i,j;
  4. int h,m;
  5. double s,sum;
  6. int main()
  7. {
  8.     cin>>T;
  9.     for(i=0;i<T;++i){ cin>>n;
  10.         sum=0;
  11.         for(j=0;j<n;++j)scanf("%d:%d:%f",&h,&m,&s),sum+=3600*h+60*m+s; while(sum>86400)sum-=86400;
  12.         cout<<"case #"<<i<<":\nGood "; if(sum>=14400&&sum<43200)cout<<"morning!\n"; else if(sum>=43200&&sum<64800)cout<<"afternoon!\n"; else if(sum>=64800&&sum<79200)cout<<"evening!\n";
  13.         else if(sum<14400||sum>=79200)
  14.         cout<<"night!\n";
  15.     }
  16.     return 0;
  17. }

E3145 互素勾股数
First AC: 2018-02-09 Latest Modification: 2018-02-09

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T;
  4. long a,b,c;
  5. long r,i,j,k;
  6. long gcd(long a,long b)
  7. {
  8.     long c=1;
  9.     while(c)c=a%b,a=b,b=c;
  10.     return a;
  11. }
  12. struct data{
  13.     long a,b,c;
  14. }num[11];
  15. bool cmp(data a,data b)
  16. {
  17.     return a.a<b.a; } int main() { cin>>T;
  18.     for(r=0;r<T;++r){ cin>>c;
  19.         long m=(long)(sqrt(c/2.0))+1;
  20.         for(i=1,k=0;i<m;++i){ j=(long)(sqrt(c-i*i)); if(i*i+j*j==c){ a=abs(i*i-j*j),b=2*i*j; if(a>b)a^=b,b^=a,a^=b;
  21.                 if(gcd(a,b)==1&&gcd(a,c)==1&&gcd(b,c)==1)
  22.                     num[k].a=a,num[k].b=b,num[k++].c=c;
  23.             }
  24.         }
  25.         sort(num,num+k,cmp);
  26.         cout<<"case #"<<r<<":\n"<<k<<endl;
  27.         for(i=0;i<k;++i)
  28.             cout<<num[i].a<<"^2+"<<num[i].b<<"^2="<<num[i].c<<"^2\n";
  29.     }
  30.     return 0;
  31. }

E3147 维吉尼亚密码
First AC: 2017-11-03 Latest Modification: 2018-06-08

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

E3148 线性表比较
First AC: 2018-04-14 Latest Modification: 2018-04-14

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,M;
  4. int a[1000],b[1000];
  5. int i;
  6. int main()
  7. {
  8.     cin>>m>>n;
  9.     for(i=0;i<m;++i)cin>>a[i];
  10.     for(i=0;i<n;++i)cin>>b[i];
  11.     M=min(m,n);
  12.     bool jdg=1;
  13.     for(i=0;i<M;++i){
  14.         if(a[i]<b[i]){
  15.             cout<<"-1"; jdg=0; break; } else if(a[i]>b[i]){
  16.             cout<<"1";
  17.             jdg=0;
  18.             break;
  19.         }
  20.     }
  21.     if(jdg){
  22.         if(m<n)cout<<"-1";
  23.         else if(m<n)cout<<"1";
  24.         else cout<<0;
  25.     }
  26.     return 0;
  27. }

E3149 倒置顺序表
First AC: 2017-11-03 Latest Modification: 2017-11-03

  1. #include
  2. using namespace std;
  3. int N,i;
  4. int main()
  5. {
  6.     cin>>N;
  7.     int a[N];
  8.     for(i=0;i<N;++i)cin>>a[i];
  9.     for(i=N-1;i>0;i--)cout<<a[i]<<" ";
  10.     cout<<a[0];
  11.     return 0;
  12. }

E3150 线性表去重
First AC: 2017-11-22 Latest Modification: 2017-11-22

  1. #include 
  2. using namespace std;
  3. int N,n,cnt;
  4. int a[101];
  5. int i;
  6. int main()
  7. {
  8.     cin>>N;
  9.     while(N--){
  10.         cin>>n;
  11.         if(a[n]==0)++a[n];
  12.     }
  13.     for(i=0;i<101;++i) if(a[i]>0){
  14.             if(cnt==0)cout<<i,++cnt;
  15.             else cout<<' '<<i;
  16.         }
  17.     return 0;
  18. }

E3151 循环打印
First AC: 2017-12-30 Latest Modification: 2017-12-30

  1. #include
  2. using namespace std;
  3. int num,bgn,step,cnt;
  4. int a[105],b[105];
  5. int i,j,k,n;
  6. int main()
  7. {
  8.     cin>>num>>bgn>>step;
  9.     for(i=1;i<101;++i)a[i]=i;
  10.     for(i=bgn;;++i){
  11.         if(i==num+1)i=0;
  12.         if(a[i]){
  13.             if(++cnt==step)b[n++]=a[i],a[i]=0,cnt=0;
  14.         }
  15.         if(n==num)break;
  16.     }
  17.     cout<<b[0];
  18.     for(i=1;i<num;++i)cout<<' '<<b[i];
  19.     return 0;
  20. }

E3158 特殊计算
First AC: 2017-11-08 Latest Modification: 2017-11-08

  1. #include
  2. using namespace std;
  3. long a,b,temp;
  4. int main()
  5. {
  6.     cin>>a>>b;
  7.     temp=a&&b;
  8.     cout<<temp<<endl;
  9.     temp=a&b;
  10.     cout<<temp;
  11.     return 0;
  12. }

E3160 统计字符及行数
First AC: 2017-12-25 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string s;
  4. int len,maxl,numl,rst;
  5. int main()
  6. {
  7.     while(getline(cin,s)){
  8.         len=s.length();
  9.         if(len>maxl)maxl=len;
  10.         ++numl,rst+=len;
  11.     }
  12.     cout<<rst<<','<<numl<<','<<maxl;
  13.     return 0;
  14. }

E3161 位运算
First AC: 2017-11-25 Latest Modification: 2017-11-25

  1. #include
  2. using namespace std;
  3. long long N,a[64]={1};
  4. int p,n,i;
  5. int main()
  6. {
  7.     for(i=1;i<64;++i)a[i]=2*a[i-1]; cin>>N>>p>>n;
  8.     for(i=p;n--;--i)N&a[i]? N-=a[i]:N+=a[i];
  9.     cout<<N;
  10.     return 0;
  11. }

E3162 逻辑或、位或、位亦或
First AC: 2017-11-08 Latest Modification: 2017-11-08

  1. #include
  2. using namespace std;
  3. long a,b,t;
  4. int main()
  5. {
  6.     cin>>a>>b;
  7.     t=a||b;
  8.     cout<<t<<endl;
  9.     t=a|b;
  10.     cout<<t<<endl;
  11.     t=a^b;
  12.     cout<<t<<endl;
  13.     return 0;
  14. }

E3163 二进制中1的占比
First AC: 2017-11-03 Latest Modification: 2017-12-04

  1. #include
  2. using namespace std;
  3. long n,i,a[32],s;
  4. int main()
  5. {
  6.     cin>>n;
  7.     for(i=0;n!=0;++i){
  8.         a[i]=n%2,n/=2;
  9.         if(a[i]==1)++s;
  10.     }
  11.     if(s==0)cout<<"0,0:32";
  12.     else if(s==32)cout<<"32,1:1";
  13.     else {
  14.         cout<<s<<","; for(i=16;i>=1;i/=2)if(s%i==0)break;
  15.         cout<<s/i<<":"<<32/i;
  16.     }
  17.     return 0;
  18. }

E3167 去掉多余的空白符
First AC: 2017-12-09 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string s;
  4. int len,cnt,i;
  5. int isspace(char c)
  6. {
  7.     if(c!='\n'&&c!=' '&&c!='\t')return 0;
  8.     return 1;
  9. }
  10. int main()
  11. {
  12.     while(getline(cin,s)){
  13.         len=s.length();
  14.         for(cnt=1,i=len-1;i>=0;--i){
  15.             if(cnt){
  16.                 if(isspace(s[i])==1)s[i]='\n';
  17.                 else{cnt=0;break;}
  18.             }
  19.         }
  20.         if(cnt)continue;
  21.         for(cnt=1,i=0;i<len;++i){
  22.             if(cnt){
  23.                 if(isspace(s[i])==1)s[i]='\n';
  24.                 else{cnt=0;break;}
  25.             }
  26.         }
  27.         for(i=0;i<len;++i){
  28.             if(isspace(s[i])==0||(s[i]!='\n'&&isspace(s[i-1])==0))
  29.                 cout<<s[i];
  30.         }
  31.         cout<<endl;
  32.     }
  33.     return 0;
  34. }

E3169 字符串出现次数
First AC: 2017-11-09 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. #define N 80
  3. using namespace std;
  4. int count(char s[],char t[])
  5. {
  6.     int lens=strlen(s),lent=strlen(t),i,j,cnt=0,num=0,M=lens-lent;
  7.     for(i=0;i<=M;++i){
  8.         if(s[i]==t[0]){
  9.             for(j=1;j<lent;++j){
  10.                 if(s[i+j]!=t[j]){num++;break;}
  11.             }
  12.             if(num==0)cnt++,--i+=lent;
  13.             else num=0;
  14.         }
  15.     }
  16.     return cnt;
  17. }
  18. int main()
  19. {   char s[N+1],t[N+1];
  20.     scanf("%s%s",s,t);
  21.     printf("%d\n",count(s,t));
  22.     return 0;
  23. }

E3170 二进制转十进制
First AC: 2017-11-07 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. #define N 32
  3. using namespace std;
  4. unsigned b2i(char s[])
  5. {
  6.     int len=strlen(s);
  7.     int i;
  8.     unsigned int m=0,n=1;
  9.     for(i=len-1;i>=0;--i){
  10.         if(s[i]=='1')m+=n;
  11.         n*=2;
  12.     }
  13.     return m;
  14. }
  15. int main()
  16. {
  17.     char s[N+1];
  18.     scanf("%s",s);
  19.     printf("%u\n",b2i(s));
  20.     return 0;
  21. }

E3171 波兰表达式
First AC: 2017-12-16 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int len,flag,i,cnt;
  4. char a[15],c;
  5. double num,tmp1,tmp2;
  6. int sig[50];
  7. stackm;
  8. stackn;
  9. int main()
  10. {
  11.         while(1){
  12.             cin>>a;
  13.             len=strlen(a);
  14.             flag=1;
  15.             if(len==1){
  16.                 switch(a[0]){
  17.                     case '+':case '-': case '*':case '/':
  18.                         m.push(a[0]);flag=0;++cnt;break;
  19.                 }
  20.             }
  21.             if(flag){
  22.                 num=atof(a);
  23.                 n.push(num);
  24.                 ++sig[cnt];
  25.             }
  26.             while(sig[cnt]>1&&m.size()&&n.size()>1){
  27.                 tmp2=n.top();
  28.                 n.pop();
  29.                 tmp1=n.top();
  30.                 n.pop();
  31.                 c=m.top();
  32.                 m.pop();
  33.                 switch(c){
  34.                     case '+':n.push(tmp1+tmp2);break;
  35.                     case '-':n.push(tmp1-tmp2);break;
  36.                     case '*':n.push(tmp1*tmp2);break;
  37.                     case '/':n.push(tmp1/tmp2);break;
  38.                 }
  39.                 sig[cnt]=0,++sig[--cnt];
  40.             }
  41.             c=getchar();
  42.             if(c!=' '){
  43.                 num=n.top();
  44.                 n.pop();
  45.                 printf("%.6f",num);
  46.                 cnt=0;
  47.                 return 0;
  48.             }
  49.         }
  50. }

E3172 整数转化为字符串
First AC: 2017-11-20 Latest Modification: 2017-11-20

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

E3182 字符串排序
First AC: 2018-01-03 Latest Modification: 2018-06-08

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

E3183 坐标排序
First AC: 2017-12-06 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n;
  4. int i,j;
  5. struct data{
  6.     long long dis;
  7.     int x,y,qua,absx;
  8. }a[101];
  9. bool cmp(data a,data b)
  10. {
  11.     if(a.dis-b.dis)return a.dis<b.dis;
  12.     if(a.qua-b.qua)return a.qua<b.qua;
  13.     return a.absx<b.absx; } int main() { cin>>T;
  14.     for(i=0;i<T;++i){ cin>>n;
  15.         for(j=0;j<n;++j){ cin>>a[j].x>>a[j].y;
  16.             a[j].dis=a[j].x*a[j].x+a[j].y*a[j].y;
  17.             if(a[j].y>=0){
  18.                 if(a[j].x>=0)a[j].qua=1,a[j].absx=a[j].x;
  19.                 else a[j].qua=2,a[j].absx=-a[j].x;
  20.             } 
  21.             else{
  22.                 if(a[j].x>0)a[j].qua=4,a[j].absx=a[j].x;
  23.                 else a[j].qua=3,a[j].absx=-a[j].x; 
  24.             }
  25.         }
  26.         sort(a,a+n,cmp);
  27.         cout<<"case #"<<i<<":\n";
  28.         for(j=0;j<n-1;++j)cout<<'('<<a[j].x<<','<<a[j].y<<')'<<' ';
  29.         cout<<'('<<a[n-1].x<<','<<a[n-1].y<<')'<<endl;
  30.     }
  31.     return 0;
  32. }

E3184 二维数组排序
First AC: 2017-12-21 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct data{int n[101],sumn;}a[101];
  4. int T,n,m,cnt;
  5. int i,j,k;
  6. bool cmp(data a,data b)
  7. {
  8.     if(a.sumn^b.sumn)return a.sumn<b.sumn;
  9.     for(int i=0;i<m;++i)if(a.n[i]^b.n[i])return a.n[i]<b.n[i];
  10.     return a.n[0]<b.n[0]; } int main() { cin>>T;
  11.     for(i=0;i<T;++i){ cin>>n>>m;
  12.         for(j=0;j<n;++j){
  13.             for(cnt=k=0;k<m;++k)cin>>a[j].n[k],cnt+=a[j].n[k];
  14.             a[j].sumn=cnt;
  15.         }
  16.         sort(a,a+n,cmp);
  17.         cout<<"case #"<<i<<":\n";
  18.         for(j=0;j<n;++j){
  19.             cout<<a[j].n[0];
  20.             for(k=1;k<m;++k)cout<<' '<<a[j].n[k];
  21.             cout<<endl;
  22.         }
  23.     }
  24.     return 0;
  25. }

E3185 双阶乘的质因数个数
First AC: 2018-01-05 Latest Modification: 2018-01-05

  1. #include
  2. using namespace std;
  3. int a[10001]={1,1};
  4. int T,n,m,tmp,cnt;
  5. int i,j;
  6. int main()
  7. {
  8.     for(i=2;i<10001;++i){
  9.         if(a[i]==0){
  10.             for(j=2*i;j<10001;j+=i)++a[j]; } } cin>>T;
  11.     for(i=0;i<T;++i){ cnt=0; cin>>n>>m;
  12.         for(cnt=0,j=n%2;j<=n;j+=2){
  13.             tmp=j;
  14.             while(tmp&&tmp%m==0)++cnt,tmp/=m;
  15.         }
  16.         cout<<"case #"<<i<<":\n"<<cnt<<endl;
  17.     }
  18.     return 0;
  19. }

E3186 A+B
First AC: 2017-11-13 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,num,rst1,rst2;
  4. string s,t[2];
  5. int i;
  6. int main()
  7. {
  8.     cin>>T;
  9.     for(i=0;i<T;++i){
  10.         cout<<"case #"<<i<<":\n"; while(cin>>s){
  11.             if(s.length()!=1){
  12.                 t[num++]=s;
  13.             }
  14.             else if(s=="+"){
  15.                 if(t[0]=="one")rst1=1;
  16.                 else if(t[0]=="two")rst1=2;
  17.                 else if(t[0]=="three")rst1=3;
  18.                 else if(t[0]=="four")rst1=4;
  19.                 else if(t[0]=="five")rst1=5;
  20.                 else if(t[0]=="six")rst1=6;
  21.                 else if(t[0]=="seven")rst1=7;
  22.                 else if(t[0]=="eight")rst1=8;
  23.                 else if(t[0]=="nine")rst1=9;
  24.                 else rst1=0;
  25.                 if(num==2){
  26.                     rst1*=10;
  27.                     if(t[1]=="one")rst1+=1;
  28.                     else if(t[1]=="two")rst1+=2;
  29.                     else if(t[1]=="three")rst1+=3;
  30.                     else if(t[1]=="four")rst1+=4;
  31.                     else if(t[1]=="five")rst1+=5;
  32.                     else if(t[1]=="six")rst1+=6;
  33.                     else if(t[1]=="seven")rst1+=7;
  34.                     else if(t[1]=="eight")rst1+=8;
  35.                     else if(t[1]=="nine")rst1+=9;
  36.                 }
  37.                 num=0;
  38.             }
  39.             else{
  40.                 if(t[0]=="one")rst2=1;
  41.                 else if(t[0]=="two")rst2=2;
  42.                 else if(t[0]=="three")rst2=3;
  43.                 else if(t[0]=="four")rst2=4;
  44.                 else if(t[0]=="five")rst2=5;
  45.                 else if(t[0]=="six")rst2=6;
  46.                 else if(t[0]=="seven")rst2=7;
  47.                 else if(t[0]=="eight")rst2=8;
  48.                 else if(t[0]=="nine")rst2=9;
  49.                 else rst2=0;
  50.                 if(num==2){
  51.                     rst2*=10;
  52.                     if(t[1]=="one")rst2+=1;
  53.                     else if(t[1]=="two")rst2+=2;
  54.                     else if(t[1]=="three")rst2+=3;
  55.                     else if(t[1]=="four")rst2+=4;
  56.                     else if(t[1]=="five")rst2+=5;
  57.                     else if(t[1]=="six")rst2+=6;
  58.                     else if(t[1]=="seven")rst2+=7;
  59.                     else if(t[1]=="eight")rst2+=8;
  60.                     else if(t[1]=="nine")rst2+=9;
  61.                 }
  62.                 num=0,cout<<rst1+rst2<<endl;
  63.                 break;
  64.             }
  65.         }
  66.     }
  67.     return 0;
  68. }

E3187 凹数
First AC: 2018-02-21 Latest Modification: 2018-02-21

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long cnt;
  4. int tmp1,tmp2,tmp3;
  5. long d[1000001];
  6. int T,a,b;
  7. long i,j,k;
  8. bool jdg(long n)
  9. {
  10.     int cnt=0;
  11.     tmp1=n%10,n/=10;
  12.     tmp2=n%10,n/=10;
  13.     if(tmp1==tmp2)return 0;
  14.     while(n){
  15.         tmp3=n%10,n/=10;
  16.         if(tmp2==tmp3)return 0;
  17.         if(tmp2<tmp1&&tmp2<tmp3)++cnt; else if(tmp2>tmp1&&tmp2>tmp3)return 0;
  18.         tmp1=tmp2,tmp2=tmp3;
  19.     }
  20.     if(cnt!=1)return 0;
  21.     return 1;
  22. }
  23. int main()
  24. {
  25.     for(i=100;i<1000001;++i){ if(jdg(i))++cnt; d[i]=cnt; } cin>>T;
  26.     for(i=0;i<T;++i){ cin>>a>>b;
  27.         cout<<"case #"<<i<<":\n"<<d[b]-d[a-1]<<endl;
  28.     }
  29.     return 0;
  30. }

E3188 坏掉的彩灯
First AC: 2017-11-08 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,len,M,m,R,B,Y,G,temp,cnt;
  4. string s;
  5. int i,j,k;
  6. int main()
  7. {
  8.     cin>>T,getchar();
  9.     for(i=0;i<T;++i){
  10.         getline(cin,s);
  11.         cout<<"case #"<<i<<":\n";
  12.         len=s.length();
  13.         R=B=Y=G=M=len/4,m=len%4,temp=len-m,cnt=0;
  14.         for(j=0;j<temp;++j)
  15.             if(s[j]=='R')R--;
  16.             else if(s[j]=='B')B--;
  17.             else if(s[j]=='G')G--;
  18.             else if(s[j]=='Y')Y--;
  19.         if(m==0){
  20.             cout<<R<<' '<<B<<' '<<Y<<' '<<G<<endl;
  21.             continue; 
  22.         }
  23.         for(j=1;j<=m;++j)
  24.             if(s[len-j]=='!'){
  25.                 for(k=4;k<=len;k+=4)
  26.                     if(s[len-j-k]!='!'){
  27.                         cnt++;
  28.                         s[len-j]=s[len-j-k];
  29.                         if(s[len-j-k]=='R')R++;
  30.                         else if(s[len-j-k]=='B')B++;
  31.                         else if(s[len-j-k]=='G')G++;
  32.                         else if(s[len-j-k]=='Y')Y++;
  33.                         break;
  34.                     }
  35.             }
  36.             else cnt++;
  37.         if(cnt==m)cout<<R<<' '<<B<<' '<<Y<<' '<<G<<endl; else{ ++R,++B,++Y,++G; for(j=4;j>m;--j)
  38.                 for(k=-4;j+k<len;k+=4)
  39.                     if(s[j+k]!='!'){
  40.                         if(s[j+k]=='R')R--;
  41.                         else if(s[j+k]=='B')B--;
  42.                         else if(s[j+k]=='G')G--;
  43.                         else if(s[j+k]=='Y')Y--;
  44.                         break;
  45.                     }
  46.             for(j=1;j<=m;++j)
  47.                 if(s[len-j]=='R')R--;
  48.                 else if(s[len-j]=='B')B--;
  49.                 else if(s[len-j]=='G')G--;
  50.                 else if(s[len-j]=='Y')Y--;
  51.             cout<<R<<' '<<B<<' '<<Y<<' '<<G<<endl;
  52.         }
  53.  
  54.     }
  55.     return 0;
  56. }

E3189 求和
First AC: 2018-05-11 Latest Modification: 2018-05-11

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll T,n,m,num,l,r;
  5. ll a[1005],b[500005];
  6. ll i,j,k;
  7. int main()
  8. {
  9.     cin>>T;
  10.     for(i=0;i<T;++i){ cin>>n>>m;
  11.         for(j=1;j<=n;++j)cin>>a[j],a[j]+=a[j-1];
  12.         num=1;
  13.         for(j=0;j<n;++j)for(k=j+1;k<=n;++k)b[num++]=a[k]-a[j];
  14.         sort(b+1,b+num);
  15.         for(j=2;j<num;++j)b[j]+=b[j-1];
  16.         cout<<"case #"<<i<<":\n"; while(m--){ cin>>l>>r;
  17.             cout<<b[r]-b[l-1]<<endl;
  18.         }
  19.     }
  20.     return 0;
  21. }

E3190 平衡三进制
First AC: 2017-11-25 Latest Modification: 2018-03-09

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a[21]={1};
  4. string s;
  5. int T,len,sum;
  6. int i,j,k;

int main()
{
for(i=1;i<21;++i)a[i]=3*a[i-1]; cin>>T;
for(i=0;i<T;++i){ cin>>s;
len=s.length()-1;
for(j=len,sum=k=0;j+1;–j,++k)
if(s[j]==’-‘)sum-=a[k];
else if(s[j]==’1’)sum+=a[k];
cout<<“case #”<<i<<“:\n”<<sum<<endl;
}
return 0;
}

E3191 闰年问题
First AC: 2017-11-05 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,d;
  4. long long y,n1,n2;
  5. string m;
  6. int i;
  7. int main()
  8. {
  9.     cin>>T;
  10.     for(i=0;i<T;++i){
  11.         cout<<"case #"<<i<<":\n"; cin>>m,scanf("%d,%ld",&d,&y);
  12.         n1=y/4-y/100+y/400;
  13.         if((y%4==0&&y%100!=0||y%400==0)&&
  14.            (m=="February"||m=="January"))--n1;
  15.         cin>>m,scanf("%d,%ld",&d,&y);
  16.         n2=y/4-y/100+y/400;
  17.         if((y%4==0&&y%100!=0||y%400==0)&&
  18.           ((m=="February"&&d<29)||m=="January"))--n2;
  19.         cout<<n2-n1<<endl; 
  20.     }
  21.     return 0;
  22. }

E3193键盘
First AC: 2017-12-21 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,a,b,c,m,pri,cntu,cntp,sumn,sump,tmpu,tmpp,cnt;
  4. int u[301],p[301],tmp[601];
  5. string s;
  6. int i,j;
  7. int main()
  8. {
  9.     cin>>T;
  10.     for(i=0;i<T;++i){ cin>>a>>b>>c>>m;
  11.         for(cntu=cntp=j=0;j<m;++j){ cin>>pri>>s;
  12.             if(s[0]=='U')u[cntu++]=pri;
  13.             else p[cntp++]=pri;
  14.         }
  15.         cout<<"case #"<<i<<":\n"; sort(u,u+cntu),sort(p,p+cntp); sumn=sump=cnt=0; if(cntu>=a){
  16.             sumn=a;
  17.             for(j=0;j<a;++j)sump+=u[j];
  18.             for(j=a;j<cntu;++j)tmp[cnt++]=u[j];
  19.         }
  20.         else{
  21.             sumn=cntu;
  22.             for(j=0;j<cntu;++j)sump+=u[j]; } if(cntp>=b){
  23.             sumn+=b;
  24.             for(j=0;j<b;++j)sump+=p[j];
  25.             for(j=b;j<cntp;++j)tmp[cnt++]=p[j];
  26.         }
  27.         else{
  28.             sumn+=cntp;
  29.             for(j=0;j<cntp;++j)sump+=p[j]; } if(c){ sort(tmp,tmp+cnt); if(c>cnt){
  30.                 sumn+=cnt;
  31.                 for(j=0;j<cnt;++j)sump+=tmp[j];
  32.             }
  33.             else{
  34.                 sumn+=c;
  35.                 for(j=0;j<c;++j)sump+=tmp[j];
  36.             }
  37.         }
  38.         cout<<sumn<<' '<<sump<<endl;
  39.     }
  40.     return 0;
  41. }

E3194 字符串消除
First AC: 2018-03-15 Latest Modification: 2018-03-15

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,len,rst,tmp;
  4. string s,t;
  5. int i,j;
  6. int cnt(string s)
  7. {
  8.     int num=s.length();
  9.     while(1){
  10.         s=" "+s+" ";
  11.         int len=s.length()-1,i;
  12.         string t="";
  13.         for(i=1;i<len;++i){ if(s[i]!=s[i-1]&&s[i]!=s[i+1])t+=s[i]; } if(t.length()==len-1)return num-len+1; s=t; } } int main() { cin>>T;
  14.     for(i=0;i<T;++i){ cin>>s;
  15.         len=s.length();
  16.         rst=0;
  17.         for(j=0;j<len;++j){ tmp=cnt(s.substr(0,j)+'A'+s.substr(j,len)); if(tmp>rst)rst=tmp;
  18.             tmp=cnt(s.substr(0,j)+'B'+s.substr(j,len));
  19.             if(tmp>rst)rst=tmp;
  20.             tmp=cnt(s.substr(0,j)+'C'+s.substr(j,len));
  21.             if(tmp>rst)rst=tmp;
  22.         }
  23.         tmp=cnt(s+'A');
  24.         if(tmp>rst)rst=tmp;
  25.         tmp=cnt(s+'B');
  26.         if(tmp>rst)rst=tmp;
  27.         tmp=cnt(s+'C');
  28.         if(tmp>rst)rst=tmp;
  29.         cout<<"case #"<<i<<":\n"<<rst<<endl;
  30.     }
  31.     return 0;
  32. }

E3195 Ubiquitous Religions
First AC: 2018-06-08 Latest Modification: 2018-06-08

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

E3196 WormHoles
First AC: 2019-02-09 Latest Modification: 2019-02-09

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int maxn=505,maxm=5205;
  4. int F,n,m,w,ne;
  5. int u,v,val;
  6. int h[maxn],dis[maxn],vis[maxn],cnt[maxn];
  7. queueq,emp;
  8. struct edge{
  9.     int to,val,nxt;
  10. }e[maxm];
  11. void insert(int u,int v,int val)
  12. {
  13.     e[++ne].to=v;
  14.     e[ne].val=val;
  15.     e[ne].nxt=h[u];
  16.     h[u]=ne;
  17. }
  18. bool spfa(int ask)
  19. {
  20.     memset(dis,0x3f,sizeof dis);
  21.     dis[ask]=0;
  22.     memset(vis,0,sizeof vis);
  23.     vis[ask]=1;
  24.     memset(cnt,0,sizeof cnt);
  25.     ++cnt[ask];
  26.     q=emp;
  27.     q.push(ask);
  28.     while(!q.empty()){
  29.         int x=q.front();
  30.         q.pop();
  31.         vis[x]=0;
  32.         for(int i=h[x];i;i=e[i].nxt){
  33.             int to=e[i].to;
  34.             if(dis[to]>dis[x]+e[i].val){
  35.                 dis[to]=dis[x]+e[i].val;
  36.                 if(!vis[to]){
  37.                     vis[to]=1;
  38.                     if(++cnt[to]>=n)return 0;
  39.                     q.push(to);
  40.                 }
  41.             }
  42.         }
  43.     }
  44.     return 1;
  45. }
  46. int main()
  47. {
  48.     cin>>F;
  49.     while(F--){
  50.         cin>>n>>m>>w;
  51.         ne=0;
  52.         memset(h,0,sizeof h);
  53.         while(m--){
  54.             cin>>u>>v>>val;
  55.             insert(u,v,val);
  56.             insert(v,u,val);
  57.         }
  58.         while(w--){
  59.             cin>>u>>v>>val;
  60.             insert(u,v,-val);
  61.         }
  62.         spfa(1)? cout<<"NO\n":cout<<"YES\n";
  63.     }
  64.     return 0;
  65. }

E3198 挖井
First AC: 2019-05-16 Latest Modification: 2019-05-16
Note: 把单独挖井作为和0号节点连边,0号节点默认有水,然后kruskal即可

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int maxn=305,maxm=50005;
  4. int n,m,x,ans;
  5. struct edge{
  6.     int u,v,w;
  7. }e[maxm];
  8. int pre[maxn];
  9. int i,j;
  10. bool cmp(edge a,edge b)
  11. {
  12.     return a.w<b.w; } int find(int x) { int r=x,i; while(pre[r]!=r)r=pre[r]; while(pre[x]!=r)i=pre[x],pre[x]=r,x=i; return r; } void join(int x,int y,int z) { int fx=find(x),fy=find(y); if(fx==0&&fy==0)return; if(x==y)pre[fx]=0,ans+=z; else if(fx==0)pre[fy]=0,ans+=z; else if(fy==0)pre[fx]=0,ans+=z; else if(fx!=fy)pre[fx]=fy,ans+=z; } int main() { cin>>n;
  13.     for(i=0;i<n;++i){ e[i].u=e[i].v=i+1; cin>>e[i].w;
  14.     }
  15.     m=n;
  16.     for(i=1;i<=n;++i){
  17.         for(j=1;j<=n;++j){ cin>>x;
  18.             if(i<j){
  19.                 e[m].u=i;
  20.                 e[m].v=j;
  21.                 e[m].w=x;
  22.                 ++m;
  23.             }
  24.         }
  25.     }
  26.     sort(e,e+m,cmp);
  27.     for(i=1;i<=n;++i)pre[i]=i;
  28.     for(i=0;i<m;++i)join(e[i].u,e[i].v,e[i].w);
  29.     cout<<ans;
  30.     return 0;
  31. }

E3199 Agri-Net
First AC: 2019-05-16 Latest Modification: 2019-05-16

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int maxn=105,maxm=5005;
  4. int n,m,x,ans;
  5. struct edge{
  6.     int u,v,w;
  7. }e[maxm];
  8. int pre[maxn];
  9. int i,j;
  10. bool cmp(edge a,edge b)
  11. {
  12.     return a.w<b.w; } int find(int x) { int r=x,i; while(pre[r]!=r)r=pre[r]; while(pre[x]!=r)i=pre[x],pre[x]=r,x=i; return r; } void join(int u,int v,int w) { int fu=find(u),fv=find(v); if(fu!=fv){ pre[fu]=fv; ans+=w; } } int main() { cin>>n;
  13.     for(i=1;i<=n;++i){
  14.         for(j=1;j<=n;++j){ cin>>x;
  15.             if(i<j){
  16.                 e[m].u=i;
  17.                 e[m].v=j;
  18.                 e[m].w=x;
  19.                 ++m;
  20.             }
  21.         }
  22.     }
  23.     sort(e,e+m,cmp);
  24.     for(i=1;i<=n;++i)pre[i]=i;
  25.     for(i=0;i<m;++i){
  26.         join(e[i].u,e[i].v,e[i].w);
  27.     }
  28.     cout<<ans;
  29.     return 0;
  30. }

E3200 Six Degrees of Cowvin Bacon
First AC: 2019-02-07 Latest Modification: 2019-02-07

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,num,rst,tmp;
  4. int dis[301][301];
  5. int movie[301];
  6. int sumdegree[301];
  7. int i,j,k;
  8. int main()
  9. {
  10.     cin>>n>>m;
  11.     memset(dis,0x3f,sizeof dis);
  12.     for(i=1;i<=n;++i)dis[i][i]=0; while(m--){ cin>>num;
  13.         for(i=0;i<num;++i)cin>>movie[i];
  14.         for(i=0;i<num;++i){
  15.             for(j=i+1;j<num;++j){
  16.                 dis[movie[i]][movie[j]]=1;
  17.                 dis[movie[j]][movie[i]]=1;
  18.             }
  19.         }
  20.     }   
  21.     for(k=1;k<=n;++k){
  22.         for(i=1;i<=n;++i){
  23.             for(j=1;j<=n;++j){
  24.                 dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
  25.             }
  26.         }
  27.     }
  28.     rst=1e6;
  29.     for(i=1;i<=n;++i){
  30.         tmp=0;
  31.         for(j=1;j<=n;++j){
  32.             if(i!=j)tmp+=dis[i][j];
  33.         }
  34.         rst=min(rst,tmp);
  35.     }
  36.     cout<<(int)(rst*100.0/(n-1));
  37.     return 0;
  38. }

E3202 RoadBlocks
First AC: 2019-02-13 Latest Modification: 2019-02-13
Note: 添加一个数组dis2[]存次短路,注意更新时要避免||的短路操作

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int maxn=5005,maxm=200005;
  4. int n,m,ne;
  5. int u,v,val;
  6. int h[maxn],dis[maxn],dis2[maxn],vis[maxn],cnt[maxn];
  7. struct edge{
  8.     int to,val,nxt;
  9. }e[maxm];
  10. queue q,emp;
  11. void insert(int u,int v,int val)
  12. {
  13.     e[++ne].to=v;
  14.     e[ne].val=val;
  15.     e[ne].nxt=h[u];
  16.     h[u]=ne;
  17. }
  18. bool update(int index,int val)
  19. {
  20.     if(dis[index]==val||dis2[index]<=val)return 0; if(dis[index]>val){
  21.         dis2[index]=dis[index];
  22.         dis[index]=val;
  23.     }
  24.     else{
  25.         dis2[index]=val;
  26.     }
  27.     return 1;
  28. }
  29. bool spfa(int ask)
  30. {
  31.     memset(dis,0x3f,sizeof dis);
  32.     dis[ask]=0;
  33.     memset(dis2,0x3f,sizeof dis2);
  34.     memset(vis,0,sizeof vis);
  35.     vis[ask]=1;
  36.     memset(cnt,0,sizeof cnt);
  37.     ++cnt[ask];
  38.     q=emp;
  39.     q.push(ask);
  40.     while(!q.empty()){
  41.         int x=q.front();
  42.         q.pop();
  43.         vis[x]=0;
  44.         for(int i=h[x];i;i=e[i].nxt){
  45.             int to=e[i].to;
  46.             if(update(to,dis[x]+e[i].val)|update(to,dis2[x]+e[i].val)){
  47.                 if(!vis[to]){
  48.                     if(++cnt[to]>=n)return 0;
  49.                     vis[to]=1;
  50.                     q.push(to);
  51.                 }
  52.             }
  53.         }
  54.     }
  55.     return 1;
  56. }
  57. int main()
  58. {
  59.     cin>>n>>m;
  60.     while(m--){
  61.         cin>>u>>v>>val;
  62.         insert(u,v,val);
  63.         insert(v,u,val);
  64.     }
  65.     spfa(1);
  66.     cout<<dis2[n];
  67.     return 0;
  68. }

E3205 Prime Gap
First AC: 2018-05-05 Latest Modification: 2018-05-05

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. bool pri[1300000];
  4. int n;
  5. int i,j;
  6. int main()
  7. {
  8.     ios::sync_with_stdio(false);
  9.     for(i=2;i<650000;++i)
  10.         if(!pri[i])
  11.             for(j=i+i;j<1300000;j+=i) pri[j]=1; while(cin>>n,n){
  12.         i=j=n;
  13.         while(pri[i])--i;
  14.         while(pri[j])++j;
  15.         cout<<j-i<<endl;
  16.     }
  17.     return 0;
  18. }

E3206 Aggressive Cows
First AC: 2018-05-06 Latest Modification: 2018-05-06

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,c;
  4. int x[100000];
  5. int i;
  6. bool jdg(int dis)
  7. {
  8.     int tmp=0,num=1;
  9.     for(int i=1;i<n;++i){ tmp+=x[i]-x[i-1]; if(tmp>=dis)tmp=0,++num;
  10.     }
  11.     if(num>=c)return 1;
  12.     return 0;
  13. }
  14. void find(int lft,int rgt)
  15. {
  16.     if(lft+1>=rgt){
  17.         if(jdg(rgt))cout<<rgt;
  18.         else cout<<lft; exit(0); } int mid=(lft+rgt)/2; if(jdg(mid))find(mid,rgt); else find(lft,mid); } int main() { ios::sync_with_stdio(false); cin>>n>>c;
  19.     for(i=0;i<n;++i)cin>>x[i];
  20.     sort(x,x+n);
  21.     find(1,x[n-1]-x[0]);
  22.     return 0;
  23. }

E3209 分数加法
First AC: 2018-05-16 Latest Modification: 2018-05-16

  1. from fractions import Fraction
  2. T=int(input())
  3. a=0
  4. for i in range(T):
  5.     a+=Fraction(input())
  6. print(a)

E3210 Maximum Element
First AC: 2018-02-13 Latest Modification: 2018-02-13

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,q,x,tmp;
  4. stackteam,maxu;
  5. int main()
  6. {
  7.     cin>>n;
  8.     while(n--)
  9.     {
  10.         scanf("%d",&q);
  11.         if(q==1){
  12.             cin>>x;
  13.             team.push(x);
  14.             if(maxu.empty())maxu.push(x);
  15.             else if(x>=maxu.top())maxu.push(x);
  16.         }
  17.         else if(q==2){
  18.             tmp=team.top();
  19.             team.pop();
  20.             if(tmp==maxu.top())maxu.pop();
  21.         }
  22.         else cout<<maxu.top()<<endl;
  23.     }
  24. }

E3211 Rails
First AC: 2018-04-13 Latest Modification: 2018-04-13

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m;
  4. stacks,t,emps;
  5. queueq,empq;
  6. int i;
  7. bool op()
  8. {
  9.     if(!t.empty()&&t.top()==q.front()){
  10.         t.pop();
  11.         q.pop();
  12.         return 1;
  13.     }
  14.     while(!s.empty()&&s.top()!=q.front()){
  15.         t.push(s.top());
  16.         s.pop();
  17.     }
  18.     if(!s.empty()&&s.top()==q.front()){
  19.         s.pop();
  20.         q.pop();
  21.         return 1;
  22.     }
  23.     else return 0;
  24. }
  25. int main()
  26. {
  27.     while(cin>>n,n){
  28.         while(cin>>m){
  29.             if(!m){
  30.                 cout<<endl;
  31.                 break;
  32.             }
  33.             s=emps,t=emps,q=empq;
  34.             q.push(m);
  35.             for(i=1;i<n;++i)cin>>m,q.push(m);
  36.             for(i=n;i;--i)s.push(i);
  37.             bool jdg=1;
  38.             for(i=0;i<n;++i){
  39.                 if(!op()){
  40.                     jdg=0;
  41.                     break;
  42.                 }
  43.             }
  44.             jdg? cout<<"Yes\n":cout<<"No\n";
  45.         }
  46.     }
  47.     return 0;
  48. }

E3212 Balances Brackets
First AC: 2018-04-13 Latest Modification: 2018-04-13

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,len;
  4. string s;
  5. stackstk,emp;
  6. int i;
  7. int main()
  8. {
  9.     cin>>n;
  10.     while(n--){
  11.         cin>>s;
  12.         len=s.length();
  13.         stk=emp;
  14.         bool jdg=1;
  15.         for(i=0;i<len;++i){
  16.             if(s[i]==')'){
  17.                 if(stk.empty()||stk.top()!='('){
  18.                     jdg=0;
  19.                     break;
  20.                 }
  21.                 else stk.pop();
  22.             }
  23.             else if(s[i]==']'){
  24.                 if(stk.empty()||stk.top()!='['){
  25.                     jdg=0;
  26.                     break;
  27.                 }
  28.                 else stk.pop();
  29.             }
  30.             else if(s[i]=='}'){
  31.                 if(stk.empty()||stk.top()!='{'){
  32.                     jdg=0;
  33.                     break;
  34.                 }
  35.                 else stk.pop();
  36.             }
  37.             else stk.push(s[i]);
  38.         }
  39.         if(jdg&&stk.empty())cout<<"YES\n";
  40.         else cout<<"NO\n";
  41.     }
  42.     return 0;
  43. }

E3213 向右看齐
First AC: 2018-06-04 Latest Modification: 2018-06-04

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,h;
  4. int a[100005];
  5. stack< pair<int,int> >stk;
  6. int i;
  7. int main()
  8. {
  9.     ios::sync_with_stdio(false);
  10.     cin>>n;
  11.     for(i=1;i<=n;++i){ cin>>h;
  12.         while(!stk.empty()&&stk.top().first<h){
  13.             a[stk.top().second]=i;
  14.             stk.pop();
  15.         }
  16.         stk.push(pair<int,int>(h,i));
  17.     }
  18.     for(i=1;i<=n;++i)cout<<a[i]<<endl;
  19.     return 0;
  20. }

E3221 北京记者跑得最快
First AC: 2017-11-01 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long L,v,a,i,s,b;
  4. int main()
  5. {
  6.     cin>>L>>v>>a;
  7.     s=v*v,b=a*2;
  8.     for(i=0;i<L;++i){
  9.         s+=b;printf("%.7f\n",(sqrt(s)-v)/a);
  10.     }
  11.     return 0;
  12. }

E3222 六六六
First AC: 2018-06-08 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,x,tmp,sum;
  4. bool jdg[1000000];
  5. int i,j;
  6. int main()
  7. {
  8.     cin>>T;
  9.     for(i=1;i<=T;++i){ cin>>x;
  10.         memset(jdg,0,sizeof(jdg));
  11.         cout<<"Case "<<i<<": ";
  12.         sum=tmp=6%x;
  13.         bool rst=1;
  14.         for(j=1;j<=x;++j){
  15.             if(!sum){
  16.                 cout<<j<<endl;
  17.                 rst=0;
  18.                 break;
  19.             }
  20.             tmp=10*tmp%x;
  21.             (sum+=tmp)%=x;
  22.         }
  23.         if(rst)cout<<"-1\n";
  24.     }
  25.     return 0;
  26. }

E3226 声控开关(Easy)
First AC: 2018-12-17 Latest Modification: 2018-12-17

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,k;
  4. int a[32];
  5. int i,j;
  6. int main()
  7. {
  8.     cin>>T;
  9.     for(i=1;i<=T;++i){ cin>>n>>k;
  10.         for(j=0;j<32;++j){ a[j]=k&1; k>>=1;
  11.         }
  12.         cout<<"Case "<<i<<": O";
  13.         bool flag=1;
  14.         for(j=0;j<n;++j){
  15.             if(!a[j]){
  16.                 cout<<"FF\n";
  17.                 flag=0;
  18.                 break;
  19.             }
  20.         }
  21.         if(flag)cout<<"N\n";
  22.     }
  23.     return 0;
  24. }

E3227 声控开关(Hard)
First AC: 2018-12-17 Latest Modification: 2018-12-17

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,k;
  4. int a[32];
  5. int i,j;
  6. int main()
  7. {
  8.     cin>>T;
  9.     for(i=1;i<=T;++i){ cin>>n>>k;
  10.         for(j=0;j<32;++j){ a[j]=k&1; k>>=1;
  11.         }
  12.         cout<<"Case "<<i<<": O";
  13.         bool flag=1;
  14.         for(j=0;j<n;++j){
  15.             if(!a[j]){
  16.                 cout<<"FF\n";
  17.                 flag=0;
  18.                 break;
  19.             }
  20.         }
  21.         if(flag)cout<<"N\n";
  22.     }
  23.     return 0;
  24. }

E3233 N!
First AC: 2017-10-27 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long n;
  4. int main()
  5. {
  6.     while(cin>>n)
  7.         cout<<n/5+n/25+n/125+n/625+n/3125+n/15625
  8.              +n/78125+n/390625+n/1953125+n/9765625
  9.              +n/48828125+n/244140625<<endl;
  10.     return 0;
  11. }

E3234 Sort
First AC: 2018-04-27 Latest Modification: 2018-04-27

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const ll M=100001;
  5. ll a[M],b[M];
  6. ll n,rst;
  7. ll i,j,k;
  8. void Merge(ll a[],ll lft,ll mid,ll rgt)
  9. {
  10.     i=lft,j=mid+1,k=lft;
  11.     while(i<=mid&&j<=rgt){
  12.         if(a[i]<=a[j])b[k++]=a[i++];
  13.         else rst+=j-k,b[k++]=a[j++];
  14.     }
  15.     while(i<=mid)b[k++]=a[i++];
  16.     while(j<=rgt)b[k++]=a[j++];
  17.     for(i=lft;i<=rgt;++i)a[i]=b[i];
  18. }
  19. void MergeSort(ll a[],ll lft,ll rgt)
  20. {
  21.     if(lft<rgt){ ll mid=(lft+rgt)/2; MergeSort(a,lft,mid); MergeSort(a,mid+1,rgt); Merge(a,lft,mid,rgt); } } int main() { ios::sync_with_stdio(false); while(cin>>n){
  22.         for(i=0;i<n;++i)cin>>a[i];
  23.         rst=0;
  24.         MergeSort(a,0,n-1);
  25.         cout<<rst<<endl;
  26.     }
  27.     return 0;
  28. }

E3236 因子平方和
First AC: 2017-10-30 Latest Modification: 2017-10-30

  1. #include
  2. using namespace std;
  3. int T,s,n;
  4. int i,j;
  5. int main()
  6. {
  7.     cin>>T;
  8.     for(i=0;i<T;++i){ s=0; cin>>n;
  9.         for(j=2;j<n;++j)if(n%j==0)s+=j*j;
  10.         cout<<"case #"<<i<<":\n"<<s<<endl;
  11.     }
  12.     return 0;
  13. }

E3237 n!进制
First AC: 2017-12-11 Latest Modification: 2017-12-11

  1. #include
  2. using namespace std;
  3. long a[10]={0,1};
  4. int T,i,j,cnt;
  5. long n,tmp;
  6. int main()
  7. {
  8.     for(i=2;i<10;++i)a[i]=a[i-1]*i; cin>>T;
  9.     for(i=0;i<T;++i){ cin>>n;
  10.         cout<<"case #"<<i<<":\n";
  11.         for(cnt=0,j=9;j;--j){
  12.             if(tmp=n/a[j])cnt=1;
  13.             if(cnt)cout<<tmp;
  14.             n%=a[j];
  15.         }
  16.         cout<<endl;
  17.     }
  18.     return 0;
  19. }

E3238 字串非重复字符数排序
First AC: 2017-11-24 Latest Modification: 2018-03-01

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,len;
  4. struct data{
  5.     string s;
  6.     int len,num;
  7. }a[100];
  8. bool jdg[26];
  9. int i,j,k;
  10. bool cmp(data a,data b)
  11. {
  12.     if(a.num!=b.num)return a.num>b.num;
  13.     return a.s<b.s; } int main() { cin>>T;
  14.     for(i=0;i<T;++i){ cin>>n;
  15.         for(j=0;j<n;++j){ cin>>a[j].s;
  16.             a[j].len=a[j].s.length();
  17.             a[j].num=0;
  18.             memset(jdg,0,sizeof(jdg));
  19.             for(k=0;k<a[j].len;++k){
  20.                 if(!jdg[a[j].s[k]-'A'])++a[j].num,jdg[a[j].s[k]-'A']=1;
  21.             }
  22.         }
  23.         sort(a,a+n,cmp);
  24.         cout<<"case #"<<i<<":\n";
  25.         for(j=0;j<n;++j)cout<<a[j].s<<endl;
  26.     }
  27.     return 0;
  28. }

E3239 最长的等差数列
First AC: 2017-12-23 Latest Modification: 2018-06-08

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,rst,cnt,tmp;
  4. int a[101];
  5. int i,j,k,r;
  6. int main()
  7. {
  8.     cin>>T;
  9.     for(i=0;i<T;++i){ cin>>n;
  10.         for(rst=j=0;j<n;++j)cin>>a[j];
  11.         cout<<"case #"<<i<<":\n";
  12.         if(n==1){cout<<1<<endl;continue;}
  13.         sort(a,a+n);
  14.         for(j=0;j<n;++j){
  15.             for(k=j+1;k<n;++k){
  16.                 tmp=a[k]-a[j];
  17.                 for(cnt=2,r=k+1;r<n;++r){ if(a[r]==a[j]+cnt*tmp)++cnt;continue; if(a[r]>a[j]+cnt*tmp&&a[r-1]<a[j]+cnt*tmp)break; } if(cnt>rst)rst=cnt;
  18.             }
  19.         }
  20.         cout<<rst<<endl;
  21.     }
  22.     return 0;
  23. }

E3240 小香农范诺编码
First AC: 2018-03-07 Latest Modification: 2018-03-07

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n;
  4. int suma[201];
  5. struct data{
  6.     int n;
  7.     string s;
  8. }a[200];
  9. int i,j;
  10. void code(int lft,int rgt)
  11. {
  12.     int m=suma[lft]+suma[rgt];
  13.     int i,j;
  14.     for(i=lft+1;;++i){
  15.         if((abs(2*suma[i+1]-m)>=abs(2*suma[i]-m)))break;
  16.     }
  17.     for(j=lft;j<i;++j)a[j].s+='0';
  18.     for(j=i;j<rgt;++j)a[j].s+='1'; if(i-lft>1)code(lft,i);
  19.     if(rgt-i>1)code(i,rgt);
  20. }
  21. int main()
  22. {
  23.     cin>>T;
  24.     for(i=0;i<T;++i){ cin>>n;
  25.         for(j=0;j<n;++j) cin>>a[j].n,suma[j+1]=suma[j]+a[j].n,a[j].s="";
  26.         code(0,n);
  27.         cout<<"case #"<<i<<":\n";
  28.         for(j=0;j<n;++j)cout<<a[j].n<<':'<<a[j].s<<endl;
  29.     }
  30.     return 0;
  31. }

E3241 字母替换
First AC: 2017-10-27 Latest Modification: 2018-06-09

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,i,j,l;
  4. string s;
  5. int main()
  6. {
  7.     cin>>T;
  8.     for(i=0;i<T;++i){
  9.         cout<<"case #"<<i<<":\n"; cin>>s;
  10.         l=s.length();
  11.         for(j=0;j<l;++j) if(j%2==0&&s[j]>='A'&&s[j]<='Z')
  12.                 cout<<(char)(s[j]-'A'+'a');
  13.             else cout<<s[j];
  14.         cout<<endl;
  15.     }
  16.     return 0;
  17. }

E3242 重复数
First AC: 2017-11-04 Latest Modification: 2018-06-09

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n;
  4. int a[1005],b[1005],M;
  5. int i,j,k;
  6. int main()
  7. {
  8.     cin>>T;
  9.     for(i=0;i<T;++i){ cin>>n;
  10.         memset(a,0,sizeof(a)),memset(b,0,sizeof(b)),M=0;
  11.         for(j=0;j<n;++j)cin>>a[j];
  12.         for(j=0;j<n-1;++j){
  13.             for(k=j+1;k<n;++k)if(a[j]==a[k])++b[j]; if(b[j]>M)M=b[j];
  14.         }
  15.         cout<<"case #"<<i<<":\n"<<M+1<<endl; 
  16.     }
  17.     return 0;
  18. }

E3243 搜索联系人
First AC: 2017-12-22 Latest Modification: 2018-06-09

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long T,n,ls,cnt;
  4. struct data{
  5.     string name,tel;
  6.     long lt;
  7.     bool flag;
  8. }a[10005];
  9. string s;
  10. long i,j,k,l;
  11. bool cmp(data a,data b)
  12. {
  13.     if(a.flag!=b.flag)return a.flag>b.flag;
  14.     if(a.name!=b.name){
  15.         int len1=a.name.length(),len2=b.name.length();
  16.         int tmp=len1<len2? len1:len2;
  17.         for(int i=0;i<tmp;++i)
  18.             if(a.name[i]-b.name[i])
  19.                 return a.name[i]<b.