B. Neutral Tonality 寒假思维训练计划day8

一道cf的构造题，休息一天，今天开始恢复更新。

题目链接：Problem - B - Codeforces

还是老样子，附上我的思维题一点浅薄的总结:

每日回顾一次（刷题还是要多总结，让自己有印象，即使是想到了多总结也有很多好处）：

?1、前后缀贪心，比如说观察前后缀的sum，去看以后怎么考虑最好。Problem - 1903C - Codeforces

2、双指针贪心法，考虑两端相消或者相互作用，还有就是考虑左右边界。? ?Problem - 1891C - Codeforces

Problem - 1907D - Codeforces

3、转换观察法，有些关系可以抽象成图，观察图的某些性质去总结规律。也可以抽象成一个集合，两个集合相等可以说明有解可构造。Problem - 1891C - Codeforces

4、打表找规律，一般没什么规律可循即可打表找规律，一般和数论有关的很喜欢考，acm也喜欢考，属于人类智慧题。Problem - 1916D - Codeforces

5、公式推导演算，常见的分为公式的等价变形、公式的化简（这个常考，一般需要先证明某些性质，可以直接抵消，一般如果原公式处理起来很复杂时就可以考虑）。Problem - 1889B - Codeforces

6、考虑奇偶数去简化问题或者分类问题，从其中的一些运算性质入手，因为奇数偶数的加减以及%运算（这个结论很重要）的结果的奇偶性是固定的，Problem - 1898C - Codeforces

7、根据性质构造模型，看看能不能分成几个块，几个不同的集合，再选择算法去解决。Problem - 1873G - Codeforces

8、考虑从小到大处理，或者是从大到小处理，有时候先处理小的对大的不会有影响，或者反过来，这样的处理顺序是最完美的。Problem - 1904D2 - Codeforces

9、边界贪心法，一般要在问题的最边界处考虑，有时候这样做结果是最优的，或者考虑边界上的影响，假如让影响最小，就使得影响<= 固定值 。???????Problem - E - Codeforces?and?Problem - 1903C - Codeforces

day8（思维 + 构造 + 贪心，模型：边界贪心法）题目链接： Problem - B - Codeforces

题意：
给定一个长度为n的序列a和序列b，要求再序列a的任何位置插入序列b的元素，使得最后的序列最长上升子序列最短，a序列是该序列的子序列，b的元素随意放置。

题解：
设目标序列是q, a是子序列，假设先放入a的所有元素，那么因为a是q的子序列，所以a的每一个数开头的最长上升子序列都是固定<=此时的长度，当加入b的元素，考虑当前位置，应该在当前位置前面放置>=当前位置a元素的值，而且是倒序的放，这样能保证这些元素包括当前位置的元素一定<=当前位置的最长上升子序列长度。最后可能剩下一些元素，那显然他们满足小于前面所有数字的性质，那将他们倒序放入结尾即可不会缠上新长度的上升序列长度。

代码：

代码非常简单，主要是理解贪心的每一步为什么是最好的，他和"边界"的微妙关系：

#include <bits/stdc++.h> 
#define int long long 
#define ff first 
#define ss second 
using namespace std; 
using PII = pair<int,int>;
const int N = 2e5 + 10; 
int n, m; 
int a[N], b[N];
void solve() {
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> a[i]; 
    for(int i = 1; i <= m; i ++ ) cin >> b[i]; 
    vector<int> ans;
    sort(b + 1, b + 1 + m); 
    int l = m + 1; 
    for(int i = 1; i <= n; i ++ ) {
        int x = a[i]; 
        while(l - 1 >= 1 && b[l - 1] >= x) 
            ans.push_back(b[-- l]); 
        ans.push_back(x);
    }
    while(l - 1 >= 1) ans.push_back(b[-- l]);  
    for(auto t : ans) cout << t << ' ';
    cout << endl;
}
signed main() {
    
    int ts; 
    
    cin >> ts; 
    while(ts --) solve();
    
    return 0;
}

?