首页 程序设计 杂题集

# 最小字符串

# 题目大意

给定两个字符串（只包含小写字母），长度分别为 N,MN,M
你可以把 MM 个小写字母任意插入到 NN 个字符的字符串中，请问能得到的字典序最小的字符串是什么？

# 数据范围

  • 1≤N,M≤1051 \le N,M \le 10^5

# 题解

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void solve () {
    cin >> n >> m >> a >> b;
    map<int, int> cnt;
    for (int i = 0; i < m; i++)
        cnt[b[i] - 'a']++;
    
    int idx = 0;
    for (int i = 0; i < n; i++) {
        while (idx < 26 && idx + 'a' < a[i]) {
            while (cnt[idx] > 0)
                cout << (char)(idx + 'a'), cnt[idx]--;
            idx++;
        }
        cout << a[i];
    }

    while (idx < 26) {
        while (cnt[idx] > 0)
            cout << (char)(idx + 'a'), cnt[idx]--;
        idx++;
    }
}

# 合法密码

# 题目大意

密码的要求是这样的

  • 长度大于等于 88 个字符，小于等于 1616 个字符
  • 必须包含至少 11 个数字字符和至少 11 个符号字符

字符串为： kfdhtshmrw4nxg#f44ehlbn33ccto#mwfn2waebry#3qd1ubwyhcyuavuajb#vyecsycuzsmwp31ipzah#catatja3kaqbcss2th
请问有多少个子串可以当作合法密码？

# 题解

篮球杯是什么逆天题目，从题中能看出来 至少一个符号字符 的意思是至少要有一个 # ？

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
bool judge(string s) {
    int cntNum = 0, fhNum = 0;
    for (char c : s) {
        if (isdigit(c))
            cntNum++;
        if (c == '#')
            fhNum++;
    }

    return (cntNum >= 1 && fhNum >= 1);
}

void solve () {
    int res = 0;
    string s = "kfdhtshmrw4nxg#f44ehlbn33ccto#mwfn2waebry#3qd1ubwyhcyuavuajb#vyecsycuzsmwp31ipzah#catatja3kaqbcss2th";
    for (int i = 0; i < s.size(); i++) {
        int len = 8;
        while (i + len - 1 < s.size() && len <= 16) {
            res += judge(s.substr(i, len));
            len++;
        }
    }

    cout << res << endl;
}

# 立定跳远

# 题目大意

小明从数轴的原点开始向正方向立定跳远，设置了 nn 个检查点 a1,a2,...,an(ai≥ai−1≥0)a_1,a_2,...,a_n~(a_{i} \ge a_{i-1} \ge 0)
小明必须先后跳跃到每个检查点上且只能跳跃到检查点上
为了使跳远更加轻松，小明可以自己添加 mm 个检查点

在运动会前，小明单次跳远最远距离是 LL
小明可以爆发一次，使得跳跃距离达到 2L2L
请问，LL 的最小值是多少，小明可以完成这个项目

# 数据范围

  • 2≤n≤1052 \le n \le 10^5
  • m≤108m \le 10^8
  • 0≤ai≤1080 \le a_i \le 10^8

# 题解

可以将爆发一次改为多添加一个检查点（即可以添加 m+1m+1）个检查点
观察题目，跳跃距离 LL 具有单调性，故可以二分答案

checkcheck 函数的实现是这样的，保留上一个位置 last
对于每遍历到的一个 aia_i，计算 last 位置到 aia_i 需要添加的检查点个数 kk

kk 是这样计算的，不妨假设需要添加 xx 个检查点，那么 last 到 aia_i 则需要跳跃 x+1x+1 次
若要在 LL 中能跳过去的话，则需要满足 ai−lastx+1≤L\frac{a_i - last}{x+1} \le L
解得 x≥ai−lastL−1x \ge \frac{a_i - last}{L} - 1
需要注意的是 ai−lastL\frac{a_i - last}{L} 需要用 ceil 先上取整

代码如下：

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, m, a[N];

bool check(int l, int m) {
    int last = 0;
    for (int i = 1; i <= n; i++) {
        int k = max(int(ceil((a[i] - last) * 1.0 / l)) - 1, 0);
        if (m < k)
            return false;
        m -= k, last = a[i];
    }

    return true;
}

void solve () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    int l = 1, r = 1e9;
    
    while (l < r) {
        int mid = l + r >> 1;

        if (check(mid, m + 1))
            r = mid;
        else
            l = mid + 1;
    }

    cout << l << endl;
}