目录
————————————————————2020年10月25日（周日）
一、最长连续不重复子序列
首先要明白，子序列不一定要所有元素挨在一起！
== 子串当然就是要再在一起啦==，就像一串糖葫芦一样，被串在一起了。
但是，这道题所谓的“最长连续子序列”其实是“子串”啦。
题目
思路注释
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n;
int a[N];
bool s[N];
int cnt = 0, t = 0;
int main(){
memset(s, 0, sizeof s);
cin >> n;
for(int i = 0; i < n; i ++)
cin >> a[i];
int j = -1, i;
for(i = 0; i < n; i ++){//i不断往前走
//每一轮都要找到从i开始的最长不重复子序列
// for(int k = 0; k < 20; k ++) cout << s[k] << ' ';
// cout << endl;
if(t > 0)//如果当前有长度，往前走就要长度-1
t --;
while(j + 1 < n && !s[a[j + 1]]){
s[a[j + 1]] = 1;
t ++;
j ++;
}
// cout << i << endl;
s[a[i]] = 0;
cnt = max(cnt, t);
// cout << "cnt :" << cnt << endl;
}
cout << cnt;
return 0;
}
二、数的三次方根
题目
思路：不断二分找答案，然后记得小数要判断精度！
#include <iostream>
using namespace std;
int main(){
double x;
scanf("%lf", &x);
double l = -100, r = 100;
while(r - l > 1e-8){
double mid = (l + r) / 2;
if(mid * mid * mid >= x) r = mid;
else l = mid;
}
printf("%.6lf", r);
return 0;
}
三、差分
思路：
将要加上某个数的区间第一个数加上要加的数，
区间末后一个元素减去此元素
就可以使区间内的数都加上此元素而后面的数保持原样
#include<bits/stdc++.h>
#define MAXN 200005
using namespace std;
int n,m,a[MAXN],b[MAXN];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> a[i];
int l, r, c;
for(int i =1 ; i <= m; i ++){
cin >> l >> r >> c;
b[l] += c; b[r + 1] -= c;
}
for(int i = 1; i <= n ;i ++) b[i] += b[i - 1];
for(int i = 1; i <= n; i ++) cout << a[i] + b[i] << " ";
return 0;
}
四、前缀和
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], s[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i]; // 前缀和的初始化
while(m --){//这是第一种输入输出方式
int l, r;
cin >> l >> r;
cout << s[r] - s[l - 1] << endl;
}
while (m -- )//这是第二种输入输出方式
{
int l, r;
scanf("%d%d", &l, &r);
printf("%d
", s[r] - s[l - 1]); // 区间和的计算
}
return 0;
}
可以看到时间差了很远很远！！！,所以输入一定要用scanf !
————————————————————2020年10月26日（周一）
一、最大异或对
传送
整理博客时发现的，之前没仔细写思路，现在一开始自己也没有想起来之前怎么做的 （滑稽） 。
（过了一周后再回来看，发现又忘记怎么做了……我的记忆果然是假的。——一周后的我
注：-1的二进制码全是 1，所以 ~-1 == 0 ！
答案
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 3000000;
int n;
int a[N], son[M][2], idx;
void insert (int x){
int p = 0;
for(int i = 30; ~i; i --){
int s = x >> i & 1;
if(!son[p][s]){
son[p][s] = ++idx;
p = idx;
}
else p = son[p][s];
}
}
//这个函数就是说，将这个数分解为一个二进制数，然后按照这个二进制不断地往下开辟一条道路
//每到一个新节点就给它取一个新的名字，这样往下找儿子的时候就不会产生混乱……
int find(int x){
int p = 0, res = 0;
for(int i = 30; i >= 0; i --){
int s = x >> i & 1;
if(son[p][!s]){
res += 1 << i;
p = son[p][!s];
}
else p = son[p][s];
}
return res;
}
int main(){
scanf("%d", &n);
for(int i = 0; i < n; i ++){
scanf("%d", &a[i]);
insert(a[i]);
}
int res = 0;
for(int i = 0; i < n; i ++) res = max(res, find(a[i]));
cout << res ;
return 0;
}
二、快速排序
传送
没啥好说的，对着模板打吧，边界问题一直是个迷……反正也很少用得着手写。(除了练习的时候，谁会手打这玩意儿？)
#include <iostream>
using namespace std;
const int N = 100010;
int q[N];
void quick_sort(int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(l, j);
quick_sort(j + 1, r);
}
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i ++) scanf("%d ", &q[i]);
quick_sort(0, n - 1);
for(int i = 0; i < n; i ++) printf("%d ", q[i]);
return 0;
}
————————————————————2020年10月27日（周二）
一、子矩阵的和（二维前缀和）
跳
思路：
s[i][j] += ( s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] ) ;
这个是将输入后的数组进行初始化，代表的是以（1, 1）为左上角以（i, j）为右下角的原矩阵的所有元素之和。
s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]
这句话是求规定范围（以（x1, y1）为左上角，以（x2, y2）为右下角）内的矩阵的所有元素之和。
答案
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, q;
int s[N][N];
int main(){
scanf("%d%d%d", &n, &m, &q);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
scanf("%d", &s[i][j]);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
s[i][j] += ( s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] ) ;
for(int i = 1; i <= q; i ++){
int x1, x2, y1, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%d
", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
}
return 0;
}
二、差分矩阵
turn
思路
只有一个操作：
void insert(int x1, int y1, int x2, int y2, int c){
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;
}
就是这个insert函数，意思是 将这个矩阵之内的数全部加上c， 其余部分不会变。
而最后的实现其实就是前面子矩阵的和这道题的方法，也就是将最后得到的b数组进行二维前缀和的操作,
得到的b数组就是答案
举例理解：
首先 假设 有一个4X4 的小方块要加上 2， 那么我们先将方块的左上角(1, 1)加上2。
然后你想，我们最后是要进行二维前缀和的运算的，
那么为了不让其它部分受到影响，我们要将（1, 5）（5, 1）上的数减去2，与从（1， 1）传递过来的2相互抵消了，这样它们后面的数也不会受到影响了。
但是注意！有一个位置，那就是b（5, 5）它减去了两次2！
因为它同时受b（5， 1）b（1， 5）的影响，所以我们还要在b（5， 5）再加上2.
答案
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c){
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;
}
int main(){
scanf("%d%d%d", &n, &m, &q);
for(int i = 1; i <= n; i ++)
for(int j = 1;j <= m; j ++){
scanf("%d", &a[i][j]);
insert(i, j, i, j, a[i][j]);
}
for(int i = 1; i <= q; i ++){
int x1, x2, y1, y2, c;
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
insert(x1, y1, x2, y2, c);
}
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++)
printf("%d ", b[i][j]);
puts("");
}
return 0;
}
————————————————————2020年10月28日（周三）
一、区间和
传送
思路
离散化（Discretization）：把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。
离散化 —— 模板题 AcWing 802. 区间和
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素
// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1; // 映射到1, 2, ...n
}
作者：yxc
链接：https://www.acwing.com/blog/content/277/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
传送
答案
总感觉这种写法太麻烦了 ……
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
const int N = 300010;
int m, n;
int a[N], s[N];
vector<int> alls;
vector<P> add, query;
int find(int x){
int l = 0, r = alls.size() - 1;
while(l < r){
int mid = (l + r) >> 1;
if(alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r;
}
vector<int>::iterator unique(vector<int> &a){
int j = 0;
for(int i = 0; i < a.size(); i ++)
if(!i || a[i] != a[i - 1])
a[j ++] = a[i];
// a[0] ~ a[j - 1] 所有a中不重复的数
return a.begin() + j;
//返回end坐标
}
int main(){
scanf("%d%d", &n, &m);
//"首先进行 n 次操作，每次操作将某一位置x上的数加c。"
for(int i = 0; i < n; i ++){
int x, c;
scanf("%d%d", &x, &c);
add.push_back({x, c});
alls.push_back(x);
}
//"接下来，进行 m 次询问，每个询问包含两个整数l和r，你需要求出在区间[l, r]之间的所有数的和"
for(int i = 0; i < m; i ++){
int l, r;
scanf("%d%d", &l, &r);
query.push_back({l, r});
alls.push_back(l);
alls.push_back(r);
}
//去重
sort(alls.begin(), alls.end());
alls.erase(unique(alls), alls.end());
// 处理插入
for(auto item : add){
int x = find(item.first);
a[x] += item.second;
}
// 预处理前缀和
for(int i = 1; i <= alls.size(); i ++)
s[i] = s[i - 1] + a[i];
// 处理询问
for(auto item : query){
int l = find(item.first);
int r = find(item.second);
cout << s[r] - s[l - 1] << endl;
}
return 0;
}
————————————————————2020年10月30日 （周五）
一、区间合并
传送
思路
区间合并 —— 模板题 AcWing 803. 区间合并
// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
vector<PII> res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for (auto seg : segs)
if (ed < seg.first)
{
if (st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);
if (st != -2e9) res.push_back({st, ed});
segs = res;
}
作者：yxc
链接：https://www.acwing.com/blog/content/277/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
答案
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
void merge(vector<PII> &segs){
vector<PII> res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for (auto seg : segs)
if (ed < seg.first){//没有交集
if (st != -2e9) res.push_back({st, ed});//也不是第一个,那就加入一个新的合成后的区间
st = seg.first, ed = seg.second;//但是不论如何，st和ed都要重新开始
}
else ed = max(ed, seg.second);
if (st != -2e9) res.push_back({st, ed});//有交集的话，比较一下谁的尾巴更长就用谁的尾巴,这就是合并
segs = res;
}
int main(){
int n;
scanf("%d", &n);
vector<PII> segs;
for (int i = 0; i < n; i ++ ){
int l, r;
scanf("%d%d", &l, &r);
segs.push_back({l, r});
}
merge(segs);
cout << segs.size() << endl;
return 0;
}
————————————————————2020年10月31日（周六）
一、单链表
传送
模板
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;
// 初始化
void init(){
head = -1;
idx = 0;
}
// 在链表头插入一个数a
void insert(int a){
e[idx] = a, ne[idx] = head, head = idx ++ ;
}
// 将头结点删除，需要保证头结点存在
void remove(){
head = ne[head];
}
答案
根据题目做了一些小改动，就是把nxt[0]看作是头结点，从而省略了head这个变量以及insert_head这个单独的函数。
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int nxt[N], e[N];
int idx = 1;
void add (int n, int a){//在n位置之后加入元素a
e[idx] = a, nxt[idx] = nxt[n], nxt[n] = idx ++;//注意，与头相反的方向是尾，也就是后面
}
void del(int k){
nxt[k] = nxt[nxt[k]];
}
int main(){
int m;
scanf("%d", &m);
for(int i = 1; i <= m; i ++){
char c;
cin >> c;
if(c == 'I'){
int k, a;
scanf("%d%d", &k, &a);
add(k, a);
}
else if(c == 'D'){
int k;
scanf("%d", &k);
del(k);
}
else if(c == 'H'){//注意：新插入的点是头
int a;
scanf("%d", &a);
add(0, a);
}
}
for(int i = nxt[0]; i ; i = nxt[i]) printf("%d ", e[i]);
return 0;
}
二、双链表
传送
这个形象多了，个人觉得更好理解。
教训：if , else if 和 else一定要区分清楚，不然真的怎么出错都不知道！！
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int l[N], r[N], e[N], idx = 2;
void insert(int k, int x){
e[idx] = x;
l[idx] = k, r[idx] = r[k];
l[r[k]] = idx, r[k] = idx ++;
}
void del(int k){
l[r[k]] = l[k];
r[l[k]] = r[k];
}
int main(){
r[0] = 1, l[1] = 0;
int m;
cin >> m;
for(int i = 1; i <= m; i ++){
string s;
cin >> s;
int k, x;
if(s == "L"){
scanf("%d", &x);
insert(0, x);
}
else if(s == "R"){
scanf("%d", &x);
insert(l[1], x);
}
else if(s == "D"){
cin >> k;
del(k + 1);//这里k + 1是因为我们是从2开始计算第一个节点的。
}
else if(s == "IL"){
scanf("%d%d", &k, &x);
insert(l[k + 1], x);
}
else{
scanf("%d%d", &k, &x);
insert(k + 1, x);
}
}
for(int i = r[0]; i != 1; i = r[i]) printf("%d ", e[i]);
return 0;
}
三、模拟栈
这种题真的有存在的必要吗……
解答
#include <iostream>
using namespace std;
const int N = 100010;
int m;
int stk[N], tt;
int main()
{
cin >> m;
while (m -- )
{
string op;
int x;
cin >> op;
if (op == "push")
{
cin >> x;
stk[ ++ tt] = x;
}
else if (op == "pop") tt -- ;
else if (op == "empty") cout << (tt ? "NO" : "YES") << endl;
else cout << stk[tt] << endl;
}
return 0;
}
四、模拟队列
这个也是……
解答
#include <iostream>
using namespace std;
const int N = 100010;
int m;
int q[N], hh, tt = -1;
int main()
{
cin >> m;
while (m -- )
{
string op;
int x;
cin >> op;
if (op == "push")
{
cin >> x;
q[ ++ tt] = x;
}
else if (op == "pop") hh ++ ;
else if (op == "empty") cout << (hh <= tt ? "NO" : "YES") << endl;
else cout << q[hh] << endl;
}
return 0;
}
五、单调栈
转
思路
这里为什么用单调栈呢？
因为如果输出第一个小于某数的数的话，那么每次一直往左找，直到找到最左边的那个，输出并记录。
如果后来输入的数比它大，那就没有必要保留，类似出栈操作。
这样可以很快地解决这种问题。
#include <iostream>
using namespace std;
const int N = 100010;
int stk[N], tt;
int main()
{
int n;
cin >> n;
while (n -- )
{
int x;
scanf("%d", &x);
while (tt && stk[tt] >= x) tt -- ;
if (!tt) printf("-1 ");
else printf("%d ", stk[tt]);
stk[ ++ tt] = x;
}
return 0;
}
六、滑动窗口（单调队列）
传送
思路
经典的单调队列问题，三刷了……
简单地说就死维护一个单调队列，每次输出队尾即可。
梦幻联动（调试版也在里面啦）
#include <iostream>
using namespace std;
const int N = 1000010;
int a[N], q[N];
int main()
{
int n, k;
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
//这里处理的是最小值
int hh = 0, tt = -1//头 和 尾
for (int i = 0; i < n; i ++ )
{
if (hh <= tt && i - k + 1 > q[hh] ) hh ++ ;
//这里是当队列里面还有元素 以及 头不在这个窗口范围的时候，头就往后走一位
while (hh <= tt && a[q[tt]] >= a[i] ) tt -- ;
//这里是要把队列中所有比 现在要插入的元素 大的元素出队
//然后就会发现 现在队列里的元素 正是当前状态（加入新元素）的单调队列
q[ ++ tt] = i;
if (i >= k - 1) printf("%d ", a[q[hh]])；
//队头是最小的
}
puts("");
//这里处理的是最大值
hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
if (hh <= tt && i - k + 1 > q[hh]) hh ++ ;
while (hh <= tt && a[q[tt]] <= a[i]) tt -- ;
q[ ++ tt] = i;
if (i >= k - 1) printf("%d ", a[q[hh]]);
}
puts("");
return 0;
}
已完结 （标题满100了塞不下了） ，刚好一周！以后就一周算一章吧！就像日（周）记一样好了……
什么嘛，这周只有16道题而已嘛，平均一天也就两道题多一点……