Codeforces Round #496 (Div. 3) ABCDE1-白红宇

Codeforces Round #496 (Div. 3) ABCDE1

阅读量：4486 次

发布时间：2019-06-08

本文共 3769 字，大约阅读时间需要 12 分钟。

1 //B. Delete from the Left 2 #include 
     
       3 #include 
      
        4 #include 
       
         5 #include 
        
          6 #include 
         
           7 #include 
           8 #include 
           
             9 using namespace std;10 const int inf=0x3f3f3f3f;11 const int N=2e5+9;12 char a[N],b[N];13 int main()14 {15 scanf("%s%s",a,b);16 int lena=strlen(a);17 int lenb=strlen(b);18 int i=lena-1,j=lenb-1;19 int sum=0;20 while(a[i]==b[j]&&i>=0&&j>=0)//s[-1]与p[-1]是不确定的21 { //因此加上i>=0&&j>=0 和下面的D题相似22 sum++;23 i--,j--;24 } 25 printf("%d\n",lena+lenb-2*sum);26 return 0;27 }

1 //C. Summarize to the Power of Two /*

2^(n-1) x 2^n 2^(n+1）

因为x<2^n,所以2*x<2^(n+1)，那么x+y(0<x<y)一定位于

2^(n-1)和2^(n+1)之间。若x+y为2的指数幂，那么必定是2^n.

*/ 2 #include 
     
        3 #include 
      
         4 #include 
       
          5 #include 
        
           6 #include 
         
            7 #include 
           8 #include 
           
             9 #include 
            
              10 using namespace std; 11 typedef long long ll; 12 const int inf=0x3f3f3f3f; 13 const int N=130000; 14 ll n; 15 ll a[N]; 16 map
             
              mp; 17 set
              
               s; 18 int main() 19 { 20 scanf("%lld",&n); 21 for(int i=0;i
               
                 83 #include 
                
                  84 #include 
                 
                   85 #include 
                  
                    86 #include 
                   
                     87 #include 
                     88 #include 
                     
                       89 #include 
                      
                        90 using namespace std; 91 typedef long long ll; 92 const int inf=0x3f3f3f3f; 93 ll n; 94 map
                       
                        mp; 95 const int M=1.3e5+9; 96 ll a[M]; 97 int main() 98 { 99 scanf("%lld",&n);100 for(ll i=0;i
                        
                         1)114 //出现多次，可以互相替换，1次只要两者不等，就一定不是同一位置115 //不相等一定不是同位置116 for(int j=1;j<=30;j++)117 {118 if(mp[(1<

1 ////D. Polycarp and Div 3 2 #include 
     
       3 #include 
      
        4 #include 
       
         5 #include 
        
          6 #include  
         
           7 #include 
           8 #include 
           
             9 #include 
            
             10 using namespace std;11 typedef long long ll;12 const int inf=0x3f3f3f3f;13 const int N=2e5+9;14 ll dp[N];15 char s[N];16 int main()17 { 18 scanf("%s",s+1);19 /*20 if(s[1]=='1'&&s[2]=='1'){21 if(strlen(s+1)==2){22 printf("0\n");23 return 0;24 }25 }26 */27 28 int lens=strlen(s+1);29 memset(dp,0,sizeof(dp));30 if((s[1]-'0')%3==0){31 dp[1]=1;32 }33 //int i,j,k,sum;34 for( int i=2;i<=lens;i++)35 {36 dp[i]=dp[i-1];37 //cout<<"iii"<
             <
              
               =0;j--)//起初没加j>=039 { //如dp[-1]=dp[0]=dp[1]=0 。数组的负下标问题40 //可能令最终的结果有问题，也会时间更长41 if(dp[j]!=dp[i-1])42 break;43 if(s[j+1]=='0'&&i-j>1)44 continue;45 //cout<
               
                <<" "<
                
                 <
                 
                  =j+1;k--)48 {49 sum=(sum+(s[k]-'0'))%3;50 }51 //cout<<"sum "<
                  
                   <
                   
                    67 #include 
                    
                     68 #include 
                     
                      69 #include 
                      
                       70 #include 
                       
                        71 #include 
                        72 #include 
                         
                          73 #include 
                          
                           74 using namespace std;75 typedef long long ll;76 const int inf=0x3f3f3f3f;77 const int N=2e5+9;78 int main()79 {80 char s[N];81 scanf("%s",s);82 int sum=0,cnt=0,tmp;83 int ans=0;84 for(int i=0;s[i];i++)85 {86 tmp=(s[i]-'0')%3;87 sum+=tmp;88 cnt++;89 if(tmp==0||sum%3==0||cnt==3)90 {91 ans++;92 sum=cnt=0;93 }94 }95 printf("%d\n",ans);96 return 0;97 }

1 // E1 - Median on Segments (Permutations Edition) 2 //区间内大于m的数的个数-小于m的数的个数（sum）==0or1 3 //在m出现之前依次记录sum，用map存储每个sum出现的个数 4 //等到m出现后，每当遇到一个sum，ans+=(sum出现的次数)+(sum-1出现的次数) 5 //sum sum 区间内大于m的数的个数-小于m的数的个数==0 6 //sum(前面) sum-1(后面) 区间内大于m的数的个数-小于m的数的个数==1 7 //m出现后不再增加sum出现的次数,因为那些区间不会包含m 8 //符合条件的区间一定要包含m 9 #include 
     
      10 #include 
      
       11 #include 
       
        12 #include 
        
         13 #include  
         
          14 #include 
          15 #include 
           
            16 #include 
            
             17 using namespace std;18 typedef long long ll;19 const int inf=0x3f3f3f3f;20 const int N=2e5+9;21 int n,m,a[N];22 map
             
              mp;23 int main()24 {25 scanf("%d%d",&n,&m);26 for(int i=0;i
              
               m)39 sum++;40 if(a[i]==m)41 flag=1;42 if(flag){43 ans+=mp[sum]+mp[sum-1];44 }45 else{46 mp[sum]++;47 }48 }49 printf("%lld\n",ans);50 return 0;51 }