首页 > 其他分享 >各种OI板子

各种OI板子

时间：2023-10-12 17:33:38浏览次数：32  
标签：cnt 各种 return OI ++ ll 板子 low inline

以下内容不定时更新，想到啥写啥。。

读写优化

快读

code 
template <class T> inline void read(T &res)
{
	char ch = getchar(); bool f = 0; res = 0;
	for(; !isdigit(ch); ch = getchar()) f |= ch == '-';
	for(; isdigit(ch); ch = getchar()) res = (res << 1) + (res << 3) + (ch  ^ 48);
	res = f ? ~res + 1 : res;
}

快写

code 
template <class T> inline void waw(T x)
{
	if(x > 9) waw(x / 10);
	putchar(x % 10 ^ 48);
}

template <class T> inline void ww(T x)
{
	if(x < 0) x = ~x + 1, putchar('-');
	waw(x);
}

基础算法

排序

快排

直接用自带的函数实现即可，sort(起点，终点，排列规则（这个可以没有）)。

归并

通常会用来求逆序对。

code 
void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

\(O(n)\) 的基数排序（位运算版本）

最快的排序方法。

code ``` inline void Sort() { static ll p = 65535; for (rl i = 1; i <= n; ++i) c[a[i] & p]++; for (rl i = 1; i <= p; ++i) c[i] += c[i - 1]; for (rl i = n; i >= 1; --i) b[c[a[i] & p]--] = i; memset(c, 0, sizeof c); for (rl i = 1; i <= n; ++i) c[(a[b[i]] >> 16) & p]++; for (rl i = 1; i <= p; ++i) c[i] += c[i - 1]; for (rl i = n; i >= 1; --i) d[c[(a[b[i]] >> 16) & p]--] = b[i]; for (rl i = 1; i <= n; ++i) b[i] = d[i]; } ```

排完序后 b 中是排好的序列。

图论

最短路

Floyd

code 
for(rl k=1; k <= n; ++ k)
	for(rl i=1; i <= n; ++ i)
		for(rl j=1; j <= n; ++ j)
			g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
			
// 传递闭包

#define for(i, a, b) for(rl i=a; i <= b; ++ i)

for(k, 1, n)
	for(i, 1, n)
		for(j, 1, n)
			g[i][j] |= g[i][k] & g[k][j];

spfa

code 
inline bool spfa()
{
	queue<ll> q;
	memset(dis, 0x3f, sizeof dis);
	dis[s] = 0, q.push(s);
	
	while(!q.empty())
	{
		ll u = q.front();
		q.pop(); st[u] = false;
		for(rl i=h[u]; ~i; i = ne[i])
		{
			ll v = e[i];
			if(dis[v] > dis[u] + w[i])
			{
				dis[v] = dis[u] + w[i];
				sla[v] = sla[u] + 1;
				if(sla[v] >= n + 2) return true; // 判断是否存在负环
				if(!st[v]) st[v] = true, q.push(v);
			}
		}
	}
	
	return true;
}

dijkstra( + heap)

code 
struct node
{
	ll id, dis;
	bool operator <(const node &x) const 
	{
		return dis > x.dis;
	}
};

inline void dijkstra()
{
	priority_queue<node> q;
	memset(dis, 0x3f, sizeof dis);
	dis[s] = 0, q.push({s, 0});
	
	while(q.size())
	{
		auto t = q.top();
		q.pop();
		ll u = t.id;
		if(st[u]) continue;
		st[u] = true;
		for(rl i=h[u]; ~i; i = ne[i])
		{
			ll v = e[i];
			if(dis[v] > dis[u] + w[i])
			{
				dis[v] = dis[u] + w[i];
				q.push({v, dis[v]});
			}
		}
	}
}

最小生成树

kruskal

code 
struct node
{
	ll u, v, w;
	bool used;
}e[M];

bool cmp(node a, node b) { return a.w < b.w; }

ll find(ll x) { return p[x] == x ? x : p[x] = find(p[x]); }

