一个大大的分割线，如果这个傻逼题没有被作为某某复赛的签到题，可能我一会都一直傻逼下去了。

【2019计蒜之道复赛——星云系统】

题目是，给出一个长度为n(1<n<5e6)的只有小写字母的字符串，然后找出一个长度为m的最小字典子序列。

更新： 这是一道简单得要死掉的单调栈裸题，为什么没想到呢，因为思路是，利用单调栈尽量求取结果字符串的最优值，也就说结果字符串在理想情况下是递增的，但是非理想情况是什么呢？因为有必须限定k个字母存在，因此被删掉的字母数量为len-k个字符，当被单调栈弹出的字符数量达到n-k个时，剩余的字符【即单调栈中的递增字符以及未遍历到的剩余字符】就组成了最小字典序ans。
散了散了。。。时间复杂度是线性扫描的O(n)

想想也是，题面都这个数量级了，还要啥常数。线性就完了。
#include<bits/stdc++.h>
#define M(a,b) memset(a,b,sizeof a)
#define LL long long
using namespace std;
const int maxn=5000007;
char a[maxn];
stack<char>q;
int n,m;
int main()
{
    while(!q.empty())q.pop();
    scanf("%s %d",a,&m);
    n=strlen(a);
    int cnt=0;
    int flag=n;
    for(int i=0; i<n; i++)
    {
        if(q.empty())q.push(a[i]);
        else
        {
            if(a[i]>q.top())q.push(a[i]);
            else
            {
                while(!q.empty()&&q.top()>a[i])
                {
                    q.pop();
                    cnt++;
                    if(cnt>=n-m)
                    {
                        flag=i;
                        break;
                    }
                }
                q.push(a[i]);
            }
        }
        if(cnt>=n-m)break;
    }
    string ans="";
    for(int i=n-1;i>flag;i--)ans+=a[i];
    while(!q.empty())ans+=q.top(),q.pop();
    reverse(ans.begin(),ans.end());
    ans=ans.substr(0,m);
    cout<<ans<<"\n";
}


头条一面挂了，除了自己菜，数据结构和基础知识理解不够深刻外，还有就是面试时紧张得肚子疼到抽搐。。。可能是绝症了
言归正传，面试官本来想随便出个签到题玩一下开个场，结果被我紧张的崩了。

结束面试之后冷静下来认真想了下并不难
题目是，给出一个长度为n(1<n<10000)的只有小写字母的字符串，然后找出一个长度为m的最小字典子序列。

如 orange

当m=3时，输出结果age
若borange,且长度为3时，同样输出age
面试的时候脑子一团浆糊，想到了标号和排序，直接被反例否定了。
如果用最暴力的思想，找到n个字符里字典序最小且位序小于等于m的字母，然后砍去这个字母之前的字母，在剩余的字母中又找一个字典序最小的字母，这样一直找m个就好了。

唯一要考虑的条件就是，这样不断贪心取最小的要求是，要保证取了某个字母后，剩余待选串中的字符个数要大于等于m。
于是想到一个 复杂度为O(n*m) 的做法，每次遍历n字符串，查找符合条件的字符，再从头扫一遍找下一个字符。从头扫的原因是，当找到了一个字符，比如b，无法判断是否后面的字符是否存在一个字典序小于b的字符，所以仍要遍历完整个串才能得到一个最小值。这样是不可取的，必须进行优化。
那么做一个预处理，首先26个vector存储每个字母出现位置的下标，O(n)遍历字符串，push进每个字母出现下标，因为是顺序遍历，所以每个vector都是有序的。

然后遍历m次这26个vector，找出第一个字母的出现位置，满足<=n-(m-i)+1,说明存在一个较小的字母符合筛选条件，并且不用关心该位置剩余字符串是否存在比其更小的字母，如果存在，在字典序遍历其他vector就应该找到了。在ans中填入这个字母，然后从a字母开始继续查找下标大于上一个填入ans中字母下标的符合条件的字母。这个在有序vector中查找位置直接用二分即可。

最后时间复杂度O(26*m),空间复杂度O(n)

代码如下：
#include<bits/stdc++.h>
using namespace std;
char a[10080];
vector<int>pos[26];
int main()
{
    int n,m;
    char ans[10080];
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<=26;i++)pos[i].clear();
        scanf("%d",&m);
        scanf("%s",a);
        for(int i=0; i<n; i++) pos[a[i]-'a'].push_back(i+1);
        memset(ans,0,sizeof ans);
        int tmp=0;
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<26; j++)
            {
                if(pos[j].size()!=0)
                {
                    int num=pos[j][upper_bound(pos[j].begin(),pos[j].end(),tmp)-pos[j].begin()];
                    if(num>tmp&&num<=n-m+i+1)
                    {
                        tmp=num;
                        ans[i]='a'+j;
                        break;
                    }
                }
            }
        }
        printf("%s\n",ans);
    }
}

题目（软考-软件设计师2006上半年上午试题）：对于求取两个长度为n的字符串的最长公共子序列（LCS）问题，利用（57）策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O（n2）的正确算法。串<1,0,0,1,0,1,0,1>和<0,1,0,1,1,0,1,1>的最长公共子序列的长度为
 （58） 。 
（57）A．分治　　　 　　 　 　B．贪心　　　　 C．动态规划　　　　　 D．分支一限界 

