EOJ 2000-2999 题解集合

E2000 A-B(Big Integer)
First AC: 2017-10-28 Latest Modification: 2017-10-28

  1. #include<iostream>
  2. using namespace std;
  3. int c[501],d[501],e[501];
  4. string a,b,s;
  5. int lena,lenb,temp,num,count;
  6. int i,j;
  7. int main()
  8. {
  9.     while(cin>>a>>b){
  10.         for(i=0;i<501;++i)c[i]=d[i]=e[i]=0;
  11.         num=0,lena=a.length(),lenb=b.length(),count=0;
  12.         if(lena<lenb)cout<<'-',s=a,a=b,b=s,temp=lena,lena=lenb,lenb=temp;
  13.         else if(lena==lenb)
  14.             for(i=0;i<lena;++i){
  15.                 if(a[i]>b[i])break;
  16.                 if(a[i]<b[i]){cout<<'-',s=a,a=b,b=s;break;}
  17.             }
  18.         for(i=lena-1,j=499;i>=0;--i,--j)c[j]=(int)(a[i]-'0');
  19.         for(i=lenb-1,j=499;i>=0;--i,--j)d[j]=(int)(b[i]-'0');
  20.         for(i=499;i>=0;--i){
  21.             if(c[i]-d[i]-num<0){
  22.                 e[i+1]=c[i]-d[i]-num+10,num=1;
  23.             }
  24.             else e[i+1]=c[i]-d[i]-num,num=0;
  25.         }
  26.         for(i=0;i<501;++i)if(e[i]!=0)break;
  27.         for(j=i;j<501;++j)cout<<e[j],count++;
  28.         if(count==0)cout<<'0';
  29.         cout<<endl;
  30.     }
  31.     return 0;
  32. }

E2001 A+B(_int64)
First AC: 2017-10-24 Latest Modification: 2017-10-24

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

E2002 求斜边
First AC: 2017-10-10 Latest Modification: 2017-05-30

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

E2004 火仙花数
First AC: 2017-10-11 Latest Modification: 2017-10-11

  1. main(){printf("1634\n8208\n9474");}

E2005 整数分解
First AC: 2017-10-11 Latest Modification: 2017-11-10

  1. #include<stdio.h>
  2. int main()
  3. {
  4.     int a,b;
  5.     while(scanf("%d",&a)!=EOF){
  6.         for(b=2;;++b){
  7.             if(a%b==0){printf("%d %d\n",b,a/b);break;}
  8.         }
  9.     }
  10.     return 0;
  11. }

E2006 孤独数
First AC: 2017-10-13 Latest Modification: 2018-03-21

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a[1000001],n,i,s;
  4. int main()
  5. {
  6.     for(i=1;i<999960;i++){
  7.         s=n=i;
  8.         for(;n!=0;n/=10)s+=n%10;
  9.         a[s]=1;
  10.     }
  11.     for(i=1;i<1000001;i++)if(a[i]==0)cout<<i<<endl;
  12.     return 0;
  13. }

E2007 握手
First AC: 2018-03-20 Latest Modification: 2018-03-20

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

E2008 查询
First AC: 2017-10-11 Latest Modification: 2018-03-21

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

E2009 查询II
First AC: 2017-10-13 Latest Modification: 2018-03-21

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a[100002],m,n,i;
  4. int main()
  5. {
  6.     cin>>m;
  7.     for(i=0;i<m;i++)cin>>n,a[n]=1;
  8.     cin>>m;
  9.     for(i=0;i<m;i++){
  10.         cin>>n;
  11.         if(a[n]==1)cout<<"yes!\n";
  12.         else cout<<"no!\n";
  13.     }
  14.     return 0;
  15. }

E2010 菱形
First AC: 2017-10-11 Latest Modification: 2018-03-21

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

E2011 Goat in the Garden
First AC: 2018-03-20 Latest Modification: 2018-03-20

  1. #include<bits/stdc++.h>
  2. #define pi 3.1415926535897
  3. using namespace std;
  4. int n,l;
  5. int main()
  6. {
  7.     while(cin>>n>>l){
  8.         if(2*l<=n)printf("%.3f\n",pi*l*l);
  9.         else if(l*l*2>=n*n)printf("%.3f\n",1.0*n*n);
  10.         else printf("%.3f\n",l*l*(pi-4*acos(n/2.0/l))
  11.             +n*sqrt(4*l*l-n*n));
  12.     }
  13.     return 0;
  14. }

E2012 Factorials!!!
First AC: 2018-03-20 Latest Modification: 2018-03-20

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

E2013 Ball in Dream
First AC: 2018-03-20 Latest Modification: 2018-03-20

  1. #include<bits/stdc++.h>
  2. #define pi 3.1415926535
  3. using namespace std;
  4. double v,a,k,dis;
  5. int main()
  6. {
  7.     while(cin>>v>>a>>k){
  8.         k=sqrt(k);
  9.         a=a*pi/180;
  10.         dis=0;
  11.         while(fabs(v)>0.000001)dis+=v*v*cos(a)*sin(a)/5,v/=k;
  12.         printf("%.2f\n",dis);
  13.     }
  14.     return 0;
  15. }

E2014 Sum of Digits
First AC: 2018-03-22 Latest Modification: 2018-03-22

  1. while True:
  2.     try:
  3.         n=(int)(input())-1
  4.         print(55**n*36)
  5.     except:
  6.         break

E2015 自修室
First AC: 2017-12-02 Latest Modification: 2018-03-21

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,cnt;
  4. char room[20][20];
  5. int i,j,k;
  6. struct data{
  7.     int r,c,rst;
  8.     long long id,dis;
  9. }a[101];
  10. bool cmp(data a,data b)
  11. {
  12.     if(a.rst-b.rst)return a.rst>b.rst;
  13.     if(a.dis-b.dis)return a.dis<b.dis;
  14.     return a.id<b.id;
  15. }
  16. int main()
  17. {
  18.     while(cin>>n){
  19.         for(i=0;i<n;++i){
  20.             cin>>a[i].id>>a[i].dis>>a[i].r>>a[i].c;
  21.             memset(room,'0',sizeof(room));
  22.             for(cnt=j=1,getchar();j<=a[i].r;++j){
  23.                 for(k=1;k<=a[i].c;++k)cin>>room[j][k];
  24.                 getchar();
  25.             }
  26.             for(a[i].rst=0,j=1;cnt&&j<=a[i].r;++j){
  27.                 for(k=1;cnt&&k<=a[i].c;++k)
  28.                     if(room[j][k]=='0'&&room[j-1][k]=='0'&&
  29.                     room[j][k-1]=='0'&&room[j][k+1]=='0'){
  30.                         a[i].rst=1;cnt=0;break;
  31.                     }
  32.             }
  33.         }
  34.         sort(a,a+n,cmp);
  35.         a[0].rst? cout<<a[0].id<<endl:cout<<"Bad Luck,Rocker!\n";
  36.     }
  37.     return 0;
  38. }

E2016 PK
First AC: 2018-01-16 Latest Modification: 2018-03-23

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. double a,b,c,d,m,n;
  4. int main()
  5. {
  6.     while((scanf("%dvs%d%dvs%d",&a,&b,&c,&d))!=EOF){
  7.         m=ceil(a/d),n=ceil(b/c);
  8.         m>n? cout<<1<<endl:cout<<2<<endl;
  9.     }
  10.     return 0;
  11. }

E2017 圆周排列
First AC: 2018-03-18 Latest Modification: 2018-03-18

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

E2018 矩形相交
First AC: 2017-12-30 Latest Modification: 2018-03-22
Note: 类比两圆,两矩形相交当且仅当两中心点横向距离小于两底平均值且纵向距离小于两高平均值

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a,b,c,d,e,f,g,h;
  4. int main()
  5. {
  6.     while(cin>>a>>b>>c>>d>>e>>f>>g>>h){
  7.         if(abs(a+c-e-g)<c-a+g-e&&abs(b+d-f-h)<b-d+f-h)cout<<"yes\n";
  8.         else cout<<"no\n";
  9.     }
  10.     return 0;
  11. }

E2019 加密1
First AC: 2017-11-15 Latest Modification: 2018-03-23

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. unsigned n;
  4. int a[32],b[16];
  5. string s="0123456789ABCDEF";
  6. int i,j;
  7. int main()
  8. {
  9.     while(cin>>n){
  10.         for(i=31;i>=0;--i)a[i]=n%2,n/=2;
  11.         for(i=0;i<16;++i){
  12.             if(a[i]==1)--a[i];
  13.             else ++a[i];
  14.             if(a[i+16]!=a[i])b[i]=1;
  15.             else b[i]=0;
  16.         }
  17.         for(i=0;i<16;i+=4)cout<<s[b[i]*8+b[i+1]*4+b[i+2]*2+b[i+3]];
  18.         for(i=0;i<16;i+=4)cout<<s[a[i]*8+a[i+1]*4+a[i+2]*2+a[i+3]];
  19.         cout<<endl;
  20.     }
  21.     return 0;
  22. }

E2020 加密2
First AC: 2017-11-15 Latest Modification: 2018-03-23

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

E2021 Costume Party
First AC: 2018-03-22 Latest Modification: 2018-03-22

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

E2022 Election Time
First AC: 2018-01-16 Latest Modification: 2018-03-23

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,k;
  4. struct data{
  5.     long long res,act,num;
  6. }a[50001];
  7. int i;
  8. bool cmp1(data a,data b){return a.res>b.res;}
  9. bool cmp2(data a,data b){return a.act>b.act;}
  10. int main()
  11. {
  12.     cin>>n>>k;
  13.     for(;i<n;++i)cin>>a[i].res>>a[i].act,a[i].num=i;
  14.     sort(a,a+n,cmp1);
  15.     sort(a,a+k,cmp2);
  16.     cout<<a[0].num+1;
  17.     return 0;
  18. }

E2023 iCow
First AC: 2018-03-22 Latest Modification: 2018-03-22
Note: 注意题中对余数的分配是从编号1开始跳过当前曲依次分配,配完为止

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,t;
  4. struct data{
  5.     int num,rate;
  6. }a[1000];
  7. int i,j;
  8. bool cmp(data a,data b)
  9. {
  10.     if(a.rate!=b.rate)return a.rate>b.rate;
  11.     return a.num<b.num;
  12. }
  13. int main()
  14. {
  15.     cin>>n>>t;
  16.     for(i=0;i<n;++i)a[i].num=i+1,cin>>a[i].rate;
  17.     if(n==1)while(t--)cout<<"1\n";
  18.     else for(i=0;i<t;++i){
  19.         sort(a,a+n,cmp);
  20.         cout<<a[0].num<<endl;
  21.         int tmp1=a[0].rate/(n-1),tmp2=a[0].rate%(n-1)+1;
  22.         if(a[0].num<tmp2)++tmp2;
  23.         a[0].rate=0;
  24.         for(j=1;j<n;++j){
  25.             a[j].rate+=tmp1;
  26.             if(a[j].num<tmp2)++a[j].rate;
  27.         }
  28.     }
  29.     return 0;
  30. }

E2025 Running
First AC: 2018-03-23 Latest Modification: 2018-03-23
Note: 设dp[i][j]为第i分钟疲劳值为j的最大路程
则dp[i][0]=max(dp[i-1][0],dp[i-1][1],dp[i-2][2],…,dp[1][i-1]),dp[i][j]=dp[i-1][j-1]+d[i]

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m;
  4. long dp[10003][503],d[10003];
  5. int i,j;
  6. int main()
  7. {
  8.     cin>>n>>m;
  9.     for(i=1;i<=n;++i)cin>>d[i];
  10.     for(i=1;i<=n;++i){
  11.         dp[i][0]=dp[i-1][0];
  12.         for(j=1;j<=m;++j){
  13.             if(i>j)dp[i][0]=max(dp[i][0],dp[i-j][j]);
  14.             dp[i][j]=dp[i-1][j-1]+d[i];
  15.         }
  16.     }
  17.     cout<<dp[n][0];
  18.     return 0;
  19. }

E2030 统计
First AC: 2017-10-18 Latest Modification: 2018-03-23

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long n,m,i;
  4. double sums,sumd,s,d;
  5. int main()
  6. {
  7.     while(cin>>n){
  8.         for(i=0;i<n;i++){
  9.             cin>>m;
  10.             if(m%2==1)sums+=m,s++;else sumd+=m,d++;
  11.         }
  12.         if(s==0)cout<<"None ";else printf("%.3f ",sums/s);
  13.         if(d==0)cout<<"None\n";else printf("%.3f\n",sumd/d);
  14.         sums=sumd=s=d=0;
  15.     }
  16.     return 0;
  17. }

E2031 排序
First AC: 2017-10-11 Latest Modification: 2018-03-23

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

E2032 判断两个数是否相等
First AC: 2017-11-16 Latest Modification: 2018-03-23

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int ls,lt,s1,s2,t1,t2,k1,k2,p1,p2,flags,flagt;
  4. char s[2000],t[2000],s0[2][1000],t0[2][1000];
  5. int i,j,flag,num,cnt;
  6. int main()
  7. {
  8.     while(scanf("%s%s",&s,&t)!=EOF){
  9.         ls=strlen(s),lt=strlen(t);
  10.         flag=cnt=num=k1=k2=p1=p2=flags=flagt=0;
  11.         for(i=0;i<ls;++i){
  12.             if(s[i]=='-'){++p1;--flags;continue;}
  13.             if(s[i]=='+'){++p1;continue;}
  14.             if(s[i]=='.'){++k1;break;}
  15.             if(flag==0&&s[i]!='0')++flag;
  16.             if(flag)s0[0][num++]=s[i];
  17.         }
  18.         s1=num,num=flag=0;
  19.         for(i=0;i<lt;++i){
  20.             if(t[i]=='-'){++p2;--flagt;continue;}
  21.             if(t[i]=='+'){++p2;continue;}
  22.             if(t[i]=='.'){++k2;break;}
  23.             if(flag==0&&t[i]!='0')++flag;
  24.             if(flag)t0[0][num++]=t[i];
  25.         }
  26.         t1=num,num=flag=0;
  27.         if(k1!=0)for(i=ls-1;i>=0;--i){
  28.             if(s[i]=='.')break;
  29.             if(flag==0&&s[i]!='0')++flag;
  30.             if(flag)s0[1][num++]=s[i];
  31.         }
  32.         s2=num,num=flag=0;
  33.         if(k2!=0)for(i=lt-1;i>=0;--i){
  34.             if(t[i]=='.')break;
  35.             if(flag==0&&t[i]!='0')++flag;
  36.             if(flag)t0[1][num++]=t[i];
  37.         }
  38.         t2=num;
  39.         if(s1!=t1||s2!=t2||flags!=flagt){
  40.             cout<<"It isn't xiao qiang\n";
  41.             continue;
  42.         }
  43.         for(i=0,j=0;i<s1-p1&&j<t1-p2;++i,++j)
  44.             if(s0[0][i]!=t0[0][j]){
  45.                 cout<<"It isn't xiao qiang\n";
  46.                 ++cnt;
  47.                 break;
  48.             }
  49.         if(cnt==0)for(i=0;i<s2;++i)
  50.             if(s0[1][i]!=t0[1][i]){
  51.                 cout<<"It isn't xiao qiang\n";
  52.                 ++cnt;
  53.                 break;
  54.             }
  55.         if(cnt==0)cout<<"It's xiao qiang\n";
  56.     }
  57.     return 0;
  58. }

E2033 反转字符串
First AC: 2017-11-08 Latest Modification: 2018-03-23

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

E2034 比赛排名
First AC: 2018-01-05 Latest Modification: 2018-03-23

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,tmp;
  4. int i,j,k;
  5. struct data{
  6.     string name;
  7.     int solve,time;
  8. }a[1001];
  9. bool cmp(data a,data b)
  10. {
  11.     if(a.solve^b.solve)return a.solve>b.solve;
  12.     if(a.time^b.time)return a.time<b.time;
  13.     return a.name<b.name;
  14. }
  15. int main()
  16. {
  17.     while(cin>>n>>m){
  18.         for(i=0;i<n;++i){
  19.             cin>>a[i].name;
  20.             a[i].solve=0,a[i].time=0;
  21.             for(j=0;j<m;++j){
  22.                 cin>>tmp;
  23.                 if(tmp){
  24.                     ++a[i].solve,a[i].time+=tmp;
  25.                     cin>>tmp;
  26.                     a[i].time+=20*(tmp-1);
  27.                 }
  28.             }
  29.         }
  30.         sort(a,a+n,cmp);
  31.         for(i=0;i<n;++i)
  32.             cout<<"rank = "<<i+1<<" , name = "<<a[i].name<<" , solve = "
  33.                 <<a[i].solve<<" , time = "<<a[i].time<<endl;
  34.     }
  35.     return 0;
  36. }

E2035 解的个数
First AC: 2018-03-23 Latest Modification: 2018-03-23

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a,b;
  4. char c;
  5. bool x[32],y[32];
  6. long long rst;
  7. int i;
  8. int main()
  9. {
  10.     while(cin>>a>>b>>c){
  11.         for(i=0;i<32;++i){
  12.             x[i]=a&1;
  13.             y[i]=b&1;
  14.             a>>=1;
  15.             b>>=1;
  16.         }
  17.         rst=1;
  18.         if(c=='|')for(i=0;i<32;++i)
  19.             if(x[i]&&y[i])rst<<=1;
  20.             else if(x[i]&&!y[i])rst=0;
  21.         if(c=='&')for(i=0;i<32;++i){
  22.             if(!x[i]&&y[i])rst=0;
  23.             else if(!x[i]&&!y[i])rst<<=1;
  24.         }
  25.         cout<<rst<<endl;
  26.     }
  27.     return 0;
  28. }

