Coding Practice，48天强训（29）
这几天好不容易想到五一假期能够有时间多赶下学习进度，结果婚礼的一堆事儿又忙的焦头烂额，计划总是赶不上变化，一步一步慢慢来吧。
Topic 1：排序子序列(模拟 + 贪心)
排序子序列_牛客笔试题_牛客网
#include <bits/stdc++.h>
using namespace std;int main()
{int n; cin >> n;vector<int> A(n);for(int i = 0; i < n; i++) cin >> A[i];int count = 1; // 至少一段int trend = 0; // 0: 未定, 1: 递增, -1: 递减for(int i = 1; i < n; i++) //从1开始，0被视作第1段{if(A[i] > A[i - 1]) // 如果后一个>前一个{if(trend == -1) //之前的趋势如果是递减的{count++;//要从新记一段了trend = 0;//趋势变为均势} else //之前的趋势是均势或者递增的{trend = 1;//维持在这个组内，维持趋势为递增即可}} else if(A[i] < A[i - 1]) // 如果后一个<前一个{if(trend == 1) //之前的趋势如果是递增的{count++;trend = 0;} else {trend = -1;}}// 如果相等，trend 保持不变}cout << count << endl;return 0;
}
比较简单的归纳，遇到了变化点就判断和上一次趋势的比较，如果趋势为均势or相同的趋势，归纳到一堆，否则就另起炉灶；
Topic 2：消减整数（bfs, 归纳法优化）
C-消减整数_牛客小白月赛32
用BFS能做，但是用贪心和归纳更快
两条行动路径，我要找最短的肯定优先选2a，但是2a又需要满足最后结果恰好为0，那么也就是
(y-(n1*2a)- (n2*2*2a)-(n3*2*2*2a)- …)=0,这无数个2a组成了结果，这一坨n都可以简化为一个大N
=> y-N*2a= 0, 也就是y减N个2a恰好等于0
=> y % 2a = 0，那么当y % 2a等于0时，最后结果就能恰好为0，只是操作了N次而已
即y满足y%2a=0 时,优选选择-2a操作
#include <bits/stdc++.h>
using namespace std;int minSteps(int &h)
{int res = 0, a = 1;while(h){h -= a;res++;if(h % (a * 2) == 0) a *= 2;}return res;
}int main()
{int t, h;cin >> t;while (t--) {cin >> h;cout << minSteps(h) << endl;}return 0;
}
Topic 3：最长上升子序列(二)(dp 贪心 二分)
最长上升子序列(二)_牛客题霸_牛客网
对应LeetCode：300.最长递增子序列
class Solution {
public:int LIS(vector<int>& a) {int n = a.size();if (n == 0) return 0;vector<int> dp(n, 1);// dp[i]：下标为i时最长子序列的长度 dp[i] = max(dp[i], dp[j] + 1) dp[j]:0 - j 之间最长严格上升序列的长度 j < iint res = 1;for (int i = 1; i < n; ++i)// 从下标1开始，dp[0]之前被初始化为1 {for (int j = 0; j < i; ++j) {if (a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1);}res = max(res, dp[i]);}return res;}
};
最初的样子，但是会超时，所以要用贪心加二分来优化
我们维护一个数组 dp：
完成的dp表示最长的上升子序列
dp[i]表示：长度为i + 1的上升子序列的最小结尾元素，也可以把dp[0]特殊处理让下标对应
子序列要严格上升，所以结尾元素越小，越容易接上更大的数，形成更长的序列；所以我们希望：在所有可能长度的上升子序列中，结尾尽量小。
比如14和17，此时就取4
因为长度相同的情况下4后还能接567，而7只能接>7的
那么以14756举例，我创建一个dp容器，然后开始遍历原数组a{1,4,7,5,6}，如果遍历的元素比dp中储存的最后一个元素大，意味着可以插入这个dp，构成最长的上升子序列
1 插入；4 插入；7 插入； 5，5这里要处理了，如果比7大的话，正常插入即可，但是5比7小，此时把5作为dp[2]的值，因为相比于1 4 7 而言 1 4 5同样的长度，但结尾数字更小，然后继续遍历，6 插入；最后dp中存着 1 4 5 6，此时dp的size()就是最终最大的上升子序列元素个数了；
class Solution {
public:int LIS(vector<int>& a) {vector<int> dp; // dp[i]: 长度为 i+1 的上升子序列的最小结尾元素。// 这个数组不一定是实际的子序列，它是用来辅助计算长度的。for (const auto& e : a) // 遍历输入数组a的每个元素e{// 在dp中二分查找第一个 >= e 的位置// 目的是：找到e在dp中可以接在谁后面，或替换谁auto it = lower_bound(dp.begin(), dp.end(), e); // 如果e比dp中所有元素都大，说明e可以扩展出一个更长的子序列if (it == dp.end()) dp.push_back(e); // 否则，用e替换掉第一个 >= e 的位置，保持序列结尾尽可能小else *it = e; }return dp.size(); // dp的长度就是最长上升子序列的长度}
};代码的重点在于lower_bound：
auto it = lower_bound(begin, end, x); —— 在一个有序数组（非降序）中，找到第一个“大于等于给定值 x”的元素位置。
也可以自己手写：
int my_lower_bound(const vector<int>& a, int x)
{int left = 0, right = a.size(); // 注意：right 是 a.size()，不是 a.size() - 1while (left < right) {int mid = left + (right - left) / 2;if (a[mid] < x) {left = mid + 1;} else {right = mid;}}return left; // 返回的是第一个 >= x 的下标（可能是 a.size()，表示没有）
}