首页 > 其他分享 >板子合集

板子合集

时间：2023-10-15 11:34:17浏览次数：28  
标签：int ll cin 板子 maxn include 合集 dis

板子索引

火车头

#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;
 }

FR(Fast Read)

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

 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;
 }

标签：int,ll,cin,板子,maxn,include,合集,dis
From： https://www.cnblogs.com/Unnamed-blogs/p/banzi-heji.html

相关文章

  • 考点列表（附板子）
      我不能白给啊啊啊啊啊！！！！！  我会在这里将最近的考到的知识点罗列，也当是快速复习与刷题计划吧。Part1数论相关计数类Lucas定理点击查看代码constintMod=?;intpowM(intx,inty=Mod-2){ intret=1; while(y){ if(y&1)ret=1ll*ret*x%Mod; x=1ll......
  • string用法合集
    \(string\)用法：使用索引访问：strings="123123123";则\(s[0]=1,s[1]=2\cdots\)。可以直接用运算符比较：strings1="asd";strings2="dsa";returns1<s2;//按字典序来，结果应该返回的是true字符串排序：strings="1b3rdc871yvbv";so......
  • 板子
    线段树#include<bits/stdc++.h>usingnamespacestd;structnode{intl,r;longlongpre,add,chen;}t[1000000];longlonga[1000000];longlongn,m,mod;voidbuild(intp,intl,intr){t[p].l=l;t[p].r=r;t[p].chen=1;if(l==r......
  • 各种OI板子
    以下内容不定时更新，想到啥写啥。。读写优化快读codetemplate<classT>inlinevoidread(T&res){ charch=getchar();boolf=0;res=0; for(;!isdigit(ch);ch=getchar())f|=ch=='-'; for(;isdigit(ch);ch=getchar())res=(res<<1)+......
  • 操作索引库-创建索引库（索引库相当于数据库，文档相当于数据库中的表，一种即具有相同数据
    创建索引库时可先定义映射，类似数据库中的约束 {"mappings":{"properties":{"title":{"type":"text"},"name":{"type":"text"},"created_at......
  • ps软件下载 软件电脑版 Photoshop下载_Photoshop合集下载
    Photoshop2022新版本，AdobeInc.旗下知名软件Photoshop系列推出了全新的2022版本，Photoshop2022在原来的基础上新增了一系列实用功能，可以满足用户的不同图片处理需求，Photoshop2022的图像处理能力更加优秀，有更多创意的互动工具可以体验，下面就为大家详细介绍Photoshop2022的一些新......
  • xcpc自用板子
    Bellman-Ford最短路O（nm)intINF=0x3f3f3f3f; structedge{intfrom,to,cost;}edges[12405]; intn,m; edgees[1000]; intd[2510];  voidshortest_path(ints){      for(inti=0;i<=n;i++){             d[i]=INF;     ......
  • LCT板子
    //我坚信LCT可以平替树剖#include<bits/stdc++.h>#definelst[o].ch[0]#definerst[o].ch[1]#defineintlonglongusingnamespacestd;constintN=500010;constintinf=1e9;intread(){intx=0,f=1;charch=getchar();while(ch<48||ch>57......
  • 安全工具合集：125个最佳网络安全工具-SecToolsOrg
    SecToolsOrg是什么SecToolsOrg是一个国外网友创建的安全工具网站，收集了125个最佳网络安全工具，网站为英文语言，网站提供评级、评论、搜索、排序和新工具建议表，该站点允许在任何平台上使用开源和商业工具，每款软件工具都有详细的介绍截图等等，感兴趣的同学可以到网站学习。英文页面......
  • 【合集】实在太懒把模拟赛分开新建随笔了
    B.特二分哈希找公共长度C.伯考场上其实是有往正解那个奇怪的结合上想的考虑n很小的时候怎么做：这时候可以用最小表示乘上排列数形态为树的时候，会发现可以直接dp，k中颜色实际上都是相同的所以直接设\(dp[i]\)表示节点i每一种颜色的ans考虑结合两部分将原图变为一......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99