solved：3/13
rank：
B.Random Nim Game
题意：两个人玩Nim游戏取石子，但是每次选择石子都是随机的，问最后先手获胜的概率；
瞎写了几组样例算出来都是1/2，遂大胆猜想：除了每堆石子都只有一个时按石子堆数的奇偶判断先手获胜的概率是1还是0，其余情况先手获胜概率都是1/2；
根据题解所说，可以用归纳证明的方法解决n=1的情况，n=1时，只要a1!=1结果都是1/2；且操作每一堆石子获胜的概率都是1/2，故先手获胜概率与选择的石子堆无关；
1 #include<bits/stdc++.h>
2 using namespace std;
3 int read(){
4 char ch=getchar();int x=0,f=1;
5 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
6 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
7 return x*f;
8 }
9 int T,N;
10 int main(){
11 T=read();
12 while(T--){
13 N=read();
14 int f=0;
15 for(int i=1;i<=N;i++){
16 int a=read();
17 if(a!=1)f=1;
18 }
19 if(f==0){
20 if(N%2==0){
21 cout<<"0"<<endl;continue;
22 }
23 if(N%2==1){
24 cout<<"1"<<endl;continue;
25 }
26 }
27 cout<<"499122177"<<endl;continue;
28 }
29 return 0;
30 }
D.Median Strike Back
题意：定义median，shikness，nitness；对于长度为N的序列，N%2==1时，median定义为排序后第（N+1)/2大的数；N%2==0时，median定义为排序后第N/2和第N/2+1大的数中出现多的数，若出现次数相同选小的那个；shikness是median出现的次数，nitness是所有子序列的shikness的最大值，现给定长度为N，序列中的数可取1，2，3，问对于给定的N，长度为N的序列的最小nitness；
构造，不会；
根据题解，当答案是B时，我们构造长度为2B+2的循环节：前面是B个“13”，后面两个2，二分答案的check函数为判断2的数量和mid的大小关系；
可行性分析：
当子序列在一个循环节中取时，必然不超过B；
倘若跨越多个循环节，此处以两个循环节为例，由于很多个13排列在一起，因此有
可能1：选取x个1，x个3，y个2，x<=B，此时nitness=max(x,y)；
可能2：选取a+b个1，a+b+1个3，y个2，此时a<=B且b+1<=B且y==2，故对于整个序列来说median是2，nitness=max(a,b,y）；
可能3：选取（a+1）+b个1，a+b个3，y个2，此时y==2的情况与可能2相同，但是倘若我们构造的是长度为2B+1的循环节（前面B个“13”后面一个2）这里就会因为1出现次数多 / 出现次数一样多但是1比2小选1作为median，那么答案就会大于B；
1 #include<bits/stdc++.h>
2 using namespace std;
3 int read(){
4 char ch=getchar();int x=0,f=1;
5 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
6 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
7 return x*f;
8 }
9 int T,N,ans;
10 int main(){
11 T=read();
12 while(T--){
13 N=read();
14 int L=1,R=N;
15 while(L<=R){//二分答案;
16 int mid=(L+R)>>1;
17 int tmp=N/(2*mid+2);//有tmp个长度为2mid+2的区间;
18 int s=tmp*2+max(0,N%(2*mid+2)-2*mid);
19 if(s<=mid)ans=mid,R=mid-1;
20 else L=mid+1;
21 }
22 //若答案是B,则构造{1,3,1,3……,2,2……}的数列
23 //(B个1,3后面接两个2)
24 cout<<ans<<endl;
25 }
26 return 0;
27 }
H.HEX-A-GONE Trails
题意：两个op在树上做游戏，op1是先手，操作者每一次可以选择移动到一个与当前结点 i 连有边的新结点 j ，不允许移动到另一个操作者正在的位置，且在这次移动后，两个操作者都不能移动到结点 i ，无法移动的操作者会输掉比赛，现问对于op1是否有必胜策略；
不妨以x为根节点建树，预处理x到y的链上的第 i 个点（从y点往x点遍历并标序号），在不经过链上的点的前提下，在树上能延伸的最长距离并维护区间最大值：st1维护di+i，st2维护di-i；
对于当前操作者在第 i 个点时，有两种选择：
1. 从当前所在点直接前往能延伸的最远点，即 di ；
2. 先沿着链走，到达链上一点后再前往该点能延伸的最远点，从 i 往 j 走，i > j 时（op1操作时）即 max（ i - j + dj ）= i + max（ dj - j ）；i < j 时（op2操作时）即 max（ j - i + dj ）= max（ dj + j）- i ；
1 #include<bits/stdc++.h>
2 using namespace std;
3 int read(){
4 char ch=getchar();int x=0,f=1;
5 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
6 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
7 return x*f;
8 }
9 const int maxn=1e5+10;
10 int T,N,a,b,x,y,cnt,tot;
11 int f[maxn],cha[maxn],vis[maxn],head[maxn];
12 int len[maxn],lg[maxn],st1[maxn][20],st2[maxn][20];
13 struct node{
14 int u,v,next;
15 }e[maxn<<1];
16 void add(int u,int v){
17 tot++;
18 e[tot].u=u;e[tot].v=v;e[tot].next=head[u];head[u]=tot;
19 }
20 void dfs(int u,int fa){
21 f[u]=fa;
22 for(int i=head[u];i;i=e[i].next){
23 int v=e[i].v;
24 if(v!=fa)dfs(v,u);
25 }
26 }//建树;
27 int dfs2(int u,int fa){
28 int res=0;
29 for(int i=head[u];i;i=e[i].next){
30 int v=e[i].v;
31 if(!vis[v]&&v!=fa)res=max(res,dfs2(v,u)+1);
32 }
33 return res;
34 }
35 int query1(int l,int r){
36 int k=lg[r-l+1];
37 return max(st1[l][k],st1[r-(1<<k)+1][k]);
38 }
39 int query2(int l,int r){
40 int k=lg[r-l+1];
41 return max(st2[l][k],st2[r-(1<<k)+1][k]);
42 }
43 int main(){
44 T=read();
45 while(T--){
46 N=read();x=read();y=read();
47 lg[0]=-1;cnt=0;tot=0;
48 for(int i=1;i<=N;i++){
49 vis[i]=0;lg[i]=lg[i>>1]+1;
50 }
51 for(int i=1;i<=N-1;i++){
52 a=read();b=read();
53 add(a,b);add(b,a);
54 }
55 dfs(x,0);//以x为根建树;
56 while(y){
57 cha[++cnt]=y;
58 vis[y]=1;//标记链上的点;
59 y=f[y];
60 }//按顺序记录y至x的链上的点;
61 for(int i=1;i<=cnt;i++){
62 len[i]=dfs2(cha[i],0);
63 //从链上第i个点(不走链)延伸到的最远距离;
64 st1[i][0]=len[i]+i;
65 st2[i][0]=len[i]-i;
66 }
67 for(int i=1;i<=19;i++){
68 for(int j=1;j+(1<<i)-1<=N;j++){
69 st1[j][i]=max(st1[j][i-1],st1[j+(1<<(i-1))][i-1]);
70 st2[j][i]=max(st2[j][i-1],st2[j+(1<<(i-1))][i-1]);
71 }
72 }//st表维护di+i和di-i;
73 int ca=cnt,cb=1;
74 //先手后手在链上的点的标号;
75 int cur=1;
76 while(1){
77 if(cur==1){//先手操作;
78 if(ca-1==cb){
79 //如果先手后手在链上的相邻位置,即不能走链;
80 if(len[ca]>len[cb]){
81 cout<<"1"<<endl;
82 break;
83 }
84 else{
85 cout<<"0"<<endl;
86 break;
87 }
88 }
89 if(len[ca]>query1(cb,ca-1)-cb){
90 //如果不走链的深度大于沿着链走的深度;
91 cout<<"1"<<endl;
92 break;
93 }
94 ca--;//先手沿着链前进;
95 }
96 else{//后手操作;
97 if(cb+1==ca){
98 if(len[cb]>len[ca]){
99 cout<<"0"<<endl;
100 break;
101 }
102 else{
103 cout<<"1"<<endl;
104 break;
105 }
106 }
107 if(len[cb]>query2(cb+1,ca)+ca){
108 cout<<"0"<<endl;
109 break;
110 }
111 cb++;//后手沿着链前进;
112 }
113 cur^=1;//切换操作者;
114 }
115 for(int i=1;i<=N;i++){
116 head[i]=0;
117 e[2*i-1].u=e[2*i-1].v=e[2*i-1].next=0;
118 e[2*i].u=e[2*i].v=e[2*i].next=0;
119 }
120 }
121 return 0;
122 }
K.Three Operations
题意：给定三种操作：1.x=x-1；2.x=(x+a)/2；3.x=sqrt(x+b)；问将x变成0的最小操作次数；
显然2和3最多能将x变成a/2或sqrt(b),故后续只能用操作1；模拟并贪心，选取三种操作后将x变成的最小值，而当最小值是由操作1得到的时，后续一定只有操作1，故在ans上加上当前值直接输出即可；
1 #include<bits/stdc++.h>
2 #define ll long long
3 using namespace std;
4 ll read(){
5 char ch=getchar();ll x=0,f=1;
6 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
7 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
8 return x*f;
9 }
10 ll T,X,A,B;
11 void solve(){
12 X=read();A=read();B=read();
13 ll ans=0;
14 while(1){
15 ll n1=X-1,n2=(X+A)/2,n3=sqrt(X+B);
16 ll N=min(min(n1,n2),n3);
17 if(N==n1){
18 ans+=X;break;
19 }
20 if(N==n2){
21 ans++;X=N;continue;
22 }
23 if(N==n3){
24 ans++;X=N;continue;
25 }
26 }
27 cout<<ans<<endl;
28 }
29 int main(){
30 T=read();
31 while(T--){
32 solve();
33 }
34 return 0;
35 }
M.Minimal and Maximal XOR Sum
题意：对于给定的长度为N的排列，经过多少次区间翻转的操作将其变成递增的，问每次操作区间长度的最大最小异或和；
考场上大胆猜想，最大最小异或和取决于逆序对数量（设为x）的奇偶性，设长度N的二进制最高位为第k位；
x%2==1时最小异或和为2，x%2==0时最小异或和为0；
max=（1<<(k+1)）-1，x%2==1时最大异或和为max，x%2==0时最大异或和为max^2；
贴一个题解的证明：
1 #include<bits/stdc++.h>
2 #define ll long long
3 using namespace std;
4 int read(){
5 char ch=getchar();int x=0,f=1;
6 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
7 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
8 return x*f;
9 }
10 const int maxn=1e5+10;
11 int T,N,A[maxn],B[maxn];
12 ll ans;
13 void gb(int l,int r){
14 if(l==r)return ;
15 int mid=(l+r)>>1;
16 int i=l,j=mid+1,k=l;
17 gb(i,mid);gb(mid+1,r);
18 while(i<=mid&&j<=r){
19 if(A[i]<=A[j]){
20 B[k++]=A[i++];
21 }
22 else{
23 B[k++]=A[j++];
24 ans=ans+mid-i+1;
25 }
26 }
27 while(i<=mid){
28 B[k++]=A[i++];
29 }
30 while(j<=r){
31 B[k++]=A[j++];
32 }
33 for(int o=l;o<=r;o++){
34 A[o]=B[o];
35 }
36 }
37 int main(){
38 T=read();
39 while(T--){
40 N=read();
41 for(int i=1;i<=N;i++)A[i]=read();
42 if(N==1){
43 cout<<"0 1"<<endl;
44 A[1]=0;
45 continue;
46 }
47 int mi=0,ma=1;
48 while(ma<=N){
49 ma<<=1;
50 }
51 ma--;
52 ans=0;
53 gb(1,N);
54 if(ans%2==1)mi=2;
55 if(ans%2==0)ma=ma^2;
56 cout<<mi<<" "<<ma<<endl;
57 for(int i=1;i<=N;i++)A[i]=0,B[i]=0;
58 }
59 return 0;
60 }
标签：2023.08,杭电多校,ch,int,max,第七场,mid,while,getchar From： https://www.cnblogs.com/burutaofan/p/17624976.html