惠州网站建设领头,焦作焦煤电子商务网站建设,网站如何做内部链接,营销一体化平台题目描述 L \mathrm{L} L 星球游乐园非常有趣#xff0c;吸引着各个星球的游客前来游玩。小蓝是 L \mathrm{L} L 星球 游乐园的管理员。
为了更好的管理游乐园#xff0c;游乐园要求所有的游客提前预约#xff0c;小蓝能看到系统上所有预约游客的名字。每个游客的名字由一…题目描述 L \mathrm{L} L 星球游乐园非常有趣吸引着各个星球的游客前来游玩。小蓝是 L \mathrm{L} L 星球 游乐园的管理员。
为了更好的管理游乐园游乐园要求所有的游客提前预约小蓝能看到系统上所有预约游客的名字。每个游客的名字由一个大写英文字母开始后面跟 0 0 0 个或多个小写英文字母。游客可能重名。
小蓝特别喜欢递增的事物。今天他决定在所有预约的游客中选择一部分游客在上午游玩其他的游客都在下午游玩在上午游玩的游客要求按照预约的顺序排列后名字是单调递增的即排在前面的名字严格小于排在后面的名字。
一个名字 A A A 小于另一个名字 B B B 是指存在一个整数 i i i使得 A A A 的前 i i i 个字母与 B B B 的前 i i i 个字母相同且 A A A 的第 i 1 i1 i1 个字母小于 B B B 的第 i 1 i1 i1 个字母。(如果 A A A 不存在第 i 1 i1 i1 个字母且 B B B 存在第 i 1 i1 i1 个字母, 也视为 A A A 的第 i 1 i1 i1 个字母小于 B B B 的第 i 1 i1 i1 个字母)
作为小蓝的助手你要按照小蓝的想法安排游客同时你又希望上午有尽量多的游客游玩请告诉小蓝让哪些游客上午游玩。如果方案有多种请输出上午游玩的第一个游客名字最小的方案。如果此时还有多种方案请输出第一个游客名字最小的前提下第二个游客名字最小的方案。如果仍然有多种依此类推选择第三个、第四个……游客名字最小的方案。
输入格式
输入包含一个字符串按预约的顺序给出所有游客的名字相邻的游客名字之间没有字符分隔。
输出格式
按预约顺序输出上午游玩的游客名单中间不加任何分隔字符。
样例 #1
样例输入 #1
WoAiLanQiaobei样例输出 #1
AiLanQiaobei提示
对于 20 % 20 \% 20% 的评测数据, 输入的总长度不超过 20 20 20 个字母。
对于 50 % 50 \% 50% 的评测数据, 输入的总长度不超过 300 300 300 个字母。
对于 70 % 70 \% 70% 的评测数据, 输入的总长度不超过 10000 10000 10000 个字母。
对于所有评测数据, 每个名字的长度不超过 10 10 10 个字母, 输入的总长度不超过 1 0 6 10^6 106 个字母。
蓝桥杯 2020 年国赛 B 组 G 题。
题目解读
求一些字符串的LIS最长上升子序列
算法分析
先按题目给出的大写字母开头的子串是人名把字符串分割成若干个子串每串是由大写字母开头的中间没有其他大写字母。
然后用 DP 大法算出 LIS 长度
由于数据大要有二分优化不然等着 TLE吧
用 lower_bound 函数优化每一次更新
连我这种蒟蒻都会的 DP
这就完美的 AC 了
虽然题目说用字典树(Trie)但完全不需要
#includebits/stdc.h
using namespace std;
string s,a[1000010],dp[1000010],f[1000010];
int n0,maxl0,t0;
int main()
{ios::sync_with_stdio(false); //优化cincout其实没必要cins;int ps.size();for(int i0;ip;i) //拆解成若干个子串 {if(s[i]a) {a[n]s[i];}else {a[n]s[i];}}for(int i1;in;i) //DP{tlower_bound(dp1,dpmaxl1,a[i])-dp;maxlmax(maxl,t);dp[t]a[i];f[t]f[t-1]a[i];}coutf[maxl];return 0; //完结撒花
}最近甲流写不了代码这是最后一篇存货
下一次更新估计要等下次 周五