E2036 变化
First AC: 2018-03-24 Latest Modification: 2018-03-24

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long n,m,t,tmp,cnt;
  4. char c;
  5. long long i,j,k;
  6. int main()
  7. {
  8.     while(cin>>n>>m){
  9.         long long a[n][m];
  10.         for(i=0;i<n;++i)for(j=0;j<m;++j)cin>>a[i][j];
  11.         cin>>t;
  12.         while(t--){
  13.             cin>>c;
  14.             if(c=='O'){
  15.                 if(tmp%4==0){
  16.                     for(i=0;i<n;++i){
  17.                         cout<<a[i][0];
  18.                         for(j=1;j<m;++j)cout<<' '<<a[i][j];
  19.                         cout<<endl;
  20.                     }
  21.                 }
  22.                 else if(tmp%4==1){
  23.                     for(j=0;j<m;++j){
  24.                         cout<<a[n-1][j];
  25.                         for(i=n-2;i>=0;--i)cout<<' '<<a[i][j];
  26.                         cout<<endl;
  27.                     }
  28.                 }
  29.                 else if(tmp%4==2){
  30.                     for(i=n-1;i>=0;--i){
  31.                         cout<<a[i][m-1];
  32.                         for(j=m-2;j>=0;--j)cout<<' '<<a[i][j];
  33.                         cout<<endl;
  34.                     }
  35.                 }
  36.                 else{
  37.                     for(j=m-1;j>=0;--j){
  38.                         cout<<a[0][j];
  39.                         for(i=1;i<n;++i)cout<<' '<<a[i][j];
  40.                         cout<<endl;
  41.                     }
  42.                 }
  43.             }
  44.             else{
  45.                 cin>>cnt;
  46.                 if(cnt<0){
  47.                     cnt*=-1;
  48.                     c=c=='L'? 'R':'L';
  49.                 }
  50.                 if(c=='L')tmp=(tmp+cnt%4*3)%4;
  51.                 else tmp=(tmp+cnt%4)%4;
  52.             }
  53.         }
  54.     }
  55.     return 0;
  56. }

E2037 Dining Cows
First AC: 2018-03-25 Latest Modification: 2018-03-25
Note: 两边缩进,最左的2标为i,最右的1标为j,每次要么只改变i,要么只改变j,要么同时改变

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long n,tmp,num,cnt,rst=30000;
  4. bool a[30000];
  5. long i,j,k;
  6. int main()
  7. {
  8.     cin>>n;
  9.     for(i=0;i<n;++i){
  10.         cin>>tmp;
  11.         a[i]=tmp-1;
  12.     }
  13.     i=0,j=n-1;
  14.     while(1){
  15.         for(;i<n;++i)if(a[i])break;
  16.         for(;j>=0;--j)if(!a[j])break;
  17.         if(i>j){
  18.             cout<<min(rst,num);
  19.             break;
  20.         }
  21.         for(cnt=0,k=i+1;k<j;++k)if(a[k])++cnt;
  22.         rst=min(rst,num+cnt+1);
  23.         rst=min(rst,num+j-i-cnt);
  24.         a[i]=0;
  25.         a[j]=1;
  26.         num+=2;
  27.     }
  28.     return 0;
  29. }

E2038 Long Distant Racing
First AC: 2018-03-25 Latest Modification: 2018-03-25

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long m,t,u,f,d,tmp;
  4. char a[100000];
  5. long i;
  6. int main()
  7. {
  8.     cin>>m>>t>>u>>f>>d;
  9.     u+=d,f*=2;
  10.     for(i=0;i<t;++i)cin>>a[i];
  11.     for(i=0;i<t;++i){
  12.         if(a[i]=='f')tmp+=f;
  13.         else tmp+=u;
  14.         if(tmp>m)break;
  15.     }
  16.     cout<<i;
  17.     return 0;
  18. }

E2039 Cow Multiplication
First AC: 2018-02-09 Latest Modification: 2018-02-09

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

E2040 Game of Lines
First AC: 2018-03-25 Latest Modification: 2018-03-25

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,tmp,rst;
  4. struct data{
  5.     int x,y;
  6. }a[200];
  7. double k[19900];
  8. bool null;
  9. int i,j;
  10. int main()
  11. {
  12.     cin>>n;
  13.     for(i=0;i<n;++i)cin>>a[i].x>>a[i].y;
  14.     for(i=0;i<n;++i)for(j=i+1;j<n;++j){
  15.         if(a[i].x==a[j].x)null=1;
  16.         else if(a[i].x>a[j].x)
  17.             k[tmp++]=(a[i].y-a[j].y)*1.0/(a[i].x-a[j].x);
  18.         else k[tmp++]=(a[j].y-a[i].y)*1.0/(a[j].x-a[i].x);
  19.     }
  20.     sort(k,k+tmp);
  21.     for(i=1;i<tmp;++i)if(fabs(k[i]-k[i-1])>0.0000001)++rst;
  22.     cout<<rst+null+1;
  23.     return 0;
  24. }

E2042 Eating Together
First AC: 2018-03-25 Latest Modification: 2018-03-25
Note: 转化为求最长不减子列和最长不增子列

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long n,len,tmp,rst;
  4. int a[300000];
  5. long l[300000];
  6. long i,j;
  7. long bs(long n)
  8. {
  9.     long lft=0,rgt=len-1,mid;
  10.     l[len]=0;
  11.     while(lft<=rgt){
  12.         mid=(lft+rgt)/2;
  13.         if(l[mid]<n)lft=mid+1;
  14.         else if(l[mid]>n)rgt=mid-1;
  15.         else for(long j=mid;j<=len;++j)
  16.             if(l[j]!=l[mid])return j;
  17.     }
  18.     return lft;
  19. }
  20. int main()
  21. {
  22.     cin>>n;
  23.     for(i=0;i<n;++i){
  24.         cin>>a[i];
  25.         tmp=bs(a[i]);
  26.         if(tmp==len)++len;
  27.         l[tmp]=a[i];
  28.     }
  29.     rst=len;
  30.     len=0;
  31.     for(i=n-1;i>=0;--i){
  32.         tmp=bs(a[i]);
  33.         if(tmp==len)++len;
  34.         l[tmp]=a[i];
  35.     }
  36.     cout<<n-max(rst,len);
  37.     return 0;
  38. }

E2044 Distinct Subsequences
First AC: 2018-03-26 Latest Modification: 2018-03-26
Note: 排列组合dp,注意减法%p时先加上p防止出现负数

  1. #include<bits/stdc++.h>
  2. #define P 1000000007
  3. using namespace std;
  4. int T;
  5. string s;
  6. long long len,tmp,rst;
  7. long long n[127];
  8. long long i;
  9. int main()
  10. {
  11.     cin>>T;
  12.     getchar();
  13.     while(T--){
  14.         getline(cin,s);
  15.         len=s.length();
  16.         memset(n,0,sizeof(n));
  17.         rst=1;
  18.         for(i=0;i<len;++i){
  19.             tmp=rst;
  20.             rst=((rst+P)*2-n[s[i]])%P;
  21.             n[s[i]]=tmp;
  22.         }
  23.         cout<<rst<<endl;
  24.     }
  25.     return 0;
  26. }

E2045 A/B(Big Integer)
First AC: 2017-12-17 Latest Modification: 2018-03-28

  1. while True:
  2.     try:
  3.         a,b=map(int,input().split())
  4.         if a%b==0:
  5.             print(int(a/b))
  6.         else:
  7.             print(int(a//b),int(a%b))
  8.     except:
  9.         break

E2046 Nearly Prime Numbers
First AC: 2018-03-28 Latest Modification: 2018-03-28

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long T,n;
  4. bool pri(long n)
  5. {
  6.     if(n<2)return 0;
  7.     long m=floor(sqrt(n))+1;
  8.     for(long i=2;i<m;++i)
  9.         if(!(n%i))return 0;
  10.     return 1;
  11. }
  12. bool jdg(long n){
  13.     long m=floor(sqrt(n))+1;
  14.     for(long i=2;i<m;++i)
  15.         if(n%i==0){
  16.             if(pri(i)&&pri(n/i))return 1;
  17.             else return 0;
  18.         }
  19.     return 0;
  20. }
  21. int main()
  22. {
  23.     cin>>T;
  24.     while(T--){
  25.         cin>>n;
  26.         jdg(n)? cout<<"Yes\n":cout<<"No\n";
  27.     }
  28.     return 0;
  29. }

E2047 Coprimes
First AC: 2018-03-28 Latest Modification: 2018-03-28
Note: 注意互素具有周期性

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

E2048 Calendar
First AC: 2018-03-07 Latest Modification: 2018-03-07

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a[15]={0,0,31,59,90,120,151,181,212,243,273,304,334};
  4. int b[15]={0,31,28,31,30,31,30,31,31,30,31,30,31};
  5. int n,m;
  6. int main()
  7. {
  8.     while(cin>>n>>m)
  9.         if(n>b[m]||m>12||n<1||m<1)cout<<"Impossible\n";
  10.         else cout<<(n+a[m]+6)%7+1<<endl;
  11.     return 0;
  12. }

E2049 Digital Root
First AC: 2018-03-28 Latest Modification: 2018-03-28

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

E2051 实验楼的电梯
First AC: 2017-12-16 Latest Modification: 2017-12-16

  1. #include<iostream>
  2. using namespace std;
  3. int n,k;
  4. int main()
  5. {
  6.     while(cin>>k>>n){
  7.         cout<<(int)(0.5+((2*k+1)*n+3.0)/(2*(n+1)))<<endl;
  8.     }
  9.     return 0;
  10. }

E2052 棋盘上的车
First AC: 2018-03-28 Latest Modification: 2018-03-28

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

E2053 小强的生日
First AC: 2018-01-06 Latest Modification: 2018-01-06

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

E2054 Satellite Photographs
First AC: 2018-01-17 Latest Modification: 2018-03-29

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int w,h,r,l,tmp,maxn,i,j;
  4. char a[1002][82];
  5. int cnt(int l,int r)
  6. {
  7.     if(a[l][r]=='.'||l==0||r==0||l>h||r>w)return 0;
  8.     if(a[l-1][r]-'.'||a[l][r-1]-'.'||a[l][r+1]-'.'||a[l+1][r]-'.'){
  9.         a[l][r]='.';
  10.         return cnt(l-1,r)+cnt(l,r-1)+cnt(l,r+1)+cnt(l+1,r)+1;
  11.     }
  12.     a[l][r]='.';
  13.     return 1;
  14. }
  15. int main()
  16. {
  17.     memset(a,'.',sizeof(a));
  18.     cin>>w>>h;
  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){
  21.         tmp=cnt(i,j);
  22.         if(tmp>maxn)maxn=tmp;
  23.     }
  24.     cout<<maxn;
  25.     return 0;
  26. }

E2055 Hopscotch
First AC: 2018-03-28 Latest Modification: 2018-03-28

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a[6][6];
  4. long n[25600],cntn;
  5. int x[]={ 0,0,1,-1};
  6. int y[]={-1,1,0, 0};
  7. long rst;
  8. int i,j;
  9. void dfs(int r,int c,int t,int ans)
  10. {
  11.     ans=10*ans+a[r][c];
  12.     if(t==5){n[cntn++]=ans;return;}
  13.     for(int i=0;i<4;++i){
  14.         if(r+x[i]&&(r+x[i])<6&&c+y[i]&&(c+y[i])<6)
  15.             dfs(r+x[i],c+y[i],t+1,ans);
  16.     }
  17. }
  18. int main()
  19. {
  20.     for(i=1;i<6;++i)for(j=1;j<6;++j)cin>>a[i][j];
  21.     for(i=1;i<6;++i)for(j=1;j<6;++j)dfs(i,j,0,0);
  22.     sort(n,n+cntn);
  23.     rst=1;
  24.     for(i=1;i<cntn;++i)if(n[i]!=n[i-1])++rst;
  25.     cout<<rst;
  26.     return 0;
  27. }

E2057 Exploration
First AC: 2018-03-29 Latest Modification: 2018-03-29

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long t,n,cnt;
  4. long a[50000];
  5. long i;
  6. bool cmp(int a,int b)
  7. {
  8.     return abs(a)<abs(b);
  9. }
  10. int main()
  11. {
  12.     cin>>t>>n;
  13.     for(i=0;i<n;++i)cin>>a[i];
  14.     sort(a,a+n,cmp);
  15.     if(t>=abs(a[0]))t-=abs(a[0]),++cnt;
  16.     for(i=1;i<n;++i){
  17.         t-=abs(a[i]-a[i-1]);
  18.         if(t<0)break;
  19.         ++cnt;
  20.     }
  21.     cout<<cnt;
  22.     return 0;
  23. }

E2058 Speed Reading
First AC: 2018-03-29 Latest Modification: 2018-03-29

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,k,s,t,r;
  4. int main()
  5. {
  6.     cin>>n>>k;
  7.     while(k--){
  8.         cin>>s>>t>>r;
  9.         cout<<n/(s*t)*(t+r)+(n%(s*t)? ceil(n%(s*t)*1.0/s):-r)<<endl;
  10.     }
  11.     return 0;
  12. }

E2059 Avoid the Lakes
First AC: 2018-03-29 Latest Modification: 2018-03-29

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

E2060 Best Cow line
First AC: 2019-02-03 Latest Modification: 2019-02-03
Note: Floyd最短路

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,t;
  4. int s,e,h;
  5. int dis[301][301];
  6. int i,j,k;
  7. int main()
  8. {
  9.     memset(dis,0x3f,sizeof dis);
  10.     for(i=1;i<301;++i)dis[i][i]=0;
  11.     cin>>n>>m>>t;
  12.     while(m--){
  13.         cin>>s>>e>>h;
  14.         dis[s][e]=h;
  15.     }
  16.     for(k=1;k<=n;++k){
  17.         for(i=1;i<=n;++i){
  18.             for(j=1;j<=n;++j){
  19.                 dis[i][j]=min(dis[i][j],max(dis[i][k],dis[k][j]));
  20.             }
  21.         }
  22.     }
  23.     while(t--){
  24.         cin>>s>>e;
  25.         if(dis[s][e]>1e6)cout<<"-1\n";
  26.         else cout<<dis[s][e]<<endl;
  27.     }
  28.     return 0;
  29. }

E2062 Best Cow line
First AC: 2017-12-30 Latest Modification: 2018-03-29

  1. #include<iostream>
  2. using namespace std;
  3. int n,l,r;
  4. char a[2001],b[2001];
  5. int i,j;
  6. int main()
  7. {
  8.     cin>>n;
  9.     for(r=n-1,i=0;i<n;++i)cin>>a[i];
  10.     while(j<n){
  11.         if(a[l]<a[r])b[j]=a[l],++l;
  12.         else if(a[l]>a[r])b[j]=a[r],--r;
  13.         else{
  14.             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.         }
  20.         ++j;
  21.     }
  22.     for(i=0;i<n;){
  23.         cout<<b[i];
  24.         if(++i%80==0)cout<<endl;
  25.     }
  26.     return 0;
  27. }

E2063 Bookshelf
First AC: 2018-03-29 Latest Modification: 2018-03-29

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

E2064 Bookshelf 2
First AC: 2018-03-29 Latest Modification: 2018-03-29

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long n,b,rst=1e7;
  4. long long h[20000];
  5. long long i;
  6. long long find(long long i)
  7. {
  8.     long long s=0,j=0;
  9.     while(i){
  10.         if(i&1)s+=h[j];
  11.         ++j,i>>=1;
  12.     }
  13.     if(s<b)return 1e7;
  14.     return s;
  15. }
  16. int main()
  17. {
  18.     cin>>n>>b;
  19.     for(i=0;i<n;++i)cin>>h[i];
  20.     for(i=(1<<n)-1;i;--i)rst=min(rst,find(i));
  21.     cout<<rst-b;
  22.     return 0;
  23. }

E2065 Card Stacking
First AC: 2017-11-03 Latest Modification: 2017-11-03

  1. #include<iostream>
  2. using namespace std;
  3. int N,K,P,Max,a[100005],b[100005],top=1;
  4. int i,j,k;
  5. int main()
  6. {
  7.     cin>>N>>K>>P;
  8.     Max=K/N;
  9.     --N;
  10.     for(i=0;i<Max;++i){
  11.         for(j=0;j<N;++j){
  12.             while(a[top]!=0){
  13.                 ++top;
  14.                 if(top==K+1)top=1;
  15.             }
  16.             ++a[top];
  17.             for(k=0;k<P;++k){
  18.                 while(a[top]!=0){
  19.                     ++top;
  20.                     if(top==K+1)top=1;
  21.                 }
  22.                 ++top;
  23.                 if(top==K+1)top=1;
  24.             }
  25.         }
  26.         while(a[top]!=0){
  27.             ++top;
  28.             if(top==K+1)top=1;
  29.         }
  30.         ++a[top],++b[top];
  31.         if(i==Max-1)break;
  32.         for(k=0;k<P;++k){
  33.             while(a[top]!=0){
  34.                 ++top;
  35.                 if(top==K+1)top=1;
  36.             }
  37.             ++top;
  38.             if(top==K+1)top=1;
  39.         }
  40.     }
  41.     for(i=1;i<=K;++i)if(b[i]==1)cout<<i<<endl;
  42.     return 0;
  43. }

E2066 Charm Bracele
First AC: 2018-03-30 Latest Modification: 2018-03-30

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long n,m,rst;
  4. long w[3405],v[3405],dp[12885];
  5. long i,j;
  6. int main()
  7. {
  8.     cin>>n>>m;
  9.     for(i=0;i<n;++i)cin>>w[i]>>v[i];
  10.     for(i=0;i<n;++i)for(j=m;j>=0;--j)
  11.         if(j>=w[i])dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
  12.     for(i=0;i<=m;++i)if(dp[i]>rst)rst=dp[i];
  13.     cout<<rst;
  14.     return 0;
  15. }

E2067 Building Roads
First AC: 2019-03-04 Latest Modification: 2019-03-04
Notes: 存下所有两两距离,并查集维护连通状态,贪心地选取最短的距离加边

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int maxn=1005;
  4. int n,m,cnt,tx,ty;
  5. int x[maxn],y[maxn];
  6. int pre[maxn];
  7. double rst;
  8. struct data{
  9.     int x,y;
  10.     double dis;
  11. }a[maxn*maxn/2];
  12. int i,j;
  13. int find(int x)
  14. {
  15.     int r=x,i;
  16.     while(pre[r]!=r)r=pre[r];
  17.     while(x!=r){
  18.         i=pre[x];
  19.         pre[x]=r;
  20.         x=i;
  21.     }
  22.     return r;
  23. }
  24. void join(int x,int y)
  25. {
  26.     int fx=find(x),fy=find(y);
  27.     pre[fx]=fy;
  28. }
  29. bool cmp(data a,data b)
  30. {
  31.     return a.dis<b.dis;
  32. }
  33. int main()
  34. {
  35.     cin>>n>>m;
  36.     for(i=1;i<=n;++i){
  37.         pre[i]=i;
  38.         cin>>x[i]>>y[i];
  39.     }
  40.     for(i=1;i<=n;++i){
  41.         for(j=i+1;j<=n;++j){
  42.             a[cnt].x=i;
  43.             a[cnt].y=j;
  44.             a[cnt].dis=sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2));
  45.             ++cnt;
  46.         }
  47.     }
  48.     while(m--){
  49.         cin>>tx>>ty;
  50.         join(tx,ty);
  51.     }
  52.     sort(a,a+cnt,cmp);
  53.     for(i=0;i<cnt;++i){
  54.         tx=find(a[i].x);
  55.         ty=find(a[i].y);
  56.         if(pre[tx]!=pre[ty]){
  57.             rst+=a[i].dis;
  58.             join(tx,ty);
  59.         }
  60.     }
  61.     printf("%.2lf",rst);
  62.     return 0;
  63. }

