CF #269 DIV2 A,B,C,D_html/css_WEB-ITnose

html教程评论277 views阅读模式

A

http://codeforces.com/contest/471/problem/A

解题思路：给你6个数，问是否有至少4个数都相等，没有的话输出“Alien”，有的话再看剩下的两个数，如果相等就输出"

Elephant"，否则输出"
Bear"；

#include 
  
   #include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #define Maxn 100005#define Maxm 1000005#define lowbit(x) x&(-x)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define PI acos(-1.0)#define make_pair MP#define LL long long #define Inf (1LL<<62)#define inf 0x3f3f3f3f#define re freopen("in.txt","r",stdin)#define wr freopen("out.txt","w",stdout)using namespace std;int main(){ int a[6],flag; //re;wr; while(~scanf("%d%d%d%d%d%d",&a[0],&a[1],&a[2],&a[3],&a[4],&a[5])) { flag=0; sort(a,a+6); if(a[0]==a[1]&&a[2]==a[1]&&a[3]==a[2]) flag=1; if(a[1]==a[2]&&a[2]==a[3]&&a[3]==a[4]) flag=2; if(a[2]==a[3]&&a[3]==a[4]&&a[4]==a[5]) flag=3; if(flag==0) { puts("Alien"); continue; } if(flag==1) { if(a[4]==a[5]) { puts("Elephant"); continue; } else { puts("Bear"); continue; } } else if(flag==2) { if(a[0]==a[5]) { puts("Elephant"); continue; } else { puts("Bear"); continue; } } else { if(a[0]==a[1]) { puts("Elephant"); continue; } else { puts("Bear"); continue; } } } return 0;}
                
               
              
             
            
           
          
         
       
      
     
    
   
  


B 



http://codeforces.com/contest/471/problem/B




解题思路：给你一个序列，问是否有三种不同的方法使它们按非减序排序，显然只有有2个相等的元素集合数大于等于2时或者有3个相等的元素的集合时才有解，有解的时候集合内排序一下，我写的很繁，导致后面的题目没写，整场就跪了




#include 
  
   #include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #define Maxn 100005#define Maxm 1000005#define lowbit(x) x&(-x)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define PI acos(-1.0)#define make_pair MP#define LL long long #define Inf (1LL<<62)#define inf 0x3f3f3f3f#define re freopen("in.txt","r",stdin)#define wr freopen("out.txt","w",stdout)using namespace std;struct Mask{ int dif; int id; friend bool operator <(Mask a,Mask b) { if(a.dif!=b.dif) return a.dif
                 
                  2) { flag=true; break; } if(m[i]==2) cnt++; } if(flag||cnt>=2) { puts("YES"); sort(arr+1,arr+1+n); if(flag) { for(i=1;i<=n;i++) { if(m[arr[i].dif]>2) break; } int a=arr[i].id; int b=arr[i+1].id; int c=arr[i+2].id; //cout<
                  
                   i+2) { printf("%d%c",arr[j].id,j==n?'\n':' '); } else if(i==n-2) { printf("%d %d %d\n",a,b,c); j+=2; } else { printf("%d %d %d ",a,b,c); j+=2; } } for(j=1;j<=n;j++) { if(j
                   
                    i+2) { printf("%d%c",arr[j].id,j==n?'\n':' '); } else if(i==n-2) { printf("%d %d %d\n",b,a,c); j+=2; } else { printf("%d %d %d ",b,a,c); j+=2; } } for(j=1;j<=n;j++) { if(j
                    
                     i+2) { printf("%d%c",arr[j].id,j==n?'\n':' '); } else if(i==n-2) { printf("%d %d %d\n",c,b,a); j+=2; } else { printf("%d %d %d ",c,b,a); j+=2; } } } else { int f1,f2; for(i=1;i<=n;i++) if(m[arr[i].dif]==2) { f1=i; break; } for(i=i+2;i<=n;i++) if(m[arr[i].dif]==2) { f2=i; break; } int a=arr[f1].id; int b=arr[f1+1].id; int c=arr[f2].id; int d=arr[f2+1].id; //cout<
                     
                      f1+1)&&(i
                      
                       f2+1)) printf("%d%c",arr[i].id,i==n?'\n':' '); else if(i>=f1&&i<=f1+1) { printf("%d %d ",a,b); i+=1; } else if(i>=f2&&i<=f2+1) { if(f2==n-1) printf("%d %d\n",c,d); else printf("%d %d ",c,d); i+=1; } } for(i=1;i<=n;i++) { if((i
                       
                        f1+1)&&(i
                        
                         f2+1)) printf("%d%c",arr[i].id,i==n?'\n':' '); else if(i>=f1&&i<=f1+1) { printf("%d %d ",a,b); i+=1; } else if(i>=f2&&i<=f2+1) { if(f2==n-1) printf("%d %d\n",d,c); else printf("%d %d ",d,c); i+=1; } } for(i=1;i<=n;i++) { if((i
                         
                          f1+1)&&(i
                          
                           f2+1)) printf("%d%c",arr[i].id,i==n?'\n':' '); else if(i>=f1&&i<=f1+1) { printf("%d %d ",b,a); i+=1; } else if(i>=f2&&i<=f2+1) { if(f2==n-1) printf("%d %d\n",c,d); else printf("%d %d ",c,d); i+=1; } } } } else { puts("NO"); continue; } }}
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
       
      
     
    
   
  


