首页 > 其他分享 >CSP-J/S & NOIP 常用板子大全 !

CSP-J/S & NOIP 常用板子大全 !

时间：2022-11-23 09:55:08浏览次数：74  
标签：return NOIP int tree long 板子 fa include CSP

HN CSP-J/S 2022 RP++ !

序号 算法
① SPFA
② 并查集
③ 最小生成树
④ 拓扑排序
⑤ 堆
⑥ 字典树
N 懒得加了

1. SPFA

题目链接

题目描述

输入的第一行是四个整数，代表站点个数 n 和线路条数 m ，出发点 x 和 目的地 y 。

第 2 到第 (m + 1) 行，每行三个整数 u, v, w 代表存在一条从 u 出发到达 v 的线路，边权为 w。

输出从 x 到 y 点的最短路径。

ｃｏｄｅ

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

int n , m , x , y ;
int tot ;
int head[1000005] ;
int dis[1000005] ;
int b[1000005] ;

struct node {
	int u , v , w , next ;
} e[1000005] ; 

void add ( int u , int v, int w ) {
	tot++ ;
	e[tot].u = u ;
	e[tot].v = v ;
	e[tot].w = w ;
	e[tot].next = head[u] ;
	head[u] = tot ;
}

void spfa ( int s ) {
	queue < int > q ;
	for ( int i = 1 ; i <= n ; i++ ) {
		dis[i] = 1E15 ;
	}
	b[s] = 1 ;
	dis[s] = 0 ;
	q.push ( s ) ;
	while ( ! q.empty( ) ) {
		int u = q.front( ) ;
		q.pop( ) ;
		b[u] = 0 ;
		for ( int i = 1 ; i != 0 ; i = e[i].next ) {
			int v = e[i].v ;
			int w = e[i].w ;
			if ( dis[u] + w < dis[v] ) {
				dis[v] = dis[u] + w ;
				if ( b[v] == 0 ) {
					b[v] = 1 ;
					q.push ( v ) ;
				}
			}
		}
	}
}

int main ( ) {
	
	cin >> n >> m >> x >> y ;
	for ( int i = 1 ; i <= m ; i++ ) {
		int u , v , w ;
		cin >> u >> v >> w ;
		add ( u , v , w ) ;
	}
	spfa( x ) ;
	
	cout << dis[y] ;
	
	return 0 ;
}

2. 并查集

题目链接

ＰＳ：注意要将 fa 数组指向自己

ｃｏｄｅ

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

int n , m ;
int fa[10005] ;

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

int main ( ) {
	
	cin >> n >> m ;
	for ( int i = 1 ; i <= n ; i++ ) {
		fa[i] = i ;
	}
	for ( int i = 1 ; i <= m ; i++ ) {
		int z , x , y ;
		cin >> z >> x >> y ;
		x = find ( x ) ;
		y = find ( y ) ;
		if ( z == 1 ) {
			fa[x] = y;
		}
		else if ( z == 2 ) {
			if ( x == y ) {
				cout << "Y" << endl ;
			}
			else {
				cout << "N" << endl ;
			}
		}
	} 
	
	return 0 ;
}

３. 最小生成树

题目链接

ｃｏｄｅ

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

int n , m ;
int tot , cnt , sum ;
int fa[500005] ;

struct node {
	int u , v , w , next ;
} e[400005] ;  

bool cmp ( node x , node y ) {
	return x.w < y.w ;
}

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

int main ( ) {
	
	cin >> n >> m ;
	for ( int i = 1 ; i <= n ; i++ ) {
		fa[i] = i ;
	}
	for ( int i = 1 ; i <= m ; i++ ) {
		cin >> e[i].u >> e[i].v >> e[i].w ;
	}
	
	sort ( e + 1 , e + m + 1 , cmp ) ;
	
	for ( int i = 1 ; i <= m ; i++ ) {
		int u = e[i].u ;
		int v = e[i].v ;
		int w = e[i].w ;
		u = find ( u ) ;
		v = find ( v ) ;
		if ( u != v ) {
			fa[u] = v ;
			cnt++ ;
			sum += w ;
		}
		if ( cnt == n - 1 ) {
			cout << sum ;
			return 0 ;
		}
	}
	
	cout << "orz" ;
	
	return 0 ;
}

４. 拓扑排序

题目链接

ｃｏｄｅ

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

int n , m ;
int ans ;
int head[5005] ;
int ind[5005] ;
int sum[5005] ;

struct node {
	int u , v , next ;
} e[500005] ;

void topsort ( ) {
	queue<int> q ;
	for ( int i = 1 ; i <= n ; i++ ) {
		if ( ind[i] == 0 ) {
			q.push( i ) ;
			sum[i] = 1 ;
		}
	}
	while ( !q.empty() ) {
		int u = q.front() ;
		q.pop();
		for ( int i = head[u] ; i != 0 ; i = e[i].next ) {
			int v = e[i].v ;
			ind[v]--;
			sum[v] += sum[u] ;  // 继承上一个结点 
			sum[v] %= 80112002 ;
			if ( ind[v] == 0 ) {
				q.push( v ) ;
			}
		}
	}
}

