Welcome to PhigrOS and Friday night Funkin or minecraft

来自初二的小朋友们！！ Welcome to the "Olympiad of Informatics" club! I'm your guide! Let's join the "xinao" family to study and Torture your mind~~

开胃小菜，请笑纳。 -O2 -std=c++14 -static

归并排序

const int N=1e6+10;
int n,a[N],t[N];
void ms(int l,int r){
	if(l>=r) return;
	int mid=(l+r)/2,i=l,j=mid+1,p=0;
	ms(l,mid);
	ms(mid+1,r);
	while(i<=mid&&j<=r){
		if(a[i]<=a[j]){
			t[++p]=a[i++];
		}else{
			t[++p]=a[j++];
		}
	}
	while(i<=mid) t[++p]=a[i++];
	while(j<=r) t[++p]=a[j++];
	for(int i=1;i<=p;i++) a[l++]=t[i];
}

以上均以qs/ms(1,n)使用。

重载结构体排序

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
struct student{
	int x;
	bool operator<(const student& t)const{
		return x<t.x;
	}
}stu[N];
int main(){
	for(int i=0;i<N;i++)cin>>stu[i].x;
	sort(stu,stu+N);
	return 0;
}//N只是示例而已，具体的看输入条件

堆（可用于树）

priority_queue<int>q;//默认大顶堆 
priority_queue<int,vector<int>,less<int>>q;//小顶堆 
priority_queue<int,vector<int>,greater<int>>q;//大顶堆 
q.push(x) //入堆 
q.pop() //出堆 
q.top() //堆顶 
q.size() //元素数量

迪杰斯特拉

#include<bits/stdc++.h>
using namespace std;
const int N=2505,M=6205;
int n,m,s,t,g[N][N];
void dij(){
	vector<long long> dis(N,1e18);
	vector<bool> st(N,0);
	dis[s]=0;
	for(int i=1;i<=n;i++){
		int u=-1;
		for(int j=1;j<=n;j++){
			if(!st[j]&&(u==-1||dis[u]>dis[j]))u=j;
		}
		if(u==-1) break;
		st[u]=1;
		for(int j=1;j<=n;j++){
			int v=j,w=g[u][j];
			dis[v]=min(dis[v],dis[u]+w);
		}
	}
	printf("%lld\n",dis[t]);
}
int main(){
	scanf("%d%d%d%d",&n,&m,&s,&t);
	memset(g,0x3f,sizeof(g));
	int v,u,w;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		g[u][v]=g[v][u]=min(g[v][u],w);
	}
	for(int i=1;i<=n;i++){
		g[i][i]=0;
	}
	dij();
	return 0;
}

链式前向星（用于图）

struct node{
	int v,nxt;
}e[N];//路径
int head[N],cnt;
void add(int a,int b){
	cnt++;
	e[cnt].v=b;
	e[cnt].nxt=head[a];
	head[a]=cnt;
	return;
}

树形背包（理解版）

