#include <iostream> #include <cstring> #include <map> #include <algorithm> using namespace std; string equa; int match(int i) { int c = 0; while(i < equa.size()) { if(equa[i] == '(') c ++; else if(equa[i] == ')') c --; if(c == 0) return...

1：找到所有质因数p[i]2:遍历： n / p + n / p^2 +..... 约数个数 n = (p1 ^ c1) + (p2 ^ c2);ans = (c1 + 1)(c2 + 1); 欧拉函数 1 - n 中和n 互质的个数n = (p1 ^ c1) * (p2 ^ c2)u(n) = n * (1 - 1 / p1) * (1 - 1 / p2);求欧拉函数 void init(int n) { phi[1] = 1; for(int i = 2; i <= n; ++i) { if(!vis[i]) { ...

函数 build modify query pushup 更新父节点 pushdown (多点查询) 懒标记 pushdown 在pushup 前边 最大公约数： (x, y, z) = (x, y - x, z - y);

单点修改 区间查询 区间修改 单点查询 差分数组 区间查询 区间修改 (差分 两个前缀和 (bi) (i * bi))

并查集size -> 绑定到祖宗节点 叶子节点到祖宗节点距离 -> 绑定到叶子节点上

结论 不存在奇数环染色法不存在矛盾 匈牙利 最大匹配数 = 最小点覆盖 = 总点数- 最大独立集 = 总点数- 最小路径覆盖 最小路径重复点覆盖 = 传递闭包+ 最小路径覆盖 最小路径覆盖 做法： 拆点思想

有向图 双连通分量图：max(p,q); p 起点 q 终点 无向图 边双连通分量 判定： dfn[u] < low[to] 边双连通分量图: (cnt + 1) / 2; 点双连通分量 判定：1：dfn[u] <= low[y]2: (1) u 不是根节点 √(2) u 是根节点 存在两个以上符合要求的yi

1. 倍增的思想（基于二进制拼凑的思想） 倍增法最重要的思想就是根据二进制思想加上fa和depth数组去实现fa[][] 数组depth[] 数组 2：tarjan 离线算法（类似缩点的原理） int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } void add(int from,int to,int w) { e[tot].to = to, e[tot].nxt = h[from], e[tot].w = w; h[from] = tot ++; } void dfs(int u,int f...

个人认为这个题的测试数据有问题。 前边已经对sexs设置过初值，后边else语句不加过不了最后一个测试点，说明存在对一个人性别的反复修改。因为性别不同输出是不一样的。 ac代码： #include <bits/stdc++.h> using namespace std; const int N = 3e5+10; int h[N],tot,vis[N]; bool sexs[N]; struct Edge{ int to,nxt; }e[N]; void add(int from,int to) { e[tot].to = to, e[tot].nxt = ...

1：实实在在的建图，n层 2：逻辑上的对图分层，一般就是给dis数组或者vis数组，总之就是你需要参与求解实际问题的数据结构额外增加一维数组来模拟n层的效果 例题：ACWing340通信线路 第一种： 优先队列 按照pair的第一个int按降序排列，所以路径设置为-w，但是无关紧要，它只提供选择顺序，真正修改的是dis数组，输出的也是dis数组的值。 #include<bits/stdc++.h> using namespace std; const int maxn = 1e6+100,maxm = 1e7+10,maxk = 1e3+10; int dis[maxn...

STL容器开在函数体内和体外还能卡超时？涨姿势了 #include<iostream> #include<cstring> #include<queue> using namespace std; const int maxr = 30, maxc = 30; int maze[maxr][maxc],vis[maxr][maxc][1<<15]; int dir[maxr]; int dx[4] = {1,0,-1,0}; int dy[4] = {0,-1,0,1}; int R,C,L,kase; struct Node { in...

是的 不压行就不会作死，当你调试半天调不对的时候一般是你很sb的随手打错一行你以为肯定不会错的代码，就当锻炼纠错能力了(本质还是菜。。) #include<iostream> #include<cstring> #include<queue> using namespace std; #define maxn 1005 #define maxm 500005 #define INF 1000000000 int tot; struct node { int to,w,nxt; }e[maxm],re[maxm]; int head[maxn],rhe...

分层图的两种建法 1：直接建k-1层图 2：给dis或vis或你需要记录信息的数组额外增加一维模拟n层图的效果 至于分层图的理解，个人认为就是有一些干扰信息时，比如免费经过一些路径或者有特殊限制的时候，可以从当前图免费跳到下一层或上一层图来转换状态。 #include <cstdio> #include<algorithm> #include<cstring> #include<queue> #include<cmath> using namespace std; const int maxn = 1e3+10, maxm ...

头一次见这么夸张的剪枝操作。 这个点也很难想 2*r*h=S * r*r*h=V * => V*2/r = S S + sumS >= best => return; #include <cstdio> #include<algorithm> #include<cmath> using namespace std; int best = 0x7ffffff; const int maxn = 1e3+10; int minv[maxn]; int n,m; void dfs(int now,int sums,int sumv,...