AcWing 第 90 场周赛

A、首字母大写

原题链接：AcWing 4806. 首字母大写

签到题。

#include <bits/stdc++.h>using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);string s;cin >> s;s[0] = toupper(s[0]);cout << s;return 0;
}

B、找数字

原题链接：AcWing 4807. 找数字

当 $m>1$ 时，$s$ 的取值范围是 $[1,9m]$；当 $m=1$ 时，$s$ 的取值范围是 $[0,9]=[0,9m]$。

结合 $s\ge 0$ 可知，当 s > 9 * m || !s && m > 1 成立时，一定无解。下面考虑有解的情形。

先来看最大值如何求。根据贪心原则，最高位应当尽可能填 $9$，如果填不了 $9$ 就填 $8$，以此类推，当最高位填完后填次高位，同样也是优先填 $9$，如此循环下去直到 $m$ 位都填满就能得到最大值。

再来看最小值如何求。我们可以把这 $m$ 位做一个翻转，然后按照求最大值的方法求最小值，但需要注意的是，最小值的最后一位不能是 $0$，否则翻转后最小值将不足 $m$ 位。

#include <bits/stdc++.h>using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int m, s;cin >> m >> s;if (s > 9 * m || !s && m > 1) cout << "-1 -1";else {string a(m, ' '), b(m, ' ');int sum = s;for (int i = m - 1; i; i--) {int t = min(9, sum - 1);  // 为了确保到最高位时还能有一个1可以放进去a[i] = t + '0';sum -= t;}a[0] = sum + '0';sum = s;for (int i = 0; i < m; i++) {int t = min(9, sum);b[i] = t + '0';sum -= t;}cout << a << ' ' << b;}return 0;
}

C、构造字符串

原题链接：AcWing 4808. 构造字符串

要使 $s$ 尽可能地短，需要让各个 $t$ 之间的重叠部分尽可能地多，这相当于求字符串 $t$ 的最长公共前后缀，可以通过前缀函数获得。

#include <bits/stdc++.h>using namespace std;const int N = 60;int pi[N];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, k;string t;cin >> n >> k >> t;int m = t.size();for (int i = 1; i < m; i++) {int j = pi[i - 1];while (j && t[j] != t[i]) j = pi[j - 1];if (t[j] == t[i]) j++;pi[i] = j;}string r = t.substr(pi[m - 1]);cout << t;while (--k) cout << r;return 0;
}