咕咕咕了好多天终于有时间写篇博客了_(:з」∠)_
打网赛打到自闭的一周，终于靠这场CF找回了一点信心...
(ans=maxleft { a_i ight }-minleft { a_i ight }+1-n)
#include<bits/stdc++.h> using namespace std; #define N 1001 int n,a[N],mx,mi; int main() { mi=2147483647; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]), mx=max(mx,a[i]), mi=min(mi,a[i]); printf("%d ",mx-mi+1-n); return 0; }
设(d=gcd(x,y), X=frac{x}{d}, Y=frac{y}{d})，则(ans=min(frac{a}{X},frac{b}{Y}))
#include<bits/stdc++.h> using namespace std; #define LL long long LL a,b,x,y; LL gcd(LL x,LL y){return y?gcd(y,x%y):x;} int main() { scanf("%I64d%I64d%I64d%I64d",&a,&b,&x,&y); LL d=gcd(x,y);x/=d,y/=d;printf("%I64d ",min(a/x,b/y)); }
难点在于理解题意，题意大致就是把(n)分成(x)块，使得每块里的数两两相差大于(d)，求最小的(x)
直接排序之后莽就好了，贪心是能保证正确性的
#include<bits/stdc++.h> using namespace std; #define N 200001 #define mp make_pair struct rua{int v,id;}a[N]; set<pair<int,int> >s; int n,m,d,cnt,f[N]; bool cmp(rua x,rua y){return x.v<y.v;} int main() { scanf("%d%d%d",&n,&m,&d); for(int i=1;i<=n;i++) scanf("%d",&a[i].v),a[i].id=i; sort(a+1,a+n+1,cmp); s.insert(mp(a[1].v,1)),f[a[1].id]=++cnt; for(int i=2;i<=n;i++) { if((*s.begin()).first+d<a[i].v) f[a[i].id]=(*s.begin()).second,s.erase(s.begin()),s.insert(mp(a[i].v,f[a[i].id])); else s.insert(mp(a[i].v,++cnt)),f[a[i].id]=cnt; } printf("%d ",cnt); for(int i=1;i<=n;i++) printf("%d%c",f[i],i<n?' ':' '); }
显然在气流的开头跳是最优的，因此枚举在哪个气流的开头跳，二分求出能撑到第几个气流结束，通过预处理可以得到在一个区间内可以被抬多久，从而得出答案
#include<bits/stdc++.h> using namespace std; #define N 200001 int n,h,ans,s[N]; struct rua{int l,r;}a[N]; bool check(int st,int i,int j) { return h-(a[i].r-st)+(s[i]-s[j-1])>0; } int get(int st,int i) { int l=i,r=n; while(l<r) { int mid=l+r+1>>1; if(check(st,mid,i))l=mid; else r=mid-1; } return h+(s[l]-s[i-1]); } int main() { scanf("%d%d",&n,&h); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r),s[i]=s[i-1]+a[i].r-a[i].l; for(int i=1;i<=n;i++) ans=max(ans,get(a[i].l,i)); printf("%d ",ans); return 0; }
显然(n)这个数一定会出现(n-1)次，现在只需考虑其他数字的出现情况
考虑(n-1)这个数，它出现的次数是等于(n-1)所在点到(n)所在距离的，且在从(n)到(n-1)这条路径上出现的数字是不会在输入中出现的。若将剩余出现的数从大到小排序，则有 当前数字出现次数=当前数字所在点到已知路径的距离，这里的已知路径是指已加入点之间的路径。可以发现构造一条链是足以满足题意的，对于空出的点将数字从大到小依次填入，并判断合法性即可。
代码中(c_i)为数字(i)出现的次数，(p_i)为数字(i)在答案中的位置，(x_i)则代表第(i)个位置是否已经被使用
#include<bits/stdc++.h> using namespace std; #define N 1005 int n,a[N],b[N],l,j=1,c[N],p[N],ans[N],f[N],g[N]; bool x[N]; int main() { scanf("%d",&n),c[n]=p[n]=1,l=n,x[1]=true; for(int i=2;i<=n;i++) { scanf("%d%d",&a[i],&b[i]); if(a[i]<b[i])swap(a[i],b[i]); if(a[i]<n)return printf("NO "),0; c[b[i]]++; } for(int i=n-1;i>=1;i--)if(c[i]) p[i]=p[l]+c[i],l=i,x[p[i]]=true; for(int i=n;i>=1;i--)if(!c[i]) { while(j<=n && x[j])j++;p[i]=j,x[j]=true; } for(int i=1;i<=n;i++)ans[p[i]]=i; for(int i=1;i<=n;i++)f[i]=max(f[i-1],ans[i]); for(int i=n;i>=1;i--)g[i]=max(g[i+1],ans[i]); for(int i=1;i<n;i++) { int A=f[i],B=g[i+1],xx=0; for(int j=1;j<=n;j++) if(A==a[j] && B==b[j]) {a[j]=b[j]=0,xx=1;break;} if(!xx)return printf("NO "),0; } printf("YES "); for(int i=2;i<=n;i++)printf("%d %d ",ans[i-1],ans[i]); }
(y1)和(y2)是没用的，不用管它
由于(n)和(m)均大于等于1，因此答案至少为2，不少人因此FST
考虑射出去的线打到对面板上所需要走的距离(d)，假设出发点为0，则打在自己这边上的点的坐标为(left { 0,2d,4d,6d,8d,... ight })，打在对面板上的则是(left { d,3d,5d,7d,9d,... ight })。若将距离改为(kcdot d)，则两个点集分别为(left { 0,2kd,4kd,6kd,8kd,... ight })，(left { kd,3kd,5kd,7kd,9kd,... ight })，可以发现若(k)为奇数，两个集合中的点都只会减少不会增加，(k)为偶数时则有存在增减的情况，因此设(k=2^{l})一定是最优的
接下去就直接暴力开个map做就好了，比赛的时候害怕FST还加了个优化，就是当(k)比较小时直接从(0)到(k-1)枚举余数，(k)较大时才遍历(n+m)个坐标。后来发现这个优化只优化了100ms...
#include<bits/stdc++.h> using namespace std; #define N 100001 int n,m,y,a[N],b[N]; map<int,int>f,g; int main() { scanf("%d%d",&n,&y); for(int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d%d",&m,&y); for(int i=1;i<=m;i++) scanf("%d",&b[i]); int ans=2; for(int k=2;k;k*=2) { f.clear(),g.clear(); for(int i=1;i<=n;i++) f[a[i]%k]++; for(int i=1;i<=m;i++) g[b[i]%k]++; if(k<=131072) for(int i=0;i<k;i++) ans=max(ans,f[i]+g[(i+k/2)%k]); else { for(auto j:f)ans=max(ans,f[j.first]+g[(j.first+k/2)%k]); for(auto j:g)ans=max(ans,g[j.first]+f[(j.first+k/2)%k]); } if(k==1073741824) break; } printf("%d ",ans); return 0; }