在哪网站建设,西湖区外贸网站建设,英文企业网站建设,什么优化目录
4806. 首字母大写
题目描述#xff1a;
实现代码#xff1a;
4807. 找数字
题目描述#xff1a;
实现代码#xff1a;
回溯#xff08;超时#xff09;#xff1a;
原理思路#xff1a;
贪心#xff1a;
原理思路#xff1a;
4808. 构造字符串
问题…目录
4806. 首字母大写
题目描述
实现代码
4807. 找数字
题目描述
实现代码
回溯超时
原理思路
贪心
原理思路
4808. 构造字符串
问题描述
实现代码与解析
kmp
原理思路 4806. 首字母大写
题目描述 给定一个由大小写字母构成的单词。
如果单词的首字母为小写字母则请你将该首字母转换为对应大写字母。
如果单词的首字母为大写字母则不做任何变化。
输出最终的单词。 实现代码
#includebits/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;}
}
或则直接这样写
#includebits/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;//求最小
vectorint 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;
}
原理思路 不要用回溯数据过大就会超时的比如100100。就不解释这种方法了而且麻烦又不对。
贪心
#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要求
字符串 s 恰好有 k 个子串等于字符串 t。字符串 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数组vectorint 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 不同习惯的写法也不一样。
