虽然说好像没有什么写这个的价值OAO
来了来了来写总结了，不能怨任何东西，就是自己垃圾x
开题顺序又和主流背道而驰，先一头扎进了公认最迷的T2，瞎搞两个小时头铁出来，然后T1和T3爆炸。基础很差，全靠瞎蒙，能力不足，不如滚蛋。
T1：D
发现对于一个长为n的序列，从右端点开始往回和前面的数依次求gcd最多不超过logn个，原因是每次的gcd若缩小则一定除以2。那么从前往后传递gcd，需要维护的gcd也不超过logn个。
于是从1~n枚举序列右端点，每一次把当前存在的gcd分别和新的右端点求gcd，用map映射存下这个gcd当前存在的这段序列中它的最小左端点，尝试更新答案。
不要忘了记录当前的右端点x
时间复杂度是O（nlog2n），当然有标准的O（nlogn）做法啦，但我懒嘛。
代码：
#include<iostream> #include<cstdio> #include<map> using namespace std; int n; long long a[100010]; map<long long,int>mp,m; map<long long,int>::iterator it; long long ans; long long GCD(long long a,long long b){ return !b?a:GCD(b,a%b); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); ans=max(ans,a[i]); for(it=m.begin();it!=m.end();it++){ long long gcd=GCD(a[i],it->first); if(gcd*(i-it->second+1)>ans)ans=gcd*(i-it->second+1); if(!mp.count(gcd))mp[gcd]=it->second; else mp[gcd]=min(mp[gcd],it->second); } if(!mp.count(a[i]))mp[a[i]]=i; m=mp; mp.clear(); } printf("%lld",ans); return 0; }
总之稍微记一下定义迭代器以及gcd不超过logn个的定理…
T2：E
说得简单一点，考虑两种情况。一种是最大最小两个球同色，另一种是异色。
异色的话假设最大值蓝色，最小值红色，那么要让两边的差都尽量小，直接把每一组的大值染蓝小值染红就OK了。
同色要麻烦一些，把各个组按小值从小到大排序，然后依次把同一组大小值反色，更新答案。假设最大值最小值都是蓝色，这样依次操作的时候红球的最大最小值是不降的，而翻转以后上一组最大最小值已经计算过了，不影响答案。这样解释有点玄学，但是自己举了几组例子好像没有反例，就试着写了一下，居然过了……
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int n; long long rmin=1e18,rmax,bmin=1e18,bmax,r,b; long long ans=1e18,minn=1e18,maxx,posmin,posmax; struct node{ long long a,b; }x[200010]; bool cmp(node a,node b){ if(a.a==b.a)return a.b<b.b; else return a.a<b.a; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%lld%lld",&x[i].a,&x[i].b); if(x[i].a>x[i].b)swap(x[i].a,x[i].b); rmin=min(x[i].a,rmin); rmax=max(x[i].a,rmax); bmin=min(x[i].b,bmin); bmax=max(x[i].b,bmax); if(x[i].a<minn){ minn=x[i].a; posmin=i; } if(x[i].b>maxx){ maxx=x[i].b; posmax=i; } } ans=(rmax-rmin)*(bmax-bmin); if(posmin==posmax)printf("%lld",ans); else{ sort(x+1,x+n+1,cmp); bmin=minn,bmax=maxx; rmax=max(x[n].a,x[1].b); minn=x[1].b; rmin=min(x[1].b,x[2].a); long long ans1=rmax-rmin; for(int i=2;i<n;i++){ rmax=max(rmax,x[i].b); rmin=min(min(x[i].b,x[i+1].a),minn); minn=min(minn,x[i].b); ans1=min(ans1,rmax-rmin); } ans=min(ans,ans1*(bmax-bmin)); printf("%lld",ans); } return 0; }
T3：F
你好，线段树优化DP，下一个。
说实话我连简单的三十分DP都没想出来，我大约是个睿智。不我应该自信地拿掉大约这两个字，毕竟你看垃圾就是垃圾，没什么好说的。
写出简单的转移式，f（i，j）中i为当前操作到第i个其中一个指针在pi，j为另一个指针在j处。
f（i，j）=f（i-1，j）+|pi-pi-1|，假如从上一个pi转移过来
f（i，pi-1）=f（i-1，j）+|pi-j|，假如从上一个j转移过来。
然后发现可以用线段树来维护，第一个转移式就是区间加，第二个转移式要维护最小fj-j和fj+j值，每次拆开绝对值根据正负查询。
注意开头的时候要先把a、b两处的f值维护成“第一个操作从b转移来”和“第一个操作从a转移来”，然后从第二次操作开始。因为对于p1来说，上一次移动的位置可以是aa也可以是bb。不写明白这个居然还有八十分:D
#include<iostream> #include<cstdio> #include<cmath> using namespace std; long long inf=1e18; int n,q,aa,bb,lst; struct node{ int l,r; long long min1,min2,f,add; }a[400010]; void build(int p,int l,int r){ a[p].l=l,a[p].r=r; a[p].f=a[p].min1=a[p].min2=inf; if(l==r)return; int mid=(l+r)/2; build(p*2,l,mid); build(p*2+1,mid+1,r); } void update(int p){ if(a[p].add){ a[p*2].add+=a[p].add; a[p*2+1].add+=a[p].add; a[p*2].min1+=a[p].add; a[p*2+1].min1+=a[p].add; a[p*2].min2+=a[p].add; a[p*2+1].min2+=a[p].add; a[p*2].f+=a[p].add; a[p*2+1].f+=a[p].add; a[p].add=0; } } void change(int p,int l,int r,long long val){ if(l<=a[p].l&&a[p].r<=r){ a[p].f=min(a[p].f,val); a[p].min1=a[p].f-l; a[p].min2=a[p].f+l; return; } update(p); int mid=(a[p].l+a[p].r)/2; if(l<=mid)change(p*2,l,r,val); if(r>mid)change(p*2+1,l,r,val); a[p].min1=min(a[p*2].min1,a[p*2+1].min1); a[p].min2=min(a[p*2].min2,a[p*2+1].min2); a[p].f=min(a[p*2].f,a[p*2+1].f); } void change1(int p,int l,int r,long long val){ if(l<=a[p].l&&a[p].r<=r){ a[p].add+=val; a[p].min1+=val; a[p].min2+=val; a[p].f+=val; return; } update(p); int mid=(a[p].l+a[p].r)/2; if(l<=mid)change1(p*2,l,r,val); if(r>mid)change1(p*2+1,l,r,val); a[p].min1=min(a[p*2].min1,a[p*2+1].min1); a[p].min2=min(a[p*2].min2,a[p*2+1].min2); a[p].f=min(a[p*2].f,a[p*2+1].f); } long long query1(int p,int l,int r){ if(l<=a[p].l&&a[p].r<=r){ return a[p].min1; } update(p); int mid=(a[p].l+a[p].r)/2; long long val=inf; if(l<=mid)val=min(val,query1(p*2,l,r)); if(r>mid)val=min(val,query1(p*2+1,l,r)); a[p].min1=min(a[p*2].min1,a[p*2+1].min1); a[p].min2=min(a[p*2].min2,a[p*2+1].min2); a[p].f=min(a[p*2].f,a[p*2+1].f); return val; } long long query2(int p,int l,int r){ if(l<=a[p].l&&a[p].r<=r){ return a[p].min2; } update(p); int mid=(a[p].l+a[p].r)/2; long long val=inf; if(l<=mid)val=min(val,query2(p*2,l,r)); if(r>mid)val=min(val,query2(p*2+1,l,r)); a[p].min1=min(a[p*2].min1,a[p*2+1].min1); a[p].min2=min(a[p*2].min2,a[p*2+1].min2); a[p].f=min(a[p*2].f,a[p*2+1].f); return val; } long long query(int p,int l,int r){ if(l<=a[p].l&&a[p].r<=r){ return a[p].f; } update(p); int mid=(a[p].l+a[p].r)/2; long long val=inf; if(l<=mid)val=min(val,query(p*2,l,r)); if(r>mid)val=min(val,query(p*2+1,l,r)); a[p].min1=min(a[p*2].min1,a[p*2+1].min1); a[p].min2=min(a[p*2].min2,a[p*2+1].min2); a[p].f=min(a[p*2].f,a[p*2+1].f); return val; } int main() { scanf("%d%d%d%d",&n,&q,&aa,&bb); build(1,1,n); scanf("%d",&lst); change(1,aa,aa,abs(lst-bb)); change(1,bb,bb,abs(lst-aa)); for(int i=2,x;i<=q;i++){ scanf("%d",&x); long long num1=query1(1,1,x); long long num2=query2(1,x,n); long long num=min(num1+x,num2-x); change1(1,1,n,(long long)abs(x-lst)); change(1,lst,lst,num); lst=x; } printf("%lld",query(1,1,n)); return 0; }
晚上好，今天墨雨笙小朋友复习了一个重要的道理，叫作垃圾就是垃圾。这没什么问题，毕竟你就是差劲呀:D
渣滓稍微活一活就知足吧