C  



http://codeforces.com/contest/471/problem/C




 解题思路：首先二分出n个棍子最多可以搭几层，然后从1开始枚举，注意到每一层的数目都是一个公差为3的等差数列，判断一下这一层能否满足n的需求即可 



#include 
  
   #include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #define Maxn 100005#define Maxm 1000005#define lowbit(x) x&(-x)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define PI acos(-1.0)#define make_pair MP#define LL long long #define Inf (1LL<<62)#define inf 0x3f3f3f3f#define re freopen("in.txt","r",stdin)#define wr freopen("out.txt","w",stdout)using namespace std;LL cal(LL n){ return (3*n+1)*n/2;}LL calc(LL a,LL k,LL n){ return a+(n-1)*k;}int main(){ LL n,ans; //re;wr; while(~scanf("%I64d",&n)) { ans=0; LL l=0,r=(Maxm<<1),lv; while(r>=l) { LL m=(l+r)>>1; if(cal(m)<=n) { lv=m; l=m+1; } else r=m-1; } for(LL i=1;i<=lv;i++) { LL a=cal(i); if((n-a)%3==0) ans++; } printf("%d\n",ans); } return 0;}
                
               
              
             
            
           
          
         
       
      
     
    
   
  


D 



http://codeforces.com/problemset/problem/471/D




解题思路：做出两个数列的相邻两项的差分数列，KMP判断短的差分数列在长的差分数列中出现几次即可，特判n=1和w=1的情况




#include 
  
   #include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #define Maxn 100005#define Maxm 1000005#define lowbit(x) x&(-x)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define PI acos(-1.0)#define make_pair MP#define LL long long #define Inf (1LL<<62)#define inf 0x3f3f3f3f#define re freopen("in.txt","r",stdin)#define wr freopen("out.txt","w",stdout)using namespace std;int next[Maxn<<1];void get_next(int *arr,int len){ int j=0,k=-1; next[0]=-1; while(j<=len) { if(k==-1||arr[j]==arr[k]) { j++;k++; next[j]=k; } else k=next[k]; }}int kmp(int *a,int *b,int l1,int l2){ get_next(a,l1); get_next(b,l2); int i=0,j=0,ans=0; while(i
                 
                  =1) ca[i-1]=a[i]-a[i-1]; } for(int i=0;i
                  
                   =1) cb[i-1]=b[i]-b[i-1]; } if(m==1||n==1) { printf("%d\n",max(m,n)); continue; } printf("%d\n",m>=n?kmp(ca,cb,m-1,n-1):kmp(cb,ca,n-1,m-1)); } return 0;}
企鹅博客
  • 本文由 发表于 2020年8月16日 21:38:27
  • 转载请务必保留本文链接：https://www.qieseo.com/371412.html

发表评论