526互联

板子合集

发布时间 2023-10-15 11:32:40作者: _Unnamed

板子索引

火车头

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <vector>
#include <queue>
#include <stack>
#include <sstream>
#include <cstring>
#include <string>
#include <cstdlib>
#define FOR(i, m, n) for (long long i = m; i <= n; i++)
#define FRO(i, m, n) for (long long i = m; i >= n; i--)
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define mp(a, b) make_pair(a, b)
#define INF 2147483647
#define INFF 0x3f3f3f3f3f3f3f3f
#define INFFF 0x7fffffffffffffff
using namespace std;

default


 int main(){


     return 0;
 }

 int main()
 {
     ll l,r;
     while (l < r)
     {
         int mid = (l + r) / 2;
         if (mid){
             r = mid;
         }
         else{
             l = mid + 1;
         }
     }
     return 0;
 }

DSU

 const int maxn=5010;
 int fa[maxn];
 int find(int x) {
 	if(x!=fa[x])
 		fa[x]=find(fa[x]);
 	return fa[x];
 }
 void connect(int x, int y){
 	int c=find(x);
 	int d=find(y);
 	fa[c]=d;
 }
 int main(){
     ll n,m,p;
     cin>>n>>m>>p;
     FOR(i,1,n)fa[i]=i;
     FOR(i,1,m){
         ll a,b;
         cin>>a>>b;
         connect(a,b);
     }
     FOR(i,1,p){
         ll a,b;
         cin>>a>>b;
         if(find(a)==find(b)){
             cout<<"Yes"<<endl;
         }
         else cout<<"No"<<endl;
     }
 }

Grape_DFS

 const int maxn=1000010;
 const int num=10;
 priority_queue< pair<ll,ll> >q;
 int head[maxn],nxt[maxn*num],to[maxn*num],tot,v[maxn];
 int val[maxn*num];
 int dist[maxn];
 int a,b;
 void add(int u,int v,int k){
 	to[++tot]=v;
 	val[tot]=k;
 	nxt[tot]=head[u];
 	head[u]=tot;
 	return;
 }
 ll ans;
 void dfs(ll x,ll sum){
     ans=max(sum,ans);
     v[x]=1;
     for(int i=head[x];i;i=nxt[i]){
 		int y=to[i];
 		if(v[y]) continue;
         dfs(y,val[i]+sum);
         v[y]=0;
         ans=max(sum,ans);
 	}
 }
 int main(){
     ll n,m;
     cin>>n>>m;
     FOR(i,1,m){
         ll u,v,k;
         cin>>u>>v>>k;
         add(u,v,k);
         add(v,u,k);
     }
     FOR(i,1,n){
         memset(v,0,sizeof(v));
         dfs(i,0);
     }
     cout<<ans;
     return 0;
 }

Floyd

 int a[505];
 int d[506][506];
 void Floyd(){
	for (int k=1;k<=n;k++)
		for (int i=1;i<=n;i++)
		    for (int j=1;j<=n;j++)
		        if (d[i][k]+d[k][j]<d[i][j]&&p[i]==1&&p[k]==1)
		            d[i][j]=d[i][k]+d[k][j];
   return ;
 }
 int main(){


     return 0;
 }

Dijkstra

 const int maxn = 1000010;
 const int num = 10;
 priority_queue<pair<ll, ll>> q;
 int head[maxn], nxt[maxn * num], to[maxn * num], tot, v[maxn];
 int val[maxn * num];
 int dist[maxn];
 int a, b;
 void add(int u, int v, int k)
 {
     to[++tot] = v;
     val[tot] = k;
     nxt[tot] = head[u];
     head[u] = tot;
     return;
 }
 void dijkstra()
 {
     memset(dist, 0x3f, sizeof(dist));
     dist[a] = 0;
     q.push(mp(-dist[a], a));
     while (!q.empty())
     {
         int x = q.top().second;
         if (v[x])
         {
             q.pop();
             continue;
         }
         x = q.top().second;
         q.pop();
         v[x] = 1;
         for (int i = head[x]; i; i = nxt[i])
         {
             int y = to[i];
             if (v[y])
                 continue;
             if (dist[y] > dist[x] + val[i])
             {
                 dist[y] = dist[x] + val[i];
                 q.push(mp(-dist[y], y));
             }
         }
     }
     return;
 }
 int main()
 {
     ll n, m;
     cin >> n >> m;
     FOR(i, 1, m)
     {
         ll u, v, k;
         cin >> u >> v >> k;
         add(u, v, k);
         add(v, u, k);
     }
     dijkstra();
     FOR(i, 1, n)
         cout << dist[i];
     return 0;
 }

