Codeforces Round 963 (Div. 2)

A题：Question Marks

题目：

Tim正在做一个由 4n 个问题组成的测试，每个问题都有 4 个选项：“A”、“B”、“C”和“D”。对于每个选项，有 n 个正确答案对应于该选项，这意味着有 n 个问题的答案为“A”。n 个答案为“B”的问题， n 个答案为“C”的问题，以及 n 个回答为“D”的问题。每道题，蒂姆都把答案写在答题纸上。如果他想不出答案，他就会留下一个问号。为了这个问题。您将获得 4n 个字符的答题卡。蒂姆最多能得到多少个正确答案？

输入

第一行包含单个整数 t （ 1 <= t <= 1000 ）—测试用例的数量。

每个测试用例的第一行包含一个整数 n （ 1 <= n <= 100 ）。

每个测试用例的第二行包含 4n 个字符（ si 属于{A, B, C, D, ?} ）的字符串 s —Tim对问题的回答。

输出

对于每个测试用例，打印一个整数—Tim可以达到的最大分数。

样例

注意

在第一个测试用例中，每个答案“A”、“B”、“C”和“D”，只有一个问题，所以蒂姆有可能所有的答案都是正确的。在第二个测试案例中，只有两个正确答案'A'，这使得他在任何情况下都能得到2 分。在第三个测试用例中，Tim最多可以得到 2 个选项'A'的正确答案和 2 个选项'B'的正确答案。例如，如果答案是'AACCBBDD'，他将得到 4 分。在第四个测试案例中，他拒绝回答任何问题，这使他获得 0 分。

解题思路：

问题问的是他的最大得分，例如第一个样例他的答案为ABCD,那么我们默认正确的答案为ABCD,所以能得到4分，这种确认正确答案要建立在条件之上，确保每个选项出现的次数是一样的，当为5个问题时，必然有四个答案为A,B,C,D，还剩一个答案那就可以是任意一个，因为是要得最大的分，那么剩余那一个一定是答案出现两次的选项。当出现‘ ？’时可视为他空着这个题，没写答案，必然不得分。

AC代码：

#include<iostream>
using namespace std;
const int N=500;
int t,n;
char ch[N];
int main(){
  cin>>t;
  while(t--){
    cin>>n;
    cin>>ch;
    int suma=0,sumb=0,sumc=0,sumd=0;//记录四个选项出现次数
    for(int i=0;i<4*n;i++){
      if(ch[i]=='A')suma++;
      else if(ch[i]=='B')sumb++;
      else if(ch[i]=='C')sumc++;
      else if(ch[i]=='D')sumd++;
    }//因为4*n个问题每个选项最多出现n次
    if(suma>n)suma=n;
    if(sumb>n)sumb=n;
    if(sumc>n)sumc=n;
    if(sumd>n)sumd=n;
    cout<<suma+sumb+sumc+sumd<<endl;
  }
  
  return 0;
}

B题：Parity and Sum

题目：

给定一个由n个正整数组成的数组 a 。

在一个操作中，您可以选择任意一对索引 (i, j) ，使 ai 和 aj 具有不同的奇偶校验，然后用它们的和替换较小的一个。更正式地说：

-如果ai < aj ，请将 ai 替换为 ai + aj

-否则，将 aj 替换为 ai + aj 。

找出使数组的所有元素具有相同奇偶性所需的最小操作数。

输入

第一行包含单个整数 t ( 1 <= t <= 10^4 )—测试用例的数量。

每个测试用例的第一行包含一个整数 n ( 1 <= n <= 2*10^5 )。

第二行包含 n 整数 a1, a2, ..., an ( 1 <= ai <= 10^9 )—数组 a 的元素。

保证所有测试用例的 n 之和不超过 2*10^5 。

输出

对于每个测试用例，输出一个整数——所需的最小操作数。

样例

注意

在第一个测试用例中，所有整数都具有相同的奇偶性。因此，不需要任何操作。

在第三个测试用例中，我们可以执行两个操作 (1, 2) 和 (1, 3) 。数组 a 转换如下： a = [2, 3, 4] -> [5, 3, 4] -> [5, 3, 9] 。

在第四个测试用例中，最优操作序列的示例是 (1, 2) 、 (1, 3) 、 (1, 4) 和 (1, 4) 。数组 a 转换如下： a = [3, 2, 2, 8] -> [3, 5, 2, 8] -> [3, 5, 5,8] -> [11, 5, 5, 8] -> [11, 5, 5, 19] 。

解题思路：

通过上面图片，我们知道了奇偶两两相加的特点，由此我们可以得出只有odd+even=odd是可行的，我们是这个式子中较小的为偶数，偶数与奇数相加为奇数，这就把偶数变为奇数了，当偶数>奇数时，通过这样的操作，可以把这个奇数的值变得更大，使得前面的条件偶数>奇数变为偶数<奇数,那么这样我们又可以通过操作一把偶数变为奇数。

