快读、关同步
int read(){
int f=1,x=0;char c=getchar();
while(!isdigit(c)) {
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
二进制转十进制
int get_10(string s){
int val=0;
for(int i=0;i<s.size();i++){
val*=2;
val+=s[i]-'0';
}
return val;
}
二进制拆分
int n;
v[N],w[N],dp[N];
int cnt;
for(int i=1;i<=n;i<<=1){
v[++cnt]=a*j;
w[cnt]=b*j;
c-=j;
}
if(n)v[++cnt]=a*c,w[cnt]=b*c;
子段最大异或和问题Trie树(前缀树、字典树)
const int N = 1000050;
int trie[N][26];
int cnt[N];
int id;
void insert(string s)
{
int p = 0;
for (int i = 0; i < s.size(); i++)
{
int x = s[i] - 'a';
if (trie[p][x] == 0) trie[p][x] = ++id;
p = trie[p][x];
}
cnt[p]++;
}
int find(string s)
{
int p = 0;
for (int i = 0; i < s.size(); i++)
{
int x = s[i] - 'a';
if (trie[p][x] == 0)return 0;
p = trie[p][x];
}
return cnt[p];
}
欧拉筛
int d=0;
int p[100010]={0};
int f[100010]={1,1};
int n;
cin>>n;
for(int i=2;i<=n;i++){
if(f[i]==0){//如果没被标记过，那么i是质数
p[d++]=i;
}
for(int j=0;j<d;j++){
if(p[j]*i<=n){//标记以i为最大因数的数为不是素数（除了1和本身）
f[p[j]*i]=1;
}else{
break;
}
if(i%p[j]==0){//如果p[j]是i的因数，那么后面的数都不是以i为最大因数的
break;
}
}
}
for(int i=0;i<d;i++){//打印1到n的质数
cout<<p[i]<<' ';
}
树状数组
const int N = 1000;
#define lowbit(x) ((x) & - (x))
int tree[N]={0};
void update(int x, int d) { //修改元素a[x], a[x] = a[x] + d
while(x <= N) {
tree[x] += d;
x += lowbit(x);
}
}
int sum(int x) { //返回前缀和sum = a[1] + a[2] +... + a[x]
int ans = 0;
while(x > 0){
ans += tree[x];
x -= lowbit(x);
}
return ans;
}
线段树
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 dis,int k){
if(tree[i].l==tree[i].r){//如果是叶子节点，那么说明找到了
tree[i].sum+=k;
return ;
}
if(dis<=tree[i*2].r) add(i*2,dis,k);//在哪往哪跑
else add(i*2+1,dis,k);
tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;//返回更新
return ;
}
区间修改：
void modify(int p, int l, int r, int k)
{
if(tr[p].l >= l && tr[p].r <= r) {
tr[p].num += k;
return ;
}
int mid = tr[p].l + tr[p].r >> 1;
if(l <= mid) modify(p << 1, l, r, k);
if(r > mid) modify(p << 1 | 1, l, r, k);
}
void query(int p, int x)
{
ans += tr[p].num;//一路加起来
if(tr[p].l == tr[p].r) return;
int mid = tr[p].l + tr[p].r >> 1;
if(x <= mid) query(p << 1, x);
else query(p << 1 | 1, x);
}
区间修改，区间查询：
void add(int i,int l,int r,int k)
{
if(tree[i].r<=r && tree[i].l>=l)//如果当前区间被完全覆盖在目标区间里，讲这个区间的sum+k*(tree[i].r-tree[i].l+1)
{
tree[i].sum+=k*(tree[i].r-tree[i].l+1);
tree[i].lz+=k;//记录lazytage
return ;
}
push_down(i);//向下传递
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);
tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
return ;
}
void push_down(int i)
{
if(tree[i].lz!=0)
{
tree[i*2].lz+=tree[i].lz;//左右儿子分别加上父亲的lz
tree[i*2+1].lz+=tree[i].lz;
int mid=(tree[i].l+tree[i].r)/2;
tree[i*2].sum+=tree[i].lz*(mid-tree[i*2].l+1);//左右分别求和加起来
tree[i*2+1].sum+=tree[i].lz*(tree[i*2+1].r-mid);
tree[i].lz=0;//父亲lz归零
}
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;
push_down(i);
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;
}
组合数
ll fac[110],inv[110];
const ll mod=998244353;
ll power(ll x,ll y){
ll ans=1;
while(y){
if(y&1)ans=ans*x%mod;
x=x*x%mod;
y>>=1;
}
return ans;
}
void init(){
fac[0]=1;inv[0]=power(1,mod-2);
for(ll i=1;i<=100;i++){
fac[i]=i*fac[i-1]%mod;inv[i]= power(fac[i],mod-2);
}
}
ll C(ll x,ll y){
if(x<y)return 0;
return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
另一个线段树板子
#include<bits/stdc++.h>
using namespace std;
const int inf=2e9;
const int iinf=-1;
struct node{
int minn,maxx;
}tr[400005];
int ql,qr,smn,smx;
int n,k;
int ans[100005][2];
void build(int o,int l,int r){
tr[o].maxx=iinf;
tr[o].minn=inf;
if(l==r){
int x;
scanf("%d",&x);
tr[o].maxx=tr[o].minn=x;
return;
}
int m=(l+r)>>1;
build(o*2,l,m);
build(o*2+1,m+1,r);
tr[o].maxx=max(tr[o*2].maxx,tr[o*2+1].maxx);
tr[o].minn=min(tr[o*2].minn,tr[o*2+1].minn);
}
void qu(int o,int l,int r){
if(ql<=l&&qr>=r){
smn=min(smn,tr[o].minn);
smx=max(smx,tr[o].maxx);
return;
}
int m=(l+r)>>1;
if(qr<=m)
qu(o*2,l,m);
else if(ql>m)
qu(o*2+1,m+1,r);
else{
qu(o*2,l,m);
qu(o*2+1,m+1,r);
}
}
int check(int l){
for(int i=1;i+l-1<=n;i++){
smn=inf;
smx = -1;
ql = i;
qr = i+l-1;
qu(1,1,n);
if(smx-smn<=k)
return 1;
}
return 0;
}
int main(){
ios::sync_with_stdio(false);
scanf("%d%d",&n,&k);
build(1,1,n);
int l=1,r=n,len=-1;
while(l<=r){
int m=(l+r)>>1;
if(check(m)){
l=m+1;
len=max(len,m);
}
else r=m-1;
}
int cnt=0;
for(int i=1;i+len-1<=n;i++){
smn=inf;
smx =-1;
ql=i;
qr = i+len-1;
qu(1,1,n);
if(smx-smn <= k){
ans[cnt][0]=i;
ans[cnt++][1]=i+len-1;
}
}
cout<<len<<" "<<cnt<<"\n";
for(int i=0;i<cnt;i++)
cout<<ans[i][0]<<" "<<ans[i][1]<<"\n";
return 0;
}
拓展欧几里得
定理1 gcd(a,b)是ax+by的线性组合的最小正整数，x，y∈z; 定理2 如果ax+by=c，x，y∈z；则c%gcd==0; 定理3 如果a，b是互质的正整数，c是整数，且方程
ax+by=c代码如下：
int exgcd(int a , int b , int &x , int &y) {
int res = a;
if(!b) {
x = 1 , y = 0;
}
else {
res = exgcd(b , a % b , x , y);
int temp = x;
x = y;
y = temp - a / b * y;
}
return res;
}
数论——反素数
我们知道任意一个正数都能被分解为多个素数相乘的形式，即素因数分解。我们又知道一个数的约数的个数等于各素因数的指数加一的乘积。
求有n个因数的最小正整数：
int prim[16]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};//定义16个是因为这16个想乘正好超ull
int n;
uLL ans;
void dfs(int pos,uLL v,int num){//注意v的类型。。。
if(num==n&&ans>v)ans=v;
//if(num>n)return;
for(int i=1;i<=63;i++){
if(num*(i+1)>n||v*prim[pos]>ans)break;//这里在于优化，要不要均可以；
dfs(pos+1,v*=prim[pos],num*(i+1));//保证小的素数必须成才能保证值的小。。。
}
}
字符串哈希
h[i]=h[i-1]p+s[i]-‘a’+1；
w[h-r]=h[h]-h[r-1]q ^ (h-r+1);
代码：
#include<stdio.h>
#include<string.h>
char a[1000010];
unsigned long long h[1000010],q[1000010];//一定要注意数据类型
int main()
{
int base=131;//将p取为131
scanf("%s",a+1);
int n,m,i;
m=strlen(a+1);
h[0]=0;
q[0]=1;
for(i=1;i<=m;i++)//从1开始
{
h[i]=h[i-1]*base+(a[i]-'a'+1);
q[i]=q[i-1]*base;
}
拓扑序
有向无环图 DAG
bfs模板
while(q.size()){
int x=q.top(); q.pop();
ans.push_back(x); //判环
cout<<x<<' ';
for(int i=0;i<v[x].size();i++){
int y=v[x][i];
in[y]--;
if(!in[y])q.push(y);
}
}
if(ans.size()==n) 无环，有拓扑序
else 有环，无拓扑序
最短路径——Floyd
求各顶点间距离的一种算法，
可以用于无向图和有向图中。
也可以用于负权的最短路径问题（虽然复杂度会比较高）。
Floyd算法的时间复杂度为O（n3），空间复杂度为O（n2）。
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i!=j){
f[i][j]=0x3f3f3f3f;
}
}
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
}
}
最短路径之——Bellman-ford
求解带负权边的单源最短路问题的经典算法。时间复杂度是O(nm)
一般用于实现通过m次迭代求出从起点到终点不超过m条边构成的最短路径。
注意如果图中有负权回路的话，最短路就不一定存在了
int bellman_ford()
{
//初始化距离
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=0;i<k;i++)
{
//记得备份，不然会发生串联
memcpy(backup,dist,sizeof dist);
//更新所有的边
for(int j=0;j<m;j++)
{
int a=edg[j].a,b=edg[j].b,c=edg[j].c;
dist[b]=min(dist[b],backup[a]+c);
}
}
return dist[n];
}
//这里不用0x3f3f3f3f是因为防止n号点被负权边更新
if(bellman_ford()>0x3f3f3f3f/2)
最短路之——Dijkstra
边权不能是负数
堆优化版 的Dijkstra算 法的时间复杂度是O(mlogn)，适合于稀疏图
int dist[N];
bool st[N];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
void dij(){
memset(dist,inf,sizeof(dist));
dist[s]=0;
q.push({0,s});
while(q.size()){
auto k=q.top();q.pop();
int ver=k.second,distance=k.first;
if(st[ver])continue;
st[ver]=true;
for(int i=0;i<g[ver].size();i++){
int j=g[ver][i].first;
if(dist[j]>distance+g[ver][i].second){
dist[j]=distance+g[ver][i].second;
q.push({dist[j],j});
}
}
}
}
最短路之——spfa
void spfa(){
queue<int> q;
q.push(1);
dis[1] = 0;
st[1] = true;
while(!q.empty() ){
//先初始化放入初始源点
int u = q.front();
q.pop();
st[u] = false;
//将此点优化过的点再次放入队列，重复这个过程直至队列为空即可
for(int i = h[u]; ~ i; i = ne[i] ){
int j = e[i];
if(dis[j] > dis[u] + w[i] ){
dis[j] = dis[u] + w[i];
// cnt[j] = cnt[u] + 1;
// if (cnt[j] >= n) puts("存在负环")
if(!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
}
二进制模板
while (l <= r) {
mid = (l + r) >> 1;
if (f(mid) <= 0) res = mid ,r = mid - 1; else l = mid + 1;
}
二分图
二分图定义：一定不含有奇数环，可能包含长度为偶数的环，不一定是连通图，且将所有点分成两个集合，所有边只出现在集合之间，就是二分图
判定代码：
int n = graph.size();
vector<int> cols(n, 0);
queue<int> q;
for(int i = 0; i < n; i++) {
if (!cols[i]) {
q.push(i);
cols[i] = 1;
while (!q.empty()) {
int node = q.front();
q.pop();
for(int j : graph[node]) {
int temp = cols[node];
if (temp == cols[j]) return false;
if (!cols[j]) {
cols[j] = -temp;
q.push(j);
}
}
}
}
}
return true;
}
最小生成树——prim
复杂度O（n方）
加点,n个点
void prim(){
memset(dist,inf,sizeof(dist));
dist[1]=0;vis[1]=true;
for(int i=0;i<g[1].size();i++)dist[g[1][i].first]=min(g[1][i].second,dist[g[1][i].first]);
for(int i=2;i<=n;i++){
int temp=inf,t=-1;
for(int j=2;j<=n;j++){
if(!vis[j]&&dist[j]<temp){
temp=dist[j];t=j;
}
}
if(t==-1){
res=inf;return ;
}
vis[t]=true;res+=dist[t];
for(int j=0;j<g[t].size();j++){
dist[g[t][j].first]=min(dist[g[t][j].first],g[t][j].second);
}
}
}
最小生成树——Kruskal
加边，n-1条边
并查集
int father[maxn];//father数组存放的是父亲结点
struct Edge{
int u;//左端点
int v;//右端点
int dis;//权值
}ed[maxn];
bool cmp(Edge a,Edge b){//结构体排序
return a.dis < b.dis;
}
void init(int n){//初始化
for(int i=1;i<=n;i++) father[i] = i;
}
int find_father(int x){//并查集核心操作
if(x==father[x]) return x;
int temp = find_father(father[x]);//路径压缩
return temp;
}
int Kruskal(int n,int m){
int ans = 0;//记入最小生成树的权值
int num_Edge = 0;//边的数目
for(int i=0;i<m;i++){
int fu = find_father(ed[i].u);//找最终父亲
int fv = find_father(ed[i].v);//找最终父亲
if(fu!=fv){
father[fu] = fv;//合并
ans+=ed[i].dis;
num_Edge++;
if(num_Edge==n-1) break;
}
}
if(num_Edge!=n-1) return -1;//退出条件
else return ans;
}
欧拉路
O(n+m)
欧拉路径（欧拉通路）：通过图中所有边的简单路。（换句话说，每条边都通过且仅通过一次）也叫”一笔画”问题。
欧拉回路：闭合的欧拉路径。（即一个环，保证每条边都通过且仅通过一次）
1.对于无向图，所有边都是连通的。
(1) 存在欧拉路径的充分必要条件: 度数为奇数的点只能有0或2个。
(2) 存在欧拉回路的充分必要条件: 度数为奇数的点只能有0个。
2.对于有向图，所有边都是连通.
(1) 存在欧拉路径的充分必要条件: 要么所有点的出度均等于入度要么除了两个点之外，其余所有点的出度等于入度，剩余的两个点: 一个满足出度比入度多1 (起点) ，另一个满足入度比出度多1 (终点)
(2) 存在欧拉回路的充分必要条件: 所有点的出度均等于入度
具有欧拉回路的图叫欧拉图
只具备通路无回路的图叫半欧拉图
#include <bits/stdc++.h>
using namespace std;
const int MAX=100010;
int n,m,u,v,del[MAX];
int du[MAX][2];//记录入度和出度
stack <int> st;
vector <int> G[MAX];
void dfs(int now)
{
for(int i=del[now];i<G[now].size();i=del[now])
{
del[now]=i+1;
dfs(G[now][i]);
}
st.push(now);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d%d",&u,&v),G[u].push_back(v),du[u][1]++,du[v][0]++;
for(int i=1;i<=n;i++) sort(G[i].begin(),G[i].end());
int S=1,cnt[2]={0,0}; //记录
bool flag=1; //flag=1表示,所有的节点的入度都等于出度,
for(int i=1;i<=n;i++)
{
if(du[i][1]!=du[i][0])
{
flag=0;
if(du[i][1]-du[i][0]==1/*出度比入度多1*/) cnt[1]++,S=i;
else if(du[i][0]-du[i][1]==1/*入度比出度多1*/) cnt[0]++;
else return puts("No"),0;
}
}
if((!flag)&&!(cnt[0]==cnt[1]&&cnt[0]==1)) return !puts("No"),0;
//不满足欧拉回路的判定条件，也不满足欧拉路径的判定条件，直接输出"No"
dfs(S);
while(!st.empty()) printf("%d ",st.top()),st.pop();
return 0;
}