（58）A．3　　　　　 　　　 　B．4　　　　 　 C．5　　 　　　　 　　D．6
一直没有找到自己认为合理的解释，今天看到一种解答方式，觉得有道理，特此引用，感谢解答人。以下为引用内容（引用自：http://bbs.educity.cn/bbs/1695.html  heyunyi 2006-10-31
 9:57:16）
题目中说的“子序列”是这样定义的：从给定字符序列中随意地（不一定连续）去掉若干字符（也可以一个都不去掉）后形成的字符序列。可见“最长公共子序列”指的是某两个字符串最长的公共子序列。该题中，删除串<1,0,0,1,0,1,0,1>的第2、7个字符得101011，删除串<0,1,0,1,1,0,1,1>的第1、5个字符得101011，可见101011是两串的最长子序列。

答案为：57 C,58 D

题目描述

小z玩腻了迷宫游戏,于是他找到了Easy,准备和Easy玩这么一个游戏

小Z准备了一个字符串S (S的长度不超过10000)

又准备了M个小的字符串(M最大不超过1000000,每个小字符串的长度不超过10)

现在小z想请教Easy老师,M个小字符串中有多少个小字符串是大字符串S的子序列?

如果Easy老师答不上来就要请客,现在Easy老师很苦恼,你能帮帮他吗?

子序列可以理解为不要求连续的子串,若还是不了解请看下面的链接中,最佳答案的回答

https://zhidao.baidu.com/question/120638124.html

输入

只有一组测试数据

第一行是大字符串S(S的长度不超过10000)

第二行是一个整数M,表示小字符串的个数(M最大不超过1000000)

接下来M行每行给出一个小字符串(长度不超过10)

保证没有空字符串

输出

输出只有一个整数,代表M个小字符串中是大字符串S的子序列的个数

样例输入

amrocegijgyvkgarnffb
4
i
jsj
qg
ac

样例输出

2

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<bitset>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define eps (1e-8)
#define MAX 0x3f3f3f3f
#define u_max 1844674407370955161
#define l_max 9223372036854775807
#define i_max 2147483647
#define re register
#define pushup() tree[rt]=max(tree[rt<<1],tree[rt<<1|1])
#define nth(k,n) nth_element(a,a+k,a+n);  // 将 第K大的放在k位
#define ko() for(int i=2;i<=n;i++) s=(s+k)%i // 约瑟夫
#define ok() v.erase(unique(v.begin(),v.end()),v.end()) // 排序,离散化
using namespace std;

inline int read(){
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' & c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

typedef long long ll;
const double pi = atan(1.)*4.;
const int M=1e3+5;
const int N=1e5+5;
char s[N],s1[100];
vector<int>vv[27];
int a[27];
int main(){
    scanf(" %s",s);
    int len=strlen(s);
    for(int i=0;i<len;i++)
        vv[s[i]-'a'].push_back(i);
    for(int i=0;i<27;i++)
        vv[i].push_back(len);

    int n,ans=0;
    scanf("%d",&n);
    while(n--){
        memset(a,0,sizeof(a));
        scanf(" %s",s1);
        int leap=0;
        int len1=strlen(s1);
        int ss=vv[s1[0]-'a'][0];
        if(ss==len)
            continue ;
        a[s1[0]-'a']=1;
        for(int i=1;i<len1;i++){
            int h=lower_bound(vv[s1[i]-'a'].begin()+a[s1[i]-'a'],
                              vv[s1[i]-'a'].end(),ss)-vv[s1[i]-'a'].begin();
            a[s1[i]-'a']=h+1;
            ss=vv[s1[i]-'a'][h];
            if(ss==len){
                leap=1;
                break;
            }
        }
        if(!leap)
            ans++;
    }
    printf("%d\n",ans);
    return 0;
}

 

#include <iostream>
#include <vector>
#include <string>

using namespace std;
/*
		str:	带解析字符串
	iSubLen:	字串的长度
	  index:	起始位置
	iStrLen:	str的长度
	 strSub：	子串
		vec：	存储字串

   函数功能:	求一个字符串任意长度的子序列
*/
void GetSubStrEx(const string& str,int iSubLen,int index,int iStrLen,const string& strSub,vector<string>& vec)
{
	if(index + iSubLen > iStrLen || iSubLen<=0)		// 这种情况下需退出递归
	{
		if(!strSub.empty())
		{
			vec.push_back(strSub);			// 此时，index = iStrLen +1,iSubLen=0
		}		
		return ;
	}

	for(int i=index;i<=iStrLen-iSubLen;i++)
	{
		char ch = str.at(i);
		string strNewSub = strSub;
		strNewSub.append(1,ch);		//从起始位置获得第一个字符
		
		// 下一次递归时，子串长度减1，因为刚刚获得了一个字符，同时，起始位置加1，因为刚刚获得了一个字符
		// 这个位置在下次递归时不可以再获得
		GetSubStrEx(str,iSubLen-1,i+1,iStrLen,strNewSub,vec);
	}	
}
void GetSubStr(const string& str,int iSubLen,vector<string>& vec)
{
	string strSub = "";
	GetSubStrEx(str,iSubLen,0,str.length(),strSub,vec);

	int iSize = vec.size();
	for(int i =0;i<iSize;i++)
	{
		cout<<vec[i]<<endl;
	}
}


main.cpp
	vector<string> vec;
	string str = "ABCDEF";
	GetSubStr(str,3,vec);