Bellman-ford

 const int MAXN = 100010;
 int n,m,s;
 struct Edge {
 	int v;
 	int c;
 };
 vector<Edge> edges[MAXN];
 int dis[MAXN];
 void bellman_ford(){
 	dis[s] = 0;
 	FOR(i,1,MAXN-1)
 		if (i!=s)
 			dis[i]=0x3f3f3f3f;
 	FOR(i,1,n){
 		bool f=0;
 		FOR(u,1,n)
 			for (Edge edge:edges[u])
 				if (dis[edge.v]>dis[u] + edge.c) {
 					dis[edge.v]=dis[u] + edge.c;
 					f=true;
 				}
 		if(!f)break;
 	}
 }
 int main() {
 	cin>>n>>m>>s;
 	FOR(i,1,m){
 		int u,v,c;
 		cin>>u>>v>>c;
 		edges[u].push_back({v,c});
 	}
 	bellman_ford();
 	FOR(i,1,n)
 		printf("%d ",dis[i]);
 	return 0;
 }

SPFA

 const int MAXN = 100010;
 int n,m,s;
 struct Edge{
 	int v;
 	int c;
 };
 vector<Edge> edges[MAXN];
 int dis[MAXN];
 queue<int> q;
 bool in_queue[MAXN];
 void spfa(){
 	dis[s]=0;
 	FOR(i,1,MAXN-1)
 		if (i!=s)
 			dis[i]=0x3f3f3f3f;
 	q.push(s);
 	in_queue[s]=1;
 	while(!q.empty()) {
 		int u=q.front();
 		q.pop();
 		in_queue[u]=false;
 		for (Edge e:edges[u]) {
 			int v=e.v;
 			if (dis[v]>dis[u]+e.c){
 				dis[v]=dis[u]+e.c;
 				if (!in_queue[v]) {
 					q.push(v);
 					in_queue[v]=1;
 				}
 			}
 		}
 	}
 }
 int main() {
 	cin >>n>>m>>s;
 	FOR(i,1,m){
 		int u,v,c;
 		cin>>u>>v>>c;
 		edges[u].push_back({v,c});
 	}
 	spfa();
 	FOR(i,1,n)cout<<dis[i]<<" ";
 	return 0;
 }

Prim

 const int maxn = 400500;
 struct edge
 {
     int to, nxt, val;
 } e[maxn];
 int head[maxn], cnt, dis[maxn], tot, ans;
 bool vis[maxn];
 void add(int u, int v, int k)
 {
     e[++cnt].nxt = head[u];
     e[cnt].to = v;
     e[cnt].val = k;
     head[u] = cnt;
 }
 struct node
 {
     int pos, dis;
     friend bool operator<(node a, node b)
     {
         return a.dis > b.dis;
     }
 }tmp;
 priority_queue<node>q;
 int n, m;
 void prim(){
     FOR(i,1,n){
         dis[i]=2147483647;
     }
     dis[1]=0;
     tmp.dis=0;
     tmp.pos=1;
     q.push(tmp);
     while(!q.empty()){
         tmp=q.top();q.pop();
         int u=tmp.pos,t=tmp.dis;
         if(vis[u])continue;
         tot++;
         vis[u]=1;
         ans+=dis[u];
         for(int i=head[u];i;i=e[i].nxt){
             int v=e[i].to;
             int w=e[i].val;
             if(dis[v]>w){
                 tmp.dis=dis[v]=w;
                 tmp.pos=v;
                 q.push(tmp);
             }
         }
     }
 }
 int main()
 {
     cin >> n >> m;
     FOR(i, 1, m)
     {
         int a, b, c;
         cin >> a >> b >> c;
         add(a, b, c);
         add(b, a, c);
     }
     prim();
     if (tot == n)
     {
         cout << ans;
     }
     else
         cout << "orz";
 }

