比赛链接：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代码：
#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代码：
#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代码：
#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("%lld\n",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代码：
#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代码：
#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; }
