Codeforces Educational round 58-白红宇

Codeforces Educational round 58

阅读量：6633 次

发布时间：2019-06-25

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

Ediv2 58

随手AK.jpg

D

裸的虚树，在这里就不写了

E

傻逼贪心？这个题过的比$B$都多.jpg

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 500005#define ll long longint n,now_mx,maxx;char s[10];int main(){ scanf("%d",&n); while(n--) { int x,y;scanf("%s%d%d",s+1,&x,&y); if(x
            
             =now_mx&&y>=maxx?"YES":"NO"); }}

F

似乎正解的那个单调队列做法没啥意思啊...

直接暴力二分+剪枝就好了...

然后其实能卡掉，但是懒得去卡了.jpg

然后卡一卡常数就好了.jpg

随便剪一剪枝前测就能过.jpg

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 405#define ll long longint a[N],n,m,s,t,f,c,l,r;ll ans;inline bool check(int x){ register int i,tc=c;register int now=x; for(i=s;i
            
             x)return 0; if(a[i+1]-a[i]>now) { if(!tc)return 0; tc--;now=x; } now-=a[i+1]-a[i]; }return 1;}int main(){ scanf("%d%d",&n,&m);l=0,r=1<<30; for(int i=1;i<=n;i++)scanf("%d",&a[i]); while(m--) { scanf("%d%d%d%d",&s,&t,&f,&c);if(s>t)swap(s,t); if(check(ans/f))continue; l=(ans/f)+1;r=a[t]-a[s]; while(l
             
              >1; if(check(mid))r=mid;else l=mid+1; }ans=max((ll)l*f,ans); } printf("%lld\n",ans);}

G

一个结论，能划分出的段数是线性基里的基的个数

证明嘛：

对于任意一个已经存在的基，都可以被一些数表达出来

然后就可以发现，不可能存在一个划分的段数比线性基里的基数更多（根据线性基的定义

然后就完了.jpg

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 200005#define ll long longint a[32],now;void insert(int x){ for(int i=30;~i;i--)if((x>>i)&1) if(a[i])x^=a[i]; else {a[i]=x;return ;}}int main(){ int n,x; scanf("%d",&n); while(n--)scanf("%d",&x),insert(x),now^=x; if(!now)return puts("-1"),0; x=0; for(int i=30;~i;i--)if(a[i])x++; printf("%d\n",x);}