int main() {
	
	cin >> n >> m ;
	for ( int i = 1 ; i <= m ; i++ ) {
		int u , v ;
		cin >> u >> v ;
		e[i].u = u ;
		e[i].v = v ;
		e[i].next = head[u] ;
		head[u] = i ;
		ind[v]++ ;  // 出度 +1  
	}
	topsort();
	for ( int i = 1 ; i <= n ; i++ ) {
		if ( head[i] == 0 ) {
			ans += sum[i] ;
			ans %= 80112002 ;  // 提前模 防止爆数组 
		}
	}
	
	cout << ans ;
	
	return 0 ;
}

５. 堆

题目模板

ｃｏｄｅ

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

priority_queue < int , vector < int > , greater < int > > q ;

int main ( ) {
	
	int n ;
	cin >> n ;
	for ( int i = 1 ; i <= n ; i++ ) {
		int op ;
		cin >> op ;
		if ( op == 1 ) {
			int x ;
			cin >> x ;
			q.push ( x ) ;
		}
		if ( op == 2 ) {
			cout << q.top ( ) << endl ;
		}
		if ( op == 3 ) {
			q.pop ( ) ;
		}
	}
	
	return 0 ;
}

６. 字典树

题目链接

ｃｏｄｅ

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

int t;
int cnt;
int tri[4000005][65];
long long ans[4000005];

int bh( char a ){
	if( a >= 'A' && a <= 'Z' ) {
		return a - 'A';
	}
	else if( a >= 'a' && a <= 'z' ) {
		return a - 'a' + 26;
	}
	else if( a >= '0' && a <= '9' ) {
		return a - '0' + 52; 
	}
} 

void build( string a ){
	int len = a.size();
	int root = 0;
	for( int i = 0 ; i < len ; i++ ) {
		int x = bh( a[i] );
		if( !tri[root][x] ) {
			++cnt , tri[root][x] = cnt;
			root = cnt;
		}
		else {
			root = tri[root][x];
		}
		ans[root]++;
	}
}

int query( string a ){
	int len = a.size();
	int root = 0;
	for( int i = 0 ; i < len ; i++ )
	{
		int x = bh( a[i] );
		if( !tri[root][x] ) return 0;
		else root = tri[root][x];
	}
	return ans[root];
}

void qk(){
	for( int i = 0 ; i <= cnt ; i++ ) {
		for( int j = 0 ; j <= 64 ; j++ ) {
			tri[i][j] = 0;
		}
	}
	for( int i = 1 ; i <= cnt ; i++ ) {
		ans[i] = 0;
	}
	cnt = 0;
}

void work(){
	
	qk();
	int n , q;
	cin >> n >> q;
	for( int i = 1 ; i <= n ; i++ ) {
		string a;
		cin >> a;
		build( a );
	}
	for( int i = 1 ; i <= q ; i++ ) {
		string a;
		cin >> a;
		cout << query( a ) << endl;
	}
}

int main(){
	
	cin >> t;
	for( int i = 1 ; i <= t ; i++ ) {
		work();
	}
	
	return 0;
}

二分查找

元素最后出现位置 等于upper_bound

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n,m,i,x,ans;
int a[1000005]; 
int main()
{
 scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
 for(i=1;i<=m;i++)
   {
    scanf("%d",&x);
    int li=1,ri=n,mi;
    while(li<=ri)
      {
	   mi=li+(ri-li)/2;
	   if(x<a[mid]) ri=mi-1;
	          else {ans=mi;li=mi+1;}
	  } 
	 if(a[ans]==x) printf("%d ",ans);
	        else   printf("-1 ");
    }
 return 0;
}


 元素最先出现位置 等于lower_bound
 
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n,m,i,x,ans;
int a[1000010]; 
int main()
{
 scanf("%d%d",&n,&m);
 for(i=1;i<=n;i++) scanf("%d",&a[i]);
 for(i=1;i<=m;i++)
   {
    scanf("%d",&x);
    int li=1,ri=n,mi;
    while(li<=ri)
      {
	   mi=li+(ri-li)/2;
	   if(x<=a[mi]) {ans=mi;ri=mi-1;}
	          else  li=mi+1;
	  } 
	 if(a[ans]==x) printf("%d ",ans);
	        else   printf("-1 ");
    }
 return 0;
}

hash插入函数

void insert()
{
	int hx=1;
	for(int i=0;i<re.size();i++)
	{
		hx=(hx*base+re[i])%mod;
	}
	for(int i=0;i<s[hx].size();i++)
	{
		if(s[hx][i]==re) return;
	}
	ans++;
	s[hx].push_back(re);
}

快速幂

long long pow(long long x,long long y,long long m)
{
	long long re=1;
	while(y>=1)
	{
		if(y&1) re=re*x%m;
		x=x*x%m;
		y>>=1;
	}
	return re;
}

线段树

