首页 > 其他分享 >QBXT五一集训DAY3笔记

QBXT五一集训DAY3笔记

时间：2024-05-04 20:24:12浏览次数：29  
标签：head int 元素 DAY3 QBXT tail push include 集训

\(Day\) \(3\)

位运算

位运算包含了五个运算符，分别是：

  • &与
    只有两个对应位都为 \(1\) 时才为 \(1\)

  • |或
    只要两个对应位中有一个 \(1\) 时就为 \(1\)

  • ^异或
    只有两个对应位不同时才为 \(1\)

  • <<左移
    如 \(n<<i\) 表示将 \(n\) 的二进制向左移动 \(i\) 位，等价于\(n*2^i\)

  • >>右移
    如 \(n>>i\) 表示将 \(n\) 的二进制向右移动 \(i\) 位，等价于\(n/2^i\)

这里有一个有趣的等式

\((a\)&\(b)+(a\)^\(b)=(a|b)\)

请问，^有什么用？

来看一道题

给你 \(2N+1\) 个数 ，有 \(N\) 个数出现了两次，请找出那个只出现一次的数（不能用数组）

想一想异或的含义，只要把这几个数全部异或起来就行了

用位运算判断 \(x\) 的奇偶

我们知道，若要判断 \(x\) 的奇偶，我们只要判断 \(x\)%\(1\) 是否等于\(1\)
这里，我们还可以判断 \(x\)&\(1\) 是否等于 \(1\)

当然，这里要注意，位运算的这几个运算符优先级都很低，在进行运算的时候要加上括号
而且，优先级越低，运算速度越快

数据结构

队列\(queue\)

队列是一个先进先出的数据结构，很像我们生活中的排队

它支持以下几个操作：

  • 在队尾加入一个元素
  • 在队首删除一个元素
  • 查看队首元素
点击查看代码 
#include<iostream>
#include<queue>
using namespace std;

queue<int> q;//声明了一个元素类型为int的队列 

int main(){
	q.push(233);
	q.push(2333);//向队列中放入一个元素
	cout << q.front() << endl;//询问队首元素是多少: 233
	q.pop();//从队列中删除队首元素
	cout << q.size() << endl;//询问队列中还有多少个元素 
	
	return 0;
}

可是STL中的\(queue\)无法查看队尾元素，我们可以手写\(queue\)

点击查看代码 
struct queue{
	int a[maxn];//存队列里面的元素 
	int head,tail;//代表当前队列的存储区间为 a[head~tail]
	queue(){
		head=1;tail=0;
	} 
	void push(int x){
		tail++;
		a[tail]=x;
	}
	void pop(){
		head++;
	}
	int size(){
		return tail-head+1;
	}
	int front(){
		return a[head];
	}
};

栈\(stack\)

栈是一种后进先出的数据结构

它支持以下操作：

  • 向栈顶加入一个元素
  • 删除栈顶元素
  • 询问栈顶元素
点击查看代码 
#include<iostream>
#include<stack>
using namespace std;

stack<int> s;//声明一个元素类型为int的栈

int main(){
	s.push(233);
	s.push(2333); 
	cout << s.top() << endl;//询问栈顶元素是多少:2333
	s.pop();
	cout << s.size() << endl;
}

给你\(N\)个数和一个\(L\)，求所有长度为\(L\)的区间最小值\((L \le N \le 3*10^6)\)

很容易想到队列

可是要找出最小值，这就需要一个单调递增的队列

单调队列\(monotone\) \(queue\)

如果加入的元素不符合单调递增，那就将其删除，直到满足条件

点击查看代码 
#include<iostream>

using namespace std;

struct monotone_queue{
	int a[maxn];//存队列里面的元素 当前的队列要单调不降 
	int head,tail;//代表当前队列的存储区间为 a[head~tail]
	queue(){
		head=1;tail=0;
	} 
	void push(int x){
		while (head<=tail && a[tail] > x)
			tail--;
		tail++;
		a[tail]=x;
	}
	void pop(){
		head++;
	}
	int size(){
		return tail-head+1;
	}
	int front(){
		return a[head];
	}
}q;

