qwq 怎么就17了
A.
对于待操作数列，所有的两个操作在宏观似乎都不会改变大体顺序
（至于操作2交换奇偶位数字：奇偶分离就行了）
那么定义 s1 s2 分别为奇数列和偶数列的起点（奇数和偶数自己是不会改变相对位置的）
让 s1 s2 储存每次操作一的偏移量
最后构造数列
1 #include2 #include 3 #define maxn 1000000 4 using namespace std; 5 6 int ans[maxn],s1,s2,n,m,cnt,cnt2; 7 8 int main(){ 9 scanf("%d%d",&n,&m);10 11 s1 = 1,s2 = 2;12 13 for(int i = 1;i <= m;i++){14 scanf("%d",&cnt);15 16 if(cnt%2){17 scanf("%d",&cnt2);18 s1 += cnt2;19 s2 += cnt2;20 if(s1 <= 0) s1 += n;21 if(s1 > n) s1 -= n;22 if(s2 <= 0) s2 += n;23 if(s2 > n) s2 -= n;24 }else{25 if(s1 % 2) s1++;26 else s1--;27 if(s2 % 2) s2++;28 else s2--;29 }30 }31 32 int i = s1,cnt = 1;33 while(!(i == s1 && cnt != 1)){34 ans[i] = cnt;35 i += 2;36 cnt += 2;37 if(i > n) i -= n;38 }39 40 i = s2,cnt = 2;41 while(!(i == s2 && cnt != 2)){42 ans[i] = cnt;43 i += 2;44 cnt += 2;45 if(i > n) i -= n;46 }47 48 for(int i = 1;i <= n;i++){49 printf("%d ",ans[i]);50 }51 52 return 0;53 }
B.
看了看CF的官方Editorial，二分原来是叫 Binary Search，学习了
那么，二分k秒后的最小值和k秒后的最大值
为了防止不会漏解把二分最大值嵌在二分最小值里
qwq感谢CZL的标程，写得非常对称！
1 #include2 #include 3 #define maxn 1000000 4 using namespace std; 5 6 long long k,lowpool,uppool,cnt1,n,arr[maxn],maxx,minn = 0x3f3f3f3f,L,R,L2,R2,mid,ans = 0x3f3f3f3f; 7 bool GG,GG2; 8 9 int main(){10 scanf("%I64d%I64d",&n,&k);11 for(int i = 1;i <= n;i++){12 scanf("%I64d",&arr[i]);13 maxx = max(maxx,arr[i]),14 minn = min(minn,arr[i]);15 }16 17 L = minn,R = maxx;18 GG = false;19 while(!GG){20 mid = (L+R+1)/2;21 if(L == R) GG = true;22 lowpool = uppool = cnt1 = 0;23 24 for(int i = 1;i <= n;i++) lowpool += max(0,mid-arr[i]),uppool += max(0,arr[i]-mid),cnt1 += arr[i]<=mid;25 26 if(lowpool > k || lowpool >uppool){ R = mid-1; continue;}27 else L = mid;28 29 if(lowpool == uppool && lowpool <= k) return puts("0"),0;30 31 L2 = mid+1,R2 = maxx;32 33 cnt1 = min(k,cnt1-1+lowpool);34 35 GG2 = false;36 while(!GG2){37 mid = (L2+R2)/2;38 if(L2 == R2) GG2 = true;39 40 uppool = 0;41 for(int i = 1;i <= n;i++) uppool += max(arr[i]-mid,0);42 43 if(uppool > cnt1 || uppool > k){L2 = mid+1;continue;}44 else R2 = mid;45 46 ans = min(ans,mid-L);47 }48 }49 50 printf("%I64d",ans);51 52 return 0;53 }
C.
只限定了树的直径和树的高
那就简单了，最低限度满足条件即可
首先画一条长度为D的多段线，那么一个典型的情况是：树根 1 在中点，将该多段线打折则每边的长度为 D/2
这是临界点，此时树高为 H
那么我们就知道了：如果 H * 2 < D 则必然无解（怎么打折都会有一边超过预测 H ）
那么我们只要在多段线上取一个点定为 1 就行了，接下来就是处理多余的结点（D+1 ~ n ）
（解释起来真复杂）
最简单的方法就是把多余节点一个个挂在深度第二的点当子节点
（有那么点画同分异构体的感觉）
既然这题的限制如此之少，又没有什么保证 既然这题出自CF
就要往死里加特判，不要太相信自己程序的通用度
特判见代码
1 #include2 #include 3 using namespace std; 4 5 int n,D,H,pre[1000000]; 6 7 int main(){ 8 scanf("%d%d%d",&n,&D,&H); 9 10 if(H*2 < D || H > D || D == 1 || n-1 < D || n-1 < H) cout << -1;11 else{12 if(H < D){13 14 for(int i = 2;i <= H+1;i++){15 pre[i] = i-1;16 }17 18 pre[H+2] = 1;19 for(int i = H+3;i <= D+1;i++){20 pre[i] = i-1;21 }22 23 for(int i = 2;i <= n;i++){24 if(!pre[i]) pre[i] = H;25 }26 27 }else{28 29 for(int i = 2;i <= H+1;i++){30 pre[i] = i-1;31 }32 33 for(int i = 2;i <= n;i++){34 if(!pre[i]) pre[i] = H;35 }36 37 }38 for(int i = 2;i <= n;i++)39 printf("%d %d\n",pre[i],i);40 }41 42 43 44 return 0;45 }