A. New Bus Route
题目大意：给出n个不同的数，问差值最小的数有几对。（n<=200,000）
思路：排序一下，差值最小的一定是相邻的，直接统计即可。
#include<cstdio> #include<algorithm> using namespace std; char B[1<<26],*S=B,C;int X,F; inline int read() { for(F=1;(C=*S++)<'0'||C>'9';)if(C=='-')F=-1; for(X=C-'0';(C=*S++)>='0'&&C<='9';)X=(X<<3)+(X<<1)+C-'0'; return X*F; } #define MN 200000 int a[MN+5]; int main() { fread(B,1,1<<26,stdin); int n=read(),i,mn=0x7FFFFFFF,cnt=0; for(i=1;i<=n;++i)a[i]=read(); sort(a+1,a+n+1); for(i=1;i<n;++i) { a[i]=a[i+1]-a[i]; if(a[i]<mn)mn=a[i],cnt=0; if(a[i]==mn)++cnt; } printf("%d %d",mn,cnt); }
B. Counting-out Rhyme
题目大意：n个人站成一圈，一开始第1个人是首领，k次操作，每次首领向后数ai个人让那个人滚蛋并使这个人的后一个人变成首领，求每次谁滚蛋了。（1<=k<n<=100，ai<=10^9）
思路：ai对当前剩余人数取模后模拟。
#include<cstdio> char B[1<<26],*S=B,C;int X; inline int read() { while((C=*S++)<'0'||C>'9'); for(X=C-'0';(C=*S++)>='0'&&C<='9';)X=(X<<3)+(X<<1)+C-'0'; return X; } #define MN 100 int u[MN+5]; int main() { fread(B,1,1<<26,stdin); int n,k,i,x,s=0; n=read();k=read(); for(i=0;i<k;++i) { for(x=read()%(n-i)+1;x--;)while(u[++s>n?s=1:s]); u[s]=1;printf("%d ",s); } }
C. Divide by Three
题目大意：给定一个长度为n的数字串，求一个最长的子序列满足没有前导0且是3的倍数。（n<=100,000）
思路：上过小学的都知道3的倍数各位数字和也是3的倍数。从后往前枚举哪个数字作为最后子序列的第一位数字，求出这个后缀各位之和模3的值，还有这一位后面有几个模3等1和模3等2的数，分情况判断即可。
#include<cstdio> #include<cstring> #define MN 100000 char s[MN+5]; int main() { int n,i,f=0,f1=0,f2=0,ans=-1,p,pf1,pf2; scanf("%s",s+1);n=strlen(s+1); for(i=n;i;--i) { f=(f+(s[i]-='0'))%3; if(s[i]) { if(!f&&(ans<0||i<=ans))ans=i-1,p=i,pf1=pf2=0; if(f==1&&f1&&(ans<0||i<ans))ans=p=i,pf1=1,pf2=0; if(f==1&&f2>1&&(ans<0||i+1<ans))ans=i+1,p=i,pf1=0,pf2=2; if(f==2&&f2&&(ans<0||i<ans))ans=p=i,pf1=0,pf2=1; if(f==2&&f1>1&&(ans<0||i+1<ans))ans=i+1,p=i,pf1=2,pf2=0; } else if(ans<0)ans=-2; if(s[i]%3==1)++f1; if(s[i]%3==2)++f2; } if(ans<-1)return 0*puts("0"); if(ans<0)return 0*puts("-1"); for(printf("%d",s[i=p]);++i<=n;) if(s[i]%3==1&&pf1)--pf1; else if(s[i]%3==2&&pf2)--pf2; else printf("%d",s[i]); }
D. Paths in a Complete Binary Tree
题目大意：有一棵n个节点的满二叉树，节点标号为中序遍历，每次询问一个点，经过一串操作后在哪个点，操作有U,L,R，分别为走向父亲和左右儿子。（n<=10^18，操作总长<=10^5）
思路：我觉得转成先序遍历后再转回来比较直观，具体实现看下面的代码。
#include<cstdio> #include<iostream> using namespace std; #define ll long long #define MN 100000 char s[MN+5]; ll find(ll x,ll n,ll k) { n>>=1; if(k<=n)return find(x<<1,n,k); if(k-=n+1)return find(x<<1|1,n,k); return x; } ll query(ll x,ll n) { int cnt=0,a[100];ll ans=0; while(x>1)a[cnt++]=x&1,x>>=1; while(cnt--){n>>=1;if(a[cnt])ans+=n+1;} return ans+1+(n>>1); } int main() { ll n,x;int q,i; cin>>n>>q; while(q--) { cin>>x;scanf("%s",s); x=find(1,n,x); for(i=0;s[i];++i) { if(s[i]=='U'&&x>1)x>>=1; if(s[i]=='L'&&x<<1<n)x<<=1; if(s[i]=='R'&&x<<1<n)x=x<<1|1; } cout<<query(x,n)<<endl; } }
E. Colored Balls
题目大意：给出n个数ai，问把这些数字拆成若干个相差不超过1的数字最少拆几个。（n<=500，ai<=10^9）
思路：设最后全部拆成x和x-1，对于每个ai，符合条件的x满足x能整除ai或ai/x不小于x-1-ai%x，而对于每个ai，合法的x只有O(ai^0.5)种，枚举x<=ai^0.5，暴力check x,ai/x,ai/x-1,ai/x+1即可。复杂度O(n*ai^0.5)。
#include<cstdio> #include<algorithm> using namespace std; #define MN 500 int n,a[MN+5]; long long ans=1LL<<60; void cal(int x) { if(!x)return; long long sum=0; for(int i=1;i<=n;++i) { if(a[i]%x==0||(a[i]/x>=x-1-a[i]%x))sum+=a[i]/x+bool(a[i]%x); else return; } ans=min(ans,sum); } int main() { int i; scanf("%d",&n); for(i=1;i<=n;++i)scanf("%d",&a[i]); for(i=1;i*i<=a[1];++i)cal(i),cal(a[1]/i),cal(a[1]/i-1),cal(a[1]/i+1); printf("%I64d",ans); }