Stone

#include <bits/std++.h>
using namespace std;
const int N=1e5+10;
int h[N];
int size;
//big堆 
void down(int u){
	int t=u;
	if (u*2<=size&&h[t]<h[2*u]) t=u*2;
	if (u*2+1<=size&&h[t]<h[2*u+1])t=u*2+1;
	if(t!=u){
		swap(h[t],h[u]);
		down(t);
	}
}
void up(int u){
//	if(u==0)return;
	if(u/2!=0&&h[u]>h[u/2]){//父节点存在 且 插入小于父节点 
		swap(h[u],h[u/2]);
		up(u/2);
	}
}
int main(){
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		cin>>h[i];
	}
	size=n;
	//建堆 
	for (int i=n/2;i;i--){//2（0）+2(1)+....+2(n-2)=n/2 
		down(i);
	} 
	while(size>1){
		 if(h[1]==h[2])
	}
	return 0;
}

372 【提高】拦截导弹问题 Ⅱ

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> ve;

int main() {
	freopen("missile.in","r",stdin);
   freopen("missile.out","w",stdout);
	int n;
	cin>>n;
	for (int i=0; i<n; i++) {
		int h;
		cin>>h;
   
		if (ve.size()==0) {
			ve.push_back({h});
//			ve [0].push_back({h});
		} else {
			int id=-1;
			for (int j=0; j<ve.size(); j++) {
				if (ve[j].back()>=h) {
					if (id==-1) {
						id=j;
					} else {
						if(ve[j].back()<ve[id].back()) {
							id=j;
						}
					}
				}
			}
				if(id==-1)
					ve.push_back({h});
				else {
					ve[id].push_back(h);
				}
			}
			
		}
		cout<<ve.size()<<endl;
		for(int i=0; i<ve.size(); i++) {
			cout<<i+1<<":";
			for (int j=0; j<ve[i].size(); j++)
				cout<<ve[i][j]<<" ";
			cout<<endl;
		}

		return 0;
	}

770 【基础】链表操作

#include <bits/stdc++.h>
using namespace std;
vector<int> ve;
int m,n;
int main(){
	scanf("%d%d",&n,&m);
	int op,x,y,z;
	for (int i=0;i<n;i++) {
		int val;
		scanf("%d",&val);
		ve.push_back(val);
	}
	for (int i=0;i<m;i++) {
		scanf("%d",&op);
		switch (op){
			case 1:
				scanf("%d%d",&x,&y);
				ve.insert(ve.begin()+x,y);
		        break;
		    case 2:
		    	scanf("%d",&x);
		    	ve.erase(ve.begin()+x-1);
		    	break;
		    case 3:
		    	scanf("%d%d",&x,&y);
		    	sort(ve.begin()+x-1,ve.begin()+y);
		    	break;
		    case 4:
		    	scanf("%d%d",&x,&y);
		    	reverse(ve.begin()+x-1,ve.begin()+y);
		    	break;
		    case 5:
		    	scanf("%d%d%d",&x,&y,&z);
		    	for (int j=x-1;j<=y-1;){
		    		if(ve[j]==z){
		    			ve.erase(ve.begin()+j);
		    			y--;
					}else{
						j++;
					}
				}
				break;
		}   
	}
	for (auto it=ve.begin();it!=ve.end();it++){
		cout<<*it<<" ";
	}
	
	
	
	return 0;
}

2849 单调栈(递减)

#include<bits/stdc++.h>
using namespace std;

int ans[110];
int tt=-1;
int main(){
    int n;
    cin>>n;
    for (int i=0;i<n;i++){
    	int val;
    	cin>>val;
    	while (tt!=-1&&ans[tt]<=val) {
    		tt--;
		} 
		ans[++tt]=val;
		for (int j=0;j<=tt;j++) {
			cout<<ans[j]<<" ";
		}
		cout<<endl;
	}

	
	return 0;
}

Useful

链表