int main(){
	cin >> n >> l;
	for (int i=1;i<=n;i++)
		cin >> z[i];
	for (int i=1;i<=l;i++)
		q.push(z[i]);//把第一个区间的数全部扔进单调队列
	int ans=q.front();//第一个区间的最小值必然是队首元素
	for (int i=l+1;i<=n;i++){//当前要加入第i个数
		q.push(z[i]);//把第i个数加入队列
		if (z[i-l] == q.front()) q.pop();//从队列中删除z[i-l]这个数 
		ans += q.front();//区间i-l+1~i的最小值 
	} 
	cout << ans << endl;
		
	return 0;
}

双端队列\(deque\)

可以理解为是栈和队列的结合体

点击查看代码 
#include<deque>
#include<iostream>
using namespace std;

deque<int> d;//声明了一个元素类型为int的双端队列 

int main(){
	d.size();//询问还有几个元素 
	d.push_front(1);//从前面加入1
	d.front();//询问最前面的元素是谁
	d.back();//询问最后面的元素是谁 
	d.pop_front();//从前面弹出一个元素 
	d.push_back(2);//从后面加入2 
	d.pop_back();//从后面弹出元素 
	
	return 0;
}

堆/优先队列 \(riority\) $queue￥

堆支持以下操作：

  • 加入一个数
  • 刚除最大值
  • 询问最大值

这是大根堆

若将上面的最大值改为最小值，就是小根堆

点击查看代码 
#include<iostream>
#include<queue>

using namespace std;

priority_queue<int> heap;//声明一个元素类型为int的大根堆
priority_queue<int> heap2;//小根堆 

int main(){
	heap.push(233);
	heap.push(2333);//堆中加入一个元素
	heap.top();//询问堆中最大的元素:2333
	heap.pop();//删除堆中最大的元素
	heap.size();//询问堆中还有几个元素 
	
	heap2.push(-233);//加入元素的时候取一个相反数 
	heap2.push(-2333);//取元素的时候就能够取出来最小的数的相反数 
}

看一道题：

对每种颜色的木棍放入一个大根堆，每次取每个不同颜色大根堆中最大的三根，若组不成三角形，就把最长的木棍扔掉

\(ST\)表

给你\(N\)个数，\(M\)次询问，求\(L\)到\(R\)这个区间的最小值

\(ST\)表就是用 \(f_{i,j}\) 来存储从第\(i\)个数开始的\(2^j\)个数的最小值

简单来说，\(f_{i,j}=\min(f_{i,j-1},f_{i+2^{j-1},j-1})\)

点击查看代码 
#include<iostream>

using namespace std;

const int maxn=100010;

int n,a[maxn],f[maxn][20],b[maxn];

int main()
{
	cin >> n;
	for (int i=1;i<=n;i++)
		cin >> a[i];
		
	for (int i=0;(1<<i)<=n;i++)
		for (int j=(1<<i);j<(1<<(i+1));j++)
			b[j] = i;//两个长度为2^i的区间 一定能够覆盖住一个长度为j的区间 
		
	for (int i=1;i<=n;i++)
		f[i][0] = a[i];
	for (int j=1;(1<<j)<=n;j++)//要计算长度为2^j的区间的最小值 
		for (int i=1;i+(1<<j)-1<=n;i++)//这段区间的开始位置为i
			f[i][j] = min(f[i][j-1], f[i+(1<<(j-1))][j-1]); //O(nlogn)
	cin >> m;
	for (int i=1;i<=m;i++)//O(m)
	{
		int l,r;
		cin >> l >> r;
		int len=r-l+1;//区间长度
		int x=b[len];
		cout << min(f[l][x],f[r-(1<<x)+1][x]) << endl;
		//从l开始向后的2^x个数的最小值
		//从r开始向前的2^x个数的最小值 
	}
}

\(set\)

点击查看代码 
#include<set>
#include<iostream>

using namespace std;

set<int> se;//定义了一个元素类型为int的集合 
//每个数只能在set中出现一次 

struct jgt
{
	int a,b;
};

bool operator<(const jgt &a,const jgt &b)
{
	return a.a<b.a;
}

set<jgt> se2;

