本场五六水依旧迷之难度~~往蓝桥杯省赛训练塞紫题和黑题，你无敌了~~

C. Exam and Wizard(通过人数 28/42)#

题目描述#

高桥君要参加 $N$ 门考试。第 $i$ 门考试当前的准备度为 $A_i$ ，通过所需的最小准备度为 $B_i$ 。魔法师青木可以重新分配准备度，但总准备度 $\sum A_i$ 保持不变。求最少修改多少门考试的准备度（即 $A_i \neq C_i$ 的数量），使得所有考试都能通过（ $C_i \ge B_i$ ）。如果无法达成，输出 -1。

输入格式#

输入第一行包含一个整数 $N$ 。第二行包含 $N$ 个整数 $A_1, \dots, A_N$ 。第三行包含 $N$ 个整数 $B_1, \dots, B_N$ 。

$1 \le N \le 10^5$
$1 \le A_i, B_i \le 10^9$

题解#

思路：考虑贪心，优先让多出来最多的考试匀给不够的考试。因此分配方案是，按准备度之差从低到高排序后，从后往前分配，直到所有考试准备度之差非负。

不过首先判断总准备度是否足够。如果 $\sum A_i < \sum B_i$ ，则无论如何分配都无法通过所有考试，输出 -1。

排序操作贡献时间复杂度 $O((N \log(N))$

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define endl '\n'
5
#define rep(i, f, l) for(int i(f); i <= l; ++i)
6
#define per(i, f, l) for(int i(f); i >= l; --i)
7
const int N = 2e5 + 5;
8
struct node{
9
    int x;
10
    int y;
11
    int dif;
12
};
13
node a[N];
14
bool cmp(node a, node b){
15
    return a.dif < b.dif;
16
}
17
void work() {
18
   int n;
19
     cin >> n;
20
     int sum = 0;
21
     rep(i, 1, n){
22
         cin >> a[i].x;
23
     }
24
     rep(i, 1, n){
25
         cin >> a[i].y;
26
         a[i].dif = a[i].x - a[i].y;
27
         sum += a[i].dif;
28
     }
29
     if (sum < 0) {
30
         cout << -1 << endl;
31
         return;
32
     }
33
     sort(a + 1, a + n + 1, cmp);
34
     int ans = 0;
35
     int need = 0;
36
     rep(i, 1, n){
37
         if(a[i].dif >= 0) break;
38
         need += a[i].dif;
39
         ans++;
40
     }
41
     if(need == 0){
42
         cout << 0 << endl;
43
         return;
44
     }
45
     per(i, n, 1){
46
         if(need >= 0) break;
47
         need += a[i].dif;
48
         ans++;
49

50
     }
51
     cout << ans << endl;
52
    return;
53
 }
54
 signed main() {
55
    ios::sync_with_stdio(0);
56
    cin.tie(0);
57
    cout.tie(0);
58
    int t = 1;
59
 //    cin >> t;
60
    while (t--) {
61
       work();
62
    }
63
    return 0;
64
 }

E. KEYENCE String(通过人数 21/42)#

题目描述#

如果一个字符串可以通过移除一次连续子串（可以是空串）变成 “keyence”，则称该字符串为 “KEYENCE string”。给定一个由小写英文字母组成的字符串 $S$ ，判断它是否为 “KEYENCE string”。

输入格式#

输入包含一个字符串 $S$ 。

$7 \leqslant |S| \leqslant 100$
$S$ 由小写英文字母组成

题解#

定睛一看 $|S| \leqslant 100$ ，比赛时由于着急过题直接抛弃大脑，暴力出奇迹（思路：由于是从一个字符串中间扣出一段，再拼接剩余两段，直接暴力枚举扣出字符串的首尾字符，然后再暴力拼接即可。时间复杂度 $O(|S|^3)$

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define endl '\n'
5
#define rep(i, f, l) for(int i(f); i <= l; ++i)
6
#define per(i, f, l) for(int i(f); i >= l; --i)
7
const int N = 2e5 + 5;
8
void work() {
9
   string s;
10
     cin >> s;
11
     string ans = "";
12
     if (s == "keyence") {
13
         cout << "YES" << endl;
14
         return;
15
     }
16
     for(int i = 0; i < s.size(); i++){
17
         for(int j = i; j < s.size(); j++){
18
             for(int k = 0; k < s.size(); k++){
19
                 if(k >= i && k <= j) continue;
20
                 ans += s[k];
21
             }
22
             if(ans == "keyence"){
23
                 cout << "YES" << endl;
24
                 return;
25
             } else{
26
                 ans = "";
27
             }
28
         }
29
     }
30
    cout << "NO" << endl;
31
    return;
32
 }
33
 signed main() {
34
    ios::sync_with_stdio(0);
35
    cin.tie(0);
36
    cout.tie(0);
37
    int t = 1;
38
 //    cin >> t;
39
    while (t--) {
40
       work();
41
    }
42
    return 0;
43
 }

~~不过这个思路有点太蠢了~~，有没有一种更高效的办法呢？当然有的，而且直接降维打击到 $O(1)$ 。

仔细思考一下就能发现，如果答案是 “YES“，那么这个字符串的前缀必然是 “keyence” 的某个前缀，这个字符串的后缀必然是 “keyence” 对应的那个后缀。因此实际上，我们只需要遍历 “keyence”所有的前后缀拆分情况，再和原串的前后缀作比对就行了～。

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define endl '\n'
5
#define rep(i, f, l) for(int i(f); i <= l; ++i)
6
#define per(i, f, l) for(int i(f); i >= l; --i)
7
const int N = 2e5 + 5;
8
void work() {
9
  string s;
10
    cin >> s;
11
    string targ = "keyence";
12
    if (s.size() < 7) {
13
        cout << "NO" << endl;
14
        return;
15
    }
16
    rep(i, 0, 7){
17
        string s1 = targ.substr(0, i);
18
        string s2 = targ.substr(i, targ.size() - i);
19
        if((s1 == s.substr(0, s1.size())) && (s2 == s.substr(s.size() - s2.size(), s2.size()))){
20
            cout << "YES" << endl;
21
            return;
22
        }
23
    }
24
    cout << "NO" << endl;
25
    return;
26
}
27
signed main() {
28
  ios::sync_with_stdio(0);
29
  cin.tie(0);
30
  cout.tie(0);
31
  int t = 1;
32
//  cin >> t;
33
  while (t--) {
34
    work();
35
  }
36
  return 0;
37
}

D. Double Landscape(通过人数 8/42)#

题目描述#

在一个 $N \times M$ 的网格中填入 $1$ 到 $N \times M$ 的所有整数，不重复。要求满足以下条件：

第 $i$ 行的最大值是 $A_i$ 。
第 $j$ 列的最大值是 $B_j$ 。

求填入方案数，对 $10^9 + 7$ 取模。

输入格式#

第一行包含两个整数 $N, M$ 。第二行包含 $N$ 个整数 $A_1, \dots, A_N$ 。第三行包含 $M$ 个整数 $B_1, \dots, B_M$ 。

$1 \le N, M \le 1000$
$1 \le A_i, B_j \le N \times M$

题解#

超绝思维妙妙题。实际上没有看起来的那么难。

首先我们需要打破思维定势：如果从小到大去填数，会发现由于限制条件是最大值，小的数几乎可以填到任何地方，完全没有考虑后续大数的限制；我们不妨反过来思考，如果从大到小填数，当我们把一个大数填到某行/列并满足其最大值限制后，剩下的小数就可以真正意义上的在这行/列无限制的排列了。

那么对于一个要填的数 $x$ ，我们关心的是有多少行/列是之前已经满足最大值条件，可以自由排列的。因此我们维护两个变量，用 cnt1 记录目前可用的行数（该行的最大值已经被填入），cnt2记录目前可用的列数。

那我们分析后可以得出，对于当前数字 $x$ ：

如果 $x$ 既是某行最大值 $A_i$ ，又是某列最大值 $B_j$ ：
- 那么这个数字必须填在 $(i, j)$ 这个格子上。
- 此时cnt1 += 1,cnt2 += 1。
如果 $x$ 只是某行最大值 $A_i$ ：
- 它必须填在第 $i$ 行，且必须填在一个 “可用列” 中
- 方案数为 $cnt2$
- cnt1 += 1
如果 $x$ 只是某列最大值 $B_j$ ：
- 它必须填在第 $j$ 列，且必须填在一个“可用行”中。
- 方案数为 $cnt1$ 。
- cnt2 += 1
如果 $x$ 既不是行最大值也不是列最大值：
- 它必须填在一个 “可用行” 且 “可用列” 的交叉位置上。
- 这样的位置总共有 $cnt1 \times cnt2$ 个，但是其中有一些已经填过比 $x$ 大的数了。
- 已经填过的格子总数是 $(N \times M - x)$ , 所以可选位置数为 $cnt1 \times cnt2 - (N \times M - x)$ 。

最终答案为每一步方案数的乘积。代码实现很简单，重要的是上述思维的过程。

另外注意当进行 “检查当前数 x 是否在限制条件中” 的操作时，我们直接暴力查找会导致超时。可以直接空间换时间，建立一个 bool 桶数组记录这些数是否存在。

时间复杂度 $O(NM)$

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define endl '\n'
5
#define rep(i, f, l) for(int i(f); i <= l; ++i)
6
#define per(i, f, l) for(int i(f); i >= l; --i)
7
const int N = 1e3 + 5;
8
int a[N];
9
int b[N];
10
bool in_a[N * N];
11
bool in_b[N * N];
12
const int mod = 1e9 + 7;
13
bool is_in(int arr[], int len, int x) {
14
   rep(i, 1, len) {
15
      if (arr[i] == x) return true;
16
   }
17
   return false;
18
}
19
void work() {
20
   int n, m;
21
   cin >> n >> m;
22
   rep(i, 1, n) cin >> a[i], in_a[a[i]] = true;
23
   rep(i, 1, m) cin >> b[i], in_b[b[i]] = true;
24
   int cnt1 = 0, cnt2 = 0;
25
   int ans = 1;
26
   per(x, n * m, 1){
27
      if(in_a[x] && in_b[x]){
28
         cnt1++;
29
         cnt2++;
30
         continue;
31
      }
32
      if(in_a[x]){
33
         cnt1++;
34
         ans = (ans % mod * cnt2 % mod) % mod;
35
         continue;
36
      }
37
      if(in_b[x]){
38
         cnt2++;
39
         ans = (ans % mod * cnt1 % mod) % mod;
40
         continue;
41
      }
42
      ans = (ans * (cnt1 * cnt2 - (n * m - x)) % mod) % mod;
43
   }
44
   cout << ans << endl;
45
   return;
46
}
47
signed main() {
48
   ios::sync_with_stdio(0);
49
   cin.tie(0);
50
   cout.tie(0);
51
   int t = 1;
52
//    cin >> t;
53
   while (t--) {
54
      work();
55
   }
56
   return 0;
57
}

わたしの部屋

C. Exam and Wizard(通过人数 28/42)#

题目描述#

输入格式#

题解#

E. KEYENCE String(通过人数 21/42)#

题目描述#

输入格式#

题解#

D. Double Landscape(通过人数 8/42)#

题目描述#

输入格式#

题解#