Codeforces Round 942 (Div. 2)

比赛链接：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;
}