被同学叫去打蓝桥杯模拟赛，蛮简单的，但最后两个题目尽然没有思路，暴力骗了大部分的分，遛了。

试题I：调皮的JM 25’

描述

在竞码小学，JM同学是捣蛋三巨头之一，调皮的很。

有一次，在课外活动的时候，JM同学偷偷跑到老师办公室玩耍，一不小心把英语老师电脑上准备上课用的英文文章给删掉了，导致英语老师暴跳如雷，生气的很~

老师给了JM一个改过自新的机会，如果JM能够找出删除的文章HH中出现了多少个子串与字符串SS等价，那么老师将原谅JM同学，否则，请家长是免不了的~

对于两个字符串等价，我们的定义为：两个字符串按照字典序排序后相同，则认为是等价字符串。

例如：aabaab 和 baabaa 两个字符串为等价字符串

abaaba 和 bbabba 则不是等价字符串。

输入

第一行输入一个字符串SS

第二行输入一个字符串HH

输出

输出子串个数

样例

输入复制

1 2	aab abacabaa

输出复制

提示

样例解释

第一个等价子串 abacabaa

第二个等价子串 abacabaa

第三个等价子串 abacabaa

数据规模

对于50\%50%的数据，|S|,|H| <= 2000∣S∣,∣H∣<=2000

对于100\%100%的数据，|S|,|H| <= 100000∣S∣,∣H∣<=100000，保证输入的字符串只有小写字母

因为子序列，所以统计字母个数即可，在加前缀和优化。

s1=input().strip()
s2=input().strip()

num1=[[0 for j in range(0,26)] for i in range(len(s1)+1)]
num2=[[0 for j in range(0,26)] for i in range(len(s2)+1)]


for i in range(len(s1)):
    for j in range(0,26):
        num1[i+1][j]=num1[i-1+1][j]
    num1[i+1][ord(s1[i])-ord('a')]=num1[i-1+1][ord(s1[i])-ord('a')]+1
        


for i in range(len(s2)):
    for j in range(0,26):
        num2[i+1][j]=num2[i-1+1][j]

    num2[i+1][ord(s2[i])-ord('a')]=num2[i-1+1][ord(s2[i])-ord('a')]+1



ans=0
for i in range(len(s2)):
    j=i+len(s1)-1
    if j>=len(s2):break
    flag=1
    for k in range(26):
        if num2[j+1][k]-num2[i-1+1][k]!=num1[len(s1)][k]-num1[0][k]:
            flag=0
            break
    if flag==1:
        ans+=1

print(ans)

试题J：冷嘲热讽 25’

描述

JM自从学习了约瑟夫问题，就特别感兴趣，研究了很久。设计了一个类似的游戏，取名叫做冷嘲热讽。

总共有NN个人参与游戏，一字排开，从左往右编号1，2，…，N1，2，…，N，每一个人初始有一个能力值A_iA**i。

每一轮，每一个人同时向嘲讽右边的人，如果被嘲讽的能力值比嘲讽的人大(A_i < A_{i + 1}A**i<A**i+1)，则被嘲讽的人淘汰出局。

一轮结束，没被淘汰的人向左靠齐，调整站位，重新编号1，2，…，1，2，…，，进入下一轮。

当不再会有人被淘汰时，游戏结束。

现在JM想知道，这个游戏要多少轮才会结束。你能帮帮他吗？

输入

第一行输入11个整数NN，表示总共有NN个人参加游戏。

第二行NN个整数A_iA**i。

输出

一个整数，表示游戏要多少轮才会结束。

样例

输入复制

1 2	7 6 5 8 4 7 10 9

输出复制

输入复制

1 2	5 2 4 6 8 3

输出复制

输入复制

1
2

3
3 2 1

输出复制

提示

样例1解释

初始状态：6 5 8 4 7 10 9

第一轮：6 5 4 9

第二轮：6 5 4

样例2解释

初始状态：2 4 6 8 3

第一轮：2 3

第二轮：2

数据规模

30\%30%的数据，满足1≤N≤10^41≤N≤104;

50\%50%的数据，满足 1≤N≤10^51≤N≤105;

100\%100%的数据，满足1≤N≤10^6, 0≤Ai≤10^91≤N≤106,0≤A**i≤109.

解析

可以发现，对于每一个数x，如果其左边有比他小的数，则一定会被淘汰。

思考一下，x*x在第几轮被淘汰~

当进行到某一轮，左边相邻的连续比xx的数都被淘汰掉了之后,下一轮x就会被淘汰了~

所以只要求出这一段区间最晚被淘汰的是谁即可~

这一段区间通过单调栈来维护，最晚被淘汰如果通过区间最大值来计算，会多一个log,可以在单调栈的过程种同时维护.

时间复杂度：O(n)

n=int(input())

a=list(map(int,input().split()))

sta=[[0,0] for  i in range(0,n+1)]
tt=0

ans=0 
for i in range(n-1,-1,-1):
    cnt=0
    while tt!=0 and sta[tt][0]> a[i]:
        cnt=max(cnt+1,sta[tt][1])
        tt-=1
    ans=max(cnt,ans)
    tt+=1
    sta[tt]=[a[i],cnt]
    #print(sta)
print(ans)

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, ans;
int stk[N], st[N], tp;
int main()
{
	cin >> n;
	for (int i = 0; i < n; i ++ )
	{
		int x, cnt = 0;
		cin >> x;
		while (tp && stk[tp] >= x)
		{
			cnt = max(cnt, st[tp]);
			tp -- ;
		}
		if (!tp) cnt = -1;
		stk[ ++ tp] = x;
		st[tp] = cnt + 1;
		ans = max(ans, cnt + 1);
	}
	
	cout << ans << endl;
	
	return 0;
}