（^~^）-

#include<bits/stdc++.h>
using namespace std;
int d[1000005];
int main(){
	int n,k,x,y;
	cin>>n>>k>>x>>y;
	for(int i=1;i<=n;i++){
		int a;
		cin>>a;
		if(a>y){
			d[i]=0;
		}
		else{
			d[i]=(y-a)/x+1;
		}
	}
	sort(d+1,d+1+n);
	k=min(k,n);
	cout<<d[k];
} 

神奇药水!

#include<bits/stdc++.h>
using namespace std;
int fx[4][2]={1,0,0,1,-1,0,0,-1};
int n,m;
int bfs(int x,int y){
	queue(array<int,2>) que;
	vis[x][y]=1;
	que.push({x,y});
	int res=0;
	while(que.size()){
		int px=que.front()[0];
		int px=que.front()[1];
		que.pop();
		res++;
		for(int i=0;i<4;i++){
			int xx=px+fx[i][0];
			int yy=py+fx[i][0];
			if(xx>n||xx<1||yy>m||yy<1||vis[xx][yy]||mp[xx][yy]!='*')continue;
			vis[xx][yy]=1;
			que.push({xx,yy});
		}
	}
	return res;
}
int main(){
	
}

跳台阶

#include<bits/stdc++.h>
using namespace std;
int x[1010],y[1010];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}
	long long ans=10000000000000000;
	for(int i=1;i<=n;i++){
		long long res=0;
		for(int j=1;j<=n;j++){
			if(j!=i){
				res+=abs(x[i]-x[j])+abs(y[i]-y[j]);
			} 
		}
		ans=min(ans,res);
	}
	cout<<ans; 
}

拯救食堂

#include<bits/stdc++.h>
using namespace std;
int  a[100005],b[100005],c[100005];
int dp[100005][3];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i];
	for(int i=1;i<=n;i++){
		dp[i][0]=max(dp[i-1][1]+a[i],dp[i-1][2]+a[i]);
		dp[i][1]=max(dp[i-1][0]+b[i],dp[i-1][2]+b[i]);
		dp[i][2]=max(dp[i-1][0]+c[i],dp[i-1][1]+c[i]);
	}
	cout<<max({dp[i][0]=max(dp[n][0],dp[n][1],dp[n][2]);})
}

小青的五一假期

int haed[100000];//所有以i为开头的边的合集中，最后那个边的编号 
struct Edge{
	int to;//这条边的终点 
	int w;//这条边的边权 
	int next;//这条边在遍历的时候的下一条边是什么 
}edge[100000];
int cnt=0;//现在一共有多少条边 
void add_edge(in u,int v,int w){//加边的起点、终点、边权 
	cnt++;
	edge[cnt].to=v;
	edge[cnt].w=w;
	edge[cnt].next=head[u];
	haed[u]cnt;
}

列式前向星

#include<bits/stdc++.h>
using namespace std;
vector<int> adj[1000005];
int vis[1000005];
void dfs(int u){//深度优先遍历 
	cout <<u<<" ";
	vis[u]=1;
	for(int v:adj[u]){
	    if(vis[v]==1) continue;
	    dfs(v);
    }

深度优先遍历

void bfs(int u){
	queue<int> que;
	que.push(u);
	vis[u]=1;
	while(que.size()){
		int st=que.front();
		que.pop();
		cout<<st<<" ";
		for(int v:adj[st]){
			if(vis[v]==1) continue;
			vis[v]=1;
			que.push(v);
		}
	}
}

广度优先搜索

#include<bits/stdc++.h>
using namespace std;
vector<int> adj[2000];
int vis[2000];
int ans=0;
int dfs(int u){// 
	if(ans<u) ans=u;
	vis[u]=1;
	for(auto &v:adj[u]){
	    if(vis[v]==1) {
	    	continue;
		}
	    dfs(v);
    }
}

int main(){
	int n,m;cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;cin<<u<<v;
		adj[u].push_back(v);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) vis[j]=0;
		ans=0;
		dfs(i);
		cout<<ans<<" ";
	}
}

图的遍历

void merge(int x,int y){//把x连到y上
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy)
    f[fx]=fy;
}

并查集（合并find）

int find(int x){
    if(f[x]!=x){
        return find(f[x]);
    }
    return f[x];
}

并查集（查找自己的根find）

int find(int x){
    if(f[x]!=x){
        return f[x]=find(f[x]);//记录祖先zxian
    }
    return f[x];
}

并查集（路径压缩）

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int INF=2e9;
int dis[N];
int vis[N];
int n;
vector<pair<int,int> > adj[N];
void SPFA(int st){
	for(int i=1;i<=n;i++){
		dis[i]=INF;
	}
	queue<int> que;
	que.push(st);
	vis[st]=1;
	dis[st]=0;
	while(que.size() ){
		int u=que.front();
		que.pop();
		vis[u]=0;
		for(auto &it:adj[u]){
			int v=it.first;
			int w=it.second;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				if(!vis[v]){
					que.push(v);
					vis[v]=1;
				}
			}
		}
	}
}
int main(){
	int m;cin>>n>>m;
	int st;cin>>st;
	for(int i=1;i<=m;i++){
		int u,v,w;cin>>u>>v>>w;
		adj[u].push_back({v,w});
		
	}
	SPFA(st);
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
}

最短路径

#include<bits/stdc++.h>
using namespace std;
int f[6000];
void init(int n){
	for(int i=1;i<=n;i++) f[i] =i;
}
int find(int x){
    if(f[x]!=x){
        return f[x]=find(f[x]);
    }
    return f[x];
}
void merge(int x,int y){//把x连到y上
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy)
    f[fx]=fy;
}
vector<array<int,3> > vec;
int main(){
	int n,m;cin>>n>>m;
	init(n);
	for(int i=1;i<=m;i++){
		int u,v,w;cin>>u>>v>>w;
		vec.push_back({w,u,v});
	}
	sort(vec.begin(),vec.end());
	int ans=0;
	for(auto &it:vec){
		int w=it[0];
		int u=it[1];
		int v=it[2];
		if(find(u)!=find(v)) {
			merge(u,v);
			ans+=w;
		}
	}
}

最小生成树