首页 程序设计 杂题集

# 小苯的计算器 (B 组、C 组)

水题
给你两个数 aa，bb，输出 a=k*b+c

python
1
2
3
4
5
6
7
8
9
t = int(input())

while True:
    if t == 0:
        break
    (a, b) = list(map(int, input().split()))

    print("{}={}*{}+{}".format(a, a // b, b, a - a // b * b))
    t -= 1

# 小苯的括号疑问 (A 组、C 组)

水题
给你一个括号序列，判断其是否可能经过任意修改，变成合法序列

  • 长度是奇数，一定不行
  • 长度是偶数：
    • len==2len==2：只有一种情况
    • len>2len > 2：必有若干种
      python
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      t = int(input())

      while True:
          if t == 0:
              break
          s = input()

          if len(s) & 1 == 1:
              print(-1)
          else:
              if len(s) == 2:
                  print('()')
              else:
                  print('There are multiple solutions')
          t -= 1

# 小苯的水果园 (B 组、C 组)

# 题意

题意其实很简单，有 nn 个果子，第 ii 个果子的种类是 aia_i
第 ii 天早上的时候会摘果子，同一种类若加起来的和是 ii 的话，则该种类全部都会在第 ii 天被摘掉
问：给定 qq 个询问，每次询问一个 dd，问你第 dd 天摘完后，还剩多少个

# 第一次错解

想的巨麻烦，二分都弄上了

c++
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
void solve () {
    vector<int> category;
    category.push_back(0);
    cnt.clear();

    int maxx = 0;

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        
        if (cnt[a[i]] == 0)    category.push_back(a[i]);

        cnt[a[i]]++, maxx = max(maxx, cnt[a[i]]);
    }

    sort(category.begin(), category.end(), cmp);
    for (int i = 1; i <= category.size() - 1; i++)
        pre[i] = pre[i - 1] + cnt[category[i]];
    
    while (q--) {
        cin >> d;
        int x = min(d, maxx);

        int l = 1, r = category.size() - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (cnt[category[mid]] > x)    r = mid - 1;
            else    l = mid;
        }

        cout << n - pre[l] << " ";
    }

    cout << endl;
}

# 第二次错解

思路没大问题，但是算前缀和的时候循环太多了直接 TLETLE 了，其实可以直接遍历 map 的，由此引出第三次正确解

c++
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
int n, q, a[N], pre[N];
map<int, int> cnt;
 
void solve () {
    cnt.clear();
    memset(pre, 0, sizeof pre);
 
    int maxx = 0;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i], cnt[a[i]]++, maxx = max(maxx, a[i]);
 
    // cout << endl;
 
    for (int i = 1; i <= maxx; i++)
        pre[cnt[i]] -= cnt[i];
         
    for (int i = 1; i <= maxx; i ++)
        pre[i] += pre[i - 1];
 
    // cout << endl;
    while (q--) {
        int x;
        cin >> x;
        if (x > maxx)
            cout << 0 << " ";
        else
            cout << n + pre[x] << " ";
    }
 
    cout << endl;
}

# 第三次正解

直接遍历 mapmap，不需要从 11 扫到 maxxmaxx 了，大大减少时间

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int n, q, ans[N];

void solve () {
    memset(ans, 0, sizeof ans);

    cin >> n >> q;
    map<int, int> cnt;

    for (int i = 1, x; i <= n; i++) cin >> x, cnt[x]++;
    
    for (auto t : cnt)  ans[t.second] += t.second;

    for (int i = 1; i <= n; i++)    ans[i] += ans[i - 1];
    
    while (q--) {
        int x;
        cin >> x, x = min(x, n);

        cout << n - ans[x] << " ";
    }

    cout << endl;
}

# 小苯的数组最值 (A 组、B 组、C 组)

# 题意

有一个长度为 nn 的数组
对这个数组施展 mm 次魔法，每次可以对于给定的 (l,r,d)(l, r, d)，让其中的 al→ara_l \to a_r 都加上 dd
但是，不会全部施法成功，而是会随机且等概率地失效一个魔法
问，在这种情况下，数组 aa 的最大值的期望是多少
（对于每个测试数据，输出一行一个整数表示数组的最大值对 998244353998244353 取模的值

# 题解

求一个区间的最大值，引入前缀 + 后缀最大值数组，修改值用差分来记录，注意，这题用到了快速幂和逆元

c++
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
int n, m, a[N], l[N], r[N], d[N];
 
int qmi(int a, int b) {
    int res = 1, t = a;

    while (b) {
        if (b & 1)
            res = res * a % MOD;
        a = a * a % MOD, b >>= 1;
    }

    return res;
}
 
void solve () {
    cin >> n >> m;
    vector<int> cf(n + 10);
    
    for (int i = 1; i <= n; i++)
        cin >> a[i];
        
    for (int i = 1; i <= m; i++) {
        cin >> l[i] >> r[i] >> d[i];
        cf[l[i]] += d[i], cf[r[i] + 1] -= d[i];
    }

    for (int i = 1; i <= n; i++)
        cf[i] += cf[i - 1], a[i] += cf[i];

    vector<int> pre(n + 10), suf(n + 10);
    for (int i = 1; i <= n; i++)
        pre[i] = max(pre[i - 1], a[i]);
    for (int i = n; i >= 1; i--)
        suf[i] = max(suf[i + 1], a[i]);

    int ans = 0;

    for (int i = 1; i <= m; i++) {
        int L = l[i], R = r[i], D = d[i];
        
        if (pre[L - 1] == pre[n] || suf[R + 1] == suf[1])
            ans += pre[n];
        else
            ans += max(pre[n] - D, max(pre[L - 1], suf[R + 1]));

        ans %= MOD;
    }

    ans *= qmi(m, MOD - 2);
    cout << ans % MOD << endl;
}

期望的计算公式是： 期望 = 所有可能情况总和 / 情况数
在此题中是 期望 = ans / q

在除运算中，不能直接模
(a / b) % c != (a % c) / (b % c)

这时就要用到逆元
a / b ≡ a * b^{-1} (mod p)

b^{-1} 代表 bb 的逆元，计算逆元用到了费马小定理
如果 pp 是质数，且 pp 和 qq 互质，则 q^{p-2} ≡ q^{-1} (mod p)
因此，qp−2%pq^{p-2} \% p 返回 qq 的逆元