Educational Codeforces Round 58 Div. 2 自闭记-白红宇

Educational Codeforces Round 58 Div. 2 自闭记

阅读量：5271 次

发布时间：2019-06-14

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

　　明明多个几秒就能场上AK了。自闭。

　　A：签到。

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define ll long longchar getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int T,l,r,d;signed main(){/*#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout); const char LL[]="%I64d\n";#endif*/ T=read(); while (T--) { l=read(),r=read(),d=read(); if (d

View Code

　　B：签到。

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define ll long long#define N 500010char getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n;char s[N];signed main(){/*#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout); const char LL[]="%I64d\n";#endif*/ scanf("%s",s+1);n=strlen(s+1); bool flag=0;int x=n+1,y=0; for (int i=1;i<=n;i++) { if (s[i]=='[') flag=1; if (s[i]==':') if (flag) {x=i;break;} } flag=0; for (int i=n;i>=1;i--) { if (s[i]==']') flag=1; if (s[i]==':') if (flag) {y=i;break;} } if (x>=y) cout<<-1; else { int ans=4; for (int i=x+1;i

View Code

　　C：wa了无数发。按左端点排序后找一个连续且和其他线段不相交的线段集即可。

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define ll long long#define N 100010char getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int T,n,ans[N];struct data{ int l,r,i; bool operator <(const data&a) const { return l

View Code

　　E：这才是真签到吧？wa了一发自闭啊？

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define ll long long#define N 500010char getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int m,u,v;signed main(){#ifndef ONLINE_JUDGE freopen("b.in","r",stdin); freopen("b.out","w",stdout); const char LL[]="%I64d\n";#endif m=read(); while (m--) { char c=getchar();while (c!='+'&&c!='?') c=getchar(); int x=read(),y=read();if (x>y) swap(x,y); if (c=='+') { u=max(u,x),v=max(y,v); } else { if (x>=u&&y>=v) printf("YES\n"); else printf("NO\n"); } } return 0; //NOTICE LONG LONG!!!!!}

View Code

　　D：如果路径经过某点，最后所得的路径gcd显然是该点某些质因子的倍数。对此dp即可。一发wa on 3，3可是样例啊？自闭了啊？

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define ll long long#define N 200010char getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,a[N],p[N],f[N][30],prime[N][30],t,ans;struct data{ int to,nxt;}edge[N<<1];void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}void dfs(int k,int from){ for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=from) { dfs(edge[i].to,k); for (int x=1;x<=prime[edge[i].to][0];x++) for (int y=1;y<=prime[k][0];y++) if (prime[edge[i].to][x]==prime[k][y]) { ans=max(ans,f[k][y]+f[edge[i].to][x]+1); f[k][y]=max(f[k][y],f[edge[i].to][x]+1); } }}signed main(){#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout); const char LL[]="%I64d\n";#endif n=read(); for (int i=1;i<=n;i++) a[i]=read(); bool flag=1; for (int i=1;i<=n;i++) if (a[i]!=1) flag=0; if (flag) {cout<<0;return 0;} for (int i=1;i
            
             1) prime[i][++prime[i][0]]=a[i]; } dfs(1,1); cout<

View Code

　　G：一眼线性基，然后就往别的方面想了。自闭了半天直接乱搞求个前缀异或和搞了个线性基上去就pp了。冷静了半天正确性何在。事实上划分序列相当于选出一些前缀异或和，这是一个裸到不行的线性基。注意虽然最后一个前缀和应该是必须选的，但是不考虑也不会造成什么影响（吧）。

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define ll long long#define N 200010char getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,a[N],base[32],ans;signed main(){#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout); const char LL[]="%I64d\n";#endif n=read(); for (int i=1;i<=n;i++) a[i]=a[i-1]^read(); if (a[n]==0) {cout<<-1;return 0;} for (int i=1;i<=n;i++) for (int j=30;~j;j--) if (a[i]&(1<

View Code

　　F：随便都知道是二分答案。但是nmlog显然有些吃力。考虑random_shuffle一发，每次记录当前需要的最大容量，考虑下一辆卡车时先判断当前容量是否能满足其需求，如果不行再二分一下。这样复杂度大约是nm+nlogmlogV，因为只需要对所需容量的单调栈中的卡车进行二分，而排列又是随机的。复杂度证明似乎在一篇cfblog里看到过。（突然发现整个idea都在这篇blog里https://codeforces.com/blog/entry/62602）一开始又没注意到要开long long，交一发in queue了半天，然后wa on 3，结果改了一发又没改全，交一发再次in queue了半天，接着wa on 3。然后就只剩20s了，手速不行，就，自闭了。

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;#define ll long long#define N 410#define M 250010char getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,m,a[N];ll ans;struct data{ int s,f,c,r;}b[M];bool check(ll k,int i){ ll cur=k;int cnt=0; for (int j=b[i].s;j
             
              =1ll*b[i].c*(a[j+1]-a[j])) cur-=1ll*b[i].c*(a[j+1]-a[j]); else { cur=k,cnt++; if (cur>=1ll*b[i].c*(a[j+1]-a[j])) cur-=1ll*b[i].c*(a[j+1]-a[j]); else return 0; } if (cnt>b[i].r) return 0; } return 1;}signed main(){#ifndef ONLINE_JUDGE freopen("b.in","r",stdin); freopen("b.out","w",stdout); const char LL[]="%I64d\n";#endif srand(time(0)); n=read(),m=read(); for (int i=1;i<=n;i++) a[i]=read(); for (int i=1;i<=m;i++) b[i].s=read(),b[i].f=read(),b[i].c=read(),b[i].r=read(); random_shuffle(b+1,b+m+1); for (int i=1;i<=m;i++) if (!check(ans,i)) { ll l=ans+1,r=1000000000000000000ll; while (l<=r) { ll mid=l+r>>1; if (check(mid,i)) ans=mid,r=mid-1; else l=mid+1; } } cout<

View Code

转载于:https://www.cnblogs.com/Gloid/p/10258416.html

你可能感兴趣的文章