CF1879ABC个人题解

题目链接：Dashboard - Educational Codeforces Round 155 (Rated for Div. 2) - Codeforces

A. Rigged!

有一场比赛，一共有n个人，每个人的力量是si，耐力是ei，现在有一个哑铃，哑铃的重量是w，如果第i个人的力量不低于哑铃的重量，则可以把他举起来，并且可以举ei次，也就是耐力值，那么他得到的分数也就是ei；比赛获胜的条件是：对于一个哑铃，有且只有一人的分数最高则获胜，若存在有多人分数并列第一则视为没有获胜。

主办方Monocarp希望自己的好朋友Polycarp（第一个人）能够赢下比赛（他的分数最高且高于其他所有玩家），那么请计算monocarp得将哑铃的重量设置为多少，Polycarp才能赢下比赛？

思路：贪心。

如果一个人比Polycarp力量小，则设置为比他力量大的重量, 但小于等于Polycarp的力量，这样他的分数就是0分，而Polycarp的分数为ei； $w\in(e_i, e_0]$
如果一个人的力量比Polycarp大，但耐力没有Polycarp高，那么把哑铃设置为小于等于Polycarp的力量的值，那么Polycarp的分数还是比这个人高。
如果存在比Polycarp的力量大，且耐力还要好的人，则永远不能获胜。

那么答案就出来了。w的重量一个在一个范围内：小于Polycarp的力量的所有人的最大力量值到Polycarp的力量值，这个区间内的所有答案都正确，那么我们为什么不直接取Polycarp的力量呢？

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 110;
int s[N], e[N];
int n, t;
signed main() {
  cin >> t;
  while (t -- ) {
    cin >> n;
    for (int i = 0; i < n; i ++ ) {
      cin >> s[i] >> e[i];
    }
    int ps = s[0], pe = e[0];
    bool f = false;
    for (int i = 1; i < n; i ++ ) {
      if (s[i] >= ps && e[i] >= pe) {
        cout << "-1" << endl;
        f = true;
        break;
      }
    }
    if (!f) cout << ps << endl;
  }
  return 0;
}

B. Chips on the Board

给定两个长度为n的正整数数组a和b，现在有一个n*n的矩阵m，矩阵中每一个单元格的value是 $m_{ij}=a_i+bj$

现在你将进行以下几次操作：

选中一个单元格并标记它，那么花费的代价就是该单元格的value

最后，你需要满足：对于矩阵中所有的单元格来说，该单元格所在行或所在列至少有一个被标记了的单元格。

对于此样例来说，选择这三个单元格的代价是最小的。

思路：对于上面的样例来说，第三排第二个其实可以换到第一排第二个的位置。

贪心。能把四个样例看懂了，就知道怎么做了。

答案是： $min(min(a_i)*n + \sum b_i, min(b_i)*n + \sum a_i)$

最好的答案是直接选择一列，或者一行。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 3e5 + 10;
int a[N], b[N];
int n, t;
signed main() {
  cin >> t;
  while (t -- ) {
    cin >> n;
    int suma = 0, sumb = 0;
    int mina = 1e9, minb = 1e9;
    for (int i = 0; i < n; i ++ ) {
      cin >> a[i];
      suma += a[i];
      mina = min(mina, a[i]);
    }
    for (int i = 0; i < n; i ++ ) {
      cin >> b[i];
      sumb += b[i];
      minb = min(minb, b[i]);
    }
    int res = min(suma + n * minb, sumb + n * mina);
    cout << res << endl;
  }
  return 0;
}

C. Make it Alternating

给定一个二进制字符串s（仅包含01）.

现在你可以进行任意次以下操作：（可以不操作）

选择一个 $i$ ，并删除 $s_i$ . $i \in [0, len(s) - 1]$

当你操作完后，最后的s字符串应该是一个交替的二进制字符串，即任何相邻的两个字符不能相同。

你需要计算两个value：

需要操作的次数。
不同操作序列的个数。即：进行n次操作后使得二进制字符串交替；这n个选定的i不同，则视为操作序列不同，比如：[1, 2], [2, 1] 先删除2再删除1和先删除1在删除2都能够使得二进制字符串交替，且顺序不同，视为两个不同的序列。

思路：

首先得先知道我们得删除多少个字符串

对于一段连续相同的子字符串，我们应该只留下1个字符，剩余的全部删掉。

比如样例：
- 10010：连续的两个0我们只能留下一个，删除一个；
- 111：连续的三个1我们只能留下一个，删除两个；
- 1100：同上，需要删除1个1、1个0；
- 111000111：需要删除2个1、2个0、2个1。
  
  那么第一个value我们就求出来了： $\sum (v_i-1)$
