题目描述:两个人玩牌,比较牌大的一方手牌移除,其中一人没牌游戏结束。求小笨分数最大值的牌的排列次数(小红牌不动)。
知识点:贪心,数学
思路:
首先尝试贪心策略,我们可以观察到只要大的牌一定能被淘汰掉,于是我们可已找到小红最小的牌,因为比最小的牌大的牌一定可以被排除,比最小小的牌一定无法被排除,所以全排列,ans=(比min大的牌全排列)*(比min小的牌全排列)%mod 。赛时想的过于复杂,赛后改了几行代码过了QAQ
代码:
using namespace std;
#define int long long
const int mod=998244353;
void slove() {
int n ;cin>>n;
vector<int> a(n+1),b(n+1);
int minb=200009;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) {
cin>>b[i];
minb=min(minb,b[i]);
}
sort(a.begin()+1,a.end(),greater<int>());
// for(int i=1;i<=n;i++) cout<<a[i]<<' ';
// cout<<"AAAAAAA" <<endl;
// sort(b.begin()+1,b.end());
int flag=0;
for(int i=1;i<=n;i++) {
if(a[i]<minb) {
break;
}
flag++;
}
//cout<<flag<<"Abvvv"<<endl;
int sum=0;
int f1=1,f2=1;
for(int i=1;i<=flag;i++) {
f1=(f1*i)%mod;
}
for(int i=1;i<=n-flag;i++) {
f2=(f2*i)%mod;
}
sum=(f1*f2)%mod;
cout<<sum<<endl;
}
signed main() {
int t ;cin>>t;
while(t--) {
slove();
}
}

京公网安备 11010502036488号