牛客周赛Round136总结

今天在实验室做题，战绩：过了三个半，小有进步吧。

前两题我就不说了，直接给代码：

#include<bits/stdc++.h> using namespace std; int a,b,c; int main() { cin>>a>>b>>c; int tmp=a; a=c; c=tmp; tmp=b; b=c; c=tmp; cout<<a<<' '<<b<<' '<<c<<endl; return 0; }

#include<bits/stdc++.h> using namespace std; int main() { int t; cin>>t; while(t--) { int n; cin>>n; if(n==1) { cout<<'a'<<endl; } else { cout<<"No"<<endl; } } return 0; }

话说这个第二题还挺坑的，都字符串互不相同了还是回文串，那只能是一个字母了呀，如果不是一个字母，那么直接输出No就可以了，也是被卡了十多分钟。。。

这个题要用到组合数，其实就是排列组合，我们知道，从1~n的数中，不管n的奇偶，n/2就是偶数的个数，所以n-n/2就是奇数的个数，如果'j'的个数大于n-n/2或者‘o’的个数大于n/2，那么就不能满足条件，直接输出0就可以了，然后就是在奇数中挑j个，先算C,再算A（j的个数的阶乘）,偶数也是一样，那么剩下的就只能在？中替换了，再求个阶乘，最后乘在一起就可以了，那么，组合数怎么求了，我比赛时是这么写的：

LL C(int a, int b) { LL res=1; for(int i=1,j=b;i<=a;i++,j--) { res=res*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;这样就能求出答案了

看代码吧：

#include<bits/stdc++.h> using namespace std; const int N=2e5+10,mod=998244353; typedef long long LL; LL fact[N], infact[N]; LL qmi(LL a,int k) { LL res=1; while(k) { if(k&1)res=res*a%mod; a=a*a%mod; k>>=1; } return res; } void init(int n) { fact[0]=1; for(int i=1;i<=n;i++) { fact[i]=fact[i-1]*i%mod; } infact[n]=qmi(fact[n],mod-2); for(int i=n-1;i>=0;i--) { infact[i]=infact[i+1]*(i+1)%mod; } } LL C(int a,int b) { if(a<0||a>b)return 0; return fact[b]*infact[a]%mod*infact[b-a]%mod; } int main() { int n; cin>>n; init(n); string s; cin>>s; int ji=0,ou=0; for(int i=0;i<n;i++) { if(s[i]=='j')ji++; if(s[i]=='o')ou++; } if(ji>n-n/2||ou>n/2) { cout<<0<<endl; return 0; } LL res=1; int m=n-ou-ji; res=res*C(ou,n/2)%mod*fact[ou]%mod*C(ji,n-n/2)%mod*fact[ji]%mod*fact[m]%mod; cout<<res<<endl; return 0; }

应该说是模版题，但是对我这个没有系统学过数论的小白来说，还是挺难的

看D题：

这个题就是模拟题吧，我但是就是模拟思路，贪心的直觉告诉我，要删的话就要删中位数两边的数，那就相当于所有和中位数相同的数中，最左面或者最右面的变。然后上下边界改变，反正除了中位数，其他的数不重要，随便改，注意，还有一个b数组作为备份：

#include<iostream> #include<algorithm> using namespace std; const int N=4e5+10; int a[N],b[N]; int n; int main() { cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; sort(a+1,a+n+1); int zhong=a[(n+1)/2]; //cout<<zhong<<endl; int sum=0; for(int i=1;i<=n;i++) { if(a[i]==zhong)sum++; } if(sum==n) { cout<<-1<<endl; return 0; } int start=-1,end=-1; for(int i=1;i<=n;i++) { if(start==-1&&a[i]==zhong)start=i; if(end==-1&&a[i+1]!=zhong&&start!=-1)end=i; } //cout<<start<<endl; //cout<<end<<endl; int step1=1e9,step2=1e9; for(int i=1;i<=n;i++)b[i]=a[i]; if(start!=1) { step1=0; int m=1; while(a[(m+n)/2]==zhong) { //cout<<m<<endl; step1++; m++; a[start]=a[start-1]; start++; } //cout<<step1<<endl; } for(int i=1;i<=n;i++)a[i]=b[i]; if(end!=n) { step2=0; int m=n; while(a[(m+1)/2]==zhong) { //cout<<m<<endl; step2++; m--; a[end]=a[end+1]; end--; } } cout<<min(step1,step2)<<endl; return 0; }

剩下的题等待大佬们补充，有做的不好的地方也希望可以指点出来