#include<bits/stdc++.h>
using namespace std;
struct NodeLinkList{
	int data;
	NodeLinkList *next;
};
int sum;
void init(NodeLinkList* &L){
	L=new NodeLinkList;
	L->data=-1;
	L->next=NULL;
}
void insert1(int i,NodeLinkList* L){//头 
	NodeLinkList *P=new NodeLinkList;
	P->next=L->next;
	L->next=P;
	P->data=i;
}
void insert2(NodeLinkList* &L,int i){//尾 
	NodeLinkList *node=new NodeLinkList;
	NodeLinkList *last=NULL;
	last=L;
	while(last->next)last=last->next;
	node->next=NULL;
	last->next=node;
	node->data=i;
	sum++; 
}
void delect(NodeLinkList* &L,int i){//删除
	NodeLinkList *p=new NodeLinkList;
//	if(i==0){
//		p=L;
//	}else {
//		p=L->next;
//	}
	p=L; 
	int num=0;
	while(p&&num<i){
		p=p->next;
		num++;
	}	
	NodeLinkList *ts=NULL;
	ts=p->next->next;
	delete(p->next);
	p->next=ts;
	sum--; 
}
int main(){
	NodeLinkList *L;
	init(L);
	int n,data,m;
	cin>>n;
	//头插法 
//	for(int i=0;i<n;i++){
//		cin>>data;	
//		insert(data,L);
//	}
	//尾插法 
	NodeLinkList *end;
	for(int i=0;i<n;i++){
		cin>>data;
		insert2(L,data); 
	}
	cin>>m;//删第m个 
	delect(L,m-1);
	NodeLinkList *P=L->next;
	while(P!=NULL){
		cout<<P->data<<" ";
		P=P->next;
	}
	
	return 0;
}

梦熊联盟

YOhhh 2113

#include <iostream>
#include <iomanip>
using namespace std;
int arr[20];
bool ist[10];
int n;
void dfs(int k,int val){
	arr[k]=val;
	if(k==n){
		for(int i=1;i<=n;i++){
			printf("%5d",arr[i]);\
			//cout<<setw(5)<<arr[i];
		}
		cout<<'\n';
		return;
	}
	for(int i=1;i<=n;i++){
		if(!ist[i]){
			ist[i]=true;
			dfs(k+1,i);
			ist[i]=false;
		}
	}

}
int main(){
	cin>>n;
	for (int i=1;i<=n;i++){
		ist[i]=true;
		dfs(1,i);
		ist[i]=false;
	}
	return 0;
}

439 【基础】走出迷宫

#include <bits/stdc++.h>
using namespace std;
struct point {
	int x,y;//t
};
int f[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};
char arr[150][150];
int n,m,stx,sty,edx,edy;//ans=1e6
bool is_ans;
bool ist[200][200]= {0};
point parent[200][200];//保存父节点
void print_ans() {
	stack<point> st;//利用栈（zhan）的特性--先进后出
	st.push({edx,edy});
	point p=parent[edx][edy];//终点的上一步 
	while(p.x!=stx||p.y!=sty) {//如果不是起点 
		st.push(p);//将当前路径点推入栈 
		p=parent[p.x][p.y];//将p重设为父节点；找到当前路径点的上一步（其父亲点） 
	}
	printf("(%d,%d)",stx,sty);//输出起点 
	while(!st.empty()) {//遍历栈 
		p=st.top();//got栈顶
		st.pop();//弹出栈顶 
		printf("->(%d,%d)",p.x,p.y);//输出当前路径点 
	}
}
bool isf(int x,int y) {
	return x>=1&&x<=n&&y>=1&&y<=m&&!ist[x][y];
}

void bfs() {
	queue<point>qu;
	qu.push({stx,sty});
	ist[sty][stx]=true;
	parent[stx][sty].x=-1;//起点没有父节点
	parent[edx][edy].y=-1;
	while(!qu.empty()) {
		int x=qu.front().x;
		int y=qu.front().y;
//		int t=qu.front().t;
		qu.pop();
		for(int i=0; i<4; i++) {
			int xx=x+f[i][0];
			int yy=y+f[i][1];
			if(xx==edx&&yy==edy) {
				//		ans=min(ans,t);
				is_ans=true;
				parent[edx][edy].x=x;
				parent[edx][edy].y=y;
				print_ans();
				return;
			}
			if(arr[xx][yy]!='1'&&isf(xx,yy)) {
				qu.push({xx,yy});
				ist[xx][yy]=true;
				parent[xx][yy].x=x;//保存当前子节点的父节点坐标
				parent[xx][yy].y=y;
			}
		}
	}
}
int main() {
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			cin>>arr[i][j];
		}
	}
	cin>>stx>>sty>>edx>>edy;
	bfs();
	if(!is_ans) cout<<"no way";
	//(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,3)->(5,3)->(6,3)->(6,4)->(7,4)->(8,4)

	return 0;
}

const int N=1e5+10;
bool ist[N];
int isprime[N]
int idx=0;
void Ei(int n){
	for(int i=2;i<=n;i++){
		if(ist[i]) continue;
		isprime[++idx]=i;
		int k=2;
		while(i*k<=n){//将范围内的质数倍数都标记 
			ist[i*k]=true;//保障了上面if判断ist[i]为false时一定是质数 
			k++;
		}
	}
}
void Oi(int n){
	for(int i=1;i<=n;i++){
		if(!ist[i]){
			isprime[++idx]=i;
		}
		for(int j=1;j<=idx;j++){
			if(i*isprime[j]>n) break;
			isf[i*isprime[j]]=true;
			if(i%isprime[j]==0) break;
		}
	}
}

