Zzzzzzz

用户名：uq_39511365652

访问量：173

签　名：

等　　级
排　　名	25420
经　　验	569
参赛次数	1
文章发表	1
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

LIS二分优化 + 倒序输出方案（C++）
浏览：71

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

LIS二分优化 + 倒序输出方案（C++）

　　作者: Zzzzzzz　　　　发表时间：2023-05-09 20:27:10 浏览：71　|　评论：0　

原题链接：蓝桥杯2020年第十一届国赛真题-游园安排

## 思路
找出一个子序列，并且是严格从小到大的子序列，结果需要尽可能的大，其实就是最长上升子序列的另外一种说法，读到这里题目就可以开始分析了。

从数据范围可以知道，最多有1e6个单词，用普通的n^2写法只能拿到70%的分数，显然，要拿到全部的分数，需要用二分优化的写法，并且该题需要输出方案，一般的dp问题输出方案，都是倒序从最终态往最初态逆推，但是该题的二分写法不需要用到状态数组，我们需要一个记录状态的数组record，其中record[i]表示当前位置i是长度为r + 1的上升子序列的最后一个字符串的下标（从0开始），然后我们从最长的LIS长度开始往前逆推即可。

## C++代码
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1000010;

string s;
int record[N], n;
string p[N];
string strs[N];

int main() {
    cin >> s; s += 'A';
    for(int i = 0, prev = -1; i < s.size(); i ++) {
        char c = s[i];
        if(c >= 'A' && c <= 'Z') {
            if(prev != -1) strs[n ++ ] = s.substr(prev, i - prev);
            prev = i;
        }
    }

int len = 0;
    for(int i = 0; i < n; i ++) {
        string t = strs[i];
        int l = 0, r = len;
        while(l < r) {
            int mid = l + r + 1 >> 1;
            if(p[mid] < t) l = mid;
            else r = mid - 1;
        }

if(p[r] >= t) continue;

p[r + 1] = t;
        len = max(len, r + 1);
        record[i] = r + 1; // 当前位置i是长度为r + 1的上升子序列的最后一个字符串的下标
    }

vector<string> res;
    for(int i = n - 1; i >= 0; i --) {
        if(len <= 0) break;
        if(record[i] == len) {
            res.push_back(strs[i]);
            len -- ;
        }
    }

for(int i = res.size() - 1; i >= 0; i --) cout << res[i];
    return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

Zzzzzzz

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言考试练习题_排列（C++代码）

去掉双斜杠注释（C语言代码）

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

C二级辅导-温度转换（C语言代码）

LIS二分优化 + 倒序输出方案（C++）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

钟神赛车（C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言训练-立方和不等式（C语言代码）

简单的a+b （C语言代码）

简单的a+b （C语言代码）

【计算球体积】（C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

DNA （C语言代码）

Zzzzzzz

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言考试练习题_排列 （C++代码）

去掉双斜杠注释 （C语言代码）

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

C二级辅导-温度转换 （C语言代码）

LIS二分优化 + 倒序输出方案 （C++）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

钟神赛车 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言训练-立方和不等式 （C语言代码）

简单的a+b （C语言代码）

简单的a+b （C语言代码）

【计算球体积】 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

DNA （C语言代码）

C语言考试练习题_排列（C++代码）

去掉双斜杠注释（C语言代码）

C二级辅导-温度转换（C语言代码）

LIS二分优化 + 倒序输出方案（C++）

　　评论区

钟神赛车（C语言代码）

C语言训练-立方和不等式（C语言代码）

【计算球体积】（C语言代码）