int main()
{
	scanf("%lld %lld", &n, &m);
	for(i ,1, n) p[i] = i;
	for(i, 1, m) scanf("%lld %lld %lld ", &e[i].u, &e[i].v, &e[i].w);
	sort(e + 1, e + m + 1, cmp);
	
	for(i, 1, m)
	{
		ll a = find(e[i].u), b = find(e[i].v), w = e[i].w;
		if(a != b)
		{
			ans += w;
			p[a] = b;
			e[i].used = true;
			if( ++ cnt = n - 1) break;
		}
	}
	return 0;
}

强连通分量相关

单连通分量 

ll dfn[N], low[N], timestamp, dep[N], scc_cnt, scc_size[N];

ll top, stk[N], id[N];

bool in_stk[N];

vector<ll> scc[N];

inline void tarjan(ll u)
{
	in_stk[u] = true;
	dfn[u] = low[u] = ++ timestamp, stk[ ++ top] = u;
	
	for(rl i=h[u]; ~i; i = ne[i])
	{
		ll v = e[i];
		if(!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); }
		else if(in_stk[v]) low[u] = min(low[u], low[v]);
	}
	
	if(low[u] == dfn[u])
	{
		ll ele; scc_cnt ++ ;
		do	{
			ele = stk[top -- ], in_stk[ele] = false;
			scc_size[scc_cnt] ++, scc[scc_cnt].push_back(ele);
			id[ele] = scc_cnt;
		} while(ele != u);
	}
}
点双连通分量 
ll dfn[N], low[N], dcc_cnt, dcc_size[N];

ll stk[N], top, id[N];

bool cut[N];

vector<ll> dcc[N];

inline void tarjan(ll u)
{
	dfn[u] = low[u] = ++ timestamp, stk[ ++ top] = u;
	
	if(u == root && h[u] == -1)
	{
		dcc_cnt ++, dcc[dcc_cnt].push_back(u);
		return ;
	}
	
	ll cnt = 0;
	
	for(rl i=h[u]; ~i; i = ne[i])
	{
		ll v = e[i];
		if(!dfn[v])
		{
			tarjan(v), low[u] = min(low[u], low[v]);
			if(dfn[u] <= low[v])
			{
				 ++ cnt; 
				 if(u != root || cnt > 1) cut[u] = true;
				 ++ dcc_cnt; 
				 ll ele;
				 do {
				 	ele = stk[ top -- ], dcc[dcc_cnt].push_back(ele);
				 } while(u != v);
				 dcc[dcc_cnt].push_back(u);
			}
		}
		else low[u] = min(low[u], dfn[v]);
	}
}
边双连通分量 
ll dfn[N], low[N], timestamp, id[N], dcc_cnt, dcc_size[N];

ll stk[N], top;