int main()
{
	se.insert(233);
	se.insert(233);
	se.insert(2333);//向set进行插入
	cout << se.size() << endl;//查询set的大小
	cout << se.count(233) << endl;//查询233在set中出现了多少次 要么0 要么1
	se.erase(233); //从set中删除2333 
	cout << se.count(233) << endl;
	
	se.insert(333);
	se.insert(254);
	
	//输出set中的所有元素（3种） 
	//for (set<int>::iterator it=se.begin(); it != se.end(); it++)
	//	cout << (*it) << endl;
	//for (auto it = se.begin(); it != se.end(); it++)
	//	cout << (*it) << endl;
	for (auto it : se)
		cout << it << endl;
	se.clear();
	 
}

\(pair\)

点击查看代码 
#include<iostream>
#include<algorithm>

using namespace std;

pair<int,int> p;//声明一个二元组 第一个元素类型为int 第二个元素类型为int 

pair<int,int> a[100010];

pair<int, pair<int,int> > r;//三元组 

int main()
{
	p.first = 22;//first第一个元素 
	p.second = 33;//second第二个元素
	p = make_pair(22,33);
	
	cout << (a[1] < a[2]) << endl;//先比较first 再比较second 
	cout << (a[1]==a[2]) << endl;//first和second都要相等 
	
	r.first;
	r.second.first;
	r.second.second;
	
	int n=10;
	sort(a+1,a+n+1);//按照first作为第一关键字 second作为第二关键字从小到大排序 
}

\(map\)

点击查看代码 
#include<iostream>
#include<map>
#include<string>

using namespace std;

map<int,int> ma1;//数组 
//第一个int 代表这个数组的下标类型
//第二个int 代表这个数组的元素类型 
map<int, map<int,int> > ma2;
map<pair<int,int>, int>  ma3;

map<string,string> ma4;
//log 
int main()
{
	cout << ma1.size() << endl;
	ma1.clear();
	ma1[233] = 2333;
	ma1[2147483647] = 23333;
	ma1[-2345] = 3444;
	for (auto it : ma1)
		cout << it.first << " " << it.second << endl;
		
	ma2[1][2] = 3;
	for (auto it1 : ma2)
		for (auto it2 : ma2[it1.first])
			cout << it1.first << " " << it2.first << " " << it2.second << endl;
	ma3[{1,3}] = 3;
	
	ma4["hello"] = "world";
}

\(vector\)

点击查看代码 
#include<iostream>
#include<vector>

using namespace std;

vector<int> z;//动态数组 元素类型为int 

//z 已经有32768个数
//push_back
//把占用的内存从32768 -> 65536
//第32769这个位置拿来存数 

int main()
{
	z.push_back(233);
	z.push_back(2333);//在数组后面加入一个数
	z.pop_back();//删除数组最后一个数
	z.push_back(23333);
	cout << z.size() << endl;//数组中有几个数
	for (int i=0;i<z.size();i++)
		cout << z[i] << endl; 
	z.resize(1000);//把vector数组大小变为1000 
	 
	return 0;
}

并查集






点击查看代码 
int to[233];//to[i]代表i点的箭头指向谁 

int go(int p)//从p出发最后会走到哪里 O(1)
{
	if (p==to[p]) return p;
	//else return to[p]=go(to[p]);
	else
	{
		to[p] = go(to[p]);
		return to[p];
	}
}

int main()
{
	cin >> n;
	for (int i=1;i<=n;i++)
		to[i] = i;//每个点的箭头都指向自己 
		
	//合并x和y所在的部分 
	to[go(x)] = go(y);
	
	//判断x和y是否属于同一部分
	go(x) == go(y); 
}

线段树

点击查看代码 
#include<iostream>

using namespace std;

const int maxn=100010;

int n,m,a[maxn];

struct node//线段树的一个节点 
{
	//第一个需要修改的地方：增加维护的值 
	int l,r;//这段区间的左端点、右端点
	int sum;//这段区间的和
	int minv;//这段区间的最小值 
	int tag;//懒标记
	//代表当前节点所对应的区间 每一个数都被加了tag
	//但是 这件事还没有告诉当前节点的两个儿子 
	node(){
		//第二个需要修改的地方：增加维护的值的初始化 
		l=r=sum=tag=minv=0;
	} 
}z[maxn*4];//z[i]代表线段树的第i个节点