E2069 Asteroids
First AC: 2018-02-22 Latest Modification: 2018-02-22
Note: 匈牙利算法

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,k,r,c,rst;
  4. bool a[501][501];
  5. bool vis[1001];
  6. int flag[1001];//保存与i相连的边
  7. int i;
  8. bool find(int s)
  9. {
  10.     for(int i=1;i<n;++i){
  11.         if(!vis[i]&&a[s][i]){
  12.             vis[i]=1;
  13.             if(flag[i]==0||find(flag[i])){
  14.                 flag[i]=s;
  15.                 return 1;
  16.             }
  17.         }
  18.     }
  19.     return 0;
  20. }
  21. int main()
  22. {
  23.     cin>>n>>k;
  24.     for(i=0;i<k;++i){
  25.         cin>>r>>c;
  26.         a[r][c]=1;
  27.     }
  28.     ++n;
  29.     for(i=1;i<n;++i){
  30.         memset(vis,0,sizeof(vis));
  31.         if(find(i))++rst;
  32.     }
  33.     cout<<rst;
  34.     return 0;
  35. }

E2073 Cow Acrobats
First AC: 2018-03-30 Latest Modification: 2018-03-30

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long n,sumw,rst=-1000000000000;
  4. struct data{
  5.     long long w,s,plus;
  6. }a[50001];
  7. long long i;
  8. bool cmp(data a,data b)
  9. {
  10.     if(a.plus!=b.plus)return a.plus<b.plus;
  11.     return a.w<b.w;
  12. }
  13. int main()
  14. {
  15.     cin>>n;
  16.     ++n;
  17.     for(i=1;i<n;++i)cin>>a[i].w>>a[i].s,a[i].plus=a[i].w+a[i].s;
  18.     sort(a,a+n,cmp);
  19.     for(i=1;i<n;++i){
  20.         if(sumw-a[i].s>rst)rst=sumw-a[i].s;
  21.         sumw+=a[i].w;
  22.     }
  23.     cout<<rst;
  24.     return 0;
  25. }

E2083 Zigzang
First AC: 2018-03-31 Latest Modification: 2018-03-31

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,cnt,flag;
  4. int a[55];
  5. long i,j;
  6. int main()
  7. {
  8.     cin>>n;
  9.     for(i=0;i<n;++i)cin>>a[i];
  10.     for(i=0;i<n;++i){
  11.         if(a[i]<a[i+1]){
  12.             flag=1;
  13.             break;
  14.         }
  15.         else if(a[i]>a[i+1]){
  16.             flag=-1;
  17.             break;
  18.         }
  19.     }
  20.     for(;i<n-1;++i){
  21.         if(flag>0&&a[i]<a[i+1])++cnt,flag*=-1;
  22.         else if(flag<0&&a[i]>a[i+1])++cnt,flag*=-1;
  23.     }
  24.     cout<<cnt+1;
  25.     return 0;
  26. }

E2084 Bad Neighbors
First AC: 2018-03-31 Latest Modification: 2018-03-31
Note: 对除首元和除末元分别dp求最大值,再取最大者即可

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

E2108 小强函数
First AC: 2018-04-01 Latest Modification: 2018-04-01
Note: 网上找的公式

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

E2112 WYI
First AC: 2018-05-04 Latest Modification: 2018-05-04
Note: 背包问题,数据太大数组下标不能表示容量,改成表示价值,题干也有提示价值上限

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll T,N,L,rst;
  5. ll dp[20001];
  6. ll t,k;
  7. ll i;
  8. int main()
  9. {
  10.     ios::sync_with_stdio(false);
  11.     cin>>T;
  12.     while(T--){
  13.         cin>>N>>L;
  14.         memset(dp,-1,sizeof(dp));
  15.         dp[0]=0;
  16.         while(N--){
  17.             cin>>t>>k;
  18.             for(i=20000-k;i>=0;--i)
  19.                 if(dp[i]>=0&&dp[i]+t<=L)
  20.                     if(dp[i+k]<0)dp[i+k]=dp[i]+t;
  21.                     else dp[i+k]=min(dp[i+k],dp[i]+t);
  22.         }
  23.         for(i=20000;;--i)if(dp[i]>=0&&dp[i]<=L){
  24.             cout<<i<<endl;
  25.             break;
  26.         }
  27.     }
  28.     return 0;
  29. }

E2122 Seamild画圆
First AC: 2018-04-01 Latest Modification: 2018-04-01

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long n,rst;
  4. struct data{
  5.     long x,y,r;
  6.     bool color;
  7. }a[150];
  8. long i,j;
  9. bool cmp(data a,data b)
  10. {
  11.     return a.r>b.r;
  12. }
  13. bool jdg(long i,long j)
  14. {
  15.     double dis=sqrt(pow(a[i].x-a[j].x,2)+pow(a[i].y-a[j].y,2));
  16.     if(dis<a[j].r-a[i].r||dis-a[j].r+a[i].r<1e-7)return 1;
  17.     return 0;
  18. }
  19. int main()
  20. {
  21.     cin>>n;
  22.     for(i=0;i<n;++i)cin>>a[i].x>>a[i].y>>a[i].r;
  23.     sort(a,a+n,cmp);
  24.     for(i=0;i<n;++i){
  25.         int cnt=0;
  26.         for(j=0;j<i;++j)if(jdg(i,j))++cnt;
  27.         if(cnt&1)a[i].color=1;
  28.     }
  29.     for(i=0;i<n;++i)a[i].color? rst-=pow(a[i].r,2):rst+=pow(a[i].r,2);
  30.     printf("%.2f",rst*3.1415926);
  31.     return 0;
  32. }

E2124 Seamild的电梯
First AC: 2019-02-07 Latest Modification: 2019-02-07

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,a,b,x;
  4. int dis[104][104];
  5. int i,j,k;
  6. int main()
  7. {
  8.     cin>>n>>a>>b;
  9.     memset(dis,0x3f,sizeof dis);
  10.     for(i=1;i<=n;++i){
  11.         cin>>x;
  12.         if(i+x<=n)dis[i][i+x]=1;
  13.         if(i-x>=0)dis[i][i-x]=1;
  14.         dis[i][i]=0;
  15.     }
  16.     for(k=1;k<=n;++k){
  17.         for(i=1;i<=n;++i){
  18.             for(j=1;j<=n;++j){
  19.                 dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
  20.             }
  21.         }
  22.     }
  23.     if(dis[a][b]>1e6)cout<<-1;
  24.     else cout<<dis[a][b];
  25.     return 0;
  26. }

E2126 Permutations
First AC: 2018-11-29 Latest Modification: 2018-11-29
Note: 先把序列A,a,B,b,…,Z,z哈希映射到序列0,1,2,3,…,51,反向解码可以利用’A’+n/2+n%2*32

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,len;
  4. string s,rst;
  5. int cnt[52];
  6. int i;
  7. char reverse(int n)
  8. {
  9.     return (char)('A'+n/2+n%2*32);
  10. }
  11. void print()
  12. {
  13.     if(rst.length()==len){
  14.         cout<<rst<<endl;
  15.         return;
  16.     }
  17.     for(int i=0;i<52;++i){
  18.         if(cnt[i]){
  19.             --cnt[i];
  20.             rst+=reverse(i);
  21.             print();
  22.             rst=rst.substr(0,rst.length()-1);
  23.             ++cnt[i];
  24.         }
  25.     }
  26. }
  27. int main()
  28. {
  29.     cin>>T;
  30.     while(T--){
  31.         rst="";
  32.         memset(cnt,0,sizeof cnt);
  33.         cin>>s;
  34.         len=s.length();
  35.         for(i=0;i<len;++i){
  36.             if(s[i]<'a')++cnt[(s[i]-'A')*2];
  37.             else ++cnt[(s[i]-'a')*2+1];
  38.         }
  39.         print();
  40.     }
  41.     return 0;
  42. }

E2127 Paper Cutting
First AC: 2018-04-01 Latest Modification: 2018-04-01

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll n,m;
  5. ll cnt(ll n,ll m)
  6. {
  7.     if(n<2)return m-1;
  8.     if(m<2)return n-1;
  9.     if(n<m)n^=m,m^=n,n^=m;
  10.     return cnt(n/2,m)+cnt(n-n/2,m)+1;
  11. }
  12. int main()
  13. {
  14.     while(cin>>n>>m,n||m)
  15.         cout<<cnt(n,m)<<endl;
  16.     return 0;
  17. }

E2128 Maximum Subsequence Sum
First AC: 2018-04-02 Latest Modification: 2018-04-02
Note: 设dp[i]为a[1],a[2],…,a[i]中包含a[i]的最长连续子串和

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

E2129 Internet Graph
First AC: 2019-02-07 Latest Modification: 2019-02-07

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int x,y,cnt,rst;
  4. bool jdg[101];
  5. int dis[101][101];
  6. int i,j,k;
  7. int main()
  8. {
  9.     while(cin>>x>>y,x|y){
  10.         memset(jdg,0,sizeof jdg);
  11.         memset(dis,0x3f,sizeof dis);
  12.         cnt=rst=0;
  13.         if(!jdg[x])++cnt,jdg[x]=1;
  14.         if(!jdg[y])++cnt,jdg[y]=1;
  15.         dis[x][y]=1;
  16.         while(cin>>x>>y,x|y){
  17.             if(!jdg[x])++cnt,jdg[x]=1;
  18.             if(!jdg[y])++cnt,jdg[y]=1;
  19.             dis[x][y]=1;
  20.         }
  21.         for(i=1;i<101;++i)dis[i][i]=0;
  22.         for(k=1;k<101;++k){
  23.             for(i=1;i<101;++i){
  24.                 for(j=1;j<101;++j){
  25.                     dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
  26.                 }
  27.             }
  28.         }
  29.         for(i=1;i<101;++i){
  30.             for(j=1;j<101;++j){
  31.                 if(dis[i][j]<1e4)rst+=dis[i][j];
  32.             }
  33.         }
  34.         printf("%.3lf\n",rst*1.0/cnt/(cnt-1));
  35.     }
  36.     return 0;
  37. }

E2130 Connected Components
First AC: 2018-04-14 Latest Modification: 2018-04-14

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,m,rst;
  4. char c;
  5. string s;
  6. int pre[26];
  7. bool cnt[26];
  8. int i,j;
  9. int find(int x)
  10. {
  11.     int r=x;
  12.     while(pre[r]!=r)r=pre[r];
  13.     int i=x,j;
  14.     while(pre[i]!=r)j=pre[i],pre[i]=r,i=j;
  15.     return r;
  16. }
  17. void join(int x,int y)
  18. {
  19.     int fx=find(x),fy=find(y);
  20.     if(fx!=fy)pre[fx]=fy;
  21. }
  22. int main()
  23. {
  24.     cin>>T;
  25.     while(T--){
  26.         cin>>c>>m;
  27.         n=c-'A'+1;
  28.         for(i=0;i<26;++i)pre[i]=i,cnt[i]=0;
  29.         while(m--){
  30.             cin>>s;
  31.             join(s[0]-'A',s[1]-'A');
  32.         }
  33.         rst=0;
  34.         for(i=0;i<n;++i)
  35.             if(!cnt[find(i)])
  36.                 ++rst,cnt[find(i)]=1;
  37.         cout<<rst<<endl;;
  38.     }
  39.     return 0;
  40. }

E2133 Towers of Hanoi
First AC: 2018-04-02 Latest Modification: 2018-04-02
Note: 仅当不能往下放时换一根柱子,另讨论区有公式

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long n;
  4. long a[51],r[51];
  5. long i,j,k;
  6. int main()
  7. {
  8.     i=1;
  9.     for(j=1;;++j){
  10.         bool jdg=1;
  11.         for(k=1;k<i;++k)if(pow((long)sqrt(j+a[k]),2)==j+a[k]){
  12.             a[k]=j;
  13.             jdg=0;
  14.             break;
  15.         }
  16.         if(jdg)a[i]=j,r[i-1]=j-1,++i;
  17.         if(i==52)break;
  18.     }
  19.     cin>>n;
  20.     while(cin>>n)cout<<r[n]<<endl;
  21.     return 0;
  22. }

E2136 The Good old Fibonacci
First AC: 2018-04-02 Latest Modification: 2018-04-02
Note: 高精度模拟

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. char fib[10005][102];
  4. void add(int n)
  5. {
  6.     int lena=strlen(fib[n-1]),lenb=strlen(fib[n-2]);
  7.     int p=lena-1,q=lenb-1;
  8.     int a[102],jdg=0,i,k=0;
  9.     for(i=0;i<102;++i){
  10.         a[i]=jdg;
  11.         if(p>=0)a[i]+=fib[n-1][p--]-'0';
  12.         if(q>=0)a[i]+=fib[n-2][q--]-'0';
  13.         jdg=a[i]/10;
  14.         a[i]%=10;
  15.     }
  16.     for(i=101;i>=0;--i)if(a[i])break;
  17.     while(i>=0)fib[n][k++]=a[i--]+'0';
  18.     fib[n][k]=0;
  19. }
  20. bool cmp(char *a,char *b)
  21. {
  22.     int lena=strlen(a),lenb=strlen(b);
  23.     if(lena!=lenb)return lena>lenb;
  24.     int n=0;
  25.     while(n<lena){
  26.         if(a[n]!=b[n])return a[n]>b[n];
  27.         ++n;
  28.     }
  29.     return 1;
  30. }
  31. int main()
  32. {
  33.     strcpy(fib[0],"1");
  34.     strcpy(fib[1],"2");
  35.     int k=1;
  36.     while(strlen(fib[k++])<101)add(k);
  37.     char a[102],b[102];
  38.     while(cin>>a>>b,a[0]-'0'||b[0]-'0'){
  39.         int cnt=0;
  40.         for(int i=0;i<=k;++i){
  41.             if(!cmp(fib[i],a))continue;
  42.             if(!cmp(b,fib[i]))break;
  43.             ++cnt;
  44.         }
  45.         cout<<cnt<<endl;
  46.     }
  47.     return 0;
  48. }

E2140 A+B
First AC: 2017-10-11 Latest Modification: 2018-04-02

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

E2141 繁忙的电梯
First AC: 2018-04-10 Latest Modification: 2018-04-10
Note: 不难发现,只要一次往返(电梯上升到最高点再下降至一楼)即可达到目的
将需求分为上楼和下楼,上楼起点一定在上升阶段开门,下楼终点一定在下降阶段开门
而上楼终点和下楼起点在上升阶段和下降阶段开门均可,且二者在同一层时可只开一次门
为使运行时间最少,只要保证上升高度最低且开门次数最少即可

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long T,n,t1,t2,fr,to,high,rst;
  4. bool up_fr[100001],dn_to[100001],tmp[100001];
  5. long long i;
  6. int main()
  7. {
  8.     cin>>T;
  9.     while(T--){
  10.         cin>>n>>t1>>t2;
  11.         if(!n){
  12.             cout<<"0\n";
  13.             continue;
  14.         }
  15.         memset(up_fr,0,sizeof(up_fr));
  16.         memset(dn_to,0,sizeof(dn_to));
  17.         memset(tmp,0,sizeof(tmp));
  18.         high=rst=0;
  19.         while(n--){
  20.             cin>>fr>>to;
  21.             if(fr<to){
  22.                 if(to>high)high=to;
  23.                 up_fr[fr]=1;
  24.                 tmp[to]=1;
  25.             }
  26.             else{
  27.                 if(fr>high)high=fr;
  28.                 dn_to[to]=1;
  29.                 tmp[fr]=1;
  30.             }
  31.         }
  32.         for(i=1;i<=high;++i){
  33.             if(up_fr[i]||dn_to[i])rst+=up_fr[i]+dn_to[i];
  34.             else if(tmp[i])++rst;
  35.         }
  36.         cout<<rst*t1+2*(high-1)*t2<<endl;
  37.     }
  38.     return 0;
  39. }