inline void build(int i,int l,int r){//递归建树
    tree[i].l=l;tree[i].r=r;
    if(l==r){//如果这个节点是叶子节点
        tree[i].sum=input[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(i*2,l,mid);//分别构造左子树和右子树
    build(i*2+1,mid+1,r);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;//刚才我们发现的性质return ;
}
例子：求和
inline int search(int i,int l,int r){
    if(tree[i].l>=l && tree[i].r<=r)//如果这个区间被完全包括在目标区间里面，直接返回这个区间的值
        return tree[i].sum;
    if(tree[i].r<l || tree[i].l>r)  return 0;//如果这个区间和目标区间毫不相干，返回0
    int s=0;
    if(tree[i*2].r>=l)  s+=search(i*2,l,r);//如果这个区间的左儿子和目标区间又交集，那么搜索左儿子
    if(tree[i*2+1].l<=r)  s+=search(i*2+1,l,r);//如果这个区间的右儿子和目标区间又交集，那么搜索右儿子
    return s;
}

区间修改

inline void add(int i,int l,int r,int k){
    if(tree[i].l>=l && tree[i].r<=r){//如果这个区间被完全包括在目标区间里面，讲这个区间标记k
        tree[i].sum+=k;
        return ;
    }
    if(tree[i*2].r>=l)
        add(i*2,l,r,k);
    if(tree[i*2+1].l<=r)
        add(i*2+1,l,r,k);
}

//单点查询
void search(int i,int dis){
    ans+=tree[i].sum;//一路加起来
    if(tree[i].l==tree[i].r)
        return ;
    if(dis<=tree[i*2].r)
        search(i*2,dis);
    if(dis>=tree[i*2+1].l)
        search(i*2+1,dis);
}

树状数组（简单版线段树）

int lowbit(int x)
{
	return x&(-x);
}//求二进制最低位1 
/*void add(int u,int v)//u表示位置,v表示加数 
{
	for(int i=u;i<=n;i+=lowbit(i))
	{
		c[i]+=v;
	}
	return;
}
void build()
{
	for(int i=1;i<=n;i++)
	{
		add(i,a[i]);
	}
	return;
}O(nlogn)build*/
void build()
{
	for(int i=1;i<=n;i++)
	{
		c[i]+=a[i];
		int fa=i+lowbit(i);
		if(fa<=n)
		{
			c[fa]+=c[i];
		}
	}
	return;
}//O(n)build

   单点修改
   
void change(int u,int v)//u is address,v is the number that add.
{
	for(int i=u;i<=n;i+=lowbit(i))
	{
		c[i]+=v;
	}
} 
int getsum(int m)//前缀和
{
	int ans=0;
	for(int i=m;i>0;i-=lowbit(i))
	{
		ans+=c[i];
	}
	return ans;
}

标签：return,NOIP,int,tree,long,板子,fa,include,CSP
From： https://www.cnblogs.com/HaoranZing/p/16917322.html

相关文章

  • 过往的NOIP啊（叹
    感觉最近状态相当差劲。P7960[NOIP2021]报数依题意枚举特殊数字的倍数即可。P7961[NOIP2021]数列直接无脑状压可以拿到\(\operatorname{50pts}\)。实际上可以不......
  • NOIP2017Day2T3-列队
    3、列队TimeLimit:2SecMemoryLimit:512MBDescriptionSylvia是一个热爱学习的女♂孩子。前段时间，Sylvia参加了学校的军训。众所周知，军训的时候需要站方......
  • 2022NOIPA层联测33
    C.建筑鹤了才发现我的50pts部分分居然和正解很沾边！！感觉所有序列上说什么用笛卡尔树的东西都可以用单调栈代替，比如《矩形》。50%code/*二缺吧我是，调了俩小时才发现......
  • 2022NOIP A层联测33 GCD 简单题 建筑 树上前缀和
    T1:[图论/枚举]给出有边权无向图，边权保证互不相同，Q次询问从S到T的路径中，边权的gcd最大是多少。(n<=1e4,Q<=2e5,w<=1e6)考场根据之前的一道图论题经验，在最短路上加个“\(w......
  • 快速幂（板子）
    先讨论无需取模的当b为偶数时：ab=a(b/2)*2=(a2)b/2当b为奇数时：ab=a*ab-1=a*(a2)(b-1)/2如 28=（22）4     27=2*(22)3所以，我们可以如此迭代下......
  • NOIP2017Day2T1-奶酪
    题目描述现有一块大奶酪，它的高度为  ，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系，在坐标系中，奶......
  • NOIP2016Day2T2-蚯蚓
    B:蚯蚓时间限制:1Sec  内存限制:512MB题目描述本题中，我们将用符号LcJ表示对c向下取整，例如：L3.0J=L3.1J......
  • NOIP2015Day1T2-信息传递
    2．信息传递(message.cpp/c/pas)【问题描述】有n个同学（编号为1到n）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为i的同学的信息传递......
  • NOIP2015Day2T1-跳石头
    1．跳石头(stone.cpp/c/pas)【问题描述】一年一度的“跳石头”比赛又要开始了！这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石......
  • NOIP2015Day2T2-子串
    2．子串(substring.cpp/c/pas)【问题描述】有两个仅包含小写英文字母的字符串A和B。现在要从字符串A中取出k个互不重叠的非空子串，然后把这k个子串按照其在字符串A中出现......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99