文章目录
——2020年11月15日（周日）——————————————————
#单调栈
一、模板单调栈
#include<bits/stdc++.h>
using namespace std;
const int N = 3e6 + 10;
int a[N], b[N];
int main(){
stack<int> s;
int n; cin >> n;
for(int i = 1; i <= n; i ++){
scanf("%d", &a[i]);
while(!s.empty() && a[i] > a[s.top()]){
b[s.top()] = i;
s.pop();
}
s.push(i);
}
for(int i = 1;i <= n; i ++)
printf("%d ", b[i]);
return 0;
}
递减单调栈……
#队列
二、机器翻译
队列……
链接
#include<iostream>
#include<queue>
using namespace std;
bool vis[1010];
int main()
{
queue<int>q;
int m,n;
cin>>m>>n;//内存容量和文章长度
int cnt=0,a,num=0;
for(int i=1;i<=n;i++)
{
cin>>a;
//有翻译记录就跳过
if(vis[a])continue;
//没有翻译记录时
//查找次数加1
cnt++;
//满了的入队列的操作
if(num==m)
{
//首先清除记录
vis[q.front()]=0;
//去掉队列头
q.pop();
//加入队列尾
q.push(a);
vis[a]=1;
}
//没满队列时的操作
else
{
//添加一个记录
vis[a]=1;
//加入队列尾
q.push(a);
//队列元素的数量
num++;
}
}
cout<<cnt<<endl;
return 0;
}
三、Blah数集
#include<iostream>
#include<queue>
using namespace std;
int a,n,k;
int main(){
while(cin>>a>>n)
{
//两个队列 一个装2a+1 一个装3a+1
queue<int> q1,q2;
k=1;
//确定第n位的操作
while(k<n)
{
q1.push(a*2+1);//入队列操作
q2.push(a*3+1);//
//循环替换a的值
//有点像归并排序合并时那种二分的思想
//反正就是两个单调递增的队列，其中一个的队头一定是两个队列中最小的数
//由题意得，我们整个序列是单调递增的，但是我们不需要合并，只要一只保留两个队列就好了
if(q1.front()<q2.front()){
a=q1.front();
q1.pop();
}
else if(q1.front()>q2.front()){
a=q2.front();
q2.pop();
}
//这是两者相同的情况，由于整个序列其实是没有重复元素的，所以要同时弹出队头
else{
a=q1.front();
q1.pop();
q2.pop();
}
//对应要加1
k++;
}
//确定好后就输出
cout<<a<<endl;
}
return 0;
}
总之，这些容器就是这么用的啦！
#双端队列(容器)
四、滑动窗口（这次是用deque做哒！）
四刷了哦，滑动窗口这道题……
以下是四种定义deque的方法
// 直接定义
std::deque<int> first; // empty deque of ints
//填充数字
std::deque<int> second (4,100); // four ints with value 100
//The contents of second are: 100 100 100 100
//复制某双端队列的某一段
std::deque<int> third (second.begin(),second.end()); // iterating through second
//The contents of third are: 100 100 100 100
//或者直接复制下整个其它双端队列
std::deque<int> fourth (third); // a copy of third
//The contents of fourth are: 100 100 100 100
//或者复制某个数组
// the iterator constructor can be used to copy arrays:
int myints[] = {16,2,77,29};
std::deque<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );
//The contents of fifth are: 16 2 77 29
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N];
//不要给双端队列q定义大小，我也不清楚
deque<int>q;
int main(){
//个数，窗口大小
int n, k; cin >> n >> k;
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
//递增
//依次将数组元素入队
for(int i = 1; i <= n; i ++){
//首先是出队操作
while( !q.empty() && a[i] < a[q.back()]) q.pop_back();
q.push_back(i);
if(!q.empty() && q.front() < i - k + 1) q.pop_front();
if(!q.empty() && i >= k) printf("%d ", a[q.front()]);
}
puts("");
//递减
q.clear();
for(int i = 1; i <= n; i ++){
//首先是出队操作
while( !q.empty() && a[i] > a[q.back()]) q.pop_back();
q.push_back(i);
if(!q.empty() && q.front() < i - k + 1) q.pop_front();
if(!q.empty() && i >= k) printf("%d ", a[q.front()]);
}
puts("");
return 0;
}
——2020年11月16日（周一）——————————————————
#并查集
一、How Many Tables （几张桌子）
这是题目哒！
仔细分析，这就是模板题一道而已啦。
//POJ不能用万能头，一时间不习惯hh
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
int n, m, P;
int p[N];
int find(int x){
//这个写法有个名字，叫做路径压缩，可以减少时间。写法也很简单，很容易理解。
return p[x] == x ? p[x] : p[x] = find(p[x]);
}
int main(){
// freopen("ttt.in", "r", stdin);
// freopen("ttt.out", "w", stdout);
int t;cin >> t;
while(t --){
int n, m;
scanf("%d%d", &n, &m);
int cnt = n;
//一开始自己是自己的父节点
for (int i = 1; i <= n; i ++ ) p[i] = i;
//关系输入
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
//将两个连同块连在一起
//根据题目需求，要计算有几个连通块;
//这里find在搜过一次后，会直接将整个连通块的父节点都赋值为根节点
//但是 p[find(a)] = find(b);之后a所在连通块所有的节点（除了上一个根节点）的父节点还是上一个根节点，并不是当前根节点。
//这里，要是不是一个连通块的，合并，那么就少一个连通块了哦。
if(p[find(a)] != find(b)) cnt --;
p[find(a)] = find(b);
}
cout << cnt << endl;
}
return 0;
}
——2020年11月17日（周二）——————————————————
一、How Many Answers Are Wrong
How Many Answers Are Wrong
这道题从昨晚一直做到现在，其原因有两个
一是本蒟蒻巨弱；
二就是被一个奇奇怪怪的例子给误导了……
去网上看了一大堆没用的博客，其解析真的是不清不楚……果然大佬都是一遍过，根本不需要这么多解释。
还好有这位巨老的博客给我答疑解惑，我才能走出来。
看这里，加入输入的是(4, 8, 10)的话，说明从格子内的4开始一直到8这个红色的方块就是10了，
用前缀和数组sum来计算就是sum[8] - sum[3];这里sum[n]中的n是下标,也就是 蓝色方框 中的数字。
#include <iostream>
#include <cstdio>
using namespace std;
//父节点 和 伪前缀和节点
int fa[200015], sum[200015];
//就是find()啦
int father(int x){
//找到了最大的爸爸 ，返回爸爸
if (x == fa[x]) return x;
//没找到最大的爸爸，那就继续找
else {
//这里用t来记录当前点的爸爸
int t = fa[x];
//然后重新认最大的爸爸做爸爸 ，这就叫路径压缩！
fa[x] = father(fa[x]);
//如果fa[x]不是祖先(最大的爸爸)节点就加上之前那个爸爸到最大的爸爸的距离
//是祖先节点则sum[t]为零,毕竟最大的爸爸的爸爸就是自己，自己和自己难道还有距离吗？（笑）
sum[x] += sum[t];
//然后就是返回这个最大的爸爸啦！
return fa[x];
}
}
int main()
{
// freopen("in.in" , "r" , stdin);
int n,m,a,b,c,r1,r2;
//如果输入不停 ……
while (scanf("%d%d" , &n, &m)!=EOF){
for (int i = 0; i <= n ; i++) {
fa[i] = i;
sum[i] = 0;
}
int ans=0;
for (int i = 0; i < m; i++){
scanf("%d%d%d", &a, &b, &c);
//这就要用前缀和来理解啦，因为是闭区间，所以左右端点都要取
//如果难理解的话，就想想前缀和，在前缀和中我们取[a, b]之间的值的时候不也是s[b] - s[a - 1]吗？
//这样就把a也算进来了。
a --;
//找爸爸
r1 = father(a);
r2 = father(b);
//不是同一个爸爸，那就不是同一个家里面的人。
//这里注意了，这里的点并不是按照顺序来的，也就是说1到6距离是300，而1到2距离是900这样也是成立的！
//点号不代表序号！我就是被学案上的例题误解了！
if (r1 != r2){
fa[r1] = r2;
sum[r1] = -sum[a] + sum[b] + c;
}
else if (sum[a] != sum[b] + c) ans ++;
}
printf("%d
", ans);
}
return 0;
}
二、食物链
既然都做了一道带权并查集了，那就顺便把这道有趣的题目也复习一下吧
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
int sum;
int n, m, P;
int p[N];
int d[N];
//这里每执行一次都会直接将祖宗节点作为所有在内节点的父节点，
//其距离不会重复计算第二次，因为下一次就遍历不到之前的父节点了.
int find(int x){
if(x != p[x]){
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}
int main(){
// freopen("ttt.in", "r", stdin);
// freopen("ttt.out", "w", stdout);
int n, k;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i ++ ) p[i] = i;
while (k -- ){
int z, a, b;
scanf("%d%d%d", &z, &a, &b);
int pa = find(a), pb = find(b);
//假话
if(a > n || b > n) sum ++;
else{
//1代表同类
if (z == 1){
//d[a] - d[b]) % 3这里如果不是0就说明他们根本就不是同类的
if(pa == pb && (d[a] - d[b]) % 3 ) sum ++;
//这里用else if 是因为上面的if有两个判断句，
//用else 的话就是肯定了其它三种情况，
//然而我们需要处理的只是四种中的两种
else if(pa != pb){
p[pa] = pb;
//添加的时候由于还没有用到find()函数，所以并不会立即更新新连通块内所有点到其对应根节点的距离
//这时候就要先将之前的根节点到当前根节点的距离处理一下，
//下一次的find()就会更新新连通块内所有点到其根节点的距离了
d[pa] = d[b] - d[a];
}
}
//2代表a吃b
else
{
//假话，说反了
if(pa == pb && (d[a] - d[b] - 1) % 3) sum ++;
else if(pa != pb){
p[pa] = pb;
d[pa] = d[b] + 1 - d[a];
}
}
}
}
cout << sum;
return 0;
}
三、连通块中点的数量
现在看看还是很简单的一道题，不是吗？
AcWing 837. 连通块中点的数量
#include <iostream>
using namespace std;
const int N = 100010;
int p[N];
int sum[N];
int a, b;
string op;
int find(int x){
return p[x] == x ? p[x] : p[x] = find(p[x]);
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) p[i] = i, sum[i] = 1;
while (m -- )
{
cin >> op;
if(op == "C"){
scanf("%d%d", &a, &b);
if(a != b){
int pa = find(a), pb = find(b);
if(pa != pb) sum[pb] += sum[pa], p[pa] = pb;
}
}
else{
if(op == "Q1"){
scanf("%d%d", &a, &b);
if(find(a) == find(b)) printf("Yes
");
else printf("No
");
}
else scanf("%d", &a), printf("%d
", sum[find(a)]);
}
}
return 0;
}
——（未完，但是标题不够写了……）————————————————
四.2的链接：点这里