#define root 1,n,1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

node operator+(const node &l,const node &r)//定义线段树如何合并两个区间 
{
	//第三个需要修改的地方：增加维护的值 计算方法 
	node res;
	
	res.l=l.l; res.r=r.r;
	res.sum = l.sum + r.sum;
	res.minv = min(l.minv,r.minv);
	
	return res;
}

void build(int l,int r,int rt)//当前的线段树节点编号为rt 其所对应的区间为l~r
//建立这棵线段树 
{
	if (l==r)//走到了最下面 区间只有一个数 那就建立这个节点 
	{
		//第四个需要修改的地方：长度为1的区间这个值怎么处理 
		z[rt].l=z[rt].r=l;
		z[rt].sum = a[l];
		z[rt].minv=a[l];
		return;
	}
	int m=(l+r)>>1;//从l~r中间砍开 l~m作为左儿子区间 m+1~r作为右儿子区间
	build(lson);//build(l,m,rt<<1);//build(l,m,rt*2);//建立左儿子 
	build(rson);//build(m+1,r,rt<<1|1);//build(m+1,r,rt*2+1);//建立右儿子 
	z[rt] = z[rt<<1] + z[rt<<1|1];
} 

void color(int rt,int v)//给节点rt打一个+v的懒标记
{
	//第五个需要修改的地方：增加维护的值的打标记方法 
	z[rt].sum += v * (z[rt].r-z[rt].l+1);
	z[rt].tag += v;
	z[rt].minv += v;
} 

void push_col(int rt)//把节点rt的标记告诉它的儿子
{
	if (z[rt].tag != 0)
	{
		color(rt<<1,z[rt].tag);
		color(rt<<1|1,z[rt].tag);
		z[rt].tag=0;
	}
} 

node query(int l,int r,int rt,int nowl,int nowr)//logn
//当前线段树节点为l~r，编号为rt 此时要询问nowl~nowr这段区间
{
	if (nowl<=l && r<=nowr) return z[rt];//l~r当前线段树节点所对应的区间被询问区间完全包含
	push_col(rt);//把懒标记下放 
	int m=(l+r)>>1; 
	if (nowl<=m)//询问区间和左儿子有交 
	{
		if (m<nowr)//询问区间和右儿子有交
			return query(lson,nowl,nowr) + query(rson,nowl,nowr);
		else//代表只和左儿子有交
			return query(lson,nowl,nowr); 
	}
	else//只和右儿子有交
		return query(rson,nowl,nowr); 
} 

void modify(int l,int r,int rt,int nowl,int nowr,int v)
//当前线段树节点编号为rt 区间为l~r
//修改操作为给nowl~nowr这段区间整体+v
{
	if (nowl<=l && r<=nowr) {//当前区间被修改区间整体包含 
		color(rt,v);//给节点rt打一个整体+v的懒标记
		return; 
	}
	push_col(rt);//把懒标记下放 
	int m=(l+r)>>1;
	if (nowl<=m) modify(lson,nowl,nowr,v);//修改区间和左儿子有交 
	if (m<nowr) modify(rson,nowl,nowr,v);//修改区间和右儿子有交
	z[rt] = z[rt<<1] + z[rt<<1|1]; 
} 

int main()
{
	cin >> n >> m;
	for (int i=1;i<=n;i++)
		cin >> a[i];
		
	build(root);//建树 
	for (int i=1;i<=m;i++)
	{
		int opt;
		cin >> opt;
		if (opt==1)//修改操作
		{
			int x,y,k;
			cin >> x >> y >> k;
			modify(root,x,y,k);
		}
		else//询问操作 
		{
			int x,y;
			cin >> x >> y;
			cout << query(root,x,y).sum << endl;
		} 
	}
	
	return 0;
}

标签：head,int,元素,DAY3,QBXT,tail,push,include,集训
From： https://www.cnblogs.com/TianJiajun-chaqjs/p/18172632