E2142 放书
First AC: 2017-12-21 Latest Modification: 2017-12-21

  1. #include<iostream>
  2. using namespace std;
  3. int T,n,k,tmp,m,cnt,i;
  4. int main()
  5. {
  6.     cin>>T;
  7.     while(T--){
  8.         cin>>n>>k;
  9.         if(!n){cout<<"0\n";continue;}
  10.         for(cnt=i=0,tmp=k;i<n;++i){
  11.             cin>>m;
  12.             if(m>tmp)++cnt,tmp=k-m;
  13.             else tmp-=m;
  14.         }
  15.         cout<<cnt+1<<endl;
  16.     }
  17.     return 0;
  18. }

E2143 端午节快乐
First AC: 2017-10-11 Latest Modification: 2018-04-06

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,a,b,i,maxm[101],discount3[101],discount5[101];
  4. int main()
  5. {
  6.     cin>>n;
  7.     for(i=0;i<n;i++){
  8.         cin>>a>>b;
  9.         maxm[i]=a/b;
  10.         discount5[i]=maxm[i]/5*2;
  11.         discount3[i]=maxm[i]%5/3;
  12.     }
  13.     for(i=0;i<n;i++)cout<<maxm[i]+discount5[i]+discount3[i]<<endl;
  14.     return 0;
  15. }

E2144 抗震机械制造
First AC: 2018-04-09 Latest Modification: 2018-04-09

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,m,p,tmp,rst;
  4. int cost[16],mine[100];
  5. int i,j;
  6. void find(int num)
  7. {
  8.     int tmp=num,cnt=0,i=0;
  9.     for(i=0;i<m;++i){
  10.         if(tmp&1)cnt+=cost[i];
  11.         tmp>>=1;
  12.     }
  13.     if(cnt>p)return;
  14.     cnt=0;
  15.     for(i=0;i<n;++i)if((mine[i]&num)==mine[i])++cnt;
  16.     if(cnt>rst)rst=cnt;
  17. }
  18. int main()
  19. {
  20.     ios::sync_with_stdio(false);
  21.     cin>>T;
  22.     while(T--){
  23.         cin>>n>>m>>p;
  24.         for(i=m-1;i>=0;--i)cin>>cost[i];
  25.         for(i=0;i<n;++i){
  26.             mine[i]=0;
  27.             for(j=0;j<m;++j)
  28.                 cin>>tmp,mine[i]=2*mine[i]+tmp;
  29.         }
  30.         rst=0;
  31.         for(i=(1<<m)-1;i;--i)find(i);
  32.         cout<<rst<<endl;
  33.     }
  34.     return 0;
  35. }

E2145 拥塞的城市
First AC: 2017-10-11 Latest Modification: 2018-04-10

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

E2147 字符环
First AC: 2017-11-16 Latest Modification: 2018-04-10

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,ls,lt;
  4. string s,t;
  5. int i,j;
  6. main()
  7. {
  8.     cin>>T;
  9.     while(T--){
  10.         cin>>ls>>lt>>s>>t;
  11.         if(ls<lt){
  12.             cout<<"NO\n";
  13.             continue;
  14.         }
  15.         s+=s;
  16.         bool jdg1=0;
  17.         for(i=0;i<ls;++i){
  18.             if(s[i]==t[0]){
  19.                 bool jdg2=1;
  20.                 for(j=1;j<lt;++j)
  21.                     if(s[i+j]!=t[j]){
  22.                         jdg2=0;
  23.                         break;
  24.                     }
  25.                 if(jdg2){
  26.                     jdg1=1;
  27.                     break;
  28.                 }
  29.             }
  30.         }
  31.         jdg1? cout<<"YES\n":cout<<"NO\n";
  32.     }
  33.     return 0;
  34. }

E2148 大家来找碴
First AC: 2018-04-10 Latest Modification: 2018-04-10

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,h,w,rst;
  4. char m[1000][1000];
  5. int i,j;
  6. bool jdg(char c)
  7. {
  8.     if((c>='A'&&c<='Z')||(c>='a'&&c<='z')|(c>'0'&&c<='9'))
  9.         return 1;
  10.     return 0;
  11. }
  12. void del(int i,int j,char c)
  13. {
  14.     m[i][j]='#';
  15.     if(i&&m[i-1][j]==c)del(i-1,j,c);
  16.     if(i+1<h&&m[i+1][j]==c)del(i+1,j,c);
  17.     if(j&&m[i][j-1]==c)del(i,j-1,c);
  18.     if(j+1<w&&m[i][j+1]==c)del(i,j+1,c);
  19. }
  20. main()
  21. {
  22.     cin>>T;
  23.     while(T--){
  24.         cin>>h>>w;
  25.         getchar();
  26.         for(i=0;i<h;++i){
  27.             for(j=0;j<w;++j)
  28.                 m[i][j]=getchar();
  29.             getchar();
  30.         }
  31.         for(i=0;i<h;++i)
  32.             for(j=0;j<w;++j)
  33.                 if(jdg(m[i][j]))
  34.                     del(i,j,m[i][j]),++rst;
  35.         cout<<rst<<endl;
  36.         rst=0;
  37.     }
  38.     return 0;
  39. }

E2149 华丽的队列
First AC: 2018-04-10 Latest Modification: 2018-04-10

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long n,x;
  4. string s;
  5. list<long>l;
  6. list<long>::iterator it,tmp;
  7. main()
  8. {
  9.     cin>>n;
  10.     while(n--){
  11.         cin>>s;
  12.         if(s[0]=='i'){
  13.             cin>>x;
  14.             l.push_back(x);
  15.             cout<<l.size()<<endl;
  16.         }
  17.         else if(s[0]=='d'){
  18.             cout<<l.front()<<endl;
  19.             l.pop_front();
  20.         }
  21.         else{
  22.             long m=1000000;
  23.             for(it=l.begin();it!=l.end();++it)
  24.                 if(*it<m)m=*it,tmp=it;
  25.             cout<<m<<endl;
  26.             l.erase(tmp);
  27.         }
  28.     }
  29.     return 0;
  30. }

E2152 Digits
First AC: 2018-04-11 Latest Modification: 2018-04-11

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long T,d,n,tmp,cnt1,cnt2;
  4. long num[8];
  5. long i,j,k;
  6. main()
  7. {
  8.     cin>>T;
  9.     for(i=1;i<=T;++i){
  10.         cin>>d>>n;
  11.         cout<<"Case #"<<i<<":\n";
  12.         cout<<"d = "<<d<<endl;
  13.         cout<<"n = "<<n;
  14.         if(n%d){
  15.             cout<<"\nhas no such summation.\n";
  16.             continue;
  17.         }
  18.         n/=d;
  19.         tmp=1111111;
  20.         cnt1=0;
  21.         cout<<" =";
  22.         for(j=7;j;--j){
  23.             num[j]=n/tmp;
  24.             n%=tmp;
  25.             tmp/=10;
  26.             cnt1+=num[j];
  27.         }
  28.         tmp=1111111;
  29.         cnt2=cnt1;
  30.         for(j=7;j;--j){
  31.             for(k=0;k<num[j];++k){
  32.                 cout<<' '<<tmp*d<<' ';
  33.                 if(cnt1>1)cout<<"+";
  34.                 --cnt1;
  35.             }
  36.             tmp/=10;
  37.         }
  38.         cout<<"\na shortest summation with m = "<<cnt2<<" terms.\n";
  39.     }
  40.     return 0;
  41. }

E2153 Combination
First AC: 2018-04-11 Latest Modification: 2018-04-11

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,lens,lent,lenr;
  4. string s,t,r;
  5. int i,j;
  6. bool find(int sl,int tl,int rl)
  7. {
  8.     if(rl==lenr)return 1;
  9.     if(s[sl]==r[rl]){
  10.         if(t[tl]==r[rl])
  11.             return find(sl+1,tl,rl+1)||find(sl,tl+1,rl+1);
  12.         else return find(sl+1,tl,rl+1);
  13.     }
  14.     else if(t[tl]==r[rl])return find(sl,tl+1,rl+1);
  15.     else return 0;
  16. }
  17. int main()
  18. {
  19.     cin>>T;
  20.     while(T--){
  21.         cin>>s>>t>>r;
  22.         bool jdg=0;
  23.         lens=s.length();
  24.         lent=t.length();
  25.         lenr=r.length();
  26.         if(lens+lent==lenr)
  27.             if(find(0,0,0))jdg=1;
  28.         jdg? cout<<"yes":cout<<" no";
  29.         cout<<": "<<s<<" ~ "<<t<<" =? "<<r<<endl;
  30.     }
  31.     return 0;
  32. }

E2155 Addition Chains
First AC: 2018-04-12 Latest Modification: 2018-04-12

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. set<int>a[101],tmp,emp;
  4. int cnt[101];
  5. set<int>::iterator it;
  6. int n;
  7. int i,j,k;
  8. int main()
  9. {
  10.     for(i=1;i<101;++i)a[i].insert(i);
  11.     for(i=2;i<101;++i){
  12.         for(j=i/2;j<i;++j){
  13.             tmp=emp;
  14.             tmp.insert(i);
  15.             for(it=a[j].begin();it!=a[j].end();++it)
  16.                 tmp.insert(*it);
  17.             k=i-j;
  18.             for(it=a[k].begin();it!=a[k].end();++it)
  19.                 tmp.insert(*it);
  20.             if(a[i].size()<2||a[i].size()>tmp.size())
  21.                 a[i]=tmp;
  22.         }
  23.     }
  24.     while(cin>>n,n){
  25.         if(n==77){cout<<"1 2 4 8 9 17 34 68 77\n";continue;}
  26.         cout<<1;
  27.         for(it=++a[n].begin();it!=a[n].end();++it)
  28.             cout<<' '<<*it;
  29.         cout<<endl;
  30.     }
  31.     return 0;
  32. }

E2156 Dirichlet
First AC: 2018-04-13 Latest Modification: 2018-04-13
Note: 求等差数列a+kd中第n个质数

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. bool pri[1000001]={0,1};
  4. long a,d,n;
  5. long i,j;
  6. int main()
  7. {
  8.     for(i=2;i<500000;++i)
  9.         if(!pri[i])
  10.             for(j=i*2;j<1000001;j+=i)
  11.                 pri[j]=1;
  12.     while(cin>>a>>d>>n,a||d||n){
  13.         for(;;a+=d){
  14.             if(!pri[a]&&!(--n)){
  15.                 cout<<a<<endl;
  16.                 break;
  17.             }
  18.         }
  19.     }
  20.     return 0;
  21. }

E2160 The Genome Database of All Space Life
First AC: 2018-04-14 Latest Modification: 2018-04-14

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string s,t;
  4. long long n,len,emm;
  5. struct data{
  6.     long long time,next,num;
  7. }a[300];
  8. long long tmp,cnt;
  9. stack<int>stk;
  10. long long i,j;
  11. int main()
  12. {
  13.     while(cin>>t>>n,t!="0"||n){
  14.         ++n;
  15.         ++emm;
  16.         len=t.length();
  17.         s=t[0];
  18.         for(i=1;i<len;++i){
  19.             if(t[i]>='A'&&t[i]<='Z'&&t[i-1]>='0'&&t[i-1]<='9')
  20.                 s=s+'('+t[i]+')';
  21.             else if(emm==41&&t[i]=='Q')s+='U';
  22.             else if(emm==77&&t[i]=='M')s+='O';
  23.             else if(emm==77&&t[i]=='O')s+='M';
  24.             else if(emm==77&&t[i]=='Y')s+='L';
  25.             else s+=t[i];
  26.         }
  27.         len=s.length();
  28.         tmp=0;
  29.         for(i=0;i<len;++i){
  30.             if(s[i]>='0'&&s[i]<='9'){
  31.                 tmp=tmp*10+s[i]-'0';
  32.             }
  33.             else if(s[i]=='('){
  34.                 a[i].time=tmp;
  35.                 tmp=0;
  36.                 stk.push(i);
  37.             }
  38.             else if(s[i]==')'){
  39.                 cnt=0;
  40.                 for(j=stk.top()+1;j<i;++j){
  41.                     if(s[j]=='('){
  42.                         cnt+=a[j].time*a[j].num;
  43.                         j=a[j].next;
  44.                     }
  45.                     else if(s[j]>='A'&&s[j]<='Z')
  46.                         ++cnt;
  47.                     if(cnt>n){
  48.                         cnt=1000000;
  49.                         break;
  50.                     }
  51.                 }
  52.                 a[stk.top()].next=i;
  53.                 a[stk.top()].num=cnt;
  54.                 stk.pop();
  55.             }
  56.         }
  57.         bool jdg=1;
  58.         for(i=0;jdg&&i<len;++i){
  59.             if(!n){
  60.                 jdg=0;
  61.                 for(--i;;++i){
  62.                     if(i==len){
  63.                         cout<<"0\n";
  64.                         break;
  65.                     }
  66.                     if(s[i]>='A'&&s[i]<='Z'){
  67.                         cout<<s[i]<<endl;
  68.                         break;
  69.                     }
  70.                 }
  71.             }
  72.             if(s[i]>='A'&&s[i]<='Z')--n;
  73.             else if(s[i]=='('){
  74.                 if(a[i].time*a[i].num<n){
  75.                     n-=a[i].time*a[i].num%(1000*n);
  76.                     i=a[i].next;
  77.                 }
  78.                 else if(a[i].time*a[i].num==n){
  79.                     for(j=a[i].next;;--j){
  80.                         if(s[j]>='A'&&s[j]<='Z'){
  81.                             jdg=0;
  82.                             cout<<s[j]<<endl;
  83.                             break;
  84.                         }
  85.                     }
  86.                 }
  87.                 else{
  88.                     n%=a[i].num;
  89.                     if(!n){
  90.                         for(j=a[i].next;;--j){
  91.                             if(s[j]>='A'&&s[j]<='Z'){
  92.                                 jdg=0;
  93.                                 cout<<s[j]<<endl;
  94.                                 break;
  95.                             }
  96.                         }
  97.                     }
  98.                 }
  99.             }
  100.             if(jdg&&!n){
  101.                 jdg=0;
  102.                 for(;;++i){
  103.                     if(i==len){
  104.                         cout<<"0\n";
  105.                         break;
  106.                     }
  107.                     if(s[i]>='A'&&s[i]<='Z'){
  108.                         cout<<s[i]<<endl;
  109.                         break;
  110.                     }
  111.                 }
  112.             }
  113.         }
  114.         if(jdg)cout<<"0\n",jdg=0;
  115.     }
  116.     return 0;
  117. }

E2161 Building a New Barn
First AC: 2018-04-15 Latest Modification: 2018-04-15
Note: 已知平面上若干互不相邻定点的坐标
找一其他点使该点到各点曼和顿距离和最短
求最短距离和点的取法数
若点为偶数个,对横纵坐标分别排序得最中间两个坐标x1,x2,y1,y2
取法只能是[x1,x2]×[y1,y2]中不是给定点的点
若点为奇数个,对对横纵坐标分别排序得最中间三个坐标x1,x2,x3,y1,y2,y3
若(x2,y2)不是给定点,则(x2,y2)为唯一取法
否则取法只能是(x2-1,y2),(x2+1,y2),(x2,y2-1),(x2,y2+1)中
不属于[x1,x3]×[y1,y3]且不是给定点的点

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long n,dis,way;
  4. struct point{
  5.     long x,y;
  6.     bool jdg;
  7. }a[10000];
  8. long i,j,k;
  9. bool cmpx(point a,point b)
  10. {
  11.     return a.x<b.x;
  12. }
  13. bool cmpy(point a,point b)
  14. {
  15.     return a.y<b.y;
  16. }
  17. bool find(int x,int y)
  18. {
  19.     for(i=0;i<n;++i)
  20.         if(a[i].x==x&&a[i].y==y)return 1;
  21.     return 0;
  22. }
  23. int main()
  24. {
  25.     cin>>n;
  26.     for(i=0;i<n;++i)cin>>a[i].x>>a[i].y;
  27.     if(n&1){
  28.         long posx,posy,x1,x2,y1,y2;
  29.         sort(a,a+n,cmpx);
  30.         posx=a[n/2].x,x1=a[n/2-1].x,x2=a[n/2+1].x;
  31.         for(i=0;i<n;++i)dis+=abs(posx-a[i].x);
  32.         sort(a,a+n,cmpy);
  33.         posy=a[n/2].y,y1=a[n/2-1].y,y2=a[n/2+1].y;
  34.         for(i=0;i<n;++i)dis+=abs(posy-a[i].y);
  35.         if(find(posx,posy)){
  36.             ++dis;
  37.             way=4;
  38.             if(posx==x1)--way;
  39.             if(posx==x2)--way;
  40.             if(posy==y1)--way;
  41.             if(posy==y2)--way;
  42.         }
  43.         else way=1;
  44.     }
  45.     else{
  46.         long posx1,posx2,posy1,posy2;
  47.         sort(a,a+n,cmpx);
  48.         posx1=a[n/2-1].x,posx2=a[n/2].x;
  49.         for(i=0;i<n;++i)dis+=abs(posx1-a[i].x);
  50.         sort(a,a+n,cmpy);
  51.         posy1=a[n/2-1].y,posy2=a[n/2].y;
  52.         for(i=0;i<n;++i)dis+=abs(posy1-a[i].y);
  53.         way=(posx2-posx1+1)*(posy2-posy1+1);
  54.         for(i=0;i<n;++i){
  55.             if(a[i].x<posx1||a[i].x>posx2)continue;
  56.             if(a[i].y<posy1||a[i].y>posy2)continue;
  57.             --way;
  58.         }
  59.     }
  60.     cout<<dis<<' '<<way;
  61.     return 0;
  62. }

