Educational Codeforces Round 18-白红宇

Educational Codeforces Round 18

阅读量：4322 次

发布时间：2019-06-06

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

来自FallDream的博客，未经允许，请勿转载，谢谢。

---------------------------------------------------------------------

A.New Bus Route

给定n个数，求最小的任意两个数的差的绝对值和最小值个数。$n\leqslant 2*10^{5}$

题解：排序完暴力。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define ll long long#define INF 2000000000using namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f;}int n,minn=INF,num=0;int s[200005];int main(){ n=read(); for(int i=1;i<=n;i++)s[i]=read(); sort(s+1,s+n+1); for(int i=2;i<=n;i++) { int x=s[i]-s[i-1]; if(x

B.Counting-out Rhyme

n个人围成环，每个人有一个数字，一开始从第一个人开始，数它的数字那么多个人，然后那个人离开，从它的下一个人继续...总共玩了k轮，你要输出离开的人的顺序。n,k<=100

题解：直接暴力就好了。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define ll long long#define INF 2000000000using namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f;}int n,k,pos=1;int nx[105],la[105];void del(int x){ la[nx[x]]=la[x]; nx[la[x]]=nx[x];}int main(){ n=read();k=read(); for(int i=1;i

C. Divide by Three

给定一个十进制数n，你要删去最少的位数使得剩下的数没有前导0且能被3整除。 $n\leqslant10^{100000}$

题解：可以从后往前贪心。但是我菜，所以我只会写dp

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define ll long long#define INF 1000000000#define MN 100000000using namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f;}int s[100005];int from1[100005][5],from2[100005][5];int f1[100005][5],n,f2[100005][5];char st[100005];int main(){ scanf("%s",st+1);n=strlen(st+1); for(int i=1;i<=n;i++) s[i]=(st[i]-'0')%3; memset(f1,127,sizeof(f1));memset(f2,127,sizeof(f2)); for(int i=n;i;i--) { f1[i][s[i]]=n-i; for(int j=0;j<=2;j++) { int nx=(j+3-s[i])%3; if(f1[i+1][nx]<=f1[i][j]){f1[i][j]=f1[i+1][nx];from1[i][j]=MN+(i+1)*10+nx;} if(f2[i+1][nx]<=f1[i][j]){f1[i][j]=f2[i+1][nx];from1[i][j]=(i+1)*10+nx;} if(f1[i+1][j]+1<=f2[i][j]){f2[i][j]=f1[i+1][j]+1;from2[i][j]=MN+(i+1)*10+j;} if(f2[i+1][j]+1<=f2[i][j]){f2[i][j]=f2[i+1][j]+1;from2[i][j]=(i+1)*10+j;} } } int ans=INF;int ansfrom; for(int i=1;i<=n;i++)if(st[i]!='0') if(f1[i][0]+i-1
            
             =INF) return 0*puts("-1"); for(int i=ansfrom;i;) { if(i>=MN)cout<

D.给定一个特殊编号方法的完全二叉树，然后给定初始位置和每次移动的方向，求最后在哪一个位置。

题解：直接找规律或者模拟一下线段树都可以。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define ll long long#define INF 1000000000#define MN 100000000using namespace std;inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f;}ll n;int q,d=0,dep;char s[100005];ll pd(ll x){ x+=(1LL<<(d-dep)); x/=(1LL<<(d-dep+1)); return (x&1LL)?-1:1;}int main(){ n=read();q=read(); for(ll i=n;i;i>>=1)d++; for(int i=1;i<=q;i++) { ll x=read();scanf("%s",s+1);dep=d; for(ll i=x;!(i&1);i>>=1) --dep; for(int i=1;s[i];i++) { if((s[i]=='L'||s[i]=='R')&&dep==d)continue; if(s[i]=='U'&&dep==1)continue; if(s[i]=='L')x-=(1LL<<(d-dep-1)); if(s[i]=='R')x+=(1LL<<(d-dep-1)); if(s[i]=='U')x-=pd(x)*(1LL<<(d-dep)); dep+=(s[i]!='U')?1:-1; } printf("%lld\n",x); }}

E.Colored Balls

给n堆球，可以把每一堆分成多堆，但是要求任意两个分成的堆的个数相差不超过1. $n\leqslant 500 bi \leqslant 10^{9}$

题解：考虑最小的堆分成多大，这个只有根号种可能，然后每次check一下，复杂度$n\sqrt max)$

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define ll long long#define INF 100000000000000LL#define ll long long#define MN 100000000using namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f;}int n,s[1005];ll ans=INF,size;ll mn=INF;void calc(int x){ if(!x) return ;size=0; for(int i=1;i<=n;i++) { int mod=s[i]%x,div=s[i]/x; if(mod>div)return; size+=(s[i]+x)/(x+1); } ans=min(ans,size);}int main(){ n=read(); for(int i=1;i<=n;i++)s[i]=read(),mn=min(mn,(ll)s[i]); for(int i=1,last;i<=mn;i=last+1) { last=mn/(mn/i);int ques=mn/i; calc(ques);calc(ques-1); //calc(ques+1); } cout<