5.字符排序（逆序对（难））

#include
using namespace std;
int V , len , now , cnt[27] , sum[27];
int get_max(int len){return ((len - (len / 26 + 1)) * (len / 26 + 1) * (len % 26) + (26 - len % 26) * (len / 26) * (len - len / 26)) / 2;
}
bool check(int x , int n){//当前位置i放x字母后，后面的n个位置是否符合要求 memset(cnt , 0 , sizeof(cnt));//cnt记录后面n个位置放置的对应字符数量int add1 = 0 , add2 = 0;for(int j = 26 ; j >= x + 1 ; j --) add1 += sum[j];//1~i-1里边比当前插入字符大的字符数量sum[x] ++ ;//当前字符数量增加1for(int L = 1 ; L <= n ; L ++){//当前位置i放了x,看当前位置i后面剩下的n个位置能不能放好字母使得达到V的条件，这是一个预测过程 //ma保存i位置后面的n个位置能增加的最大逆序对个数 L-1-cnt[j]+num//L-1-cnt[j]是当前字符之后的比当前字符小的字符数量的最大值//num是1~pos+L-1前的比当前放置字符字典序大的字符数量int ma = -1 , pos = 0 , num = 0;for(int j = 26 ; j >= 1 ; j --){//枚举i位置后面的n个位置，每个位置放什么字母 if(L - 1 - cnt[j] + num > ma){//L - 1是算i+1到i+L的个数(不算i+L自己) // - cnt[j] 如果在i+1到当前位置i+L前有放过字母j，然后当前位置i+L也尝试放j，//那当前位置不和前面放j的位置构成逆序对 要减掉前面放j的位置个数 ma = L - 1 - cnt[j] + num;pos = j;//在L这个位置放上字母j }num += sum[j];//num是从1-i位置里大于等于j的数的个数 //因为j是从26逆着放到1的 到下一轮循环时，j--假设记为j'，那要求的1-i里比j'大的数就是num //那么这个j'会和前面已经确定好的所有属于26~(j'+1)的数构成逆序对//其实最后的num是算的所有大于等于1的个数，但是没关系，它不会更新到ma里 }add2 += ma , cnt[pos] ++;//L这个位置确定下来，放pos这个字母 }if(now + add1 + add2 >= V) {//now是i这个位置以前的所有逆序对个数,//add1是i位置放进x后,x与前面所有字母构成的逆序对 //add2是i位置放进x后，后面的位置的所有数能增加的逆序对个数，分为2部分，//1、后面位置所有的数与1~i部分的数构成的逆序对个数//2、后面所有位置L，分别与从i+1~i+L-1之间的数构成的逆序对个数，然后这些逆序对的和 now += add1;//now更新i位置确定好放字母x后，从1~i位置所有逆序对个数 return true;}else {//i这个位置放x不能使逆序对个数>=V sum[x] -- ;return false;}
}
signed main()
{string ans = "";cin >> V;for(int i = 1 ; ; i ++) {if(get_max(i) >= V){//i这个长度的字符串最多能有get_max(i)个逆序对 如果get_max(i) >= V，//那么i这个长度就是我们需要的最短长度 len = i;break ;}}for(int i = 1 ; i <= len ; i ++){//按长度从左往右尝试放字母 for(int j = 1 ; j <= 26 ; j ++){//按顺序'a'-'z' 26个字母放   先用1-26代表这26个字母 if(check(j , len - i)){//现在是在第i位放j字母  看i后面的len-i个字母能否符合条件 ans += char(j + 'a' - 1);//符合条件就把j放在i这个位置 break ;//然后尝试放下一个位置 }}}cout << ans << '\n';return 0;
}

6.子串分值和（哈希表+子串小推导）

思路：
原始思路是枚举所有的子串，然后对每个子串进行求值，最后求和。但是这样会超时。

换个方法：枚举所有字符，累加另包含当前字符的子串数目。

#include 
#include
#include
#includeusing namespace std;const int N = 1e6 + 10,INF=0x3f3f3f3f;
int visited[1000];
long long int sum = 0;
int main()
{string s;cin >> s;memset(visited, -INF, sizeof visited);//我们要算出每个字母的贡献值累加即可//（1）当前字母如果在前面出现过，那么以最近一次出现该字母后面的一个字母为起点，字符串最后一格字符为终点。当前字母将//起点到终点分为两个部分，两个部分相乘即可for (int i = 0; i < s.length(); i++){//枚举到当前字符，以当前字符为中心将字符串分为两个部分long long int L, R;  //L表示左边的字符个数，R右边.左右相乘if (visited[s[i]] <0)  //说明该字符前面没有出现过。{L = i + 1;R = s.length() - i;}else   //否则出先过，应该从最近一次出现的后一个字符作为起始字符{L = i - visited[s[i]];R = s.length() - i;}sum += L * R;   //左右相乘visited[s[i]] = i;   //更新当前字符的位置}cout << sum << endl;return 0;
}

7.游园安排(最长不上升子序列dp）

#include 
#include
#include
using namespace std;const int N = 1e5 + 10;
int dp[N];  //dp[i]=j表示
string s[N];   //s[1]表示第一个名字
int path[N];  //存放路径
int a[N];   //存放路径int main()
{string str;cin >> str;int k = -1;for (int i = 0; i < str.length(); i++)  //预处理字符串 ,先预处理一下名字，将其放入一个string数组{if (str[i] >= 'A' && str[i] <= 'Z'){k = k + 1;s[k]+=str[i];}elses[k]+=str[i];}//初始化dpfor (int i = 0; i <= k; i++)  //k个名字dp[i] = 1;memset(path, -1, sizeof path);memset(a, -1, sizeof a);int start = 0;int res = 0;for (int i = 0; i <= k; i++){string temp="";for (int j = 0; j < i; j++){if (s[i]>s[j])  //要严格满足s[i]>s[j]才行{if (dp[j] + 1 > dp[i]){dp[i] = dp[j] + 1;path[i] = j;temp = s[j];  //将最新的s[j]保存}elseif (dp[j] + 1 == dp[i])  //如果等于，取最小的s[j]{if (temp>s[j])  //如果temp>s[j]，说明temp比当前的s[j]大，我们要取小的{path[i] = j;temp = s[j];}}}}if (dp[i] > res){res = dp[i];start = i;}elseif (dp[i] == res)  // 可能有相同长度的子序列，需要挑选出字典序最小的{if(s[start]>s[i])  //如果之前的最小字典序的子序列大于等于当前的子序列,我们优先选择小的start = i;} }int i = 0;while (start != -1){a[i++] = start;start = path[start];}for (i = res - 1; i >= 0; i--)cout<