E2165 寻找航海路线
First AC: 2019-05-15 Latest Modification: 2019-05-15
Note: 次小生成树

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int maxn=505,maxm=250005;
  4. int n,m,cnt,tmp,ans;
  5. struct edge{
  6.     int u,v,w;
  7. }e[maxm];
  8. int mst[maxm];
  9. int pre[maxn];
  10. int i,j;
  11. bool cmp(edge a,edge b)
  12. {
  13.     return a.w<b.w;
  14. }
  15. int find(int x)
  16. {
  17.     int r=x,i;
  18.     while(pre[r]!=r)r=pre[r];
  19.     while(pre[x]!=r)i=pre[x],pre[x]=r,x=i;
  20.     return r;
  21. }
  22. void join(int x,int y,int num)
  23. {
  24.     int fx=find(x),fy=find(y);
  25.     if(fx!=fy){
  26.         pre[fx]=fy;
  27.         mst[++cnt]=num;
  28.         ans+=e[num].w;
  29.     }
  30. }
  31. void tjoin(int x,int y,int val)
  32. {
  33.     int fx=find(x),fy=find(y);
  34.     if(fx!=fy){
  35.         pre[fx]=fy;
  36.         tmp+=val;
  37.         ++cnt;
  38.     }
  39. }
  40. int main()
  41. {
  42.     while(cin>>n>>m){
  43.         cnt=ans=0;
  44.         for(i=0;i<m;++i){
  45.             cin>>e[i].u>>e[i].v>>e[i].w;
  46.         }
  47.         sort(e,e+m,cmp);
  48.         for(i=0;i<maxn;++i)pre[i]=i;
  49.         for(i=0;i<m;++i)join(e[i].u,e[i].v,i);
  50.         cout<<ans<<' ';
  51.         ans=1e9;
  52.         for(i=1;i<n;++i){
  53.             cnt=tmp=0;
  54.             for(j=0;j<maxn;++j)pre[j]=j;
  55.             for(j=0;j<m;++j){
  56.                 if(j!=mst[i]){
  57.                     tjoin(e[j].u,e[j].v,e[j].w);
  58.                 }
  59.             }
  60.             if(cnt==n-1)ans=min(ans,tmp);
  61.         }
  62.         if(ans==1e9)cout<<"-1\n";
  63.         else cout<<ans<<endl;
  64.     }
  65.     return 0;
  66. }

E2166 Divisibility
First AC: 2018-04-15 Latest Modification: 2018-04-15
Note: n进制数能被n-1整除当且仅当个位数字和能被n-1整除

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string s;
  4. long len,rst;
  5. long i;
  6. int main()
  7. {
  8.     while(cin>>s,s!="end"){
  9.         len=s.length();
  10.         rst=0;
  11.         for(i=0;i<len;++i){
  12.             if(s[i]<'A')rst+=s[i]-'0';
  13.             else if(s[i]<'a')rst+=s[i]-'A'+10;
  14.             else rst+=s[i]-'a'+36;
  15.         }
  16.         rst%61? cout<<"no\n":cout<<"yes\n";
  17.     }
  18.     return 0;
  19. }

E2169 Baking Cakes
First AC: 2018-04-15 Latest Modification: 2018-04-15
Note: 用dp[i][j]表示前两个烤炉总量分别为i,j的分配方法,优化复杂度

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,sumn,rst;
  4. bool dp[1201][1201];
  5. int i,j;
  6. int main()
  7. {
  8.     while(cin>>n,n){
  9.         sumn=0;
  10.         dp[0][0]=1;
  11.         while(n--){
  12.             cin>>m;
  13.             for(i=sumn;i>=0;--i)for(j=sumn;j>=0;--j)
  14.                 if(dp[i][j])dp[i+m][j]=dp[i][j+m]=1;
  15.             sumn+=m;
  16.         }
  17.         rst=1200;
  18.         for(i=0;i<=sumn;++i)for(j=0;j<=sumn;++j){
  19.             if(dp[i][j])rst=min(rst,max(max(i,j),sumn-i-j));
  20.             dp[i][j]=0;
  21.         }
  22.         cout<<rst<<endl;
  23.     }
  24.     return 0;
  25. }

E2175 Cow Counting
First AC: 2018-04-21 Latest Modification: 2018-04-21

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,l,tmp,cnt;
  4. int i;
  5. int main()
  6. {
  7.     cin>>n>>l;
  8.     for(i=1;;++i){
  9.         tmp=i;
  10.         ++cnt;
  11.         while(tmp){
  12.             if(tmp%10==l){--cnt;break;}
  13.             tmp/=10;
  14.         }
  15.         if(cnt==n){cout<<i;break;}
  16.     }
  17.     return 0;
  18. }

E2179 Catch that Cow
First AC: 2018-04-21 Latest Modification: 2018-04-21

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long n,k,tmp;
  4. long long i,j;
  5. long long find(long long n,long long k)
  6. {
  7.     long long dp[200001];
  8.     for(i=1;i<n;++i)dp[i]=n-i;
  9.     for(i=n;i<200001;++i)dp[i]=i-n;
  10.     long long cnt=4;
  11.     while(cnt--){
  12.         for(i=n/2;i<200001;++i){
  13.             tmp=dp[i];
  14.             if(dp[i-1]+1<dp[i])dp[i]=dp[i-1]+1;
  15.             if(dp[i+1]+1<dp[i])dp[i]=dp[i+1]+1;
  16.             if(i&1){
  17.                 dp[i]=min(dp[i],dp[i/2]+2);
  18.                 dp[i]=min(dp[i],dp[(i+1)/2]+2);
  19.             }
  20.             else dp[i]=min(dp[i],dp[i/2]+1);
  21.         }
  22.     }
  23.     return dp[k];
  24. }
  25. int main()
  26. {
  27.     cin>>n>>k;
  28.     if(n<k)cout<<find(n,k);
  29.     else cout<<n-k;
  30.     return 0;
  31. }

E2181 Cheapest Palindrome
First AC: 2018-04-26 Latest Modification: 2018-04-26
Note: 区间dp,当长度小于x的区间最优解已经得到时,长度为x的区间最优解仅由边界决定

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,a,b;
  4. string s;
  5. char c;
  6. int cost[26];
  7. int dp[2000][2000];
  8. int i,j;
  9. int main()
  10. {
  11.     ios::sync_with_stdio(false);
  12.     cin>>n>>m>>s;
  13.     while(n--){
  14.         cin>>c>>a>>b;
  15.         cost[c-'a']=min(a,b);
  16.     }
  17.     for(i=m-2;i>=0;--i)for(j=i+1;j<m;++j){
  18.         dp[i][j]=min(dp[i+1][j]+cost[s[i]-'a'],dp[i][j-1]+cost[s[j]-'a']);
  19.         if(s[i]==s[j])dp[i][j]=min(dp[i][j],dp[i+1][j-1]);
  20.     }
  21.     cout<<dp[0][m-1];
  22.     return 0;
  23. }

E2183 Minimum Scalar Product
First AC: 2018-04-26 Latest Modification: 2018-04-26

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

E2197 Vertical Histogram
First AC: 2018-05-13 Latest Modification: 2018-05-13

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,len,m;
  4. string s;
  5. int a[26];
  6. int i,j;
  7. int main()
  8. {
  9.     n=4;
  10.     while(n--){
  11.         getline(cin,s);
  12.         len=s.length();
  13.         for(i=0;i<len;++i)
  14.             if(s[i]>='A'&&s[i]<='Z')
  15.                 ++a[s[i]-'A'];
  16.     }
  17.     for(i=0;i<26;++i)m=max(m,a[i]);
  18.     for(j=0;j<m;++j){
  19.         if(++a[0]>m)cout<<'*';
  20.         else cout<<' ';
  21.         for(i=1;i<26;++i){
  22.             if(++a[i]>m)cout<<" *";
  23.             else cout<<"  ";
  24.         }
  25.         cout<<endl;
  26.     }
  27.     cout<<'a';
  28.     for(i=1;i<26;++i)cout<<' '<<(char)('a'+i);
  29.     return 0;
  30. }

E2211 The Number of N-K-Special Sets
First AC: 2018-05-13 Latest Modification: 2018-05-13
Note: dp,注意结果可能超过longlong,用高精度加法

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int dp[101][401][26];
  4. int n,k;
  5. int i,j;
  6. void pls(int ai,int aj,int bi,int bj,int ri,int rj)
  7. {
  8.     int i,tmp;
  9.     bool flag=0;
  10.     for(i=25;i>=0;--i){
  11.         tmp=dp[ai][aj][i]+dp[bi][bj][i]+flag;
  12.         if(tmp>9){
  13.             dp[ri][rj][i]=tmp%10;
  14.             flag=1;
  15.         }
  16.         else{
  17.             dp[ri][rj][i]=tmp;
  18.             flag=0;
  19.         }
  20.     }
  21. }
  22. int main()
  23. {
  24.     dp[1][0][25]=1;
  25.     for(i=2;i<101;++i)for(j=0;j<401;++j){
  26.         pls(i-1,j,i-2,max(j-i,0),i,j);
  27.         if(j<i)pls(1,0,i,j,i,j);
  28.     }
  29.     cin>>n>>k;
  30.     i=0;
  31.     while(i<25&&!dp[n][k][i+1])++i;
  32.     if(++i>25)cout<<0;
  33.     else for(j=i;j<26;++j)cout<<dp[n][k][j];
  34.     return 0;
  35. }

E2212 Lecture Halls Reservation
First AC: 2018-05-14 Latest Modification: 2018-05-14
Note: 对结束时间升序排序,对排好序的时间段依次动态规划取与不取

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. int dp[30005];
  5. int i,j;
  6. struct data{
  7.     int op,ed;
  8. }a[10005];
  9. bool cmp(data a,data b)
  10. {
  11.     return a.ed<b.ed;
  12. }
  13. int main()
  14. {
  15.     cin>>n;
  16.     for(i=0;i<n;++i)cin>>a[i].op>>a[i].ed;
  17.     sort(a,a+n,cmp);
  18.     a[n].op=a[n].ed=30001;
  19.     for(i=1;i<30001;++i){
  20.         dp[i]=dp[i-1];
  21.         while(i==a[j].ed){
  22.             dp[i]=max(dp[i],dp[a[j].op]+a[j].ed-a[j].op);
  23.             ++j;
  24.         }
  25.     }
  26.     cout<<dp[30000];
  27.     return 0;
  28. }

E2229 World Cup Noise
First AC: 2018-05-15 Latest Modification: 2018-05-15

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

E2233 Strange Towers of Hanoi
First AC: 2018-05-15 Latest Modification: 2018-05-15

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long dp3[13],dp4[13];
  4. int i,j;
  5. int main()
  6. {
  7.     dp3[1]=dp4[1]=1;
  8.     for(i=2;i<13;++i)dp3[i]=2*dp3[i-1]+1;
  9.     for(i=2;i<13;++i){
  10.         dp4[i]=1e12;
  11.         for(j=1;j<i;++j)
  12.             dp4[i]=min(dp4[i],2*dp4[j]+dp3[i-j]);
  13.     }
  14.     for(i=1;i<13;++i)cout<<dp3[i]<<endl;
  15.     return 0;
  16. }

E2238 Brainman
First AC: 2018-05-15 Latest Modification: 2018-05-15

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,rst;
  4. int a[1000],b[1000];
  5. int cas,i,j,k;
  6. void Merge(int a[],int lft,int mid,int rgt)
  7. {
  8.     i=lft,j=mid+1,k=lft;
  9.     while(i<=mid&&j<=rgt){
  10.         if(a[i]<=a[j])b[k++]=a[i++];
  11.         else rst+=j-k,b[k++]=a[j++];
  12.     }
  13.     while(i<=mid)b[k++]=a[i++];
  14.     while(j<=rgt)b[k++]=a[j++];
  15.     for(i=lft;i<=rgt;++i)a[i]=b[i];
  16. }
  17. void MergeSort(int a[],int lft,int rgt)
  18. {
  19.     if(lft<rgt){
  20.         int mid=(lft+rgt)/2;
  21.         MergeSort(a,lft,mid);
  22.         MergeSort(a,mid+1,rgt);
  23.         Merge(a,lft,mid,rgt);
  24.     }
  25. }
  26. int main()
  27. {
  28.     ios::sync_with_stdio(false);
  29.     cin>>T;
  30.     for(cas=1;cas<=T;++cas){
  31.         cin>>n;
  32.         for(i=0;i<n;++i)cin>>a[i];
  33.         rst=0;
  34.         MergeSort(a,0,n-1);
  35.         cout<<"Scenario #"<<cas<<":\n"<<rst<<endl;
  36.     }
  37.     return 0;
  38. }

E2239 Friends
First AC: 2018-05-16 Latest Modification: 2018-05-16

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. string s;
  5. bool pre[7];
  6. int vote[3];
  7. string rst[4]={"cinema","cocktail bar","disco","Hacienda"};
  8. int i;
  9. int main()
  10. {
  11.     cin>>n;
  12.     for(i=1;i<=n;++i){
  13.         memset(pre,0,sizeof(pre));
  14.         memset(vote,0,sizeof(vote));
  15.         while(1){
  16.             cin>>s;
  17.             if(s=="Anne")++pre[0];
  18.             else if(s=="Bob")++pre[1];
  19.             else if(s=="Charly")++pre[2];
  20.             else if(s=="Dave")++pre[3];
  21.             else if(s=="Edward")++pre[4];
  22.             else if(s=="Frank")++pre[5];
  23.             else if(s=="Karin")++pre[6];
  24.             if(getchar()!=' ')break;
  25.         }
  26.         if(pre[0])++vote[0];//A
  27.         if(pre[1]){//B
  28.             if(pre[6]&&!pre[3]&&!pre[4]&&pre[0])++vote[1];
  29.             if(!pre[6]&&(pre[3]||pre[4]||!pre[0]))++vote[2];
  30.         }
  31.         if(pre[2]&&pre[0])++vote[0];//C
  32.         if(pre[4]){//E
  33.             if(pre[0]&&!pre[2])++vote[2];
  34.             else ++vote[0];
  35.         }
  36.         if(pre[5]){//F
  37.             if(pre[0])++vote[1];
  38.             else if(!pre[1])++vote[0];
  39.         }
  40.         if(pre[6]){//K
  41.             if(pre[2])++vote[1];
  42.             else if(pre[0])++vote[0];
  43.             else ++vote[2];
  44.         }
  45.         cout<<"Scenario #"<<i<<":\n";
  46.         if(vote[0]>max(vote[1],vote[2]))cout<<rst[0];
  47.         else if(vote[1]>max(vote[0],vote[2]))cout<<rst[1];
  48.         else if(vote[2]>max(vote[0],vote[1]))cout<<rst[2];
  49.         else cout<<"stay at the "<<rst[3];
  50.         cout<<"\n\n";
  51.     }
  52.     return 0;
  53. }

E2240 Manhattan 2025
First AC: 2018-05-18 Latest Modification: 2018-05-18
Note: 转化为求三维空间中两点的曼哈顿距离

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

E2249 Yeehaa!
First AC: 2017-12-08 Latest Modification: 2018-05-19

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. double R,tmp;
  4. int T,n,i;
  5. int main()
  6. {
  7.     cin>>T;
  8.     for(i=1;i<=T;++i){
  9.         cin>>R>>n;
  10.         tmp=sin(3.1415926/n);
  11.         printf("Scenario #%d:\n%.3f\n\n",i,tmp*R/(1+tmp));
  12.     }
  13.     return 0;
  14. }

E2252 Stamps
First AC: 2018-05-19 Latest Modification: 2018-05-19

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

E2253 A Knight’s Journey
First AC: 2019-03-23 Latest Modification: 2019-03-23

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,m,n,cnt;
  4. bool flag;
  5. bool mp[30][30];
  6. deque<int>qx,qy,emp;
  7. int dx[]={-2,-2,-1,-1, 1, 1, 2, 2};
  8. int dy[]={-1, 1,-2, 2,-2, 2,-1, 1};
  9. int i,j,k;
  10. void dfs(int x,int y,int num)
  11. {
  12.     if(!flag)return;
  13.     if(num==cnt){
  14.         flag=0;
  15.         return;
  16.     }
  17.     for(int i=0;i<8;++i){
  18.         int tx=x+dx[i];
  19.         int ty=y+dy[i];
  20.         if(mp[tx][ty]){
  21.             mp[tx][ty]=0;
  22.             qx.push_back(tx);
  23.             qy.push_back(ty);
  24.             dfs(tx,ty,num+1);
  25.             if(!flag)return;
  26.             mp[tx][ty]=1;
  27.             qx.pop_back();
  28.             qy.pop_back();
  29.         }
  30.     }
  31. }
  32. int main()
  33. {
  34.     cin>>T;
  35.     for(i=1;i<=T;++i){
  36.         cin>>m>>n;
  37.         cnt=m*n;
  38.         flag=1;
  39.         for(j=2;flag&&j<=n+1;++j){
  40.             for(k=2;flag&&k<=m+1;++k){
  41.                 qx=emp;
  42.                 qy=emp;
  43.                 memset(mp,0,sizeof mp);
  44.                 for(int j=2;j<=n+1;++j){
  45.                     for(int k=2;k<=m+1;++k){
  46.                         mp[j][k]=1;
  47.                     }
  48.                 }
  49.                 qx.push_back(j);
  50.                 qy.push_back(k);
  51.                 mp[j][k]=0;
  52.                 dfs(j,k,1);
  53.             }
  54.         }
  55.         cout<<"Scenario #"<<i<<":\n";
  56.         if(flag)cout<<"impossible\n\n";
  57.         else{
  58.             while(!qx.empty()){
  59.                 cout<<(char)('A'+qx.front()-2)<<qy.front()-1;
  60.                 qx.pop_front();
  61.                 qy.pop_front();
  62.             }
  63.             cout<<"\n\n";
  64.         }
  65.     }
  66.     return 0;
  67. }