#include<iostream>
#include<vector>
using namespace std;
struct Thing//定义一个物品结构体包括物品属性体积和价值 
{
	int vi;
	int wi;
};
/*定义以下全局变量*/ 
vector< vector<int> >tree;//定义一个二维数组存储各个节点的子节点信息 
vector<Thing>things; //定义物品数组存储物品的信息 
int N,V;//定义物品的数量和背包的体积 
int ans[110][110]; //定义二维数组存储答案ans[i][j]表示在选节点i且体积不超过j的前提下所能得到的最大价值 
void dfs(int Node)
{/*此函数的功能是在得到一个节点后我们要把在选这个节点的情况下
   的每一体积下的最大值都求出来并存入ans数组中 */
	if(things[Node].vi <= V)//先判断背包能否放下该节点代表的物品如果可以则进入判断 
	{
		if(tree[Node].size()==0||things[Node].vi == V)
    	{/*判断如果该节点没有子节点或其代表的物品体积恰好等于背包体积
		   在这两种情况下都不必再去考虑该节点的子节点怎么选择直接赋值*/ 
    		for(int i=things[Node].vi;i<=V;i++)
    		{/*将大于或等于该物品的各个体积全赋为该物品的价值
			   并将其他体积全赋值为0这里因为ans为全局变量所以
			   各点本身就以赋初值为0在这里就不再进行这一操作*/
    			ans[Node][i]=things[Node].wi;
    		}	
    	}
    	else//否则我们需要考虑其子节点的选择情况 
    	{
    		for(int k=0;k<tree[Node].size();k++)//我们要遍历各个子节点 
    		{
				dfs(tree[Node][k]);//首先我们求出选这个子节点的情况下各体积下的最优解 
    			for(int i=V-things[Node].vi;i>=0;i--)
    			{/*我们开始求选当前节点的情况下各体积下的最优解
				   我们的体积从V-things[Node].vi开始到0因为我们
				   确定了选当前物品所以要为他留出空间，体积从大
				   到小是因为和01背包一样子节点的每种体积至多可以选一遍*/
    				for(int j=0;j<=i;j++)//当前0到i这个范围就是这个子节点以下所能占用的体积我们要从这些体积中选出最优的那个体积 
    					ans[Node][i] = max(ans[Node][i],ans[Node][i-j]+ans[tree[Node][k]][j]);
						/*状态转移我们要用在不选、以及分别从这个子节点以下选总体积为1、2……i的物品中
						  选择一个最佳决策，即比较当前价值和选不同体积下的价值分别作比较*/
    			}
    		}
    		for(int i=V;i>=things[Node].vi;i--)//最后我们要将我们的根节点的价值加入即开始我们为之空出的体积 
    		{//在这个体积以上的全部加上这个节点代表的物品的价值 
    			ans[Node][i] = ans[Node][i-things[Node].vi] + things[Node].wi;
    		}
    		for(int i = 0;i < things[Node].vi;i++ )
			{/*这个体积以下的代表这个节点不能选这个节点不能选那么他所有的子节点也不能选所以全部赋初值为0
			   这里需要赋值是因为我们在上面的求大体积最优解的时候用到了这块体积我们已经为他们赋上值了
			   它们已经不是0了所以这里的赋0不能省*/
				ans[Node][i]=0;
			}
    	}
	}
}
int main()
{
	int root;      //定义一个变量一会储存根节点 
	cin>>N>>V;     //输入物品数和背包体积 
	tree.resize(N);//开辟空间一个数组储存各节点的子节点信息从而储存整棵树的结点关系 
	for(int i=0;i<N;i++)//遍历输入物品信息 
	{
		int v,w,f;
		cin>>v>>w>>f;
		things.push_back({v,w});//将物品信息放入物品数组things 
		if(f==-1)//检查该节点的父节点是哪一个如果它是父节点则记录它 
		{
			root=i;
		}
		else//如果不是父节点在在其父节点代表的一维数组中存入该节点 
		{
			tree[f-1].push_back(i);//我们的节点下标从0到n-1输入的父节点是1到n所以让输入的f减去1即我们要找的父节点 
		}
	}
	dfs(root);//从根节点调用递归函数 
	cout<<ans[root][V]<<endl;//输出最终结果 
	return 0;
} 
//https://zhuanlan.zhihu.com/p/648341058

线段树

初段