那么我们的操作顺序是什么，先哪个奇数跟哪个偶数先操作，由题意知，我们要最大程度满足偶数<奇数这个条件，因为只有这个条件操作才是对目标序列有贡献的。这样我们的奇数使其最大，偶数使其最小，既能把偶数变为奇数的情况下，奇数的值也可能得到了更新。使偶数按照递增的顺序是最优的，例如a={2，3，4，8}，开始奇数最大为3，偶数递增为{2，4，8}，第一次把2变为5，此时奇数最大值为5，第二次5与4操作变为9，奇数最大值又得到更新变为9，第三次操作9与8变为17结束。这样最优没有奇数＜偶数的情况。那么如果有奇数＜偶数的情况，我们就让此时最大的奇数与最大的偶数进行一次操作，这样得到的奇数足够大，可以满足所有的偶数了，例如a={1，2，6}，开始最大奇数一个也不满足，先让1与6进行一次操作，1变为7，这样7可以与2也可以与6进行操作了。如果1先于2进行操作，1变为3，在进行一次2变为5，5<6,最大奇数又小于偶数这样无非多一次操作。

AC代码：

#include<iostream>
#include<queue>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll a[N];//原数组
ll n,t;
priority_queue<ll,vector<ll>,greater<ll>> q;//升序优先队列（偶数）
int main(){
  cin>>t;
  while(t--){
    cin>>n;
    ll maxodd=0,maxeven=0;//最大奇数，最大偶数
    ll sum=0;//操作次数
    while(!q.empty()){//多次输入，清空队列
      q.pop();
    }
    for(int i=1;i<=n;i++){
      cin>>a[i];
      if(a[i]%2==1){
        maxodd=max(maxodd,a[i]);//求奇数最大值
      }else{
        q.push(a[i]);
        maxeven=max(maxeven,a[i]);//求偶数最大值
      }
    }
    if(maxodd==0||q.empty()){//都为奇数或偶数
      cout<<0<<endl;
    }else{
      ll len=q.size();
      ll sum1=0;//队内偶数操作次数
      while(1){
        if(q.top()>maxodd){
          maxodd=maxodd+maxeven;
        }else{
          maxodd=maxodd+q.top();
          q.pop();
          sum1++;
        }
        sum++;
        if(sum1==len)break;
      }
      cout<<sum<<endl;
    }
  }
  return 0;
}

C题：Light Switches

题目：

有一个由 n 个房间组成的公寓，每个房间的灯最初都是关闭的。为了控制这些房间的灯光，公寓的主人决定在房间里安装芯片，这样每个房间只有一个芯片。并且在不同的时间安装芯片。具体来说，这些时间由数组 a1, a2,..., an 表示，其中 ai 是时间(以分钟为单位)芯片安装在第 i 个房间。一旦安装了芯片，它就会每隔 k 分钟改变一次房间的灯光状态—它会打开灯光 k 分钟。然后在接下来的 k 分钟内将其关闭，然后在接下来的 k 分钟内将其重新打开，依此类推。换句话说，芯片在分钟 ai 、ai + k 、ai + 2k 、ai + 3k 改变灯的状态，公寓里所有房间的灯最早什么时候打开？

输入

第一行包含单个整数 t ( 1 <= t <= 10^4 )—测试用例的数量。

每个测试用例的第一行包含两个整数 n 和 k ( 1 <= k <= n <= 2*10^5 )—公寓中的房间数和芯片的周期。

第二行包含 n 不同的整数 a1, a2, ..., an ( 1 <= ai <= 10^9 )—安装芯片的时刻。

保证所有测试用例的 n 之和不超过 2*10^5 。

输出

对于每个测试用例，打印一个整数—问题的答案(以分钟为单位)。如果不存在所有房间的灯都打开的时刻，则改为打印 -1。

样例

注意

在第一个测试案例中，所有的灯都会在 5 分钟内打开，而不会被芯片关闭。答案是 5 。在第二个测试案例中，由于第一个指示灯将在 2, 3, 4, 8, 9, 10, 14, ... 分钟时亮起。同时，第 4 个指示灯将在 5, 6, 7, 11, 12, 13, 17, ... 分钟亮起。这两个序列没有任何相同的数字，因此它们永远不会同时出现。在第三个测试案例中，可以看到第一个灯和第二个灯将在 6 和 7 分钟关闭。但芯片将在 9 和 10 分钟时重新打开它们。第 3 和第 4 个灯也将在第 10 分钟亮起，因此答案是 10 。

解题思路：

灯亮的时刻：

• x→x+k−1
• x+2k→x+3k−1
• x+4k→x+5k−1
• …

列表中的每个段(除了第一个)实际上是它前面的段，移动了 2k 分钟。这也意味着，如果我们除以 2k 并在每个线段的两端取余数，则所有这些线段都变得相等。因此，我们将第 i 个芯片的片段称为 (ai mod 2k,(ai+k−1) mod 2k) 。因此，我们的问题被简化为：找到最小整数 s ，使得：

1. max（a）≤ s 出现在每个部分中
   
2. s mod 2k 属于其中的每个段之中
   

AC代码：

#include<bits/stdc++.h>
using namespace std;
int a[200001];
int main() {
  int t;
  cin>>t;
  while(t--)
  {
    int n,k;
    cin >> n >> k;
    for(int i = 1; i <=n; ++i)
      cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1; i<=n; ++i)
      a[i]+=(a[n]+k-1-a[i])/(k*2)*k*2;
    sort(a+1,a+n+1);
    if(a[n]-a[1]+1>k) cout<<-1<<endl;
    else cout<<a[n]<<endl;
  }
  return 0;
}