比赛链接：Dashboard - Codeforces Round 942 (Div. 2) - Codeforces
A题
翻译中文题面：
一场比赛包含 n 个问题，第 i 个问题的难度预期最多为 bi。已经有 n 个问题的提议，第 i 个问题的难度是 ai。最初，数组 a1,a2,…,an 和 b1,b2,…,bn 按非递减顺序排序。 一些问题可能比预期更难，所以写手必须提出更多问题。当提出难度为 w 的新问题时，最难的问题将被删除，问题将按非递减的难度排序。 换句话说，在每个操作中，你选择一个整数 w，将其插入数组 a，按非递减顺序排序数组 a，并从中删除最后一个元素。 找到使 ai≤bi 对所有 i 成立的新问题的最小数量。 输入 每个测试包含多个测试用例。第一行包含测试用例的数量 t（1≤t≤100）。以下是测试用例的描述。 每个测试用例的第一行仅包含一个正整数 n（1≤n≤100），表示问题的数量。 每个测试用例的第二行包含长度为 n 的数组 a（1≤a1≤a2≤⋯≤an≤109）。 每个测试用例的第三行包含长度为 n 的数组 b（1≤b1≤b2≤⋯≤bn≤109）。 输出 对于每个测试用例，在新行中打印一个整数作为你的答案。
解题思路：
在a数组中寻找到第一个不满足的数，把它替换成数组b中的数即可。
AC代码：
代码语言：javascript复制#include<iostream>
using namespace std;
const int N=105;
int n,t;
int a[N],b[N];
int cheak(int a[],int b[]){//判断a数组任意一个数是否小于b数组对应位置的数
for(int i=0;i<n;i ){
if(a[i]>b[i]){
return i;
}
}
return -1;
}
int main(){
cin>>t;
while(t--){
cin>>n;
int sum=0;
for(int i=0;i<n;i ){
cin>>a[i];
}
for(int i=0;i<n;i ){
cin>>b[i];
}
while(cheak(a,b)!=-1){
int dep=cheak(a,b);//记录下标
for(int i=n-1;i>=dep;i--){//数组右移
a[i 1]=a[i];
}
a[dep]=b[dep];//替换
sum ;
}
cout<<sum<<endl;
}
return 0;
}B题：
翻译中文题面：
在桌子上有 n 枚硬币组成一个圆圈，每枚硬币都可能正面朝上或者背面朝上。Alice 和 Bob 轮流玩以下游戏，Alice 先开始。 在每一步操作中，玩家选择一枚正面朝上的硬币，移除该硬币，并翻转其相邻的两枚硬币。如果（在操作之前）只剩下两枚硬币，则一枚会被移除，另一枚不会被翻转（因为它将被翻转两次）。如果（在操作之前）只剩下一枚硬币，则不会翻转任何硬币。如果（在操作之前）没有正面朝上的硬币，则玩家输掉游戏。 决定在他们都以最优方式玩游戏时谁将赢得游戏。可以证明游戏将在有限步数内结束，其中一个玩家将获胜。 输入 每个测试包含多个测试用例。第一行包含测试用例的数量 t（1≤t≤100）。以下是测试用例的描述。 每个测试用例的第一行仅包含一个正整数 n（1≤n≤100），表示硬币的数量。 每个测试用例的第二行包含一个长度为 n 的字符串 s，其中只包含 "U" 和 "D"，表示每枚硬币是正面朝上还是背面朝上。 输出 对于每个测试用例，如果 Alice 将赢得游戏，则打印 "YES"，否则打印 "NO"。 你可以以任何大小写形式输出答案。例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 都将被识别为肯定响应。
解题思路：
hhh,当你看完样例你就知道这是奇偶问题，当U的数量为奇数，Alice 将赢得游戏，偶数Bob赢得游戏。
AC代码：
代码语言：javascript复制#include<iostream>
#include<cstring>
using namespace std;
string s;
int t,n;
int main(){
cin>>t;
while(t--){
cin>>n;
int sumu=0;
cin>>s;
for(int i=0;i<s.size();i ){
if(s[i]=='U')sumu ;
}
cout<<(sumu%2==0?"NO":"YES")<<endl;
}
return 0;
}C题：
翻译中文题面：
你有一些卡片。每张卡片上都写着一个介于 1 和 n 之间的整数：具体来说，从 1 到 n 的每张 i ，你们有 ai 张写着数字 i 的卡片。
还有一个商店，里面有无限量的各种类型的卡片。您有 k 枚金币，因此您总共可以购买 k 张新卡片，您购买的卡片可以包含 1 到 n 之间的任意整数。
买完新牌后，你要将所有牌重新排列成一行。重新排列的得分是长度为 n 的（连续）子数组的数量，这些子数组是 [1, 2, ..., n] 的排列组合。你能得到的最高分是多少？
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 t (1<=t<=100) 。测试用例说明如下。
每个测试用例的第一行包含两个整数 n , k ( 1<= n <=2 *10^5 , 0<=k<=10^12 )不同类型纸牌的数量和硬币的数量。
每个测试用例的第二行包含 n 个整数 a1, a2, ..., an ( 1<=ai <=10^12 ) 开始时拥有的 i 类型的纸牌数量。
保证所有测试用例中 n 的总和不超过 5 *10^5 。
输出
对于每个测试用例，输出一行包含一个整数的数据：你能得到的最大分数。
解题思路：
这个问题看上去是一个数的排列问题，无非就是求一个组合排列，里面有多少个[1--n]的组合数，看完给的测试数据之后，从第三组测试样例来看，3 4 6 1 8，我们可以看出来主要贡献最大分数的还是数字2（1个），这就说明了这个一组合要得到最大的分数，那就要看短板，这就相当于木桶效应，能乘多少水取决于木桶里面最短的一个木板。这个样例中数字1（6个）数字2（1个）数字3（8个）,最少的是数字2，无论咋样组合，数字2只有一个，最多只能有两种组合（数字2左边组合，右边组合）,那么我们有k枚金币，可以去买不同的数，那就要买这堆数里面最少的那个数，比如1 6 8，先把数字1买到跟数字2一样6个，再往后让数字1跟数字2买到跟数字3相同8个，再多了就三个一组一起买，所求的分数如何算。(a[i] k/i)*n n-i k%i-n 1为了方便写在纸上，如下图：
AC代码：
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
const int N=5e5 5;
int t,n;
long long k,a[N];
int main(){
scanf("%d",&t);
while(t--){
scanf("%d %lld",&n,&k);
for(int i=1;i<=n;i ){
scanf("%lld",&a[i]);
}
sort(a 1,a n 1);//排序方便金币购买
for(int i=1;i<=n;i ){
if(i<n&&k>=(a[i 1]-a[i])*i){//金币足够买到与下一个数相同的个数
k-=(a[i 1]-a[i])*i;
}
else{
printf("%lldn",max(0ll,(a[i] k/i)*n n-i k%i-n 1));
//由于涉及到减法，防止答案为负数，与0取最大值
break;
}
}
}
return 0;
} D1题：
翻译中文题面：
两个版本的问题不同。您可能需要同时阅读两个版本。只有两个版本的问题都解决了，您才能进行破解。
给你两个正整数 n ， m 。
计算满足以下条件的有序数对 (a, b) 的个数：
- 1<=a<=n , 1<=b<=m ; - a b 是 b *gcd(a,b) 的倍数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 t ( 1<=t<=10^4 )。测试用例说明如下。
每个测试用例的第一行包含两个整数 n , m (1<=n,m<=2 *10^6 )。
保证所有测试用例中 n 和 m 的总和不超过 2 *10^6 。
输出
为每个测试用例打印一个整数：有效配对的数量。
注
在第一个测试案例中，只有 (1,1) 满足条件。
在第四个测试用例中， (1,1),(2,1),(2,2),(3,1),(4,1),(5,1),(6,1),(6,2),(6,3),(7,1),(8,1),(9,1),(10,1),(10,2) 满足条件。
解题思路：
AC代码：
代码语言：javascript复制#include<iostream>
using namespace std;
typedef long long ll;
int n,m,t;
ll ans;
int main(){
cin>>t;
while(t--){
cin>>n>>m;
ans=0;
for(int i=1;i<=m;i ){
ans =(n i)/(1ll*i*i);
}
cout<<ans-1<<endl;
}
return 0;
}D2题：
翻译中文题面：
两个版本的问题不同。您可能需要同时阅读两个版本。只有两个版本的问题都解决了，您才能进行破解。
给你两个正整数 n , m 。
计算满足以下条件的有序数对 (a, b) 的个数：
- 1<=a<=n, 1<=b<=m ; - b*gcd(a,b) 是 a b的倍数。
解题思路：
与上一个D1题倒过来了，假设都与上一个题一样的思路。这里粘一个官方题解。
AC代码：
代码语言：javascript复制#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int t,n,m;
int main(){
cin>>t;
while(t--){
cin>>n>>m;
int ans=0;
for(int i=1;i<=sqrt(n);i ){
for(int j=1;j<=sqrt(m);j ){
if(__gcd(i,j)==1){
ans = min(n/(i*(i j)),m/(j*(i j)));
}
}
}
cout<<ans<<"n";
}
return 0;
}
