1042 模拟

permutation 排列
题目大意： 洗牌 。54张牌的初始序列为[1,…54]。给出每次改变的位置，即将第i个位置的牌挪到第a[i]个位置上。 循环往复。 输出最终的序列。

#include<iostream>
#include<vector>
using namespace std;

char s[5] = {\'S\',\'H\', \'C\', \'D\', \'J\'};
int k; //k<=20 重复次数
vector<int> v(55), a(55),temp;

void shuchu(){
	for(int i=1;i<=54;i++){
		if( i != 1 ){
			cout<<\" \";
		}
		cout<<s[(a[i]-1)/13];
		a[i]%13 == 0? cout<<13 : cout<<a[i]%13;
	}
}

int main(){
	cin>>k;
	for(int i=1;i<=54;i++){
		cin>>v[i];
		a[i] = i;
	} 
	for(int i=1;i<=k;i++){
		temp.clear();
		temp.resize(55);
		for(int i = 1;i<=54;i++){
			temp[v[i]] = a[i];
		}
		for(int i = 1;i<=54;i++){
			a[i] = temp[i];
		}
	}
	shuchu();
	return 0;
}

1043 排序二叉树

题目大意： 已知先序遍历，说明他是排序二叉树还是排序二叉树的镜像（即交换左右子树）； 若是 排序二叉树还是排序二叉树的镜像 ，则输出 后序遍历。 若不是，输出NO。
思路：

• 如果第二个数字小于（大于等于）第一个数字，则推测是排序二叉树（镜像二叉树），因为第二个数字是左孩子，一定比根节点小。（排除递增或者递减序列，这样根本无法判断）。
• 然后将序列重新排序，因为是排序二叉树，因此中序遍历一定是个递增（递减）序列。找到第一个大于根节点的数字，则是右子树的开始，递归查找左右子树。对于排序二叉树（镜像）来说，若左子树出现大于等于（小于）根节点的值，则输出NO，若右子树出现小于（大于等于）根节点的值，则输出NO。
• 若输出YES，递归输出后序遍历。值得注意的是，在每次在中序遍历的数组中查找根节点的时候，排序二叉树找的是 第一个 等于 前序遍历的第一个值 得数。镜像二叉树找的是 最后一个 等于 前序遍历的第一个值 得数。

关于一个排序二叉树的小插曲 >>>点击<<<

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n; //<=1000
vector<int> pre, in, post;
bool flag = true; 
int is = 0;
 
void check1(int root, int end){
	if(root >= end) return;
	int p = root + 1, rst;
	while( p < end && pre[root] <= pre[p] ) p++;
	for(rst = p; p < end; p++){
		if(pre[root] <= pre[p]){
			flag = false;
			return;
		}
	}
	check1(root+1, rst); //检查左
	check1(rst, end); //检查右 
	return;
}

void check2(int root, int end){
	if(root >= end) return;
	int p = root + 1, rst;
	while( p < end && pre[root] > pre[p] ) p++;
	for(rst = p; p < end; p++){
		if(pre[root] > pre[p]){
			flag = false;
			return;
		}
	}
	check2(root+1, rst); //检查左
	check2(rst, end); //检查右 
}

void reverse(int prep,int preq, int inp, int inq){
	if(prep >= preq || inp >= inq) return;
	int inroot;
	for(inroot = inp; inroot < inq; inroot++){
		if(pre[prep] == in[inroot]){
			if(is == 1){ // 如果是镜像，找到相同的值得最后一个 
				for(int i = inroot+1; i<inq; i++){
					if(pre[prep] != in[i]){
						inroot = i-1;
						break;
					}
				}
			}
			break;
		}
	}
	reverse(prep+1, prep + 1 + inroot - inp , inp, inroot );
	reverse(prep + 1 + inroot - inp, preq, inroot +1, inq );
	post.push_back(pre[prep]);
}

int main(){
	
	cin>>n;
	pre.resize(n);
	in.resize(n);
	for(int i=0;i<n;i++){
		cin>>pre[i];
	}
	in = pre;
	
	if(pre[0] <= pre[1]){//是镜像 
		is = 1;
		sort(in.begin(), in.end(), greater<int>() ); //从大到小即是中序遍历。
		check1(0,n); 
	}else{
		sort(in.begin(), in.end()); //从小到大即是中序遍历。
		check2(0,n); 
	}
	if(!flag){
		cout<<\"NO\"<<endl;
	}else{
		cout<<\"YES\"<<endl;
		reverse(0,n,0,n);
		for(int i=0;i<n;i++){
			if(i!=0){
				cout<<\" \";
			}
			cout<<post[i];
		}
	}	 
	return 0;
} 

1044 尺取法

题目大意： 找到所有和为m的连续子序列。若找不到， 找到大于m的最小和 ，输出所有结果。

#include<iostream>
#include<vector>
using namespace std;

typedef struct node{
	int p,q;
}node;

int main(){
	int n, m; // n<=10^5, m<=10^8
	cin>>n>>m;
	vector<int> v(n);
	for(int i=0;i<n;i++){
		cin>>v[i];
	}
	
	bool flag = false;
	int sum = 0;
	for(int p=0,q=0; p<n && q<n+1; ){ 
		if( sum == m){
			cout<<p+1<<\"-\"<<q<<endl;
			flag = true;
			sum -= v[p];
			p++;
		}else if(sum < m){
			sum += v[q];
			q++;
		}else{
			sum -= v[p];
			p++;
		}
	}
	
	if(!flag){
		vector<node> ans;
		int sum = 0, min = 99999999;
		for(int p=0,q=0; p<n && q<n+1; ){ 
			if( sum > m){
				//cout<<sum<<\" \"<<min<<endl;
				if(sum < min){
					min = sum;
					ans.clear();
					node temp;
					temp.p = p+1, temp.q = q;
					ans.push_back(temp);
				}else if(sum == min){
					node temp;
					temp.p = p+1, temp.q = q;
					ans.push_back(temp);
				}
				sum -= v[p]; 
				p++;
			}else if(sum < m){
				sum += v[q];
				q++;
			}else{
				sum -= v[p];
				p++;
			}
		}
		for(int i=0; i<ans.size(); i++){
			cout<<ans[i].p<<\"-\"<<ans[i].q<<endl;
		} 
	}
	return 0;
} 

1045 动态规划

题目大意： 给出一串数字A，和一串数字B；想让A中的数字只能是B中的数字的最长子字符串。找最长不下降子字符串。 结果不唯一，只需输出最长的长度。例如：

• 给出A= {2 2 4 1 5 5 6 3 1 1 5 6}, B= {2 3 1 5 6}。
• 找出的最长字符串为 {2 2 1 1 1 5 6}, {2 2 1 5 5 5 6}, {2 2 1 5 5 6 6},和{2 2 3 1 1 5 6}。
• 因此答案为7。

思路： 将每个喜欢的颜色按照输入顺序编号，转化成最长不下降子序列。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	int n, m, x;
	cin>>n>>m; //n<=200,颜色编号从1...n 
	vector<int> fav(n+1); 
	bool visit[205];
	for(int i=1;i<=m;i++){
		cin>>x;
		fav[x] = i; //存入编号 
		visit[x] = true;
	} 
	int l; // l<= 10^4
	cin>>l;
	vector<int> v(l+1);
	int num = 0;
	for(int i=0;i<l;i++){
		cin>>x;
		if(visit[x] == true){ //剔除不喜欢的 
			v[num++] = fav[x];
		}
	}
	
	//按照最长不下降子序列 
	int dp[10005];
	int ans = 0;
	for(int i = 0; i < num; i++){
		dp[i] = 1;
		for(int j = 0; j < i; j++){
			if(v[i] >= v[j]){
				dp[i] = max(dp[i], dp[j]+1);
			}
		}
		ans = max(dp[i], ans);
	}
	
	cout<<ans;
	
	return 0;
}