视频题解

---

A

#include <iostream>
using namespace std;

int main()
{
    int x, y, z, a, b;
    cin >> x >>y >> z >> a >> b;
    cout << min(a, b) * z + (max(a,b)-min(a,b)) * (a > b ? x : y);
    return 0;
}

B

#include <iostream>
using namespace std;
int cnt[2000];
int main()
{
    int n; cin >> n;
    int ans = -1;
    for(int i = 1; i <= n; i++) {
        int x; cin >> x;
        cnt[x]++;
        if(cnt[x] >= 4 && x > ans) ans = x; 
    }
    cout << ans;
    return 0;
}

C

60pts

枚举每一个分数，再循环判断是否满足男女数量一致：$O(n^2)$

100pts

先对所有学号排序，那么分界线一定在最中心的两个分数之间

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    sort(a.begin(), a.end());

    int k = n / 2;
    // 有效x的数量 = 后n/2个的最小值 - 前n/2个的最大值
    long long ans = a[k] - a[k - 1];

    cout << ans << endl;

    return 0;
}

D

- 60pts：

枚举 $2$ 条边长即可

- 100pts：

即求 $min|2\times(x+y)-k|$，同时有 $2\le x+y\le n+m$。

当 $x+y=\frac{k}2$ 时最佳

• $n+m\le \frac{k}2$ 时：取 $x+y=n+m$
• $2\geq \frac{k}2$ 时：取 $x+y=2$
• 否则取 $x+y=\lfloor\frac{k}2 \rfloor$ 或 $x+y=\lfloor\frac{k}2 \rfloor+1$

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        int N, M, K;
        cin >> N >> M >> K;
        
        long long lt = 2;
        long long rt = (long long)N + M;
        double best = K / 2.0;
        long long sp; // 半周长
        
        if (best <= lt) {
            sp = lt;
        } else if (best >= rt) {
            sp = rt;
        } else {
            long long bst = (long long)best;
            long long d1 = abs(2 * bst - K);
            long long d2 = abs(2 * (bst + 1) - K);
            sp = d1 <= d2 ? bst : bst + 1;
        }
        
        cout << abs(2 * sp - K) << '\n';
    }
    return 0;
}

E

明显不能真正执行每一次的操作二，考虑优化。我们维护一个当前字符串的“起点” $st$（从 $0$ 开始），每次进行操作二后，即有：

$$st = (st+n) \% 2n$$

确定当前起点之后，可以创建出当前位置与原始实际位置之间的映射关系：

$$i_{old}=(st+i_{now}-1)\%2n$$

需要进行操作一时，求出当前要交换的 $i,j$ 位置在原始字符串中的位置即可。$O(n+k)$

#include <iostream>
#include <string>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    string s;
    cin >> s;

    int len = 2 * n;
    int st = 0;

    while (k--) {
        int op;
        cin >> op;

        if (op == 1) {
            int i, j;
            cin >> i >> j;
            i--;
            j--;
            int old_i = (st + i) % len;
            int old_j = (st + j) % len;
            swap(s[old_i], s[old_j]);
        } else if (op == 2)  st = (st + n) % len;
    }

    
    for (int i = 0; i < len; i++)   cout << s[(st + i) % len];
    
    return 0;
}

F

观察可以发现，一定是从前向后进行翻转，这样后续操作不会修改前方的部分。

考虑先把所有位置都修改为 $0$，发生反转的部分 $i$ 满足 $s_i\neq s_{i-1}$。因为最后的目标是前 $0$ 后 $1$，那么考虑选择中间代价最大的某一位 $i$ 在上述全变 $0$ 的操作中去除，则可以实现 $i$ 之后全为 $1$ 的结果。

#include <iostream>
using namespace std;

int main() {
  int t = 1;
  while (t--) {
    int n;
    string s;
    cin>>n>>s;
    s = '0' + s;
    long long sum = 0;
    int mx = 0, x;
    for (int i=1; i<=n; i++) {
      cin>>x;
      if (s[i-1] != s[i]) {
        sum += x;
        mx = max(mx, x);
      }
    }
    cout<<sum-mx<<'\n';
  }
  
  return 0;
}