A
签到，开long long（不开也pp不了）
#include<bits/stdc++.h> using namespace std; long long a,b,ans; int main() { cin>>a>>b>>ans;ans*=2; if(a==b)ans+=a*2; else ans+=min(a,b)*2+1; cout<<ans; }
B
two-pointer，注意特判n<=k||m<=k的情况，因为这个还WA了一发真是自闭（不然就翻掉Gaozijian了）
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+7; int n,m,k; ll ans,ta,tb,a[N],b[N]; int main() { scanf("%d%d%I64d%I64d%d",&n,&m,&ta,&tb,&k); for(int i=1;i<=n;i++)scanf("%I64d",&a[i]); for(int i=1;i<=m;i++)scanf("%I64d",&b[i]); if(n<=k||m<=k){puts("-1");return 0;} for(int i=0,p=0;i<=k;i++) { while(p<m&&a[i+1]+ta>b[p+1])p++; if(p+k-i>=m){puts("-1");return 0;} ans=max(ans,b[p+k-i+1]+tb); } cout<<ans; }
C
构造，发现每个位置总能和1/n中的一个位置交换，考虑前(i-1)个数已经排好序了，这时候考虑第i个数，记第i个数的位置为pos，当pos!=i时(pos=i直接跳过不管了)，有以下四种情况：1、2(pos-i)>=n，直接交换。2、2(n-pos)>=n，这个先交换pos和n，再交换i和n。3、2(i-1)>=n，这个依次交换(1,pos)、(1,i)、(1,pos)。4、其余的情况，这个依次交换(1,pos),(1,n),(i,n),(1,pos)。大力讨论一波即可。
#include<bits/stdc++.h> using namespace std; const int N=3e5+7; int n,pos,num,a[N],b[N],ax[N*5],ay[N*5]; void Swap(int x,int y) { ax[++num]=x,ay[num]=y; int p=a[x],q=a[y]; swap(a[x],a[y]); swap(b[p],b[q]); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[a[i]]=i; for(int i=1;i<=n;i++) if(b[i]!=i) { pos=b[i]; if(2*(b[i]-i)>=n)Swap(i,b[i]); else if(2*(n-b[i])>=n)Swap(pos,n),Swap(i,n); else if(2*(i-1)>=n)Swap(1,pos),Swap(1,i),Swap(1,pos); else Swap(1,pos),Swap(1,n),Swap(i,n),Swap(1,pos); } printf("%d ",num); for(int i=1;i<=num;i++)printf("%d %d ",ax[i],ay[i]); }
D
签到，排序。
#include<bits/stdc++.h> using namespace std; const int N=3e5+7; struct node{int a,b,id;}a[N],b[N]; int n,n1,n2,ans,an[N]; bool cmp(node a,node b){return a.b<b.b;} int main() { scanf("%d",&n); for(int i=1,x,y;i<=n;i++) { scanf("%d%d",&x,&y); if(x<y)a[++n1]=(node){x,y,i}; else b[++n2]=(node){x,y,i}; } if(n1>=n2) { sort(a+1,a+n1+1,cmp); printf("%d ",n1); for(int i=n1;i;i--)printf("%d ",a[i].id); } else{ sort(b+1,b+n2+1,cmp); printf("%d ",n2); for(int i=1;i<=n2;i++)printf("%d ",b[i].id); } }
E
首先若位置坐标和不同直接puts("NO")。然后先找到每个石子的相对位置，理性分析一波发现能够不改变相对位置交换，否则就无解。具体的就是把石子分成向右移动和向左移动两种，记录距离，然后直接前面和前面匹配，后面和后面匹配，直接模拟这个过程，发现位置上会发生交叉也是puts("NO")。
#include<bits/stdc++.h> using namespace std; const int N=3e5+7; typedef long long ll; struct node{ll d;int id;}a[N],a1[N],a2[N]; int n,n1,n2,num,ai[N*5],aj[N*5]; ll s1,s2,b[N],ad[N*5]; bool cmp(node a,node b){return a.d<b.d;} int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%I64d",&a[i].d),s1+=a[i].d,a[i].id=i; for(int i=1;i<=n;i++)scanf("%I64d",&b[i]),s2+=b[i]; if(s1!=s2){puts("NO");return 0;} sort(a+1,a+n+1,cmp); sort(b+1,b+n+1); for(int i=1;i<=n;i++) if(a[i].d<b[i])a1[++n1]=(node){b[i]-a[i].d,i}; else if(a[i].d>b[i])a2[++n2]=(node){a[i].d-b[i],i}; for(int i=1,j=1;i<=n1;i++) { ll res=a1[i].d; while(res) { if(a1[i].id>a2[j].id){puts("NO");return 0;} if(res<a2[j].d)ai[++num]=a[a1[i].id].id,aj[num]=a[a2[j].id].id,ad[num]=res,a2[j].d-=res,res=0; else ai[++num]=a[a1[i].id].id,aj[num]=a[a2[j].id].id,ad[num]=a2[j].d,res-=a2[j].d,j++; } } puts("YES"); printf("%d ",num); for(int i=1;i<=num;i++)printf("%d %d %I64d ",ai[i],aj[i],ad[i]); }
F
听说随机能过？后来又说随机基本都FST了。看到了一种非随机的解法：每个数先按照最低的非零位排序，然后按位处理，对于每一位，仅考虑当前位选0/1造成的影响，选择偏小的那种即可。
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll>pii; int n; ll sum,ans; vector<pii>a[80]; int getbit(ll x) { int ret=0; while(x) { if(x&1)return ret; ret++,x>>=1; } } int count(ll x) { int ret=0; while(x)ret+=x&1,x>>=1; return ret; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { ll v,x;cin>>v>>x,sum+=v; a[getbit(x)].push_back(pii(v,x)); } for(int i=62;~i;i--) if(a[i].size()) { ll s0=0,s1=0; for(int j=0;j<a[i].size();j++) if(count(a[i][j].second&ans)&1)s1+=a[i][j].first; else s0+=a[i][j].first; if(sum>0&&s0>s1||sum<0&&s0<s1)ans+=1ll<<i; } cout<<ans; }
GH
不会，告辞。
result：终于用大号lintoto打了，rank97，rating+=113，now_rating=2267，超了小号hfctf0210的2210（大号的原来的max_rating也是2210）啦！div1+2终于进前100啦！不过这次是由于E和F FST了一大片（不过本身F放随机过也实在是不合理）才涨了这么多rating，不过感觉这场把签到题都切了怎么都能涨吧。立个flag AFO前其中一个号rating上2300
吐槽一下不知道为啥cf C和E全部给5n，C只要4n就行，E只要n就行，4n+n=5n刚好用一半2333，什么垃圾构造题。
好像还抽到T-shirt了？