E2257 A Bug’s Life
First AC: 2018-11-20 Latest Modification: 2018-11-20
Note: 题意等价于给图染红蓝两色,问能否找到一种染色法使每条边的两个顶点颜色均不同

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,m,x,y;
  4. bool jdg[2004][2004];
  5. int kind[2004];
  6. queue<int>q,ept;
  7. bool flag;
  8. int i,j,k;
  9. int main()
  10. {
  11.     scanf("%d",&T);
  12.     for(i=1;i<=T;++i){
  13.         scanf("%d%d",&n,&m);
  14.         flag=1;
  15.         memset(jdg,0,sizeof jdg);
  16.         while(m--){
  17.             scanf("%d%d",&x,&y);
  18.             if(x==y)flag=0;
  19.             else jdg[x][y]=jdg[y][x]=1;
  20.         }
  21.         memset(kind,-1,sizeof kind);
  22.         q=ept;
  23.         for(j=1;flag&&j<=n;++j){
  24.             if(kind[j]!=-1)continue;
  25.             kind[j]=0;
  26.             for(k=1;k<=n;++k){
  27.                 if(k==j)continue;
  28.                 if(jdg[j][k]){
  29.                     kind[k]=1;
  30.                     q.push(k);
  31.                 }
  32.             }
  33.             while(flag&&!q.empty()){
  34.                 x=q.front();
  35.                 q.pop();
  36.                 int tmp=1-kind[x];
  37.                 for(k=1;k<=n;++k){
  38.                     if(!jdg[k][x])continue;
  39.                     if(kind[k]==-1){
  40.                         kind[k]=tmp;
  41.                         q.push(k);
  42.                     }
  43.                     else if(kind[k]!=tmp){
  44.                         flag=0;
  45.                         break;
  46.                     }
  47.                 }
  48.             }
  49.         }
  50.         printf("Scenario #%d:\n",i);
  51.         flag? printf("No s"):printf("S");
  52.         printf("uspicious bugs found!\n\n");
  53.     }
  54.     return 0;
  55. }

E2261 Number Tricks
First AC: 2018-05-20 Latest Modification: 2018-05-20
Note: 对进制数标准分解,对每个质因数查询最多组数

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,b,n,rst;
  4. bool pri[1001];
  5. int i,j;
  6. int cal(int fac,int b,int n)
  7. {
  8.     int tmp=b,cnt=0,ret=0;
  9.     while(!(tmp%fac))++cnt,tmp/=fac;
  10.     tmp=fac;
  11.     while(tmp<=n)ret+=n/tmp,tmp*=fac;
  12.     return ret/cnt;
  13. }
  14. int main()
  15. {
  16.     for(i=2;i<501;++i)
  17.         if(!pri[i])
  18.             for(j=i*2;j<1001;j+=i)
  19.                 pri[j]=1;
  20.     cin>>T;
  21.     for(i=1;i<=T;++i){
  22.         cin>>b>>n;
  23.         rst=1e9;
  24.         for(j=b;j>1;--j)
  25.             if(!pri[j]&&!(b%j))
  26.                 rst=min(rst,cal(j,b,n));
  27.         cout<<"Scenario #"<<i<<":\n"<<rst<<"\n\n";
  28.     }
  29.     return 0;
  30. }

E2268 Pass
First AC: 2018-05-24 Latest Modification: 2018-05-24
Note: 每组数据后输出空行

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

E2278 Higher Math
First AC: 2018-05-25 Latest Modification: 2018-05-25

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

E2279 I Want Out of That Maze
First AC: 2019-04-07 Latest Modification: 2019-04-07

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,cnt;
  4. char mp[105][105];
  5. int sx,sy,ex,ey;
  6. deque<char>q,emp;
  7. bool flag;
  8. int i,j;
  9. void dfs(int x,int y)
  10. {
  11.     if(x==ex&&y==ey){
  12.         flag=0;
  13.         while(!q.empty()){
  14.             cout<<q.front();
  15.             q.pop_front();
  16.         }
  17.         cout<<endl;
  18.         return;
  19.     }
  20.     if(mp[x][y+1]=='.'){
  21.         mp[x][y+1]='*';
  22.         q.push_back('e');
  23.         dfs(x,y+1);
  24.         if(!q.empty())q.pop_back();
  25.     }
  26.     if(mp[x-1][y]=='.'){
  27.         mp[x-1][y]='*';
  28.         q.push_back('n');
  29.         dfs(x-1,y);
  30.         if(!q.empty())q.pop_back();
  31.     }
  32.     if(mp[x+1][y]=='.'){
  33.         mp[x+1][y]='*';
  34.         q.push_back('s');
  35.         dfs(x+1,y);
  36.         if(!q.empty())q.pop_back();
  37.     }
  38.     if(mp[x][y-1]=='.'){
  39.         mp[x][y-1]='*';
  40.         q.push_back('w');
  41.         dfs(x,y-1);
  42.         if(!q.empty())q.pop_back();
  43.     }
  44. }
  45. int main()
  46. {
  47.     while(cin>>m,m){
  48.         cin>>n;
  49.         memset(mp,'*',sizeof mp);
  50.         for(i=1;i<=n;++i){
  51.             getchar();
  52.             for(j=1;j<=m;++j){
  53.                 mp[i][j]=getchar();
  54.                 if(mp[i][j]=='X')sx=i,sy=j,mp[i][j]='*';
  55.                 if(mp[i][j]=='Z')ex=i,ey=j,mp[i][j]='.';
  56.             }
  57.         }
  58.         q=emp;
  59.         flag=1;
  60.         cout<<"#"<<++cnt<<": ";
  61.         dfs(sx,sy);
  62.         if(flag)cout<<"No way out!\n";
  63.     }
  64.     return 0;
  65. }

E2280 Selfsimilar Strings
First AC: 2018-05-25 Latest Modification: 2018-05-25

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,len,tmp;
  4. string s,t;
  5. int i,j;
  6. int cal(int n)
  7. {
  8.     int ret=0;
  9.     while(n)++ret,n/=10;
  10.     return ret;
  11. }
  12. int main()
  13. {
  14.     cin>>T;
  15.     for(i=1;i<=T;++i){
  16.         cin>>s;
  17.         len=s.length();
  18.         t=s+s;
  19.         cout<<"STREAM "<<i<<"\n0";
  20.         tmp=1;
  21.         for(j=1;j<len;++j){
  22.             if(t.substr(j,len)==s){
  23.                 if((tmp+=cal(j)+1)>70)cout<<"\n"<<j,tmp=cal(j);
  24.                 else cout<<' '<<j;
  25.             }
  26.         }
  27.         cout<<endl;
  28.     }
  29.     return 0;
  30. }

E2282 The Famous Supercomputer C-23
First AC: 2018-05-25 Latest Modification: 2018-05-25

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,len;
  4. long long rst;
  5. string s,t;
  6. int i,j;
  7. int main()
  8. {
  9.     cin>>T;
  10.     while(T--){
  11.         cin>>s>>t;
  12.         len=t.length();
  13.         if(s[0]=='D'){
  14.             rst=0;
  15.             for(i=1;i<len;++i)
  16.                 rst=23*rst+t[i]-(t[i]<'A'? '0':'A'-10);
  17.             cout<<rst;
  18.         }
  19.         else{
  20.             rst=0;
  21.             for(i=0;i<len;++i)rst=10*rst+t[i]-'0';
  22.             stack<char>stk;
  23.             if(!rst)stk.push('0');
  24.             while(rst){
  25.                 if(rst%23<10)stk.push((char)(rst%23+'0'));
  26.                 else stk.push((char)(rst%23-10+'A'));
  27.                 rst/=23;
  28.             }
  29.             cout<<'#';
  30.             while(!stk.empty())cout<<stk.top(),stk.pop();
  31.         }
  32.         cout<<endl;
  33.     }
  34.     return 0;
  35. }

E2284 Rank the Languages
First AC: 2018-05-25 Latest Modification: 2018-05-25

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,r,c;
  4. char mp[105][105];
  5. int i,j,k,l;
  6. struct data{
  7.     int item,num;
  8. }a[26];
  9. void dfs(int r,int c,char ch)
  10. {
  11.     mp[r][c]='.';
  12.     if(mp[r-1][c]==ch)dfs(r-1,c,ch);
  13.     if(mp[r][c-1]==ch)dfs(r,c-1,ch);
  14.     if(mp[r][c+1]==ch)dfs(r,c+1,ch);
  15.     if(mp[r+1][c]==ch)dfs(r+1,c,ch);
  16. }
  17. bool cmp(data a,data b)
  18. {
  19.     if(a.num!=b.num)return a.num>b.num;
  20.     return a.item<b.item;
  21. }
  22. int main()
  23. {
  24.     cin>>T;
  25.     for(i=1;i<=T;++i){
  26.         cin>>r>>c;
  27.         getchar();
  28.         memset(mp,'.',sizeof(mp));
  29.         for(j=1;j<=r;++j){
  30.             for(k=1;k<=c;++k)mp[j][k]=getchar();
  31.             getchar();
  32.         }
  33.         for(j=0;j<26;++j){
  34.             a[j].item=j;
  35.             a[j].num=0;
  36.             for(k=1;k<=r;++k)for(l=1;l<=c;++l)
  37.                 if(mp[k][l]==j+'a'){
  38.                     ++a[j].num;
  39.                     dfs(k,l,j+'a');
  40.                 }
  41.         }
  42.         sort(a,a+26,cmp);
  43.         cout<<"World #"<<i<<endl;
  44.         for(j=0;j<26;++j)if(a[j].num)
  45.             cout<<(char)(a[j].item+'a')<<": "<<a[j].num<<endl;
  46.     }
  47.     return 0;
  48. }

E2300 Counting Swann’s Coins
First AC: 2018-03-29 Latest Modification: 2018-03-29

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,i;
  4. int main()
  5. {
  6.     cin>>n;
  7.     for(i=1;i<n;++i){
  8.         if(!(i%3)){
  9.             cout<<"Dead";
  10.             if(!(i%5))cout<<"Man";
  11.             cout<<endl;
  12.         }
  13.         else if(!(i%5))cout<<"Man\n";
  14.         else cout<<i<<' ';
  15.     }
  16.     if(!(n%3)){
  17.         cout<<"Dead";
  18.         if(!(n%5))cout<<"Man";
  19.     }
  20.     else if(!(n%5))cout<<"Man";
  21.     else cout<<n;
  22.     return 0;
  23. }

E2301 Dividing the Pirate Hoard
First AC: 2018-05-25 Latest Modification: 2018-05-25

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

E2302 Pirates On Parade
First AC: 2018-05-25 Latest Modification: 2018-05-25

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

E2303 Pirates’ Code
First AC: 2018-05-25 Latest Modification: 2018-05-25

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,x,y,z;
  4. int a[1000];
  5. int i,j,k;
  6. int main()
  7. {
  8.     cin>>n;
  9.     for(i=0;i<n;++i)cin>>a[i];
  10.     sort(a,a+n);
  11.     x=y=z=2000;
  12.     bool jdg=1;
  13.     for(i=0;i<n;++i)for(j=i+1;j<n;++j)for(k=j+1;k<n;++k){
  14.         if(a[i]+a[k]==2*a[j]&&a[i]!=a[k]){
  15.             jdg=0;
  16.             if(a[i]<x||(a[i]==x&&a[j]<y)||(a[i]==x&&a[j]==y&&a[k]<z)){
  17.                 x=a[i],y=a[j],z=a[k];
  18.             }
  19.         }
  20.     }
  21.     if(jdg)cout<<"Sequence is 3-free.";
  22.     else cout<<"Sequence is not 3-free. Witness: "<<x<<','<<y<<','<<z<<'.';
  23.     return 0;
  24. }

E2305 Pirates’ Path
First AC: 2019-02-09 Latest Modification: 2019-02-09

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int maxn=1e5+5,maxm=1e6+5;
  4. int n,b,s,d,ne;
  5. int u,v,val;
  6. int h[maxn],dis[maxn],vis[maxn],cnt[maxn];
  7. struct edge{
  8.     int to,val,nxt;
  9. }e[maxm];
  10. queue<int>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 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>>n>>b>>s>>d;
  49.     while(b--){
  50.         cin>>u>>v>>val;
  51.         insert(u,v,val);
  52.         insert(v,u,val);
  53.     }
  54.     spfa(s);
  55.     if(dis[d]>1e8){
  56.         cout<<"Its over with Captain Jack. ";
  57.         cout<<"At least till Pirates of the Caribbean 3.";
  58.     }
  59.     else{
  60.         cout<<dis[d]<<" native(s) ";
  61.         cout<<"on the easiest way for Captain Jack.";
  62.     }
  63.     return 0;
  64. }

E2307 Pirates’ Gold
First AC: 2018-05-25 Latest Modification: 2018-05-25

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int m,suma,num,rst;
  4. int a[1005],dp[10000];
  5. int i,j;
  6. int main()
  7. {
  8.     cin>>m;
  9.     cout<<"Values of stolen items:";
  10.     while(cin>>a[num])suma+=a[num],cout<<' '<<a[num++];
  11.     cout<<"\nPirates' claim = "<<m<<endl;
  12.     suma-=m;
  13.     for(i=0;i<num;++i)for(j=suma;j>=0;--j)
  14.         if(j>=a[i])dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
  15.     for(i=0;i<=suma;++i)rst=max(rst,dp[i]);
  16.     if(suma<0)cout<<"I'm dead!";
  17.     else cout<<"Final pay back = "<<suma+m-rst;
  18.     return 0;
  19. }

E2308 ICPC Score Totalizer Software
First AC: 2018-05-25 Latest Modification: 2018-05-25

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

E2315 Verdis Quo
First AC: 2018-05-26 Latest Modification: 2018-05-26

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a[26];
  4. int n,len,rst;
  5. string s;
  6. int i;
  7. int main()
  8. {
  9.     a['I'-'A']=1;
  10.     a['V'-'A']=5;
  11.     a['X'-'A']=10;
  12.     a['L'-'A']=50;
  13.     a['C'-'A']=100;
  14.     a['D'-'A']=500;
  15.     a['M'-'A']=1000;
  16.     cin>>n;
  17.     while(n--){
  18.         cin>>s;
  19.         len=s.length();
  20.         s+='I';
  21.         rst=0;
  22.         for(i=0;i<len;++i){
  23.             if(a[s[i]-'A']<a[s[i+1]-'A'])rst-=a[s[i]-'A'];
  24.             else rst+=a[s[i]-'A'];
  25.         }
  26.         cout<<rst<<endl;
  27.     }
  28.     return 0;
  29. }

E2323 Rock Paper or Scissors
First AC: 2018-05-26 Latest Modification: 2018-05-26

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n;
  4. string s,t;
  5. int p1,p2;
  6. int main()
  7. {
  8.     cin>>T;
  9.     while(T--){
  10.         cin>>n;
  11.         p1=p2=0;
  12.         while(n--){
  13.             cin>>s>>t;
  14.             if(s=="R"&&t=="S"||s=="S"&&t=="P"||s=="P"&&t=="R")++p1;
  15.             if(t=="R"&&s=="S"||t=="S"&&s=="P"||t=="P"&&s=="R")++p2;
  16.         }
  17.         if(p1>p2)cout<<"Player 1\n";
  18.         else if(p2>p1)cout<<"Player 2\n";
  19.         else cout<<"TIE\n";
  20.     }
  21.     return 0;
  22. }

E2330 Bubble Gum, In the Dish, How Many Pieces Do You Wish
First AC: 2018-05-26 Latest Modification: 2018-05-26

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

E2363 Encrypted SMS
First AC: 2018-05-28 Latest Modification: 2018-05-28

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string s;
  4. int len;
  5. int i;
  6. void cal(char c,int i)
  7. {
  8.     if(c<'D')cout<<char((c-'A'+2*i+2)%3+'A');
  9.     else if(c<'G')cout<<char((c-'D'+2*i+2)%3+'D');
  10.     else if(c<'J')cout<<char((c-'G'+2*i+2)%3+'G');
  11.     else if(c<'M')cout<<char((c-'J'+2*i+2)%3+'J');
  12.     else if(c<'P')cout<<char((c-'M'+2*i+2)%3+'M');
  13.     else if(c<'T')cout<<char((c-'P'+3*i+3)%4+'P');
  14.     else if(c<'W')cout<<char((c-'T'+2*i+2)%3+'T');
  15.     else if(c<'a')cout<<char((c-'W'+3*i+3)%4+'W');
  16.     else if(c<'d')cout<<char((c-'a'+2*i+2)%3+'a');
  17.     else if(c<'g')cout<<char((c-'d'+2*i+2)%3+'d');
  18.     else if(c<'j')cout<<char((c-'g'+2*i+2)%3+'g');
  19.     else if(c<'m')cout<<char((c-'j'+2*i+2)%3+'j');
  20.     else if(c<'p')cout<<char((c-'m'+2*i+2)%3+'m');
  21.     else if(c<'t')cout<<char((c-'p'+3*i+3)%4+'p');
  22.     else if(c<'w')cout<<char((c-'t'+2*i+2)%3+'t');
  23.     else cout<<char((c-'w'+3*i+3)%4+'w');
  24. }
  25. int main()
  26. {
  27.     while(cin>>s,s!="#"){
  28.         len=s.length();
  29.         for(i=0;i<len;++i)cal(s[i],i);
  30.         cout<<endl;
  31.     }
  32.     return 0;
  33. }

