Codeforces Round #470 Div. 1-白红宇

Codeforces Round #470 Div. 1

阅读量：5122 次

发布时间：2019-06-13

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

　　A：暴力枚举x₂的因子，由此暴力枚举x₁，显然此时减去其最大质因子并+1即为最小x₀。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long#define N 1000010char 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,p[N],prime[N],cnt,ans=N;bool flag[N];signed main(){#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout);#endif n=read(); flag[1]=1; for (int i=2;i<=1000000;i++) { if (!flag[i]) {prime[++cnt]=i;p[i]=i;} for (int j=1;j<=cnt&&prime[j]*i<=n;j++) { flag[prime[j]*i]=1; p[prime[j]*i]=p[i]; if (i%prime[j]==0) break; } } for (int i=1;i<=n;i++) if (n%i==0&&!flag[i]) { for (int x=n-i+1;x<=n;x++) if (flag[x]) ans=min(ans,x-p[x]+1); } cout<

　　B：小根堆维护每堆雪的体积，记录总偏移量，堆顶融化完就将其弹出。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
              using namespace std;#define ll long long#define int 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],b[N],cnt;priority_queue
             
              
               ,greater
               
                 > q;signed main(){#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout);#endif n=read(); for (int i=1;i<=n;i++) a[i]=read(); for (int i=1;i<=n;i++) b[i]=read(); ll delta=0; for (int i=1;i<=n;i++) { q.push(a[i]+delta);cnt++;ll ans=0; while (!q.empty()&&q.top()<=b[i]+delta) ans+=q.top()-delta,cnt--,q.pop(); ans+=1ll*b[i]*cnt;delta+=b[i]; printf("%I64d ",ans); } return 0; //NOTICE LONG LONG!!!!!}

　　C：建棵trie，维护子树内数的个数，暴力按位贪心即可。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
              using namespace std;#define ll long long#define N 300010char 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],b[N],trie[N<<5][2],size[N<<5],cnt;void ins(int x){ int k=0; for (int i=31;~i;i--) { if (!trie[k][(x&(1<
             
              0]) trie[k][(x&(1<
              
               0]=++cnt; k=trie[k][(x&(1<
               
                0]; size[k]++; }}signed main(){#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout);#endif n=read(); for (int i=1;i<=n;i++) a[i]=read(); for (int i=1;i<=n;i++) ins(read()); for (int i=1;i<=n;i++) { int k=0,x=0; for (int j=31;~j;j--) { if (a[i]&(1<

　　D：降智好题。首先发现BC可以相互转化，变换3次再删掉AAA即可。同时发现每次可以增加AA，由于可以删除AAA，也就是说可以任意增删AA。并且BC的数量不会减少且奇偶性不变。哇这个题好弱智！一发wa on 2。

　　冷静一下可以发现，当原串没有BC且目标串也没有BC时，我们是不能任意变换的，而只能删除AAA。于是特判一下这种情况。哇这个题好弱智！一发wa on 8。

　　再冷静一下发现，我们对A的增删事实上并不能在尾部进行。于是满足之前条件的同时，数一下原串尾部A的长度x和目标串尾部A的长度y。如果BC数量相同，只能通过删AAA来对尾部变换，于是判一下是否x%3==y%3&&x>=y；否则可以在任意位置截掉，只需要x>=y。

#include
     
       #include
      
       #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;}char a[N],b[N];int n,m,q,s1[N],s2[N];int query1(int x,int y){ int l=x,r=y+1,ans=y+1; while (l<=r) { int mid=l+r>>1; if (s1[mid]==s1[y]) ans=mid,r=mid-1; else l=mid+1; } return y-ans+1;}int query2(int x,int y){ int l=x,r=y+1,ans=y+1; while (l<=r) { int mid=l+r>>1; if (s2[mid]==s2[y]) ans=mid,r=mid-1; else l=mid+1; } return y-ans+1;}signed main(){#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout);#endif scanf("%s",a+1);n=strlen(a+1); scanf("%s",b+1);m=strlen(b+1); for (int i=1;i<=n;i++) s1[i]=s1[i-1]+(a[i]!='A'); for (int i=1;i<=m;i++) s2[i]=s2[i-1]+(b[i]!='A'); q=read(); while (q--) { int l1=read(),r1=read(),l2=read(),r2=read(); int x=s1[r1]-s1[l1-1],y=s2[r2]-s2[l2-1]; if (x|y) { int u=query1(l1,r1),v=query2(l2,r2); if (x==y) { if (u%3==v%3&&u>=v) putchar('1'); else putchar('0'); } else if (x>y) putchar('0'); else { if ((x&1)==(y&1)&&u>=v) putchar('1'); else putchar('0'); } } else { if ((r1-l1)%3==(r2-l2)%3&&(r1-l1>=r2-l2)) putchar('1'); else putchar('0'); } } return 0; //NOTICE LONG LONG!!!!!}

　　E怎么是这种不可能会的板子题啊

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

你可能感兴趣的文章