inline void tarjan(ll u, ll from)
{
	dfn[u] = low[u] = ++ timestamp;
	stk[ ++ top] = u; in_stk[u] = true;
	
	for(rl i=h[u]; ~i; i = ne[i])
	{
		ll v = e[i];
		if(!dfn[v]) 
		{
			tarjan(v), low[u] = min(low[u], low[v]);
			if(dfn[u] < low[v]) is_bridge[i] = is_bridge[i ^ 1] = true;
		}
		else if(i != (from ^ 1)) low[u] = min(low[u], dfn[v]);
	}
	
	if(dfn[u] == low[u])
	{
		ll ele; 
		dcc_cnt ++ ;
		do {
			ele = stk[top -- ]; dcc_size[dcc_cnt] ++ ;
			dcc[dcc_cnt].push_back(ele); id[ele] = dcc_cnt;
		} whie(ele != u);
	}

匈牙利算法

\(最小点覆盖 \leftrightarrow 最大匹配数 \leftrightarrow 顶点数 - 最小边覆盖 \leftrightarrow 顶点数 - 最大独立集\)

一维 
inline bool find(ll u)
{
	for(rl i=h[u]; ~i; i = ne[i])
	{
		ll v = e[i], t = match[v];
		if(st[v]) continue;
		st[v] = true;
		if(!t || find(r)) {match[v] = u; return true; }
	}
	return false;
}

int main()
{
	ll res = 0;
	
	for(i, 1, n)
	{
		memset(st, 0, sizeof st);
		if(find(i)) res ++ ;
	}
	return 0;
}
二维 
typedef pair<ll, ll> pll;

pll match[N][N];

ll dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // 不同的方向数组可能不同

inline bool find(ll x, ll y)
{
	for(i, 0, 3)
	{
		ll a = x + dx[i], b = y + dy[i];
		if(a < 1 || a > n || b < 1 || b > m) continue;
		if(st[a][b] || g[a][b]) continue; // st 为是否查询过，g 为是否能够放置棋子
		st[a][b] = true;
		
		auto = match[a][b];
		
		if(!t.x || find(t.x, t.y)) { match[a][b] = {x, y}; return true; }
	}
	
	return false;
}

差分约束

将式子转化为

\[x_a - x'_a \le k \]

连接从 \(x'_a\) 到 \(x_a\) 一条长度为 \(k\) 的边

倍增法求LCA

code 
#define ll long long 
#define rl register ll 

ll fa[N][M], dep[N];

inline void bfs()
{
    memset(dep, 0x3f, sizeof dep);

    dep[0] = 0, dep[1] = 1;

    ll hh = 0, tt = -1;

    q[ ++ tt] = 1;

    while(hh <= tt)
    {
        ll u = q[hh ++ ];
        for(rl i=h[u]; ~i; i = ne[i]) // 我的邻接表初始化为-1
        {
            ll v = e[i];
            if(dep[v] > dep[u] + 1)
            {
                dep[v] = dep[u] + 1;
                q[ ++ tt] = v;
                fa[v][0] = u;
                for(rl k=1; k < 21; ++ k)
                    fa[v][k] = fa[fa[v][k-1]][k-1];
            }
        }
    }
}

inline ll lca(ll a,  ll b)
{
    if(dep[a] < dep[b]) swap(a, b);
    for(rl i = 21; i >= 0; -- i)
        if(dep[fa[a][i]] >= dep[b])
            a = fa[a][i];

    if(a == b) return a;

    for(rl i=21; i >= 0; -- i)
        if(fa[a][i] != fa[b][i])
            a = fa[a][i], b = fa[b][i];
        
    return fa[a][0];
}

O(1) 复杂度访问LCA

code 
ll dep[N], st[M][N], dfn[N], idx;

inline ll get(ll a, ll b) { return dep[a] > dep[b] ? b : a; }

inline void dfs(ll u, ll fa)
{
    dep[u] = dep[fa] + 1, dfn[u] = ++ idx, st[0][idx] = fa;
    for(rl i=h[u]; ~i; i = ne[i]) { ll v = e[i]; if(v == fa) continue; dfs(v, u); } // 原因同上
}

inline void init()
{
    dfs(root, -1);

    for(rl j=0; j <= M; ++ j)
        for(rl i=1; i + (1 << j) - 1 <= n; ++ i)
            st[j][i] = get(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);
}

inline ll lca(ll a, ll b)
{
    if(a == b) return a;
    if((a = dfn[a]) > (b = dfn[b])) swap(a, b);
    ll l = __lg(b - a);
    return  get(st[l][a + 1], st[l][b - (1 << l) + 1]);
}

数据结构

树状数组（一维，单点修改，区间查询)

如若想要区间修改，单点查询，则只需要对存储的序列进行差分。然后存入树状数组

code 
#define lowbit(x) (x & -x)

inline void add(ll x, ll c)
{
	for(; x <= n; x += lowbit(x)) tr[x] += c;
}

inline ll sum(ll x)
{
	ll res = 0;
	for(; x; x -= lowbit(x)) res += tr[x];
	return res;
}

树状数组（二维，区间修改，区间查询）

树状数组在存储的时候同样也是存储差分序列。2023-10-12 16:20:18 星期四

code 
#define lowbit(x) (x & -x)

ll tr1[N], tr2[N];

inline void add(ll x, ll c)
{
	ll i = x - 1;
	for(; x <= n; x += lowbit(x)) tr1[x] += c, tr2[x] += i * c;
}

inline void sum(ll x)
{
	ll res = 0, resu = 0, i = x;
	for(; x; x -= lowbit(x)) res += tr1[x], resu += tr2[x];
	return i * res - resu
}

树链剖分

注意下面有打注释的地方不同题目可能不同，只是放了一些常见的操作。

code 

inline void add(ll a, ll b) { e[ ++ tot] = {b, h[a]}, h[a] = tot; }

inline void dfs1(ll u, ll p, ll d)
{
    fa[u] = p, dep[u] = d, sz[u] = 1;
    for(rl i=h[u]; ~i; i = e[i].ne)
    {
        ll v = e[i].v;
        if(v == p) continue;
        dfs1(v, u, d + 1);
        sz[u] += sz[v];
        if(sz[son[u]] < sz[v]) son[u] = v;
    }
}

inline void dfs2(ll u, ll t)
{
    top[u] = t, id[u] = ++ cnt, nw[cnt] = w[u];

    if(!son[u]) return ;
    
    dfs2(son[u], t);

    for(rl i=h[u]; ~i; i = e[i].ne)
    {
        ll v = e[i].v;
        if(v == son[u] || v == fa[u]) continue;

        dfs2(v, v);
    }
}

inline void update(ll u, ll l, ll r, ll k)
{
    if(l <= tr[u].l && r >= tr[u].r)
    {
        tr[u].tag += k, tr[u].minn += k; // 依据题目而不同
        return ;
    }

    pushdown(u); // 如果是区间修改且有懒标记的话，递归前要pushdown

    ll mid = tr[u].l + tr[u].r >> 1; // 注意别写成 l + r >> 1

    if(l <= mid) update(u << 1, l, r, k);
    if(r > mid) update(u << 1 | 1, l, r, k);

    pushup(u);
}

inline ll query(ll u, ll l, ll r)
{
    ll res = 1e17; // 依据题目求最大值最小值区间和而不同
    if(l <= tr[u].l && r >= tr[u].r) return tr[u].minn; // 同上

    pushdown(u);

    ll mid = tr[u].l + tr[u].r >> 1; // 注意同上

    if(l <= mid) res = min(res, query(u << 1, l, r));
    if(r > mid) res = min(res, query(u << 1 | 1, l, r)); // 同上

    return res;
}

inline void upd_path(ll u, ll v, ll k)
{
    while(top[u] != top[v])
    {
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        update(1, id[top[u]], id[u], k);
        u = fa[top[u]];
    }

    if(dep[u] < dep[v]) swap(u, v);

    update(1, id[v], id[u], k);
}

inline ll query_path(ll u, ll v) // 注释的查询路径的东西因题目而不同
{
    ll res = 1e17; // 

    while(top[u] != top[v])
    {
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        res = min(res, query(1, id[top[u]], id[u])); // query函数一样，但是求和还是最大值还是最小值不同
        u = fa[top[u]];
    }

    if(dep[u] < dep[v]) swap(u, v);

    res = min(res, query(1, id[v], id[u])); // 同上

    return res;
}

inline void upd_tree(ll u, ll k) // 修改子树
{
    update(1, id[u], id[u] + sz[u] - 1, k); 
}

inline ll que_tree(ll u) // 查询子树
{
    return query(1, id[u], id[u] + sz[u] - 1);
}

标签：cnt,各种,return,OI,++,ll,板子,low,inline
From： https://www.cnblogs.com/carp-oier/p/17749275.html

相关文章

  • 【noip赛前20天冲刺集训 day4】正在出模拟赛
    题目描述想象学竞赛网站CodeFancy举办了\(m\)场比赛。你在CodeFancy上关注了\(n\)个账号，编号为\(1\)到\(n\)。你知道这\(n\)个账号分别参加了\(m\)场比赛中的哪些。但是你发现可能存在一个人使用多个账号的情况，你想知道这\(n\)个账号的使用者最少共有多少人。......
  • CMD和ENTRYPOINT同时使用会如何？
    一问题CMD和ENTRYPOINT同时使用会如何？ 二解答ENTRYPOINT会将CMD中的值作为参数使用 验证如下：dockerfile文件如下：FROMcentos:7ENTRYPOINT["cal"]CMD["cal"]打包成镜像，随后run，结果如下： 三备注可以在run后，添加参数，将CMD中的值覆盖，覆盖后的值，会给ENTERPOINT......
  • 2023.10.9NOIPSIM1总结
    ##T1区分度先手算一下找下规律，发现数列呈现$1,2,2,3,3,4,4,4,5,5,5,6,6,6,6,7,7,7,7,8,8,8,8,8......$的规律。数据范围到$1e13$，考虑数论分块，每块的块长由前一块块长递推得到。在块内累$\Omicron$(1)累计答案，跳块时间复杂度$\Omicron$($\sqrtn$)，总复杂度$\Omicron(t\sqr......
  • Spring Boot + EasyExcel 导入导出，好用到爆，可以扔掉 POI 了
    1、EasyExcelEasyExcel是阿里巴巴开源poi插件之一，主要解决了poi框架使用复杂，sax解析模式不容易操作，数据量大起来容易OOM，解决了POI并发造成的报错。主要解决方式：通过解压文件的方式加载，一行一行的加载，并且抛弃样式字体等不重要的数据，降低内存的占用。EasyExcel优势注解式自定义操作......
  • [POI2004] Gra
    前言：谁知道我是怎么看教练的bug代码AC而怀疑人生的。已经研究困了。思路：题目传送门博弈论最重要的是，发现模型并进行转模。这题很容易发现，与阶梯模型十分相似。可以考虑每个棋子距离\(M\)还有多少空格转化成当前在第几级阶梯。可是当我们转化后发现，胜利条件有一些不一样......
  • Blazor Server App Cannot find the fallback endpoint specified by route values
    github官方issues中提到的解决方案，CreateBuilder时指定项目绝对路径可以解决。1//指定项目路径，也可以用Assembly.GetCallingAssembly获取2conststringContentRootPath=@"C:\Users\BlazorServer";//项目的路径3conststringApplicationName=nameof(BlazorServer);......
  • noip赛前20天冲刺集训 day2 ###寻找有向图中的最小疲惫路径###
    T1###寻找有向图中的最小疲惫路径###题目描述有一张n个点m条边的有向图，每条边上有一个正整数边权，你要顺着图上的有向边从1号点走到n号点。假设你经过的边边权依次为(w_1,w_2,\dots,w_t)，则你的疲惫程度为\[\f(w)=\max_{i=1}^{t}w_i\timesi\,.\]你需要找到最......
  • 【noip赛前20天冲刺集训 day3】矩阵挑战
    NOIP比赛前的冲刺训练-第3天：矩阵挑战问题描述您有一个n×m矩阵，行编号从0到n−1，列编号从0到m−1。最初，第i行第j列的元素是i*m+j。系统支持三种类型的操作：交换两行。交换两列。交换两个特定的元素。任务是确定执行q次操作后矩阵的状态。输入格式为了最小化输......
  • 2023NOIP A层联测9
    A.长春花简单题。打表发现情况并不多，记录下平方后模\(p\)对应的值，然后枚举\(a\)，用链表维护即可。点击查看代码#include<bits/stdc++.h>usingll=longlong;usingull=unsignedlonglong;inta[100005],b[100005],p,ans,mx;boolvis[100005];std::list<int>l;std::st......
  • 20231010NOIP训练赛
    20231010NOIP训练赛时间安排7:50-8:10写T18:10-8:40写T29:40-10:40写T310:40-11:50写T4总结没时间写T5，T4和T3没写对题解T1简单题，用两个桶记录一下，然后再做两遍前缀和T2二分+哈希T3分组背包T4双指针+动态开点的值域线段树T5建图之后发现是内向基环树森林，对于......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99