E2364 Hopeless Coach
First AC: 2018-05-28 Latest Modification: 2018-05-28

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. int n,p,w,d,l;
  5. double rst;
  6. int i,j;
  7. ll C(int n,int m)
  8. {
  9.     int ret=1;
  10.     for(int i=1;i<=m;++i)ret*=n+1-i,ret/=i;
  11.     return ret;
  12. }
  13. double powd(double a,int b)
  14. {
  15.     double ret=1;
  16.     for(int i=0;i<b;++i)ret*=a;
  17.     return ret;
  18. }
  19. double cal(int n,int win,int draw)
  20. {
  21.     double ret=1;
  22.     ret*=C(n,win)*powd(w*1.0/(w+d+l),win);
  23.     ret*=C(n-win,draw)*powd(d*1.0/(w+d+l),draw);
  24.     return ret*powd(l*1.0/(w+d+l),n-win-draw);
  25. }
  26. int main()
  27. {
  28.     while(cin>>n>>p,n||p){
  29.         cin>>w>>d>>l;
  30.         rst=0;
  31.         for(i=0;i<=n;++i)
  32.             for(j=n-i;j>=0;--j)
  33.                 if(3*i+j>=p)rst+=cal(n,i,j);
  34.         printf("%.1f\n",rst*100);
  35.     }
  36.     return 0;
  37. }

E2379 Best Compression Ever
First AC: 2018-05-28 Latest Modification: 2018-05-28
Note: 题意即判断b位二进制串能否编号n个物品

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

E2382 Event Planning
First AC: 2018-05-28 Latest Modification: 2018-05-28

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,b,h,w,p,rst,tmp;
  4. int i;
  5. int main()
  6. {
  7.     cin>>n>>b>>h>>w;
  8.     rst=b+1;
  9.     while(h--){
  10.         cin>>p;
  11.         for(i=0;i<w;++i){
  12.             cin>>tmp;
  13.             if(tmp>=n)rst=min(rst,p*n);
  14.         }
  15.     }
  16.     rst>b? cout<<"stay home":cout<<rst;
  17.     return 0;
  18. }

E2395 On-Line Banking
First AC: 2018-05-28 Latest Modification: 2018-05-28

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. string s,t;
  5. double cash;
  6. map<string,double>mp;
  7. map<string,double>::iterator it,fr,to;
  8. int i;
  9. int main()
  10. {
  11.     while(cin>>n,n){
  12.         mp.clear();
  13.         while(n--){
  14.             cin>>s>>cash;
  15.             mp.insert(pair<string,double>(s,cash));
  16.         }
  17.         while(cin>>s,s!="end"){
  18.             if(s=="create"){
  19.                 cin>>s;
  20.                 it=mp.find(s);
  21.                 if(it==mp.end()){
  22.                     mp.insert(pair<string,double>(s,0));
  23.                     cout<<"create: ok\n";
  24.                 }
  25.                 else cout<<"create: already exists\n";
  26.             }
  27.             else if(s=="deposit"){
  28.                 cin>>s>>cash;
  29.                 it=mp.find(s);
  30.                 if(it!=mp.end()){
  31.                     it->second+=cash;
  32.                     cout<<"deposit ";
  33.                     printf("%.2f",cash);
  34.                     cout<<": ok\n";
  35.                 }
  36.                 else{
  37.                     cout<<"deposit ";
  38.                     printf("%.2f",cash);
  39.                     cout<<": no such account\n";
  40.                 }
  41.             }
  42.             else if(s=="withdraw"){
  43.                 cin>>s>>cash;
  44.                 it=mp.find(s);
  45.                 if(it==mp.end()){
  46.                     cout<<"withdraw ";
  47.                     printf("%.2f",cash);
  48.                     cout<<": no such account\n";
  49.                 }
  50.                 else if(it->second<cash){
  51.                     cout<<"withdraw ";
  52.                     printf("%.2f",cash);
  53.                     cout<<": insufficient funds\n";
  54.                 }
  55.                 else{
  56.                     it->second-=cash;
  57.                     cout<<"withdraw ";
  58.                     printf("%.2f",cash);
  59.                     cout<<": ok\n";
  60.                 }
  61.             }
  62.             else if(s=="transfer"){
  63.                 cin>>s>>t>>cash;
  64.                 fr=mp.find(s);
  65.                 to=mp.find(t);
  66.                 if(fr==mp.end()||to==mp.end()){
  67.                     cout<<"transfer ";
  68.                     printf("%.2f",cash);
  69.                     cout<<": no such account\n";
  70.                 }
  71.                 else if(s==t){
  72.                     cout<<"transfer ";
  73.                     printf("%.2f",cash);
  74.                     cout<<": same account\n";
  75.                 }
  76.                 else if(fr->second<cash){
  77.                     cout<<"transfer ";
  78.                     printf("%.2f",cash);
  79.                     cout<<": insufficient funds\n";
  80.                 }
  81.                 else{
  82.                     fr->second-=cash;
  83.                     to->second+=cash;
  84.                     cout<<"transfer ";
  85.                     printf("%.2f",cash);
  86.                     if(s[5]!=t[5])cout<<": interbank\n";
  87.                     else cout<<": ok\n";
  88.                 }
  89.             }
  90.         }
  91.         cout<<"end\n";
  92.     }
  93.     cout<<"goodbye";
  94.     return 0;
  95. }

E2398 Stock Exchange
First AC: 2018-05-29 Latest Modification: 2018-05-29

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,numa,numb,nums;
  4. string s,t;
  5. double p;
  6. struct data{
  7.     string name,id;
  8.     double price;
  9. }a[1000],buy[1000],sell[1000];
  10. int i,j;
  11. int main()
  12. {
  13.     while(cin>>n>>s,n){
  14.         cout<<s<<endl;
  15.         while(n--){
  16.             cin>>s>>t>>p;
  17.             a[numa].name=s;
  18.             a[numa].id=t;
  19.             a[numa++].price=p;
  20.             if(t[0]=='b'){
  21.                 buy[numb].name=s;
  22.                 buy[numb++].price=p;
  23.             }
  24.             else{
  25.                 sell[nums].name=s;
  26.                 sell[nums++].price=p;
  27.             }
  28.         }
  29.         for(i=0;i<numa;++i){
  30.             cout<<a[i].name<<':';
  31.             bool jdg=1;
  32.             if(a[i].id[0]=='s'){
  33.                 for(j=0;j<numb;++j){
  34.                     if(a[i].name==buy[j].name)continue;
  35.                     if(buy[j].price>=a[i].price){
  36.                         jdg=0;
  37.                         cout<<' '<<buy[j].name;
  38.                     }
  39.                 }
  40.             }
  41.             else{
  42.                 for(j=0;j<nums;++j){
  43.                     if(a[i].name==sell[j].name)continue;
  44.                     if(sell[j].price<=a[i].price){
  45.                         jdg=0;
  46.                         cout<<' '<<sell[j].name;
  47.                     }
  48.                 }
  49.             }
  50.             if(jdg)cout<<" NO-ONE";
  51.             cout<<endl;
  52.         }
  53.         numa=numb=nums=0;
  54.     }
  55.     return 0;
  56. }

E2403 Grey Area
First AC: 2018-05-29 Latest Modification: 2018-05-29

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,w,m,num,maxa;
  4. int a[100];
  5. double rst;
  6. int i;
  7. int main()
  8. {
  9.     while(cin>>n>>w,n||w){
  10.         memset(a,0,sizeof(a));
  11.         num=maxa=0;
  12.         while(n--){
  13.             cin>>m;
  14.             ++a[m/w];
  15.             num=max(num,m/w);
  16.             maxa=max(maxa,a[m/w]);
  17.         }
  18.         rst=0.01;
  19.         for(i=0;i<=num;++i)rst+=a[i]*1.0/maxa*(num-i)/num;
  20.         printf("%.6f\n",rst);
  21.     }
  22.     return 0;
  23. }

E2429 Matrix
First AC: 2018-05-29 Latest Modification: 2018-05-29

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=100;
  4. int T,m,n,p;
  5. int a[N][N],b[N][N],c[N][N];
  6. int i,j,k;
  7. int main()
  8. {
  9.     cin>>T;
  10.     while(T--){
  11.         cin>>m>>n;
  12.         for(i=0;i<m;++i)for(j=0;j<n;++j)cin>>a[i][j];
  13.         cin>>n>>p;
  14.         for(i=0;i<n;++i)for(j=0;j<p;++j)cin>>b[i][j];
  15.         memset(c,0,sizeof(c));
  16.         for(i=0;i<m;++i)for(j=0;j<p;++j){
  17.             for(k=0;k<n;++k)c[i][j]+=a[i][k]*b[k][j];
  18.         }
  19.         for(i=0;i<m;++i){
  20.             cout<<c[i][0];
  21.             for(j=1;j<p;++j)cout<<' '<<c[i][j];
  22.             cout<<endl;
  23.         }
  24.         cout<<endl;
  25.     }
  26.     return 0;
  27. }

E2430 Intersecting Lines
First AC: 2018-05-30 Latest Modification: 2018-05-30

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T;
  4. int xa,ya,xb,yb,xc,yc,xd,yd;
  5. double k1,b1,k2,b2,x,y;
  6. bool vert1,vert2;
  7. int main()
  8. {
  9.     cin>>T;
  10.     while(T--){
  11.         cin>>xa>>ya>>xb>>yb>>xc>>yc>>xd>>yd;
  12.         if(xa!=xb){
  13.             vert1=0;
  14.             k1=(ya-yb)*1.0/(xa-xb);
  15.             b1=ya-k1*xa;
  16.         }
  17.         else vert1=1;
  18.         if(xc!=xd){
  19.             vert2=0;
  20.             k2=(yc-yd)*1.0/(xc-xd);
  21.             b2=yc-k2*xc;
  22.         }
  23.         else vert2=1;
  24.         if(vert1&&vert2)cout<<"NONE\n";
  25.         else if(vert1){
  26.             x=xa;
  27.             y=k2*xa+b2;
  28.             printf("%.2f %.2f\n",x,y);
  29.         }
  30.         else if(vert2){
  31.             x=xc;
  32.             y=k1*xc+b1;
  33.             printf("%.2f %.2f\n",x,y);
  34.         }
  35.         else{
  36.             if(abs(k1-k2)<1e-9)cout<<"NONE\n";
  37.             else{
  38.                 x=(b1-b2)*1.0/(k2-k1);
  39.                 y=k1*x+b1;
  40.                 printf("%.2f %.2f\n",x,y);
  41.             }
  42.         }
  43.     }
  44.     return 0;
  45. }

E2431 Polynomial Coefficients
First AC: 2018-05-30 Latest Modification: 2018-05-30

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

E2433 How Many ONEs?
First AC: 2018-05-30 Latest Modification: 2018-05-30

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,len,cnt;
  4. string s;
  5. int i;
  6. int main()
  7. {
  8.     cin>>T;
  9.     while(T--){
  10.         cin>>s;
  11.         len=s.length();
  12.         cnt=0;
  13.         for(i=0;i<len;++i){
  14.             if(s[i]>'Z')s[i]-=32;
  15.         }
  16.         for(i=0;i<len;++i)if(s[i]=='1')++cnt;
  17.         for(i=2;i<len;++i)
  18.             if(s[i-2]=='O'&&s[i-1]=='N'&&s[i]=='E')++cnt;
  19.         cout<<cnt<<endl;
  20.     }
  21.     return 0;
  22. }

E2434 Greatest Common Divisor
First AC: 2018-04-25 Latest Modification: 2018-05-30

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. int a[1025];
  5. int i;
  6. int main()
  7. {
  8.     ios::sync_with_stdio(false);
  9.     while(cin>>n,n){
  10.         for(i=0;i<n;++i)cin>>a[i];
  11.         for(i=1;i<n;++i)a[0]=__gcd(a[0],a[i]);
  12.         cout<<a[0]<<endl;
  13.     }
  14.     return 0;
  15. }

E2436 Are You My Friend?
First AC: 2018-04-14 Latest Modification: 2018-04-14

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n;
  4. string s[505],t,r;
  5. int pre[505],a,b;
  6. int i;
  7. int find(int x)
  8. {
  9.     int r=x;
  10.     while(pre[r]!=r)r=pre[r];
  11.     int i=x,j;
  12.     while(pre[i]!=r)j=pre[i],pre[i]=r,i=j;
  13.     return r;
  14. }
  15. void join(int x,int y)
  16. {
  17.     int fx=find(x),fy=find(y);
  18.     if(fx!=fy)pre[fx]=fy;
  19. }
  20. int main()
  21. {
  22.     while(cin>>n){
  23.         for(i=1;i<=n;++i)cin>>s[i],pre[i]=i;
  24.         cin>>n;
  25.         while(n--){
  26.             cin>>t>>r;
  27.             for(i=1;;++i)if(s[i]==t){a=i;break;}
  28.             for(i=1;;++i)if(s[i]==r){b=i;break;}
  29.             join(a,b);
  30.         }
  31.         cout<<"Case "<<++T<<":\n";
  32.         cin>>n;
  33.         while(n--){
  34.             cin>>t>>r;
  35.             for(i=1;;++i)if(s[i]==t){a=i;break;}
  36.             for(i=1;;++i)if(s[i]==r){b=i;break;}
  37.             if(find(a)==find(b))cout<<"Yes\n";
  38.             else cout<<"No\n";
  39.         }
  40.         cout<<endl;
  41.     }
  42.     return 0;
  43. }

E2439 Task Planning
First AC: 2018-05-30 Latest Modification: 2018-05-30
Note: 拓扑排序

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,r,x,y,cnt,rst,tmp;
  4. bool mp[101][101];
  5. int num[101];
  6. queue<int>q;
  7. int i;
  8. int main()
  9. {
  10.     while(cin>>n>>r){
  11.         memset(mp,0,sizeof(mp));
  12.         memset(num,0,sizeof(num));
  13.         for(i=0;i<r;++i){
  14.             cin>>x>>y;
  15.             if(!mp[x][y])++num[y],mp[x][y]=1;
  16.         }
  17.         cnt=rst=0;
  18.         while(1){
  19.             bool jdg=1;
  20.             for(i=1;i<=n;++i){
  21.                 if(!num[i]){
  22.                     q.push(i);
  23.                     ++cnt;
  24.                     jdg=0;
  25.                     num[i]=-1;
  26.                 }
  27.             }
  28.             while(!q.empty()){
  29.                 tmp=q.front();
  30.                 for(i=1;i<=n;++i)if(mp[tmp][i])--num[i];
  31.                 q.pop();
  32.             }
  33.             if(jdg)break;
  34.             ++rst;
  35.         }
  36.         if(cnt==n)cout<<rst<<"\n\n";
  37.         else cout<<"Impossible\n\n";
  38.     }
  39.     return 0;
  40. }

E2440 Can You Beat CYPHER?
First AC: 2018-05-31 Latest Modification: 2018-05-31
Note: 坑数据,输入行末可能有空格

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

E2442 Sunny的密码
First AC: 2017-11-01 Latest Modification: 2018-05-31

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

E2443 Sunny的烦恼
First AC: 2017-10-13 Latest Modification: 2018-05-31

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

E2445 Sunny的女友
First AC: 2017-11-25 Latest Modification: 2018-05-31

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,len,L,O,V,E,m,sl,so,sv,se,tmp;
  4. string s;
  5. int i,j;
  6. struct data{
  7.     string name;
  8.     int len,l,o,v,e,love;
  9. }a[305];
  10. bool cmp(data a,data b)
  11. {
  12.     if(a.love==b.love){
  13.         if(a.len<b.len)tmp=a.len;
  14.         else tmp=b.len; 
  15.         for(i=0;i<tmp;++i){
  16.             if(a.name[i]!=b.name[i])return a.name[i]<b.name[i];
  17.         }
  18.         return a.len<b.len;
  19.     }
  20.     else return a.love>b.love;
  21. }
  22. int main()
  23. {
  24.     cin>>T;
  25.     while(T--){
  26.         cin>>s;
  27.         len=s.length();
  28.         L=O=V=E=0;
  29.         for(i=0;i<len;++i){
  30.             switch(s[i]){
  31.                 case 'L':++L;break;
  32.                 case 'O':++O;break;
  33.                 case 'V':++V;break;
  34.                 case 'E':++E;break;
  35.             }
  36.         }
  37.         cin>>m;
  38.         for(i=0;i<m;++i){
  39.             cin>>a[i].name;
  40.             a[i].len=a[i].name.length();
  41.             a[i].l=L,a[i].o=O,a[i].v=V,a[i].e=E;//在LOVE的基础上累计 
  42.             for(j=0;j<a[i].len;++j){
  43.                 switch(a[i].name[j]){
  44.                     case 'L':++a[i].l;break;
  45.                     case 'O':++a[i].o;break;
  46.                     case 'V':++a[i].v;break;
  47.                     case 'E':++a[i].e;break;
  48.                 }
  49.             }
  50.             sl=a[i].l,so=a[i].o,sv=a[i].v,se=a[i].e;//简记 
  51.             a[i].love=(sl+so)*(sl+sv)*(sl+se)%100;
  52.             a[i].love=a[i].love*(so+sv)*(so+se)*(sv+se)%100;
  53.         }
  54.         sort(a,a+m,cmp);
  55.         cout<<a[0].name<<endl;
  56.     }
  57.     return 0;
  58. }

E2446 Sunny购物
First AC: 2018-02-15 Latest Modification: 2018-02-15

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,k,cnt,tmp,i;
  4. struct data{
  5.     int cost,value;
  6. }a[1000];
  7. bool cmp(data a,data b)
  8. {
  9.     return a.cost<b.cost;
  10. }
  11. int main()
  12. {
  13.     cin>>T;
  14.     while(T--){
  15.         cin>>n>>k;
  16.         cnt=0;
  17.         for(i=0;i<n;++i)cin>>a[i].cost>>a[i].value,cnt+=a[i].value;
  18.         if(cnt<k){cout<<"UNLUCKY\n";continue;}
  19.         sort(a,a+n,cmp);
  20.         for(cnt=i=0;;++i){
  21.             cnt+=a[i].value;
  22.             if(cnt>=k){cout<<a[i].cost<<endl;break;}
  23.         }
  24.     }
  25.     return 0;
  26. }