//P1313 区间和 
#include<bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const long long maxn=1e6+10;
long long n,sum[maxn<<2],q;
//依照题意非子节点赋值 
void Pushup(long long rt){
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
//建树 
void build(long long l,long long r,long long rt){//l区间左边界 ，r区间右边界 ，rt此时节点编号 
	//sum[rt]
	if(l==r){//判断-如果是叶子节点，赋值sum[rt] 
		scanf("%lld",&sum[rt]);
		return;//因为是叶子节点，所以没有子节点 
	}
	long long m=(l+r)>>1;//中点 
	//lson:l,m,rt<<1，rson:l,m,rt<<1|1 
	build(lson);//建左子结点 
	build(rson);//建右子结点
	Pushup(rt);//放入sum[rt]的值 
}
//依照题意更新
void update(long long L,long long R,long long v,long long l,long long r,long long rt){//L目标区间左边界，R标目区间右边界，v更新值 
	if(l==r){
		sum[rt]+=v;
		return;
	}
	long long m=(l+r)>>1;//二分查找 --| 
	if(L<=m)update(L,R,v,lson);//     |左端 
	if(m<R)update(L,R,v,rson);//    <-|右端 
 	Pushup(rt);//更新此节点 
}
//依照题意查询 
long long query(long long L,long long R,long long l,long long r,long long rt){//L目标区间左边界，R标目区间右边界，v更新值 
	if(L<=l&&r<=R){
		return sum[rt];
	}
	long long m=(l+r)>>1,res=0;//二分查找
	if(L<=m)res+=query(L,R,lson);//左端
	if(m<R)res+=query(L,R,rson);//右端 
 	return res;//返回答案 
}
int main(){
	scanf("%lld%lld",&n,&q);
	build(1,n,1);//从根节点rt=1开始建树 
	long long op,a,b;
	while(q--){
		scanf("%lld%lld%lld",&op,&a,&b);
		if(op==1){
			update(a,a,b,1,n,1);
		}else{
			printf("%lld\n",query(a,b,1,n,1));
		}
	}
	return 0;
}

lazy优化

//P1313 区间和 
#include<bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const long long maxn=1e6+10;
long long n,sum[maxn<<2],lazy[maxn<<2],q;
//依照题意非子节点赋值 
void Pushup(long long rt){
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
//建树 
void build(long long l,long long r,long long rt){//l区间左边界 ，r区间右边界 ，rt此时节点编号 
	if(l==r){//判断-如果是叶子节点，赋值sum[rt] 
		scanf("%lld",&sum[rt]);
		return;//因为是叶子节点，所以没有子节点 
	}
	long long m=(l+r)>>1;//中点 
	//lson:l,m,rt<<1，rson:l,m,rt<<1|1 
	build(lson);//建左子结点 
	build(rson);//建右子结点 
	Pushup(rt);//放入sum[rt]的值 
}
//为sum[rt]标记并改变其值 
void addlazy(long long l,long long r,long long rt,long long v){
	lazy[rt]+=v;//其以下的叶子结点标记值位v 
	sum[rt]+=v*(r-l+1);//其本身的值加上其以下的叶子结点所改变的总和（v*r-l+1） 
}
//下放标记（lazy） 
void Pushdown(long long l,long long r,long long rt,long long m){
	if(lazy[rt]==0) return;
	//lson:l,m,rt<<1，rson:l,m,rt<<1|1 
	addlazy(lson,lazy[rt]);//为左儿子标记并使其本身的值加上其以下的叶子结点所改变的总和  
	addlazy(rson,lazy[rt]);//为左儿子标记并使其本身的值加上其以下的叶子结点所改变的总和  
	lazy[rt]=0;//消除标记 
}
//依照题意更新（lazy） 
void update(long long L,long long R,long long v,long long l,long long r,long long rt){//L目标区间左边界，R标目区间右边界，v更新值 
	if(L<=l&&r<=R){//确定符合条件的区间 
		addlazy(l,r,rt,v);//在这一区间内在sum[rt]放下lazy标记，标记值为v 
		return;
	}
	long long m=(l+r)>>1;//二分
	Pushdown(l,r,rt,m);
	if(L<=m)update(L,R,v,lson);
	if(m<R)update(L,R,v,rson);
 	Pushup(rt);//更新此节点 
}
//依照题意查询 
long long query(long long L,long long R,long long l,long long r,long long rt){//L：目标区间左边界，R：标目区间右边界，v：更新值 
	if(L<=l&&r<=R){//如果现在的区间就在目标区间内 
		return sum[rt];//返回其值 
	}
	long long m=(l+r)>>1,res=0;//二分查找
	Pushdown(l,r,rt,m);
	if(L<=m)res+=query(L,R,lson);//左端
	if(m<R)res+=query(L,R,rson);//右端
	Pushup(rt);//更新此节点，可要可不要 
	return res;//返回答案 
}
int main(){
	scanf("%lld%lld",&n,&q);
	build(1,n,1);//从根节点rt=1开始建树 
	long long op,a,b;
	while(q--){
		scanf("%lld%lld%lld",&op,&a,&b);
		if(op==1){
			update(a,a,b,1,n,1);
		}else{
			printf("%lld\n",query(a,b,1,n,1));
		}
	}
	return 0;
}