Kruskal

 const int maxn=1000010;
 int fa[maxn],n,k,m;
 struct node{
 	int u,v;
   ll w;
 }c[20*maxn];
 bool cmp(node a,node b){
 	return a.w<b.w;
 }
 int find(int x) {
 	if(x!=fa[x])
 		fa[x]=find(fa[x]);
 	return fa[x];
 }
 void connect(int x, int y){
 	int c=find(x);
 	int d=find(y);
 	fa[c]=d;
 }
 int main(){
     ll n,m;
     cin>>n>>m;
 	FOR(i,1,m)fa[i]=i;
     FOR(i,1,m){
         ll u,v,k;
         cin>>c[i].u>>c[i].v>>c[i].w;
     }
 	sort(c+1,c+n+1,cmp);
     ll ans=0,cnt=0;
 	FOR(i,1,n){
 		if(find(c[i].u)!=find(c[i].v)){
             int eu=find(c[i].u), ev=find(c[i].v);
             if(eu==ev){
                 continue;
             }
             ans+=c[i].w;
             fa[ev]=eu;
             if(++cnt==n-1)
             {
                 break;
             }
 		}
 	}
     cout<<ans;
 	return 0;
 }

Segment Tree

 const int maxn=1000006;
 ll a[maxn],w[maxn*4];
 void pushup(int u){
     w[u]=w[u*2]+w[u*2+1];
     return ;
 }
 void build(int u,int L,int R){
     if (L==R){
         w[u]=a[L];
         return ;
     }
     int M=(L+R)/2;
     build(u*2,L,M);
     build(u*2+1,M+1,R);
     pushup(u);
 }
 ll query1(int u,int L,int R,int p){
     if(L==R){
         return w[u];
     }
     else {
         int M=(L+R)/2;
         if(M>=p){
             return query1(u*2,L,M,p);
         }
         else return query1(u*2+1,M+1,R,p);
     }
 }
 void update1(int u,int L,int R,int p,ll x){
     if(L==R){
         w[u]=x;
         return;
     }
     else {
         int M=(L+R)/2;
         if(M>=p){
             update1(u*2,L,M,p,x);
         }
         else update1(u*2+1,M+1,R,p,x);
         pushup(u);
     }
 }
 bool InRange(int L,int R,int l,int r){
     return (l<=L) && (R<=r);
 }
 bool OutofRange(int L,int R,int l,int r){
     return (L>r) || (R<l);
 }
 ll lzy[maxn*4];
 void maketag(int u,int len,ll x){
     lzy[u]+=x;
     w[u]+=len*x;
     return ;
 }
 void pushdown(int u,int L,int R){
     int M=(L+R)/2;
     maketag(u*2,M-L+1,lzy[u]);
     maketag(u*2+1,R-M,lzy[u]);
     lzy[u]=0;
 }
 ll query(int u,int L,int R,int l,int r){
     if(InRange(L,R,l,r)){
         return w[u];
     }
     else if(!OutofRange(L,R,l,r)){
         int M=(L+R)/2;
         pushdown(u,L,R);
         return query(u*2,L,M,l,r) + query(u*2+1,M+1,R,l,r);
     }
     else return 0;
 }
 void update(int u,int L,int R,int l,int r,ll x){
     if(InRange(L,R,l,r)){
         maketag(u,R-L+1,x);
     }
     else if(!OutofRange(L,R,l,r)){
         int M=(L+R)/2;
         pushdown(u,L,R);
         update(u*2,L,M,l,r,x);
         update(u*2+1,M+1,R,l,r,x);
         pushup(u);
     }
 }
 int main(){
     int n,m;
     cin>>n>>m;
     FOR(i,1,n){
         cin>>a[i];
     }
     build(1,1,n);
     FOR(t,1,m){
         int op,x,y;
         ll k;
         cin>>op;
         if(op==1){
             cin>>x>>y>>k;
             update(1,1,n,x,y,k);
         }
         else {
             cin>>x>>y;
             cout<<query(1,1,n,x,y)<<endl;
         }
     }
     return 0;
 }

BIT

 const int maxn = 500010;
 int n, m;
 int a[maxn], c[maxn];
 int lowbit(int x)
 {
     return x & (-x);
 }
 int sum(int x)
 {
     int res = 0;
     for (int i = x; i; i -= lowbit(i))
         res += c[i];
     return res;
 }
 void add(int x, int y)
 {
     for (int i = x; i <= n; i += lowbit(i))
         c[i] += y;
 }
 int main()
 {
     cin >> n >> m;
     FOR(i, 1, n)
     {
         cin >> a[i];
         add(i, a[i]);
     }
     while (m--)
     {
         int op, x, y;
         cin >> op >> x >> y;
         if (op == 1)
         {
             add(x, y);
         }
         else
             cout << sum(y) - sum(x - 1) << endl;
     }
     return 0;
 }