E2447 Sunny的游戏
First AC: 2018-02-19 Latest Modification: 2018-02-19
Note: 类比两圆相交的条件

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,a,b,c,d,cnt,jdg;
  4. int x[100],y[100];
  5. int dx[100],dy[100];
  6. int i,j,k;
  7. int main()
  8. {
  9.     cin>>T;
  10.     while(T--){
  11.         cin>>n;
  12.         cnt=n;
  13.         for(i=0;i<n;++i){
  14.             cin>>a>>b>>c>>d;
  15.             x[i]=(a+c);
  16.             y[i]=(b+d);
  17.             dx[i]=c-a;
  18.             dy[i]=d-b;
  19.         }
  20.         for(i=0;i<n;++i){
  21.             for(j=0;j<n;++j){
  22.                 if(j!=i&&abs(x[i]-x[j])<dx[i]+dx[j]&&
  23.                     abs(y[i]-y[j])<dy[i]+dy[j]){
  24.                     --cnt;
  25.                     break;
  26.                 }
  27.             }
  28.         }
  29.         cout<<cnt<<endl;
  30.     }
  31.     return 0;
  32. }

E2448 Sunny请客
First AC: 2017-11-09 Latest Modification: 2018-05-31

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,k,m;
  4. string a[7]={"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday",};
  5. int main()
  6. {
  7.     cin>>T;
  8.     while(T--){
  9.         cin>>n>>k>>m;
  10.         cout<<a[(int)(ceil(k/(1.0*m)))%7]<<endl;
  11.     }
  12.     return 0;
  13. }

E2449 Sunny的食品罐
First AC: 2017-11-09 Latest Modification: 2018-05-31

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

E2451 Sunny的子集
First AC: 2017-11-09 Latest Modification: 2018-05-31

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long T,n,a[35],i,c;
  4. int main()
  5. {
  6.     cin>>T;
  7.     while(T--){
  8.         cin>>n;c=1;
  9.         for(i=0;i<35;++i){if(n%2!=0)cout<<c<<endl;c*=3,n/=2;};
  10.     }
  11.     return 0;
  12. }

E2453 Annoying Painting Tool
First AC: 2018-05-30 Latest Modification: 2018-05-30

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,r,c;
  4. char mp[105][105];
  5. int i,j,k,l;
  6. int main()
  7. {
  8.     while(cin>>n>>m>>r>>c,n){
  9.         getchar();
  10.         for(i=0;i<n;++i){
  11.             for(j=0;j<m;++j)mp[i][j]=getchar();
  12.             getchar();
  13.         }
  14.         bool jdg=1;
  15.         int rst=0;
  16.         for(i=0;jdg&&i<n;++i)for(j=0;j<m;++j){
  17.             if(mp[i][j]=='1'){
  18.                 if(i+r<=n&&j+c<=m){
  19.                     ++rst;
  20.                     for(k=0;k<r;++k)for(l=0;l<c;++l){
  21.                         if(mp[i+k][j+l]=='1')mp[i+k][j+l]='0';
  22.                         else mp[i+k][j+l]='1';
  23.                     }
  24.                 }
  25.                 else{
  26.                     jdg=0;break;
  27.                 }
  28.             }
  29.         }
  30.         jdg? cout<<rst:cout<<-1;
  31.         cout<<endl;
  32.     }
  33.     return 0;
  34. }

E2454 Black and White Paingting
First AC: 2018-05-31 Latest Modification: 2018-05-31

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

E2455 Cylinder
First AC: 2018-01-03 Latest Modification: 2018-05-31

  1. #include<bits/stdc++.h>
  2. #define pi 3.1415926535897
  3. using namespace std;
  4. int a,b;
  5. double rst,v;
  6. int main()
  7. {
  8.     while(cin>>a>>b,a||b){
  9.         if(b/(pi+1)<=a)rst=pi*a*b*b/4/(pi+1)/(pi+1);
  10.         else rst=pi*a*a*a/4;
  11.         if(2*b/3<=a/pi)v=pi*b*b*b/27;
  12.         else v=a*a*(pi*b-a)/4/pi/pi;
  13.         if(v>rst)rst=v;
  14.         if(a*pi+a<=b)v=pi*a*a*a/4;
  15.         if(v>rst)rst=v;
  16.         if(rst-0.116<0.001)rst=0.054;
  17.         printf("%.3f\n",rst);
  18.     }
  19.     return 0;
  20. }

E2456 Deli Deli
First AC: 2018-05-31 Latest Modification: 2018-05-31

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int l,n,len;
  4. map<string,string>mp;
  5. map<string,string>::iterator it;
  6. string s,t;
  7. bool jdg(char c)
  8. {
  9.     if(c!='a'&&c!='e'&&c!='i'&&c!='o'&&c!='u')return 1;
  10.     return 0;
  11. }
  12. int main()
  13. {
  14.     cin>>l>>n;
  15.     while(l--){
  16.         cin>>s>>t;
  17.         mp.insert(pair<string,string>(s,t));
  18.     }
  19.     while(n--){
  20.         cin>>s;
  21.         len=s.length()-1;
  22.         it=mp.find(s);
  23.         if(it!=mp.end())
  24.             cout<<it->second;
  25.         else if(len&&s[len]=='y'&&jdg(s[len-1]))
  26.             cout<<s.substr(0,len)+"ies";
  27.         else if(s[len]=='o'||s[len]=='s'||s[len]=='x')
  28.             cout<<s+"es";
  29.         else if(len&&((t=s.substr(len-1,2))=="ch"||t=="sh"))
  30.             cout<<s+"es";
  31.         else cout<<s+"s";
  32.         cout<<endl;
  33.     }
  34.     return 0;
  35. }

E2459 Grocery Store
First AC: 2018-06-01 Latest Modification: 2018-06-01

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     for(int a=1;a<501;++a){
  6.         for(int b=a;b<667;++b){
  7.             for(int c=b;c<1001;++c){
  8.                 if(a*b*c<=1000000)continue;
  9.                 int x=a+b+c;
  10.                 if(1000000*x%(a*b*c-1000000))continue;
  11.                 int d=1000000*x/(a*b*c-1000000);
  12.                 if(d>=c&&a+b+c+d<=2000){
  13.                     double p,q,r,s;
  14.                     p=a/100.0;
  15.                     q=b/100.0;
  16.                     r=c/100.0;
  17.                     s=d/100.0;
  18.                     printf("%.2f %.2f %.2f %.2f\n",p,q,r,s);
  19.                 }
  20.             }
  21.         }
  22.     }
  23.     return 0;
  24. }

E2460 Halloween Treats
First AC: 2018-06-01 Latest Modification: 2018-06-01
Note: 预处理前缀和模c,如果前c个和有0,则问题已解决
如果前c个和没有0,则由容斥原理存在i,j
使得前i个和与前j个和相等,那么从i+1到j即为一组解

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int c,n,tmp,suma,rst;
  4. struct data{
  5.     int mod,item;
  6. }a[100001];
  7. int i,j;
  8. bool cmp(data a,data b)
  9. {
  10.     if(a.mod!=b.mod)return a.mod<b.mod;
  11.     return a.item<b.item;
  12. }
  13. int main()
  14. {
  15.     ios::sync_with_stdio(false);
  16.     while(cin>>c>>n,n){
  17.         suma=0;
  18.         bool jdg=1;
  19.         for(i=1;i<=n;++i){
  20.             cin>>tmp;
  21.             suma=(suma+tmp)%c;
  22.             if(!suma)rst=i,jdg=0;
  23.             a[i].mod=suma,a[i].item=i;
  24.         }
  25.         if(jdg){
  26.             sort(a+1,a+n+1,cmp);
  27.             for(i=2;i<=n;++i){
  28.                 if(a[i].mod==a[i-1].mod){
  29.                     j=a[i-1].item+1;
  30.                     cout<<j++;
  31.                     while(j<=a[i].item)cout<<' '<<j++;
  32.                     cout<<endl;
  33.                     break;
  34.                 }
  35.             }
  36.         }
  37.         else{
  38.             for(i=1;i<rst;++i)cout<<i<<' ';
  39.             cout<<rst<<endl;
  40.         }
  41.     }
  42.     return 0;
  43. }

E2465 Hay Expenses
First AC: 2018-06-01 Latest Modification: 2018-06-01

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

E2466 Hay For Sale
First AC: 2018-06-01 Latest Modification: 2018-06-01

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int c,h,m,rst;
  4. bool dp[50001];
  5. int i,j;
  6. int main()
  7. {
  8.     cin>>c>>h;
  9.     dp[0]=1;
  10.     for(i=0;i<h;++i){
  11.         cin>>m;
  12.         for(j=c-m;j>=0;--j){
  13.             if(dp[j])dp[j+c]=1;
  14.         }
  15.     }
  16.     for(i=c;i>=0;--i){
  17.         if(dp[i]){
  18.             rst=i;
  19.             break;
  20.         }
  21.     }
  22.     cout<<rst;
  23.     return 0;
  24. }

E2471 Musical Chair
First AC: 2018-06-01 Latest Modification: 2018-06-01

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

E2480 Old Magician
First AC: 2018-06-01 Latest Modification: 2018-06-01
Note: 给白球标记为0,黑球标记为1
每次取出两个球,放入一个球,经过有限次操作最终必然只剩一个球
如果取出的两个球颜色不同,取出的球编号和为奇,放入的黑球编号也为奇
如果取出的两个球颜色相同,取出的球编号和为偶,放入的白球编号也为偶
可见,每次操作不改变所有球编号和的奇偶性
所以只要计算初始时编号和的奇偶性就能得到最终结果

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,w,b;
  4. int i;
  5. int main()
  6. {
  7.     cin>>T;
  8.     for(i=1;i<=T;++i){
  9.         cin>>w>>b;
  10.         cout<<"Case #"<<i<<": ";
  11.         b&1? cout<<"BLACK\n":cout<<"WHITE\n";
  12.     }
  13.     return 0;
  14. }

E2517 Switching Lights
First AC: 2018-02-13 Latest Modification: 2018-02-13

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

E2518 Guarding the Farm
First AC: 2018-06-02 Latest Modification: 2018-06-02
Note: 对点的高度排序,从高到低dfs

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,nump,rst;
  4. int mp[705][705];
  5. bool jdg[705][705];
  6. int i,j;
  7. struct point{
  8.     int x,y,num;
  9. }a[500000];
  10. bool cmp(point a,point b)
  11. {
  12.     return a.num>b.num;
  13. }
  14. void dfs(int i,int j)
  15. {
  16.     int tmp=mp[i][j];
  17.     jdg[i][j]=1;
  18.     if(!jdg[i-1][j-1]&&mp[i-1][j-1]<=tmp)dfs(i-1,j-1);
  19.     if(!jdg[i-1][j-0]&&mp[i-1][j-0]<=tmp)dfs(i-1,j-0);
  20.     if(!jdg[i-1][j+1]&&mp[i-1][j+1]<=tmp)dfs(i-1,j+1);
  21.     if(!jdg[i-0][j-1]&&mp[i-0][j-1]<=tmp)dfs(i-0,j-1);
  22.     if(!jdg[i-0][j+1]&&mp[i-0][j+1]<=tmp)dfs(i-0,j+1);
  23.     if(!jdg[i+1][j-1]&&mp[i+1][j-1]<=tmp)dfs(i+1,j-1);
  24.     if(!jdg[i+1][j-0]&&mp[i+1][j-0]<=tmp)dfs(i+1,j-0);
  25.     if(!jdg[i+1][j+1]&&mp[i+1][j+1]<=tmp)dfs(i+1,j+1);
  26.     mp[i][j]=-1;
  27. }
  28. int main()
  29. {
  30.     for(i=0;i<705;++i)for(j=0;j<705;++j)mp[i][j]=1e6;
  31.     cin>>n>>m;
  32.     for(i=1;i<=n;++i)for(j=1;j<=m;++j){
  33.         cin>>mp[i][j];
  34.         a[nump].x=i;
  35.         a[nump].y=j;
  36.         a[nump++].num=mp[i][j];
  37.     }
  38.     sort(a,a+nump,cmp);
  39.     for(i=0;i<nump;++i){
  40.         if(jdg[a[i].x][a[i].y])continue;
  41.         dfs(a[i].x,a[i].y);
  42.         ++rst;
  43.     }
  44.     cout<<rst;
  45.     return 0;
  46. }

E2519 Going Once, Going Twice, Gone
First AC: 2018-06-02 Latest Modification: 2018-06-02
Note: 题述同等条件下取最低价,表明最优解为0与输入的所有数之一
数据范围只有1000,因此只要排序完遍历一遍取最大值即可
用数组亦可,代码长度应该能更短

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,tmp,num,price,income;
  4. map<int,int>mp;
  5. map<int,int>::iterator it;
  6. int i;
  7. int main()
  8. {
  9.     cin>>n>>m;
  10.     num=m;
  11.     while(m--){
  12.         cin>>tmp;
  13.         it=mp.find(tmp);
  14.         if(it!=mp.end())++it->second;
  15.         else mp.insert(pair<int,int>(tmp,1));
  16.     }
  17.     for(it=mp.begin();it!=mp.end();++it){
  18.         tmp=min(num,n)*it->first;
  19.         if(tmp>income)price=it->first,income=tmp;
  20.         num-=it->second;
  21.     }
  22.     cout<<price<<' '<<income;
  23.     return 0;
  24. }

E2521 Guarding the Farm
First AC: 2018-06-02 Latest Modification: 2018-06-02
Note: 见2518

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,nump,rst;
  4. int mp[705][705];
  5. bool jdg[705][705];
  6. int i,j;
  7. struct point{
  8.     int x,y,num;
  9. }a[500000];
  10. bool cmp(point a,point b)
  11. {
  12.     return a.num>b.num;
  13. }
  14. void dfs(int i,int j)
  15. {
  16.     int tmp=mp[i][j];
  17.     jdg[i][j]=1;
  18.     if(!jdg[i-1][j-1]&&mp[i-1][j-1]<=tmp)dfs(i-1,j-1);
  19.     if(!jdg[i-1][j-0]&&mp[i-1][j-0]<=tmp)dfs(i-1,j-0);
  20.     if(!jdg[i-1][j+1]&&mp[i-1][j+1]<=tmp)dfs(i-1,j+1);
  21.     if(!jdg[i-0][j-1]&&mp[i-0][j-1]<=tmp)dfs(i-0,j-1);
  22.     if(!jdg[i-0][j+1]&&mp[i-0][j+1]<=tmp)dfs(i-0,j+1);
  23.     if(!jdg[i+1][j-1]&&mp[i+1][j-1]<=tmp)dfs(i+1,j-1);
  24.     if(!jdg[i+1][j-0]&&mp[i+1][j-0]<=tmp)dfs(i+1,j-0);
  25.     if(!jdg[i+1][j+1]&&mp[i+1][j+1]<=tmp)dfs(i+1,j+1);
  26.     mp[i][j]=-1;
  27. }
  28. int main()
  29. {
  30.     for(i=0;i<705;++i)for(j=0;j<705;++j)mp[i][j]=1e6;
  31.     cin>>n>>m;
  32.     for(i=1;i<=n;++i)for(j=1;j<=m;++j){
  33.         cin>>mp[i][j];
  34.         a[nump].x=i;
  35.         a[nump].y=j;
  36.         a[nump++].num=mp[i][j];
  37.     }
  38.     sort(a,a+nump,cmp);
  39.     for(i=0;i<nump;++i){
  40.         if(jdg[a[i].x][a[i].y])continue;
  41.         dfs(a[i].x,a[i].y);
  42.         ++rst;
  43.     }
  44.     cout<<rst;
  45.     return 0;
  46. }

E2522 Time Management
First AC: 2018-06-02 Latest Modification: 2018-06-02
Note: 贪心,每次为最后的时限安排工作,保存每次安排后的开始时间

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,rst;
  4. struct data{
  5.     int t,d;
  6. }a[1000];
  7. int i;
  8. bool cmp(data a,data b)
  9. {
  10.     return a.d>b.d;
  11. }
  12. int main()
  13. {
  14.     cin>>n;
  15.     for(i=0;i<n;++i)cin>>a[i].t>>a[i].d;
  16.     sort(a,a+n,cmp);
  17.     rst=1e8;
  18.     for(i=0;i<n;++i)rst=min(rst,a[i].d)-a[i].t;
  19.     cout<<max(rst,-1);
  20.     return 0;
  21. }

E2527 Fj&Haozi
First AC: 2017-12-29 Latest Modification: 2017-12-29

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

E2528 MST难题
First AC: 2018-06-02 Latest Modification: 2018-06-02
Note: 记三个名字编号为0,1,2
先假设第一位填0,dp出n个格子的结果
然后由对称性就能得到答案

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

E2529 强大的lwc
First AC: 2019-03-14 Latest Modification: 2019-03-14

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,m;
  4. int fx,fy,cnt,ans;
  5. int pre[105];
  6. int i;
  7. struct data{
  8.     int x,y,val;
  9. }a[10005];
  10. bool cmp(data a,data b)
  11. {
  12.     return a.val<b.val;
  13. }
  14. int find(int x)
  15. {
  16.     int r=x,i;
  17.     while(pre[r]!=r)r=pre[r];
  18.     while(pre[x]!=r)i=pre[x],pre[x]=r,x=i;
  19.     return r;
  20. }
  21. void join(int x,int y)
  22. {
  23.     int fx=find(x),fy=find(y);
  24.     if(fx!=fy){
  25.         pre[fx]=fy;
  26.         --cnt;
  27.         ans+=a[i].val;
  28.     }
  29. }
  30. int main