AcWing、第 90 场周赛：4806. 首字母大写、4807. 找数字、4808. 构造字符串（C++）

目录

4806. 首字母大写

题目描述：

实现代码：

4807. 找数字

题目描述：

实现代码：

回溯（超时）：

原理思路：

贪心：

原理思路：

4808. 构造字符串

问题描述：

实现代码与解析：

kmp：

原理思路：

---

4806. 首字母大写

题目描述：

        给定一个由大小写字母构成的单词。

如果单词的首字母为小写字母，则请你将该首字母转换为对应大写字母。

如果单词的首字母为大写字母，则不做任何变化。

输出最终的单词。

实现代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{string s;cin >> s;if('A' <= s[0] && s[0] <= 'Z' ){cout << s <<endl;}else{s[0]-= 32;cout << s <<endl;}
}

或则直接这样写：

#include<bits/stdc++.h>
using namespace std;
int main()
{string s;cin >> s;s[0] = toupper(s[0]);cout << s <<endl;
}

4807. 找数字

题目描述：

        给定一个正整数 m 和一个非负整数 s。

请你找到长度为 m且各位数字之和为 s 的最小和最大非负整数。

要求所求非负整数不得包含前导零。

实现代码：

回溯（超时）：

#include <bits/stdc++.h>
using namespace std;
int result1 = 0;//求最大
int result2 = INT_MAX;//求最小
vector<int> path;
void backtrack1(int m, int s, int index)
{if (path.size() == m){int sum1 = 0;for (int i = 0; i < path.size(); i++){sum1 += path[i];}if (sum1 == s){int sum = 0;for (int i = 0; i < path.size(); i++){sum = sum * 10 + path[i];}if (sum > result1) result1 = sum;if (sum < result2) result2 = sum;}    return;}int i = 0;if (path.empty()){i = 1;}for (i; i < 10 && i <=  s - index; i++){path.push_back(i);backtrack1(m, s, index + i);path.pop_back();}
}int main()
{int min = INT_MAX;int max = 0;int m;//组成个数int s;//数cin >> m;cin >> s;//排除无解if(s > m * 9 || s == 0 && m > 1){cout << "-1 -1" << endl;}else{backtrack1(m, s, 0);cout << result2 << " " << result1 << endl;  }return 0;
}

原理思路：

        不要用回溯，数据过大就会超时的，比如100，100。就不解释这种方法了，而且麻烦又不对。

贪心：

#include <bits/stdc++.h>
using namespace std;int main()
{int m;//组成个数int s;//数cin >> m;cin >> s;//排除无解if((s > m * 9) || (s == 0 && m > 1)){cout << "-1 -1" << endl;}else{int sum = s;string a(m, ' ');//最大string b(m, ' ');//最小for(int i = 0; i < m; i++){int t = min(sum, 9);a[i] = t + '0';sum -= t; //用过的去掉}sum = s;//别忘了这里再给sum赋一下值for(int i = m - 1; i > 0; i--){int t = min(sum - 1, 9);//9 和 sum 之间取最小,给最高位至少留一个1，最高位不能为0,当然最高位不一定为1b[i] = t + '0';sum -= t;}b[0] = sum + '0';//最后把第一位添上cout << b <<" "<< a;}return 0;
}

原理思路：

        求最大，就从第一位开始取，能取多大取多大，最大不是 9 么，但是肯定不能超过 sum 吧，所以就在这两个之间取最小就行。

        求最小，正好相反，从最后一位开始取，记得sum要留一个1，因为首位不能为 0 吧，所以最小就为1，不过首位也不一定为 1，所以最后剩多少就直接赋值就行。

4808. 构造字符串

问题描述：

        给定一个长度为 n 的由小写字母构成的字符串 t 以及一个整数 k。

请你构造一个字符串 s，要求：

1. 字符串 s 恰好有 k 个子串等于字符串 t。
2. 字符串 s 的长度尽可能短。

保证一定存在唯一解。

实现代码与解析：

kmp：

#include <bits/stdc++.h>
using namespace std;
int main()
{int n;string s;int k;cin >> n;cin >> k;cin >> s;string result = "";//求next数组vector<int> next(n, 0);int j = 0;next[0] = 0;for (int i = 1; i < n; i++){while (s[i] != s[j] && j > 0) j = next[j - 1];if (s[i] == s[j]) j++;next[i] = j;}string diff = s.substr(0, n - next[n - 1]);//后缀部分//把非后缀部分先重复 k  加上for (int i = 0; i < k  ; i++){result += diff;}result += s.substr(0, next[n - 1]);//最后再加一个最长公共后缀cout << result << endl;
}

原理思路：

        很简单啊，明显就是kmp，当然可能也有其他做法吧，kmp找出最长公共前后缀，然后找规律就可以，根据样例，可以看出，可以结果先加上非后缀部分 k 个，然后补上后缀，或则先加上前缀，然后再加上 k 个非前缀部分，一样的，找个规律而已。例如例子一中，可以 a ba ba ba ba这样或则 ab ab ab ab a 这样模拟，都可以。其他就没什么了，会 kmp 这题就应该会了，要是不会就建议去网上查一下，kmp 不同习惯的写法也不一样。