对于第二个value我们应该如何计算呢？

首先根据题意我们知道，这一定是一个排列组合：对于上面第三个样例，我们可以进行：(这里暂时不考虑删除后导致其他字符的位置发生改变)
- [1, 3]
- [1, 4]
- [2, 3]
- [2, 4]
  
  ~~这是顺序过来的，当然也可以进行反序：(这很重要！)~~
- [3, 1]
- [3, 2]
- [4, 1]
- [4, 2]
  
  我们将所有需要删除的字符放进一个数组中，这个数组存储着：连续相同的字符个数（长度大于1的）。
  
  那么对于 $v_i$ ,我们就需要删除 $v_i-1$ 个字符。
  
  有同学可能会想到答案是： $\prod P_{v_i}^{v_i-1}$ ,也就是高中学的排列组合，第1段我们选择 $v_1-1$ 个人进行排列、第2段我们选择 $v_2-1$ 个人进行排列…然后将所有的组合相乘就是答案了。
  
  那么恭喜你，你已经接触到答案的边缘了，but，这还是错的，有一个非常重要的问题：
  
  我们这样操作： $\prod P_{vi}^{vi-1}=\prod P_{v_i}^{v_i}$ ,实际上是固定了，我们先从第一段开始，删完了再删除第二段…一直删到最后一段。这个顺序是从前往后的，但是答案是什么？答案不仅仅包含整个，比如上面的举例，他还可以从后往前。那么到底是那些顺序呢？答案是无序的，任意顺序都可以。比如三段：中间的可以是最先开始的，也可以是最后开始的，也可以是第二次开始的，答案应该都包含这些顺序。并且一段连续的需要删除的，我们也完全可以在这两个操作中间插入一个别的操作。所以重点是无序！，不仅仅是连续的无序，更是单个操作无序；虽然要求二进制字符串是交替的，但是并没有要求我们的操作也是交替的或者必须是连续的！
  
  比如：
  
  111000
  
  v数组：3 3
  
  那么我既可以先删除后面的0，在删除前面的1；也可以先删除后面1个0，在删除前面两个1，在删除…
  
  所以对于答案： $\prod P_{v_i}^{v_i}$ 来说是片面的。
  
  那么正确的做法是什么呢？
  
  对于第i段： $v_i$ ，我们应该选择出 $v_i-1$ 个人出来（保证每次选择的人不同即可），然后对这 $\sum (v_i-1)$ 个人进行全排列，就是答案了：
  
  对于第i段： $v_i$ ，我们应该选择出 $v_i-1$ 个人出来（保证每次选择的人不同即可，所以得用组合）一共有多少种选法呢？
  $C_{v_i}^{v_i-1}=C_{v_i}^{1}=v_i$
  那么对于所有的 $v_i$ 来说，这样一共会有多少种选法？
  $\prod v_i$
  最后再乘以这 $\sum(v_i-1)$ 个人的全排列就行了。
  
  所以最后的答案就是：
  $(\prod v_i)*P_{\sum (v_i-1)}^{\sum (v_i-1)}=(\prod v_i)*(\sum(v_i-1))!$

考虑：

对于答案2，如果计算长度为1的值，会影响最终答案嘛？

答案：不会，注意看公式，左边累乘1不会有任何影响、右边累加0也不会有任何影响。
是否需要预处理计算 $i!$ 函数。

答案：最好需要，因为这是一个纯函数，纯函数：相同的输入只会有相同的输出，不会受外界干扰，不会导致副作用。对于一个纯函数，我们如果可能会多次需要计算，最好是将其进行预处理，比如:质数筛、 $log_2 n$ 这些需要反复查询的结果。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 998244353;
const int N = 2E5 + 10;
int fact[N];
// i!预处理
void init() {
  fact[0] = fact[1] = 1;
  for (int i = 2; i < N; i ++ ) {
    // 注意取模
    fact[i] = fact[i - 1] * i % MOD;
  }
}
void solve() {
  string s;
  cin >> s;
  vector<pair<char, int> > v;
  int n = s.length();
  v.push_back({ s[0], 1});
  for (int i = 1; i < n; i ++ ) {
    if (s[i] == v.back().first) v.back().second ++;
    else v.push_back({ s[i], 1 });
  }
  int cnt = 0;
  int res = 1;
  for (auto _: v) {
    int x = _.first, v = _.second;
    cnt += v - 1;
    // 注意取模
    res = res * v % MOD;
  }
  // 注意取模
  cout << cnt << " " << res * fact[cnt] % MOD << endl;
}
signed main() {
  int t; cin >> t;
  init();
  while (t--) {
    solve();
  }
}