首页 > 代码库 > Educational Codeforces Round 18
Educational Codeforces Round 18
来自FallDream的博客，未经允许，请勿转载，谢谢。
---------------------------------------------------------------------
A.New Bus Route
给定n个数，求最小的任意两个数的差的绝对值和最小值个数。$n\leqslant 2*10^{5}$
题解：排序完暴力。
#include<iostream> #include<cstdio> #include<cmath> #include<queue> #include<cstring> #include<queue> #include<algorithm> #define ll long long #define INF 2000000000 using 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<minn){minn=x;num=1;} else if(x==minn)num++; } cout<<minn<<endl<<num; return 0; }
B.Counting-out Rhyme
n个人围成环，每个人有一个数字，一开始从第一个人开始，数它的数字那么多个人，然后那个人离开，从它的下一个人继续...总共玩了k轮，你要输出离开的人的顺序。n,k<=100
题解：直接暴力就好了。
#include<iostream> #include<cstdio> #include<cmath> #include<queue> #include<cstring> #include<queue> #include<algorithm> #define ll long long #define INF 2000000000 using 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<n;i++)la[i+1]=i,nx[i]=i+1; la[1]=n;nx[n]=1; for(int i=1;i<=k;i++) { int a=read()%n; for(int j=1;j<=a;j++) pos=nx[pos]; printf("%d\n",pos); pos=nx[pos];del(la[pos]);--n; } return 0; }
C. Divide by Three
给定一个十进制数n，你要删去最少的位数使得剩下的数没有前导0且能被3整除。 $n\leqslant10^{100000}$
题解：可以从后往前贪心。但是我菜，所以我只会写dp
#include<iostream> #include<cstdio> #include<cmath> #include<queue> #include<cstring> #include<queue> #include<algorithm> #define ll long long #define INF 1000000000 #define MN 100000000 using 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<ans){ans=f1[i][0];ansfrom=MN+i*10;}for(int i=1;i<=n;i++)if(st[i]==‘0‘) { if(n-1<ans)return 0*puts("0"); break; } if(ans>=INF) return 0*puts("-1"); for(int i=ansfrom;i;) { if(i>=MN)cout<<st[i%MN/10],i=from1[i%MN/10][i%10]; else i=from2[i/10][i%10]; } return 0; }
D.给定一个特殊编号方法的完全二叉树，然后给定初始位置和每次移动的方向，求最后在哪一个位置。
题解：直接找规律或者模拟一下线段树都可以。
#include<iostream> #include<cstdio> #include<cmath> #include<queue> #include<cstring> #include<queue> #include<algorithm> #define ll long long #define INF 1000000000 #define MN 100000000 using 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<iostream> #include<cstdio> #include<cmath> #include<queue> #include<cstring> #include<queue> #include<algorithm> #define ll long long #define INF 100000000000000LL #define ll long long #define MN 100000000 using 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<<ans; return 0; }
Educational Codeforces Round 18
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。