Codeforces Round #767 (Div. 2)题解

传送门：Codeforces Round #767 (Div. 2)

A. Download More RAM

题意：商店有nn个拓展内存的软件，第ii个软件需要使用aia_i的内存，并给手机增加bib_i的内存。问手机最多能获得多少内存。

思路：贪心，直接按照aa从小到大排序，如果当前内存足够aa就将内存+b+b，否则退出循环。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T--) {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    for (auto& v : a) {
      cin >> v;
    }
    for (auto& v : b) {
      cin >> v;
    }
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&] (int x, int y) {
      return a[x] < a[y];
    });
    int ans = k;
    for (auto& v : p) {
      if (ans >= a[v]) {
        ans += b[v];
      } else {
        break;
      }
    }
    cout << ans << "\n";
  }
  return 0;
}

B. GCD Arrays

题意：一个数组包含从[l,r][l,r]的所有数各一个。有一个操作，任选数组中的两个数将其删去并添加一个新数到数组，该新数为两个被删去的数的积。做多能操作kk次，最后能否使得数组的gcd⁡>1\gcd \gt 1。

思路：为了让操作次数尽量少，我们可以让所有奇数和旁边的偶数相乘，最后让数组只留下偶数。我们只需要数出奇数个数并判断是否不超过kk即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T--) {
    int l, r, k;
    cin >> l >> r >> k;
    if (l == r) {
      cout << (l == 1 ? "NO" : "YES") << "\n";
      continue;
    }
    int odd = (r + 1) / 2 - l / 2;
    cout << (k >= odd ? "YES" : "NO") << "\n";
  }
  return 0;
}

C. Meximum Array

题意：有一个数组，每次可以选择一个数kk，然后会将前kk个数的MEXMEX值添加到新数组的尾部，并将旧数组的前kk个数删除，直到数组为空。构造一个字典序最大的新数组。

思路：我们可以先把整个数组的MEXMEX求出来，此时的MEXMEX值一定是在所有k∈[1,n]k \in [1, n]中的最大的。然后我们去遍历数组，假如遇到一个数加上后发现当前MEXMEX和最大的MEXMEX相同，我们直接将该数加入新数组，然后删去前kk个数。此时我们还需要去更新最大的MEXMEX，我们并不用重新去遍历，可以在边删数的时候边将MEXMEX更新，复杂度是线性的。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    vector<int> a(n), cnt(n + 1);
    for (auto& v : a) {
      cin >> v;
      cnt[v]++;
    }
    int mex = 0;
    for (int i = 0; i <= n; i++) {
      if (cnt[i] == 0) {
        mex = i;
        break;
      }
    }
    vector<int> ans;
    vector<bool> ok(n + 1);
    int now = 0, tmp = mex;
    for (auto& v : a) {
      ok[v] = true;
      cnt[v]--;
      if (cnt[v] == 0) {
        tmp = min(tmp, v);
      }
      while (now <= n && ok[now]) {
        now++;
      }
      if (now == mex) {
        ans.push_back(now);
        for (int i = 0; i <= now; i++) {
          ok[i] = false;
        }
        mex = min(mex, tmp);
        tmp = INT_MAX;
        now = 0;
      }
    }
    cout << int(ans.size()) << "\n";
    for (auto& v : ans) {
      cout << v << " ";
    }
    cout << "\n";
  }
  return 0;
}

D. Peculiar Movie Preferences

题意：有一个字符串列表，每个字符串长度不超过33，需要在其中找到一个子序列使得它们所连成的字符串是一个回文串。

思路：分类讨论。

假如当前字符串的长度为11，那么一定正确；

假如当前字符串长度为22，如果两个字母本身就相同，一定正确；如果存在该字符串的取反的串，也一定正确；

假如当前字符串长度为33，如果第一个字母和最后一个字母想同，一定正确；如果存在该串取反的串，一定正确；如果在它前面存在后两个字母取反的串，一定正确，例如["cb",...,"abc"]["cb",...,"abc"]，这是可以组成的，但是["abc",...,"cb"]["abc",...,"cb"]，这就不能组成；如果在他后面最在前两个字母取反的串，一定正确，和刚刚的一样，顺序一定不能错。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    map<string, int> mp;
    bool ok = false;
    int one = 0;
    for (int i = 0; i < n; i++) {
      string s;
      cin >> s;
      if (ok) continue;
      mp[s]++;
      if (s.length() == 1) {
        ok = true;
        continue;
      }
      if (s.length() == 2 && s[0] == s[1]) {
        ok = true;
        continue;
      }
      if (s.length() == 3 && s[0] == s[2]) {
        ok = true;
        continue;
      }
      if (s.length() == 2) {
        string t = s;
        reverse(t.begin(), t.end());
        if (mp.count(t)) {
          ok = true;
          continue;
        }
        for (char ch = 'a'; ch <= 'z'; ch++) {
          t.push_back(ch);
          if (mp.count(t)) {
            ok = true;
          }
          t.pop_back();
        }
        if (ok) continue;
      }
      if (s.length() == 3) {
        string t = s;
        reverse(t.begin(), t.end());
        if (mp.count(t)) {
          ok = true;
          continue;
        }
        t.pop_back();
        if (mp.count(t)) {
          ok = true;
          continue;
        }
      }
    }
    cout << (ok ? "YES" : "NO") << "\n";
  }
  return 0;
}

E. Grid Xor

题意：定义一个集合的异或和是集合内所有数异或的结果。现在知道一个二维数组，每个格子是它相邻的四个格子个异或和的结果，现在需要找到整个二维数组的异或和，该二维数组大小保证偶数。

思路：结论题。这题类似于开关灯问题，不过这题不会让自己改变状态，但道理相同。

我们将所有格子想象成按钮，按下后他四周的灯会改变状态，我们需要让所有灯变亮所需要操作的按钮，每个按钮最多被按下一次，因为再按下一次相当于没改变周围的状态。可以利用线性代数证明可行性，网上有很多证明过程。

由于这题保证有解，我们可以先让第一排为全暗的状态，从第二排开始，如果它上面的格子为暗的，就说明这是需要按下的按钮，然后同时要把另外几个相邻的灯状态改变。

其实这些需要操作的按钮所在的位置，就是整个数组异或和需要的数所在的位置，直接将这些数进行异或即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n));
    for (auto& v : a) {
      for (auto& vv : v) { 
        cin >> vv;
      }
    }
    vector<vector<int>> b(n, vector<int>(n));
    int ans = 0;
    for (int i = 1; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (b[i - 1][j] == 0) {
          ans ^= a[i][j];
          b[i - 1][j] ^= 1;
          if (i + 1 < n) {
            b[i + 1][j] ^= 1;
          }
          if (j - 1 >= 0) {
            b[i][j - 1] ^= 1;
          }
          if (j + 1 < n) {
            b[i][j + 1] ^= 1;
          }
        }
      }
    }
    cout << ans << "\n";
  }
  return 0;
}