摘要
Title: Acwing 第 90 场周赛
Tag: 字符串、贪心、KMP

Acwing 第 90 场周赛

A AcWing 4806. 首字母大写

题意

略
思路

判断

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-02-12 18:35:26
* @FilePath: \Acwing\90cp\a\a.cpp
* @LastEditTime: 2023-02-12 18:37:09
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

signed main()
{
    IOS;
    string s;
    cin >> s;

    if (islower(s[0]))
        s[0] = s[0] + 'A' - 'a';

    cout << s;
    return 0;
}

B AcWing 4807. 找数字

题意

给定一个正整数 m和一个非负整数 s
请你找到长度为 m且各位数字之和为 s的最小和最大非负整数。
要求所求非负整数不得包含前导零。
思路

贪心
对于最大数：从高位开始遍历，每次填min(9, s)
对于最小值：从低位开始遍历，每次填min(9, s - 1)，这里减一的目的是，至少留出一个1，保证最高位不是0
ps: s是和，是实时变化的

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

signed main()
{
    IOS;
    int m, s;
    cin >> m >> s;
    int s1 = s, s2 = s;
    vector<int> mn, mx;
    if (s > 9 * m || (!s && m > 1))
    {
        cout << "-1 -1\n";
        return 0;
    }
    // mx
    for (int i = 1; i <= m; ++i)
    {
        int t = min(9, s1);
        mx.push_back(t);
        s1 -= t;
    }
    // mn
    for (int i = 1; i < m; ++i)
    {
        int t = min(9, s2 - 1);
        mn.push_back(t);
        s2 -= t;
    }
    mn.push_back(s2);
    reverse(ALL(mn));

    for (auto i : mn)
        cout << i;
    cout << ' ';
    for (auto i : mx)
        cout << i;

    return 0;
}

C AcWing 4808. 构造字符串

题意

给定一个长度为 n的由小写字母构成的字符串 t以及一个整数 k
请你构造一个字符串 s，要求：
字符串 s恰好有 k个子串等于字符串 t
字符串 s的长度尽可能短。
保证一定存在唯一解。
思路

最优情况就是，找到最大长度和前缀相等的后缀（可通过KMP实现）。先放一个原字符串，再往后放k-1个去除了前缀的字符串

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 100, INF = 0x3f3f3f3f;
int ne[N];

signed main()
{
    IOS;

    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    s = " " + s;

    for (int i = 2, j = 0; i <= n; ++i)
    {
        while (j && s[i] != s[j + 1])
            j = ne[j];
        if (s[i] == s[j + 1])
            j++;
        ne[i] = j;
    }

    int l = ne[n];
    string p = s.substr(l + 1, n - l);
    cout << s.substr(1);
    for (int i = 1; i <= k - 1; ++i)
    {
        cout << p;
    }
    return 0;
}

Acwing 第 90 场周赛

A AcWing 4806. 首字母大写

题意

思路

代码

B AcWing 4807. 找数字

题意

思路

代码

C AcWing 4808. 构造字符串

题意

思路

代码