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;
}