相关文章

  • 【未整合】数学 day3.2
    阶对于\(\gcd(a,p)=1\)，最小的\(t\)使得\(a^t\equiv1(\bmodp)\)称为\(a\)的阶。写作\(\operatorname{ord}_p(a)\)。若\(a^k\equiv1(\bmodp)\)，当且仅当\(\operatorname{ord}_p(a)|k\)。求阶的复杂度是\(O(\sqrt{n})\)。给定\(\gcd(a,p)=\gcd(b,p)=1\)，问是否存在......
  • 集训 4 & 模拟 5
    集训4&模拟5有点唐简单，所以一起写了（其实是因为之前懒得写）集训4：T1模拟，赛时不删调试保龄了。T2显然贪心T3发现显然要两两互质，有因为父比子小，所以方案数就是将\(\varphi\)乘起来（甚至都不需要线性筛）T4meetinmiddle板子。模拟5T1特殊字符串显然有\(n^2\)......
  • [国家集训队] 矩阵乘法 题解
    发现实际上就是二维静态区间最大值，可以用整体二分维护。时间复杂度\(O((q+n^2)\log\max(a_{i,j})\logn^2)\)。#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintW=310005;constintQ=6e4+5;intn,q,w,ans[Q];intc[505][505],m;voidadd(i......
  • QBXT五一集训DAY1笔记
    \(Day1\)\(ASCII\)简单来说，\(ASCII\)其实就是字符与数字之间的映射比如说，\('a'\)的\(ASCII\)就是\(97\)模运算：%来复习一下小学数学：\(a/b=c……d\)这里的\(d\)就是\(a\)除以\(b\)的余数，在计算机中，用%来表示通过这个式子，我们进而得出\(a=b*c+d\)请一定要记住这......
  • day30-JavaScript(2)
    1、BOM对象BOM:Broswerobjectmodel,即浏览器提供我们开发者在javascript用于操作浏览器的对象。1.1、window对象窗口方法//BOMBrowserobjectmodel浏览器对象模型//js中最大的一个对象.整个浏览器窗口出现的所有东西都是window对象的内容.console.log(window);......
  • 云计算运维day3
    云计算运维day3花括号用法一次性在同级目录，创建多个文件关于进程号第二个数字是进程号id，不断变化表示是每一次都生成了新的进程，也就是该grep是临时生成的。mkdir{hx,wjq,hw}rm{hx,wjq}touch玩家{1..100}.log压缩和解压缩的概念打包，默认是没有压缩功能，不节省磁盘空间......
  • 洛谷 P8989 [北大集训 2021] 随机游走 题解
    前言又是随机游走？题目分析看到加边，可能性太多了。但是为了让步数最大化，我们可以贪心地想，肯定要往前面连，而且越前面要走的期望步数肯定越大。并且，我们不会浪费边在终点上。于是，题目转变成了\(1\simn-1\)连向起点\(1\)连若干条边，使得随机游走到终点的期望步数最大。那要......
  • P2839 [国家集训队] middle
    Sol:首先注意到答案是具有单调性的，考虑二分答案\(x\)解决。令$up(l,r,x)/down(l,r,x)$是\([l,r]\)中大于等于/小于\(x\)的数。那么对于一个区间\([l,r]\)，显然中位数\(\gex\)的条件为\(up(l,r,x)\gedown(l,r,x)\).变形得到\(up(l,r,x)-down(l,r,......
  • 洛谷 P4451 [国家集训队] 整数的lqp拆分
    洛谷传送门设\(G\)为斐波那契数列的生成函数，显然有\(F=F\timesG+1\)。那么\(F=\frac{1}{1-G}=1+\frac{x}{1-2x-x^2}\)。问题是如何展开\(\frac{x}{1-2x-x^2}\)。因为\(\frac{1}{1-ax}=\sum\limits_{i\ge0}(ax)^i\)，所以考虑设\(\frac{x}{1-......
  • LibreOJ-3038 「JOISC 2019 Day3」穿越时空 Bitaro <线段树> 题解
    审题一条链每条边有通行时间上下界限制通过一条边需要\(1\)单位时间站在当前节点时间减少\(1\)耗费\(1\)单位代价\(q\)次询问要么更改一条边的通信时间上下界要么询问在\(b\)时刻在城市\(a\)，\(d\)时刻到达城市\(c\)的最小代价思想做题准备......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99