今天在实验室做题战绩过了三个半小有进步吧。前两题我就不说了直接给代码#includebits/stdc.h using namespace std; int a,b,c; int main() { cinabc; int tmpa; ac; ctmp; tmpb; bc; ctmp; couta b cendl; return 0; }#includebits/stdc.h using namespace std; int main() { int t; cint; while(t--) { int n; cinn; if(n1) { coutaendl; } else { coutNoendl; } } return 0; }话说这个第二题还挺坑的都字符串互不相同了还是回文串那只能是一个字母了呀如果不是一个字母那么直接输出No就可以了也是被卡了十多分钟。。。这个题要用到组合数其实就是排列组合我们知道从1~n的数中不管n的奇偶n/2就是偶数的个数所以n-n/2就是奇数的个数如果j的个数大于n-n/2或者‘o’的个数大于n/2那么就不能满足条件直接输出0就可以了然后就是在奇数中挑j个先算C,再算Aj的个数的阶乘,偶数也是一样那么剩下的就只能在中替换了再求个阶乘最后乘在一起就可以了那么组合数怎么求了我比赛时是这么写的LL C(int a, int b) { LL res1; for(int i1,jb;ia;i,j--) { resres*j/i%mod; // ❌ 这里有问题 } return res; }也是喜提WA了因为在模运算中除法不能直接进行需要用逆元代替也就是a / b (mod mod) a * b^(mod-2) (mod mod) // 当 mod 是质数时为什么是这样呢我们应该知道费马小定理当MOD是质数时a^(MOD-1) ≡ 1 (mod MOD)那么 a * a^(MOD-2) ≡ a^(MOD-1) ≡ 1 (mod MOD)a的逆元就是a^(MOD-2)计算这个逆元就需要用快速幂套模版就行fact数组记录阶乘infect数组记录逆元的阶乘最后C(a,b)fact[b] * invfact[a] % mod * invfact[b-a] % mod;这样就能求出答案了看代码吧#includebits/stdc.h using namespace std; const int N2e510,mod998244353; typedef long long LL; LL fact[N], infact[N]; LL qmi(LL a,int k) { LL res1; while(k) { if(k1)resres*a%mod; aa*a%mod; k1; } return res; } void init(int n) { fact[0]1; for(int i1;in;i) { fact[i]fact[i-1]*i%mod; } infact[n]qmi(fact[n],mod-2); for(int in-1;i0;i--) { infact[i]infact[i1]*(i1)%mod; } } LL C(int a,int b) { if(a0||ab)return 0; return fact[b]*infact[a]%mod*infact[b-a]%mod; } int main() { int n; cinn; init(n); string s; cins; int ji0,ou0; for(int i0;in;i) { if(s[i]j)ji; if(s[i]o)ou; } if(jin-n/2||oun/2) { cout0endl; return 0; } LL res1; int mn-ou-ji; resres*C(ou,n/2)%mod*fact[ou]%mod*C(ji,n-n/2)%mod*fact[ji]%mod*fact[m]%mod; coutresendl; return 0; }应该说是模版题但是对我这个没有系统学过数论的小白来说还是挺难的看D题这个题就是模拟题吧我但是就是模拟思路贪心的直觉告诉我要删的话就要删中位数两边的数那就相当于所有和中位数相同的数中最左面或者最右面的变。然后上下边界改变反正除了中位数其他的数不重要随便改注意还有一个b数组作为备份#includeiostream #includealgorithm using namespace std; const int N4e510; int a[N],b[N]; int n; int main() { cinn; for(int i1;in;i)cina[i]; sort(a1,an1); int zhonga[(n1)/2]; //coutzhongendl; int sum0; for(int i1;in;i) { if(a[i]zhong)sum; } if(sumn) { cout-1endl; return 0; } int start-1,end-1; for(int i1;in;i) { if(start-1a[i]zhong)starti; if(end-1a[i1]!zhongstart!-1)endi; } //coutstartendl; //coutendendl; int step11e9,step21e9; for(int i1;in;i)b[i]a[i]; if(start!1) { step10; int m1; while(a[(mn)/2]zhong) { //coutmendl; step1; m; a[start]a[start-1]; start; } //coutstep1endl; } for(int i1;in;i)a[i]b[i]; if(end!n) { step20; int mn; while(a[(m1)/2]zhong) { //coutmendl; step2; m--; a[end]a[end1]; end--; } } coutmin(step1,step2)endl; return 0; }剩下的题等待大佬们补充有做的不好的地方也希望可以指点出来
牛客周赛Round136总结
发布时间：2026/5/19 17:18:46
今天在实验室做题战绩过了三个半小有进步吧。前两题我就不说了直接给代码#includebits/stdc.h using namespace std; int a,b,c; int main() { cinabc; int tmpa; ac; ctmp; tmpb; bc; ctmp; couta b cendl; return 0; }#includebits/stdc.h using namespace std; int main() { int t; cint; while(t--) { int n; cinn; if(n1) { coutaendl; } else { coutNoendl; } } return 0; }话说这个第二题还挺坑的都字符串互不相同了还是回文串那只能是一个字母了呀如果不是一个字母那么直接输出No就可以了也是被卡了十多分钟。。。这个题要用到组合数其实就是排列组合我们知道从1~n的数中不管n的奇偶n/2就是偶数的个数所以n-n/2就是奇数的个数如果j的个数大于n-n/2或者‘o’的个数大于n/2那么就不能满足条件直接输出0就可以了然后就是在奇数中挑j个先算C,再算Aj的个数的阶乘,偶数也是一样那么剩下的就只能在中替换了再求个阶乘最后乘在一起就可以了那么组合数怎么求了我比赛时是这么写的LL C(int a, int b) { LL res1; for(int i1,jb;ia;i,j--) { resres*j/i%mod; // ❌ 这里有问题 } return res; }也是喜提WA了因为在模运算中除法不能直接进行需要用逆元代替也就是a / b (mod mod) a * b^(mod-2) (mod mod) // 当 mod 是质数时为什么是这样呢我们应该知道费马小定理当MOD是质数时a^(MOD-1) ≡ 1 (mod MOD)那么 a * a^(MOD-2) ≡ a^(MOD-1) ≡ 1 (mod MOD)a的逆元就是a^(MOD-2)计算这个逆元就需要用快速幂套模版就行fact数组记录阶乘infect数组记录逆元的阶乘最后C(a,b)fact[b] * invfact[a] % mod * invfact[b-a] % mod;这样就能求出答案了看代码吧#includebits/stdc.h using namespace std; const int N2e510,mod998244353; typedef long long LL; LL fact[N], infact[N]; LL qmi(LL a,int k) { LL res1; while(k) { if(k1)resres*a%mod; aa*a%mod; k1; } return res; } void init(int n) { fact[0]1; for(int i1;in;i) { fact[i]fact[i-1]*i%mod; } infact[n]qmi(fact[n],mod-2); for(int in-1;i0;i--) { infact[i]infact[i1]*(i1)%mod; } } LL C(int a,int b) { if(a0||ab)return 0; return fact[b]*infact[a]%mod*infact[b-a]%mod; } int main() { int n; cinn; init(n); string s; cins; int ji0,ou0; for(int i0;in;i) { if(s[i]j)ji; if(s[i]o)ou; } if(jin-n/2||oun/2) { cout0endl; return 0; } LL res1; int mn-ou-ji; resres*C(ou,n/2)%mod*fact[ou]%mod*C(ji,n-n/2)%mod*fact[ji]%mod*fact[m]%mod; coutresendl; return 0; }应该说是模版题但是对我这个没有系统学过数论的小白来说还是挺难的看D题这个题就是模拟题吧我但是就是模拟思路贪心的直觉告诉我要删的话就要删中位数两边的数那就相当于所有和中位数相同的数中最左面或者最右面的变。然后上下边界改变反正除了中位数其他的数不重要随便改注意还有一个b数组作为备份#includeiostream #includealgorithm using namespace std; const int N4e510; int a[N],b[N]; int n; int main() { cinn; for(int i1;in;i)cina[i]; sort(a1,an1); int zhonga[(n1)/2]; //coutzhongendl; int sum0; for(int i1;in;i) { if(a[i]zhong)sum; } if(sumn) { cout-1endl; return 0; } int start-1,end-1; for(int i1;in;i) { if(start-1a[i]zhong)starti; if(end-1a[i1]!zhongstart!-1)endi; } //coutstartendl; //coutendendl; int step11e9,step21e9; for(int i1;in;i)b[i]a[i]; if(start!1) { step10; int m1; while(a[(mn)/2]zhong) { //coutmendl; step1; m; a[start]a[start-1]; start; } //coutstep1endl; } for(int i1;in;i)a[i]b[i]; if(end!n) { step20; int mn; while(a[(m1)/2]zhong) { //coutmendl; step2; m--; a[end]a[end1]; end--; } } coutmin(step1,step2)endl; return 0; }剩下的题等待大佬们补充有做的不好的地方也希望可以指点出来
