南京网站建设 雷仁网络,建网站花多少钱,哪里有软件定制开发公司,多用户商城系统哪里有1002 Random Nim Game
只有3种情况,要么必赢,要么必输,要么从宏观角度考虑,随机的话,赢的概率就是1/2(就像抛硬币一样,随着抛的次数越来越多,正反面的概率将越来越接近1)
当只要有一堆石头数量不是1,那么就是必赢或必输,赢的概率就是1/2
当每堆石头数量都为1时,当堆数为奇数…1002 Random Nim Game
只有3种情况,要么必赢,要么必输,要么从宏观角度考虑,随机的话,赢的概率就是1/2(就像抛硬币一样,随着抛的次数越来越多,正反面的概率将越来越接近1)
当只要有一堆石头数量不是1,那么就是必赢或必输,赢的概率就是1/2
当每堆石头数量都为1时,当堆数为奇数时,先手必赢,概率为1,当堆数为偶数时,先手必输,概率为0
AC代码:
#includeiostream
#includealgorithm
#includecstring
#includecmath
#includevector
#includecstdio
#define endl \n
//#define int long long
using namespace std;
typedef long long ll;
const int N1e510,mod998244353;
int a[N];
int n;
int qmi(int a,int k){int res1;while(k){if(k1) res(ll)res*a%mod;a(ll)a*a%mod;k1;}return res;
}
void solve()
{cinn;for(int i1;in;i) cina[i];bool flagtrue;for(int i1;in;i){if(a[i]!1){flagfalse;break;}}if(!flag) coutqmi(2,mod-2)%modendl;else if(n%21) cout1endl;else cout0endl;
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t1;cint;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*x2个数字为一周期 为什么可以这样构造呢? 首先,对于整个序列,以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*x2就太小了,那么2的个数就多了,sum就大了,所以让x刚好等于sum为最优 那么如何使得x刚好等于sum,使用二分来确定,然后答案即为x(x和sum相等)
AC代码:
#includeiostream
#includealgorithm
#includecstring
#includevector
#includedeque
#includecmath
#includecstdio
#define endl \n
//#define int long long
using namespace std;
typedef long long ll;
int n;
void solve() {cinn;int l1,rn;while(lr){int mid(lr)/2;//mid即为我们要找的xint lenmid*22;//一个周期的长度int circlen/len;//当x为mid时,一个周期的长度为mid*22,circle即为最多有几个这样的周期int sum;//sum即为整个序列的2的个数if(n%lenmid*2) sumcircle*2;//当最后一个周期长度小于等于mid*2时,2的个数即为circle*2else sumcircle*2len-n%len;//当最后一个周期长度大于mid*2时,那么2的个数即为//如果整个序列的2的个数小于等于x,那么我们寻找更小的xif(summid) rmid;//否则说明x太小了else lmid1;//反正最终我们要使得sum和x相等}coutlendl;
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t1;cint;while(t--)solve();return 0;
}1011 Three Operations
三种操作
a,b有可能很大很大,所以(xa)/2和sqrt(xb)有可能得到的结果大于等于x,当出现这种情况时,我们就没必要执行这两种操作了,就只需要一直执行x-1就行了,但是因为数很大,所以一直执行x-1会超时,所以我们直接返回resx即可
AC代码:
#includeiostream
#includealgorithm
#includecstring
#includecmath
#includevector
#includecstdio
#define endl \n
//#define int long long
using namespace std;
typedef long long ll;
ll x,a,b;
ll solve()
{cinxab;ll res0;while(x){if((xa)/2xsqrt(xb)x) return resx;else xmin((xa)/2,(ll)sqrt(xb));res;}return res;
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t1;cint;while(t--)coutsolve()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代码:
#includeiostream
#includealgorithm
#includecstring
#includecmath
#includevector
#includecstdio
#define endl \n
//#define int long long
using namespace std;
typedef long long ll;
const int N1e510;
int a[N],b[N];
int n;
int minn,maxn;
ll res;
void mergesort(int l,int r){if(lr) return;int mid(lr)/2;mergesort(l,mid),mergesort(mid1,r);int il,jmid1,k0;while(imidjr){if(a[i]a[j]) b[k]a[i];else{b[k]a[j];resmid-i1;}}while(imid) b[k]a[i];while(jr) b[k]a[j];for(int il,j0;ir;i) a[i]b[j];
}
void solve()
{cinn;for(int i1;in;i) cina[i];res0;mergesort(1,n);
// coutresendl;if(res%21) minn2;else minn0;maxnminn;maxn;int base4;while(basen){maxnbase;base1;}coutminn maxnendl;
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t1;cint;while(t--)solve();return 0;
}
