本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-02-23 09:51:04

感觉很好的一套题目，水题也有意思。

A GamingForces，考察排序与贪心。

B Stand-up Comedian 数学，推式子。

有点意思的递推

#include<bits\/stdc++.h>
using namespace std;
const int N=20;
int a[N],n; 
int work(){
	
	int ans=0,f=0;\/\/ans为进行轮数，f为当前ab最小的分数。
	for(int i=1;i<=4;i++)cin>>a[i];
	if(a[2]>a[3])swap(a[2],a[3]);
	ans=a[1],f=a[1];
	if(f==0){
		ans=min(1,a[2]+a[3]+a[4]);
		return ans;
	}
	int tmp=min(a[3]-a[2],a[1]);\/\/a[3]>=a[2] 
	f-=tmp;
	if(a[3]-a[2]>a[1])ans=a[1]+2*a[2]+a[1]+1;\/\/a,b有a1分，
	else ans=a[1]+2*a[2]+tmp+min(f+1,a[4]);
	return ans;
}
int main(){

	int t;
	cin>>t;
	while(t--){
		cout<<work()<<endl;
	}
} 

C

排序、贪心，分析出成对出现是本题的关键，由内到外连续的升序为可以不动的数对。

\/*
最多操作n\/2次。
最后一次一定操作(1,n),逆序为(2,n-1)...(n\/2,n+1-n\/2)
                 n\/2         n\/2-1..k. 1 
最容易想到的方法是二分答案，模拟从第k次操作开始执行，看能否完成有序排列。
时间复杂度o(nlogn)

在操作的过程中，手工操作发现，
	如果只需要1次操作，那么拿出(1,n)后，数据已经有序。
	同理，如果需要k次操作，那么拿出(1..k) ... (n-k+1,n)后 
	                 剩下的k+1,k+2,...n-k-1,n-k已经有序了。 
	        3 8 1 4 5 2 6 9 7
	删掉19  3 8   4 5 2 6   7
	删掉28  3     4 5   6   7 
	用链表删除吗？删除链表o(1),判断有序o(n)，复杂度太高。
	我们只需要知道剩下的3 4 5 6 7在原始数据中是连续上升子序列即可。
	找数列中最大连续上升子序列的长度。
	我们记录一x的位置，看他是否在x-1的前面。 
*\/ 
#include<bits\/stdc++.h>
using namespace std;
const int N=2e5+9;
int a[N],n; 
int work(){
	int x,ans;
	scanf("%d",&n);
	for(int i=0;i<=n+1;i++)a[i]=0; 
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		a[x]=i;	
	}
	ans=n\/2;
	\/\/1 2  8 9满座这样的条件不用动。
	\/\/从内层结构开始，看是否需要移动 4 5 6  a[4]<a[5]  a[5]<a[6]

	for(int i=n\/2;i>=1;i--){
		if(a[i]<a[i+1]&&a[n-i]<a[n-i+1]){
			ans--;
		}
		else break;
	} 
	return ans; 
	
	
}
int main(){
		int t;
	cin>>t;
	while(t--){
		cout<<work()<<endl;
	}
} 

D Fixed Prefix Permutations

逆向思维，找到一个数列的逆序列，转化为字符串的前缀匹配。利用tire树或者哈希完成。

\/*
 8 10
3 4 9 6 10 2 7 8 1 5
3 9 1 8 5 7 4 10 2 6
3 10 1 7 5 9 6 4 2 8
1 2 3 4 8 6 10 7 9 5
1 2 3 4 10 6 8 5 7 9
9 6 1 2 10 4 7 8 3 5
7 9 3 2 5 6 4 8 1 10
9 4 3 7 5 6 1 10 8 2
p*q=r: r[j]=q[p[j]]
期望得到：q[p[j]]=j
比如：a'*a3=10
j==1: q[3]=1, p1=3;  j=2,q[p[2]]=2,p[2]=9
	p[q[j]]=j
i    :1  2  3  4  5  6  7  8  9  10
a3  q:3  10 1  7  5  9  6  4  2  8
a3' p:3  9  1  8  5  7  4  10 6  2
那么找出a3的逆排列a'
	ai*a3即为ai与a3'的最大前缀,记为：f(ai,a3')。
	ans（ai）=max(f(ai*aj'))
	
算法步骤：贪心求出每一个aj',存入字典序
          对每个ai，查找其在字典序上的最大前缀。 
 
    	 
*\/ 
 
#include<bits\/stdc++.h>
using namespace std;
const int N=5e4+10,M=12;
int t,n,m,trie[800005][11],cnt=1;
int a[N][M];
void insert(int b[]){
	int p=0;
	int temp[M]={0};\/\/p[q[j]]=j
	for(int i=1;i<=m;i++)temp[b[i]]=i;
	for(int i=1;i<=m;i++){
		int v=temp[i];
		if(!trie[p][v])trie[p][v]=cnt++;
		p=trie[p][v];
	}
}
int ask(int b[]){
	int p=0,ans=0;
	for(int i=1;i<=m;i++){
		int v=b[i];
		if(trie[p][v]){
			ans++;
			p=trie[p][v];
		}else break;
	}
	return ans;
}
int main(){
	cin>>t;
	while(t--){
		cin>>n>>m;
		for(int i=0;i<cnt;i++)
			for(int j=0;j<=10;j++)
				trie[i][j]=0;
		cnt=1;
		
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
			insert(a[i]);
		}
		for(int i=1;i<=n;i++){
			cout<<ask(a[i])<<" ";
		}
		printf("\n");
	}
}