502??

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
string st,ed="123804756";
struct node {
	string x;
	int id;
} u,v;
queue<node>q;
map<string,int> vis,dis;
int d1[4]= {0,0,-1,1};
int d2[4]= {-1,1,0,0};
int bfs() {
	if(st==ed)return 0;
	u.x=st;
	dis[st]=0;
	for(int i=0; i<9; i++) if(st[i]=='0') u.id=i;
	q.push(u);
	vis[st]=1;
	u.x=ed;
	dis[ed]=0;
	for(int i=0; i<9; i++) if(ed[i]=='0') u.id=i;

	q.push(u);
	vis[ed]=-1;
	while (!q.empty()) {
		u=q.front();
		q.pop();
		int x=u.id/3,y=u.id%3;
		for(int i=0; i<4; i++) {
			int tx=x+d1[i],ty=y+d2[i];
			if(tx<0||tx>2||ty<0||ty>2) continue;
			v.id=tx*3+ty;
			v.x=u.x;
			swap(v.x[u.id],v.x[v.id]);
			if(vis[v.x]==vis[u.x]) continue;
			else if(vis[v.x]==-vis[u.x])return dis[u.x]+dis[v.x]+1;
			q.push(v);
			vis[v.x]=vis[u.x];
			dis[v.x]=dis[u.x]+1;
		}
	}

}



int main() {
	cin>>st;
	cout<<bfs();


	return 0;

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
vector<int> e[100012];
int n,d;
int main() {
	cin>>n>>d;
	int x,y;
	for(int i=1li<n;i++){
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	
	
	
	
    return 0;
}

catcatcat

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
//单源最短路：给定起点s，求s到其他点的最短路
//1.广搜（必须所有边长度相等） 
//

//



vector<int> e[100012];




queue<int>q; 
int n,d,dis[100012],vis[100012],ans;
void bfs(){
	q.push(1);
	vis[1]=true;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<e[u].size();i++){
			int v=e[u][i];
			if(vis[v])continue;
			q.push(v);
			vis[v]=true;
			dis[v]=dis[u]+1; 
		}
	}
}



int main() {
	cin>>n>>d;
	int x,y;
	for(int i=1;i<n;i++){
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	bfs();
	for(int i=2;i<=n;i++)if(dis[i]<=d)ans++;
	printf("%d\n",ans);
	return 0;
}

[CSP-J2019 江西] 道路拆除

#include<bits/stdc++.h>
using namespace std;

vector <int> e[3012];
int d1[3012],d2[3012],d3[3012],vis[3012],m,n,ans=1e9,s1,t1,s2,t2;
queue<int> q;
void bfs(int st,int dis[]) {
	for(int i=1; i<=n; i++) dis[i]=1e8,vis[i]=false;
	q.push(st);
	vis[st]=true;
	dis[st]=false;
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		for(int i=0; i<e[u].size(); i++) {
			int v=e[u][i];
			if(vis[v])continue;
			q.push(v);
			vis[v]=true;
			dis[v]=dis[u]+1;
		}
	}
}

int main() {
	cin>>n>>m;
	int x,y;
	for(int i=1; i<=m; i++) {
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	cin>>s1>>t1>>s2>>t2;
	bfs(1,d1);
	bfs(s1,d2);
	bfs(s2,d3);
	for(int i=1; i<=n; i++)if(d1[i]+d2[i]<=t1&&d1[i]+d3[i]<=t2)ans=min(ans,d1[i]+d2[i]+d3[i]);
	if(ans==1e9) puts("-1");
	else cout<<m-ans;

	
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

vector <int> e[1000212];
int st=1,dis[100012][2],vis[100012][2],n,m,Q;
struct node{
	int v,id;
}U;
queue<node>q;
void bfs(){
	for(int i=1;i<=n;i++)dis[i][0]=dis[i][1]=1e8;
	U.v=st;
	U.id=0;
	q.push(U);
	vis[st][0]=true;
	dis[st][0]=false;
	while(!q.empty()){
		int u=q.front().v,id=q.front().id;
		q.pop();
		for(int i=0;i<e[u].size();i++){
			int v=e[u][i];
			if(vis[v][id^1])continue;
			U.v=v;
			U.id=id^1;
			q.push(U);
			vis[v][id^1]=true;
			dis[v][id^1]=dis[u][id];
			
		}
	}
}





int main() {
	cin>>n>>m>>Q;
	int x,y;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
    bfs();
    while(Q--){
    	cin>>x>>y;
    	if(dis[x][y%2]>y)puts("No");
    	else puts("Yes");
	}
	
    return 0;
}