(杭电多校)2023“钉耙编程”中国大学生算法设计超级联赛（7）

1002 Random Nim Game

只有3种情况,要么必赢,要么必输,要么从宏观角度考虑,随机的话,赢的概率就是1/2(就像抛硬币一样,随着抛的次数越来越多,正反面的概率将越来越接近1)

当只要有一堆石头数量不是1,那么就是必赢或必输,赢的概率就是1/2

当每堆石头数量都为1时,当堆数为奇数时,先手必赢,概率为1,当堆数为偶数时,先手必输,概率为0 

AC代码:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<cstdio>
#define endl '\n'
//#define int long long
using namespace std;
typedef long long ll;
const int N=1e5+10,mod=998244353;
int a[N];
int n;
int qmi(int a,int k){int res=1;while(k){if(k&1) res=(ll)res*a%mod;a=(ll)a*a%mod;k>>=1;}return res;
}
void solve() 
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];bool flag=true;for(int i=1;i<=n;i++){if(a[i]!=1){flag=false;break;}}if(!flag) cout<<qmi(2,mod-2)%mod<<endl;else if(n%2==1) cout<<1<<endl;else cout<<0<<endl;
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--)solve();return 0;
}

1004 Medians Strike Back 

参考题解 | #1004.Medians Strike Back# 2023杭电暑期多校7_深翼不通四书五经的博客-CSDN博客 

在序列A中选择一个连续序列B,序列B有一个中位数,然后cnt为该中位数在序列B中出现的次数

然后任意选择连续序列B,每一个序列B都有一个cnt,我们取所有连续子序列B的最大的cnt,即为maxn

现构造一个序列A(长度为n,值的范围在[1,3]),使得其maxn最小,输出最小的maxn

首先,我们输出的是次数,所以我们可以选择一个数作为稳定的中位数,专门输出它出现的次数,选择2是比较好的,2本来就是中间数

我们发现当序列中存在两个及以上的2时,我们可以使得2作为稳定的中位数,即131313..22131313...

然后我们考虑这样构造序列:

131313...(x对13)22131313...(x对13)22131313...(x对13)221313...(不足一个周期也没关系) 

这样的话,就是131313...(x对13)22,以2*x+2个数字为一周期 

为什么可以这样构造呢?

首先,对于整个序列,以2为中位数,所以cnt为整个序列的2的个数sum

然后,对于含有多个2的子序列,2为稳定的中位数,cnt为该子序列中的2的个数,肯定是小于sum的

对于只含有一个2的长度为奇数的子序列,2为稳定的中位数,cnt为该子序列中的2的个数,肯定是小于sum的

对于只含有一个2的长度为偶数的子序列以及不含2的子序列,2将不是中位数,1成为了中位数,cnt即为该子序列中1的个数

首先其它情况中位数的个数都小于sum,所以sum作为预选答案

我们来想一想,我们要保证x刚好等于sum

为什么呢?因为对于一个以1为中位数的子序列,比如说就是131313...(x对13),中位数为1,然后1的个数为x,我们不能让x超过sum,因为我们要最小的最大次数,如果x超过了sum,那么答案就为x了,其次,我们又不能让x小于sum,x太小的话,一个周期的长度2*x+2就太小了,那么2的个数就多了,sum就大了,所以让x刚好等于sum为最优

那么如何使得x刚好等于sum,使用二分来确定,然后答案即为x(x和sum相等) 

AC代码: 

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<deque>
#include<cmath>
#include<cstdio>
#define endl '\n'
//#define int long long
using namespace std;
typedef long long ll;
int n;
void solve() {cin>>n;int l=1,r=n;while(l<r){int mid=(l+r)/2;//mid即为我们要找的xint len=mid*2+2;//一个周期的长度int circle=n/len;//当x为mid时,一个周期的长度为mid*2+2,circle即为最多有几个这样的周期int sum;//sum即为整个序列的2的个数if(n%len<=mid*2) sum=circle*2;//当最后一个周期长度小于等于mid*2时,2的个数即为circle*2else sum=circle*2+len-n%len;//当最后一个周期长度大于mid*2时,那么2的个数即为//如果整个序列的2的个数小于等于x,那么我们寻找更小的xif(sum<=mid) r=mid;//否则说明x太小了else l=mid+1;//反正最终我们要使得sum和x相等}cout<<l<<endl;
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--)solve();return 0;
}

1011 Three Operations 

三种操作

a,b有可能很大很大,所以(x+a)/2和sqrt(x+b)有可能得到的结果大于等于x,当出现这种情况时,我们就没必要执行这两种操作了,就只需要一直执行x-=1就行了,但是因为数很大,所以一直执行x-=1会超时,所以我们直接返回res+x即可

AC代码:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<cstdio>
#define endl '\n'
//#define int long long
using namespace std;
typedef long long ll;
ll x,a,b;
ll solve() 
{cin>>x>>a>>b;ll res=0;while(x){if((x+a)/2>=x&&sqrt(x+b)>=x) return res+x;else x=min((x+a)/2,(ll)sqrt(x+b));res++;}return res;
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--)cout<<solve()<<endl;return 0;
}

1013 M.Minimal and Maximal XOR Sum 

算异或后的最小代价,利用归并排序算逆序对,算一共有几对逆序对,每个逆序对倒转的代价为2,然后就是算逆序对数量是奇还是偶,如果是偶数的话,异或后全部抵消了,就变成了0,如果是奇数的话,异或后还剩下一个2,此为异或后的最小值

在这个基础上,比如说最小代价为0,二进制为00或者最小代价为2,二进制为10

首先可以与1异或,即对一个数进行翻转,也就是加1(这是肯定可以操作的,因为最小代价要么为0要么为2,转化为二进制的最后一位肯定是0)

然后最后两位已经定下来了,比如说最小代价为00,与1异或后为01,最小代价为10,与1异或后为11

然后异或的话是二进制数之间按位异或,所以我们看能否使得第三位变为1(从右往左数第三位),比如说最后两位已经确定为11(接下来所说的都是基于这个例子),然后我们看能否使其变成111,也就是在刚才的基础上能否异或一个4

对于已经升序排好的4个数,我们先两两逆序对互换使得其降序,由于4是2的次幂,逆序对的数量肯定是偶数,所以异或和可以全部抵消掉,然后再翻转4个数,即异或一个4,由此,就成功变成了111

然后基于贪心策略,我们不满足于此,我们又希望继续变成1111,即在刚才的基础上异或一个8,同理,只要n的数量大于等于8,我们就可以成功异或一个8,以此类推,看能否异或一个2的次幂

AC代码:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<cstdio>
#define endl '\n'
//#define int long long
using namespace std;
typedef long long ll;
const int N=1e5+10;
int a[N],b[N];
int n;
int minn,maxn;
ll res;
void mergesort(int l,int r){if(l==r) return;int mid=(l+r)/2;mergesort(l,mid),mergesort(mid+1,r);int i=l,j=mid+1,k=0;while(i<=mid&&j<=r){if(a[i]<=a[j]) b[k++]=a[i++];else{b[k++]=a[j++];res+=mid-i+1;}}while(i<=mid) b[k++]=a[i++];while(j<=r) b[k++]=a[j++];for(int i=l,j=0;i<=r;i++) a[i]=b[j++];
}
void solve() 
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];res=0;mergesort(1,n);
//    cout<<res<<endl;if(res%2==1) minn=2;else minn=0;maxn=minn;maxn++;int base=4;while(base<=n){maxn+=base;base<<=1;}cout<<minn<<" "<<maxn<<endl;
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--)solve();return 0;
}