ACM板子（1）（缺最短路、计算几何、数学、高级数据结构）
快排、归并
void quicksort(int* num,int l,int r)
{
if(r<=l) return;
int x=l-1,y=r+1,z=num[l+r>>1];
while(x<y)
{
do x++;while(num[x]<z);
do y--;while(num[y]>z);
if(x<y) swap(num[x],num[y]);
}
quicksort(num,l,y);
quicksort(num,y+1,r);
}
LL merge_sort(int l,int r)
{
if(l>=r) return 0;
int mid=l+r>>1;
LL res=merge_sort(l,mid)+merge_sort(mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r)
{
if(q[i]<=q[j]) tmp[k++]=q[i++];
else
{
res+=mid-i+1;
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];
return res;
}
kmp
for(int i=2,j=0;i<=n;i++)
{
while(j&&p[i]!=p[j+1]) j=ne[j];
if(p[i]==p[j+1]) j++;
ne[i]=j;
}
for(int i=1,j=0 ;i<=m;i++)
{
while(j&&s[i]!=p[j+1]) j=ne[j];
if(s[i]==p[j+1]) j++;
if(j==n)
{
printf("%d ",i-n+1-1);
j=ne[j];
}
}
滑动窗口
int n,k;//最小值为递增队列，最大值递减队列
int main()
{
cin.tie(0);
cin>>n>>k;
hh=0,tt=-1;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++)
{
if(hh<=tt&&i-k+1>q[hh]) hh++;//控制队列长度为k
while(hh<=tt&&a[q[tt]]>a[i]) tt--;//当队尾值比 a[i]大时弹出
q[++tt]=i;
if(i>=k-1) cout<<a[q[hh]]<<" ";//第k次之后才输出
}
cout<<endl;
hh=0,tt=-1;
for(int i=0;i<n;i++)
{
if(hh<=tt&&i-k+1>q[hh]) hh++;
while(hh<=tt&&a[q[tt]]<a[i]) tt--;
q[++tt]=i;
if(i>=k-1) cout<<a[q[hh]]<<" ";
}
}
Tire
int son[N][26], idx=0,cnt[N];
//son 数组 行 为根节点 列代表子节点
void insert(char str[])
{
int p=0;
for(int i=0;str[i];i++)
{
int u=str[i]-'a';
if(!son[p][u]) son[p][u]=++idx;//注意要先++，表示son这个位置存进一个idx，表示创建子节点，
p=son[p][u];//p走向下一个根节点，实际上是上一次的子节点。
}
cnt[p]++;
}
int query(char str[])
{
int p=0;
for(int i=0;str[i];i++)
{
int u=str[i]-'a';
if(!son[p][u]) return 0;//数组中在这个根节点 没有这个字母的子节点
p=son[p][u];//继续找下一个字母
}
return cnt[p];
}
散列表
const int N =100003;
int h[N],e[N],ne[N],idx;
void insert(int x)
{
int k=(x % N + N) % N;//哈希函数
e[idx]=x;
ne[idx]=h[k];
h[k]=idx++;
}
bool find(int x)
{
int k=(x %N + N) % N;
for(int i=h[k];i!=-1;i=ne[i])
if(e[i]==x) return true;
return false;
}
二分图最大匹配
const int N =510,M=100010;
int h[N],ne[M],e[M],idx;
bool st[N]; //表示本次循环右边该点是否被考虑过 每次不要重复搜一个点（因为一次循环内不需要再更改这个点的match）
int match[N];
bool find(int x)
{
for(int i=h[x];i!=-1;i=ne[i])
{
int j=e[i];
if(!st[j]) //本次循环内没有考虑过j
{
st[j]=true;
if(match[j]==0||find(match[j])) //j没有匹配过，或者再find一次和j匹配的节点能匹配到新的
//代表这个j可以和当前这个x匹配
{
match[j]=x;
return true;
}
}
}
return false;
}
int main()
{
memset(h,-1,sizeof h);
cin>>n1>>n2>>m;
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
}
int res=0;
for(int i=1;i<=n1;i++)
{
memset(st,false,sizeof st);
if(find(i)) res++;//成功匹配
}
cout<<res;
return 0;
}
spfa判断负环
const int N =1000010;
int h[N],e[N],w[N],ne[N],idx;
int dist[N],cnt[N];//存每个点最短路长度
int n,m;
bool st[N];
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int spfa()
{
queue<int> q;
for(int i=1;i<=n;i++)
{
st[i]=true;
q.push(i);
}
while(q.size())
{
int t=q.front();
q.pop();
st[t]=false;
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]>dist[t]+w[i])
{
dist[j]=dist[t]+w[i];
cnt[j]=cnt[t]+1;
if(cnt[j]>=n)
{
return true;
}
if(!st[j])
{
st[j]=true;
q.push(j);
}
}
}
}
return false;
}
筛法求欧拉函数
const int N =1000010;
int primes[N],cnt;
int phi[N];
bool st[N];
typedef long long LL;
//线筛法
void get_primes(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i]) primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++)
{
st[primes[j]*i]=true;
if(i%primes[j]==0) break;
}
}
}
//筛欧拉函数
void get_euler(int n)
{
phi[1]=1;
for(int i=2;i<=n;i++)
{
if(!st[i])
{
primes[cnt++]=i;
phi[i]=i-1;//i是质数，显然从1~i-1都是与i互质的
}
for(int j=0;primes[j]<=n/i;j++)
{
st[primes[j]*i]=true;
if(i%primes[j]==0)
{
phi[i*primes[j]]=phi[i]*primes[j];
break;
}
phi[primes[j]*i]=phi[i]*(primes[j]-1);
}
}
}
//快速幂
LL qmi(int a,int b,int p)
{
//考虑b的二进制形式
LL res=1;
while(b)
{
if(b&1) res=res*a%p;//如果b该位有1
b>>=1;//去除一位
a=a*(LL)a%p;//a平方
}
return res;
}
//线性同余
int egcd(int a,int b,int& x,int& y)
{
if(!b)
{
x=1,y=0;
return a;
}
int d=egcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
gauss消元
// a[N][N]是增广矩阵
int gauss()
{
int c, r;
for (c = 0, r = 0; c < n; c ++ )
{
int t = r;
for (int i = r; i < n; i ++ ) // 找到绝对值最大的行
if (fabs(a[i][c]) > fabs(a[t][c]))
t = i;
if (fabs(a[t][c]) < eps) continue;
for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]); // 将绝对值最大的行换到最顶端
for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c]; // 将当前上的首位变成1
for (int i = r + 1; i < n; i ++ ) // 用当前行将下面所有的列消成0
if (fabs(a[i][c]) > eps)
for (int j = n; j >= c; j -- )
a[i][j] -= a[r][j] * a[i][c];
r ++ ;
}
if (r < n)
{
for (int i = r; i < n; i ++ )
if (fabs(a[i][n]) > eps)
return 2; // 无解
return 1; // 有无穷多组解
}
for (int i = n - 1; i >= 0; i -- )
for (int j = i + 1; j < n; j ++ )
a[i][n] -= a[i][j] * a[j][n];
return 0; // 有唯一解
}
dp
//多重背包二进制优化
const int N =25000,M=2010;
int v[N],w[N];
int f[M];
int n,m;
int main()
{
cin>>n>>m;
int cnt=0;
for(int i=1;i<=n;i++)
{
int a,b,s;
cin>>a>>b>>s;
int k=1;
while(k<=s)//二进制打包，转化成01背包问题。
{
cnt++;
v[cnt]=a*k;
w[cnt]=b*k;
s-=k, k*=2;
}
if(s>0)//剩下的不够2的次幂的记得加上
{
v[++cnt]=s*a; w[cnt]=b*s;
}
}
n=cnt;//n变为打包后的物品数量
for(int i=1;i<=cnt;i++)
for(int j=m;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
cout<<f[m];
return 0;
}
//多重背包单调队列优化
int f[N],g[N],q[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int v,w,s;
cin>>v>>w>>s;
memcpy(g,f,sizeof f);
for(int j=0;j<v;j++)
{
int hh=0,tt=-1;
for(int k=j;k<=m;k+=v)
{
if(hh<=tt&&q[hh]<k-s*v) hh++;
//取最大值
if(hh<=tt) f[k]=max(f[k],g[q[hh]]+(k-q[hh])/v*w);//第i层比第i-1层多了一次偏移
while(hh<=tt&&g[q[tt]]-(q[tt]-j)/v*w<g[k]-(k-j)/v*w) tt--;//除去偏移量比较
q[++tt]=k;
}
}
}
cout<<f[m];
}
//二分+贪心求最长上升子序列
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
int len=0;
f[0]=-2e9;
for(int i=0;i<n;i++)
{
int l=0,r=len;
while(l<r)
{
int mid=l+r+1>>1;
if(f[mid]<a[i]) l=mid;
else r=mid-1;
}
len=max(len,r+1);
f[r+1]=a[i];
}
cout<<len;
return 0;
}
//求具体方案
for(int i=n;i>=1;i--)
{
for(int j=0;j<=m;j++)
{
f[i][j]=f[i+1][j];
if(j>=v[i]) f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);
}
}
int j=m;
for(int i=1;i<=n;i++)
if(j>=v[i]&&f[i][j]==f[i+1][j-v[i]]+w[i])
{
cout<<i<<" ";
j-=v[i];
}
return 0;
状压
const int N =110,M=1<<11;
int n,m;
int f[2][M][M];//第i行是b，第i-1行是a，以第i-2行c的情况做状态划分
vector<int> state;
int cnt[M];
int g[N];
int count(int state)
{
int res=0;
for(int i=0;i<m;i++) res+=state>>i&1;
return res;
}
bool check(int state)
{
for(int i=0;i<m;i++)
if((state>>i&1)&&((state>>i+1&1)|(state>>i+2&1))) return false;
return true;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=0;j<m;j++)
{
char c;
cin>>c;
if(c=='H') g[i]+=1<<j;
}
for(int i=0;i<1<<m;i++)
if(check(i))
state.push_back(i),cnt[i]=count(i);
for(int i=1;i<=n+2;i++)
for(int j=0;j<state.size();j++)
for(int k=0;k<state.size();k++)
for(int u=0;u<state.size();u++)
{
int a=state[j],b=state[k],c=state[u];
if((a&b)|(b&c)|(a&c)) continue;
if(g[i-1]&a|g[i]&b) continue;
f[i&1][j][k]=max(f[i&1][j][k],f[i-1&1][u][j]+cnt[b]);
}
cout<<f[n+2&1][0][0];
return 0;
}
//枚举子集
for(int j=(i-1)&i;j;j=(j-1)&i)
//集合类状压
int n, m;
LL f[N][M];
vector<int> state[M];
bool st[M];
int main()
{
while(cin>>n>>m,n||m)
{
for(int i=0;i<1<<n;i++)//处理出连续空着为偶数的状态
{
bool is_valid=true;
int cnt=0;
for(int j=0;j<n;j++)
{
if(i>>j&1)
{
if(cnt&1)
{
is_valid=false;
break;
}
cnt=0;
}
else cnt++;
}
if(cnt&1) is_valid=false;
st[i]=is_valid;
}
for(int i=0;i<1<<n;i++)
{
state[i].clear();//清除上一个数据
for(int j=0;j<1<<n;j++)
if((i&j)==0&&(st[i|j]))
state[i].push_back(j);
}
memset(f,0,sizeof f);
f[0][0]=1;
for(int i=1;i<=m;i++)
{
for(int j=0;j<1<<n;j++)
{
for(int k:state[j])
{
f[i][j]+=f[i-1][k];
}
}
}
cout<<f[m][0]<<endl;
}
}
树形dp
int n;
int d1[N],d2[N],up[N],p[N];//最大值子树值 次大值子树值 上行最大值 最大值子节点编号
int h[N],e[M],ne[M],w[M],idx;
bool isleaf[N];
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int dfs_d(int u,int father)
{
d1[u]=d2[u]=-INF; //如果边权存在负值
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==father) continue;
int d=dfs_d(j,u)+w[i];
if(d>=d1[u])
{
d2[u]=d1[u],d1[u]=d;
p[u]=j;
}
else if(d>d2[u]) d2[u]=d;
}
if(d1[u]==-INF)
{
d1[u]=d2[u]=0;
isleaf[u]=true;
}
return d1[u];
}
void dfs_u(int u,int father)
{
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==father) continue;
if(p[u]==j) up[j]=max(up[u],d2[u])+w[i];
else up[j]=max(up[u],d1[u]) +w[i];
dfs_u(j,u);
}
}
int main()
{
cin>>n;
memset(h,-1,sizeof h);
for(int i=0;i<n-1;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c),add(b,a,c);
}
//任取一点作为根 现取1
dfs_d(1,-1);
dfs_u(1,-1);
int res=d1[1];
for(int i=1;i<=n;i++)
if(isleaf[i]) res=min(res,up[i]);
else res=min(res,max(d1[i],up[i]));
cout<<res;
return 0;
}
单调队列优化
int n,m;
int w[N];
int f[N];//以第i个结尾的 满足连续m个必有一个 代价的最小值
int q[N],hh=0,tt=-1;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>w[i];
q[++tt]=0;
for(int i=1;i<=n;i++)
{
if(hh<=tt&&q[hh]<i-m) hh++;//这里第i个烽火台会发射信号，所以j可以取到i - m
f[i]=f[q[hh]]+w[i];
while(hh<=tt&&f[q[tt]]>=f[i]) tt--;
q[++tt]=i;
}
int res=1e9;
for(int i=n-m+1;i<=n;i++) res=min(res,f[i]);
cout<<res;
}
斜率优化
LL f[N],sumt[N],sumc[N];
int n,s;
int main()
{
cin>>n>>s;
for(int i=1;i<=n;i++)
{
cin>>sumt[i]>>sumc[i];
sumt[i]+=sumt[i-1];
sumc[i]+=sumc[i-1];
}
memset(f,0x3f,sizeof f);
f[0]=0;
for(int i=1;i<=n;i++)
for(int j=0;j<i;j++)
f[i]=min(f[i],f[j]+sumt[i]*(sumc[i]-sumc[j])+s*(sumc[n]-sumc[j]));
cout<<f[n]<<endl;
return 0;
}
//
LL f[N],sumt[N],sumc[N];
int n,s;
int q[N];
int main()
{
cin>>n>>s;
for(int i=1;i<=n;i++)
{
cin>>sumt[i]>>sumc[i];
sumt[i]+=sumt[i-1];
sumc[i]+=sumc[i-1];
}
memset(f,0x3f,sizeof f);
f[0]=0;
int hh=0,tt=-1;
q[++tt]=0;
for(int i=1;i<=n;i++)
{
//留了当前最右一个点
while(hh<tt&&(f[q[hh+1]] - f[q[hh]])<=(s+sumt[i])*(sumc[q[hh+1]]-sumc[q[hh]])) hh++;
f[i]=f[q[hh]]-(s+sumt[i])*sumc[q[hh]]+sumt[i]*sumc[i]+s*sumc[n];
while(hh<tt&&(f[q[tt]]-f[q[tt-1]])*(sumc[i]-sumc[q[tt]])
>=(f[i]-f[q[tt]])*(sumc[q[tt]]-sumc[q[tt-1]]))
tt--;
q[++tt]=i;
}
cout<<f[n]<<endl;
return 0;
}
//
int n,s;
LL sumc[N],sumt[N],f[N];
int q[N],hh=0,tt=-1;
//每次新进来比较的斜率不具有单调性（sumt不单调），而sumc仍单调
//需要维护整个凸包 然后二分查找
int binary_search(int i,int k)
{
if(hh==tt) return q[hh];
int l=hh,r=tt;
while(l<r)
{
int mid=l+r>>1;
if(f[q[mid+1]]-f[q[mid]]<=k*(sumc[q[mid+1]]-sumc[q[mid]])) l=mid+1;
else r=mid;
}
return q[l];
}
int main()
{
cin>>n>>s;
for(int i=1;i<=n;i++)
{
int t,c;
cin>>t>>c;
sumt[i]=sumt[i-1]+t;
sumc[i]=sumc[i-1]+c;
}
q[++tt]=0;
for(int i=1;i<=n;i++)
{
int l=hh,r=tt,k=s+sumt[i];
while(l<r)
{
int mid=l+r>>1;
if(f[q[mid+1]]-f[q[mid]]<=k*(sumc[q[mid+1]]-sumc[q[mid]])) l=mid+1;
else r=mid;
}
int j=q[l];
f[i]=f[j]-(s+sumt[i])*sumc[j]+sumt[i]*sumc[i]+s*sumc[n];
while(hh<tt&&(double)(f[q[tt]]-f[q[tt-1]])*(sumc[i]-sumc[q[tt]])
>=(double)(f[i]-f[q[tt]])*(sumc[q[tt]]-sumc[q[tt-1]]))
tt--;
q[++tt]=i;
}
cout<<f[n]<<endl;
}
折半查找
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N =50;
typedef long long LL;
int n,m,k;
int w[N];
int weights[1<<24],cnt=0;
int ans;
void dfs1(int u,int s)
{
if(u==k)
{
weights[cnt++]=s;
return;
}
if((LL)s+w[u]<=m) dfs1(u+1,s+w[u]);
dfs1(u+1,s);
}
void dfs2(int u,int s)
{
if(u==n)
{
int l=0,r=cnt-1;
while(l<r)
{
int mid=l+r+1>>1;
if(weights[mid]+(LL)s<=m) l=mid;
else r=mid-1;
}
if(weights[l]+(LL)s<=m) ans=max(ans,weights[l]+s);
return;
}
if((LL)s+w[u]<=m) dfs2(u+1,s+w[u]);
dfs2(u+1,s);
}
int main()
{
cin>>m>>n;
for(int i=0;i<n;i++) cin>>w[i];
sort(w,w+n);
reverse(w,w+n);
k=n/2;
dfs1(0,0);
sort(weights,weights+cnt);
int t=1;
for(int i=1;i<cnt;i++)
if(weights[i]!=weights[i-1])
weights[t++]=weights[i];
cnt=t;
dfs2(k,0);
cout<<ans<<endl;
return 0;
}
差分约束
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
const int N =1e5+10,M=3e5+10;
int n,m;
int h[N],e[M],ne[M],w[M],idx;
long long dist[N];
bool st[N];
int cnt[N];
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int spfa()
{
memset(dist,-0x3f,sizeof dist);
dist[0]=0;
stack<int> q;
q.push(0);
st[0]=true;
while(q.size())
{
int t=q.top();
q.pop();
st[t]=false;
for(int i=h[t];~i;i=ne[i])
{
int j=e[i];
if(dist[j]<dist[t]+w[i])
{
dist[j]=dist[t]+w[i];
cnt[j]=cnt[t]+1;
if(cnt[j]>=n+1) return false;
if(!st[j])
{
q.push(j);
st[j]=true;
}
}
}
}
return true;
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=0;i<m;i++)
{
int a,b,x;
cin>>x>>a>>b;
if(x==1) add(a,b,0),add(b,a,0);
else if(x==2) add(a,b,1);
else if(x==3) add(b,a,0);
else if(x==4) add(b,a,1);
else add(a,b,0);
}
for(int i=1;i<=n;i++) add(0,i,1);
if(!spfa()) cout<<"-1";
else
{
long long res=0;
for(int i=1;i<=n;i++) res+=dist[i];
cout<<res;
}
}
LCA
int root;
int n,m;
int h[N],e[M],ne[M],idx;
int depth[N];
int fa[N][16];
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void bfs()
{
memset(depth,0x3f,sizeof depth);
depth[0]=0;depth[root]=1;
queue<int> q;
q.push(root);
while(q.size())
{
int t=q.front();
q.pop();
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(depth[j]>depth[t]+1)
{
depth[j]=depth[t]+1;//这一步保证了不会更新已经更新过的节点
q.push(j);
fa[j][0]=t;
for(int k=1;k<=15;k++)
fa[j][k]=fa[fa[j][k-1]][k-1];
}
}
}
}
int lca(int a,int b)
{
//先跳到同一层
if(depth[a]<depth[b]) swap(a,b);
for(int k=15;k>=0;k--)
if(depth[fa[a][k]]>=depth[b])
a=fa[a][k];
if(a==b) return a;
//跳到lca的下一层
for(int k=15;k>=0;k--)
if(fa[a][k]!=fa[b][k])
{
a=fa[a][k];
b=fa[b][k];
}
return fa[a][0];
}
int main()
{
scanf("%d",&n);
memset(h,-1,sizeof h);
for(int i=0;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
if(b==-1) root=a;
else add(a,b),add(b,a);
}
bfs();
cin>>m;
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
int p=lca(a,b);
if(a==p) puts("1");
else if(p==b) puts("2");
else puts("0");
}
return 0;
}
//tarjan
int h[N],e[M],ne[M],w[M],idx;
int n,m;
int dist[N];
int res[M];//每个询问的结果
int st[N];
int p[N];
vector<PII> query[M];
void add(int a,int b,int c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
void dfs(int u,int fa)
{
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
dist[j]=dist[u]+w[i];
dfs(j,u);
}
}
void tarjan(int u)
{
st[u]=1;//正在递归的结点
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(!st[j])
{
tarjan(j);
p[j]=u;
}
}
for(auto item:query[u])
{
int y=item.first,id=item.second;
if(st[y]==2)
{
int anc=find(y);
res[id]=dist[u]+dist[y]-2*dist[anc];
}
}
st[u]=2;
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++) p[i]=i;
for(int i=0;i<n-1;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c),add(b,a,c);
}
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
if(a!=b)
{
query[a].push_back({b,i});
query[b].push_back({a,i});
}
}
dfs(1,-1);
tarjan(1);
for(int i=0;i<m;i++) cout<<res[i]<<endl;
}
//次小生成树
int h[N],e[M],ne[M],w[M],idx;
int n,m;
int dist[N];
int res[M];//每个询问的结果
int st[N];
int p[N];
vector<PII> query[M];
void add(int a,int b,int c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
void dfs(int u,int fa)
{
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
dist[j]=dist[u]+w[i];
dfs(j,u);
}
}
void tarjan(int u)
{
st[u]=1;//正在递归的结点
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(!st[j])
{
tarjan(j);
p[j]=u;
}
}
for(auto item:query[u])
{
int y=item.first,id=item.second;
if(st[y]==2)
{
int anc=find(y);
res[id]=dist[u]+dist[y]-2*dist[anc];
}
}
st[u]=2;
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++) p[i]=i;
for(int i=0;i<n-1;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c),add(b,a,c);
}
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
if(a!=b)
{
query[a].push_back({b,i});
query[b].push_back({a,i});
}
}
dfs(1,-1);
tarjan(1);
for(int i=0;i<m;i++) cout<<res[i]<<endl;
}
SCC
bool in_stk[N];
int din[N];
int q[N];
int h[N],hs[N],e[M*2],ne[M*2],idx;
int dfn[N],low[N];
int stk[N],top;
int timestamp;
int dcc_cnt;
int id[N];
int n,m;
void add(int h[],int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u)
{
dfn[u]=low[u]=++timestamp;
stk[++top]=u,in_stk[u]=true;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(!dfn[j])
{
tarjan(j);
low[u]=min(low[u],low[j]);
}
else if(in_stk[j]) low[u]=min(low[u],dfn[j]);
}
if(dfn[u]==low[u])
{
dcc_cnt++;
int y;
do
{
y=stk[top--];
id[y]=dcc_cnt;
in_stk[y]=false;
}while(y!=u);
}
}
bool top_sort()
{
int hh=0,tt=-1;
for(int i=1;i<=dcc_cnt;i++)
{
if(!din[i])
q[++tt]=i;
}
while(hh<=tt)
{
if(tt-hh+1>1) return false;
int t=q[hh++];
for(int i=hs[t];~i;i=ne[i])
{
int j=e[i];
if(--din[j]==0) q[++tt]=j;
}
}
return true;
}
int main()
{
int T;
cin>>T;
while(T--)
{
scanf("%d %d",&n,&m);
memset(h,-1,sizeof h);
memset(hs,-1,sizeof hs);
memset(dfn,0,sizeof dfn);
memset(in_stk,0,sizeof in_stk);
memset(din,0,sizeof din);
memset(id,0,sizeof id);
idx=0,timestamp=top=dcc_cnt=0;
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
add(h,a,b);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])
tarjan(i);
}
for(int i=1;i<=n;i++)
{
for(int j=h[i];~j;j=ne[j])
{
int k=e[j];
int a=id[i],b=id[k];
if(a!=b)
{
add(hs,a,b);
din[b]++;
}
}
}
if(top_sort()) puts("Yes");
else puts("No");
}
return 0;
}
DCC
int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
int id[N],dcc_cnt;
bool is_bridge[M];
int d[N];
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u,int from)//from表示这条边的idx e[idx]应该是u
{
dfn[u]=low[u]=++timestamp;
stk[++top]=u;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(!dfn[j])
{
tarjan(j,i);
low[u]=min(low[u],low[j]);
if(dfn[u]<low[j])
is_bridge[i]=is_bridge[i^1]=true;
}
else if(i!=(from^1))
low[u]=min(low[u],dfn[j]);
}
if(low[u]==dfn[u])
{
++dcc_cnt;
int y;
do{
y=stk[top--];
id[y]=dcc_cnt;
}while(y!=u);
}
}
并查集
const int N =30010;
int m;
int p[N],s[N],d[N];
int find(int x)
{
if(p[x]!=x)
{
int root=find(p[x]);
d[x]+=d[p[x]];
p[x]=root;
}
return p[x];
}
int main()
{
cin>>m;
for(int i=1;i<N;i++)
{
p[i]=i;
s[i]=1;
}
while(m--)
{
char op[2];
int a,b;
scanf("%s%d%d",op,&a,&b);
if(op[0]=='M')
{
int pa=find(a),pb=find(b);
if(pa!=pb)
{
d[pa]=s[pb];
s[pb]+=s[pa];
p[pa]=pb;
}
}
else
{
int pa=find(a),pb=find(b);
if(pa!=pb)
puts("-1");
else
{
cout<<max(abs(d[a]-d[b])-1,0)<<endl;
}
}
}
return 0;
}
树状数组
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int c)
{
for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}
int sum(int x)
{
int res=0;
for(int i=x;i;i-=lowbit(i))
{
res+=tr[i];
}
return res;
}
线段树+懒标记
int n,m;
int w[N];
struct Node{
int l,r;
LL sum,add;
}tr[4*N];
void pushup(int u)
{
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pushdown(int u)
{
auto &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
if(root.add)
{
left.add+=root.add,right.add+=root.add;
left.sum+=(LL)(left.r-left.l+1)*root.add;
right.sum+=(LL)(right.r-right.l+1)*root.add;
root.add=0;
}
}
void build(int u,int l,int r)
{
if(l==r) tr[u]={l,r,w[l],0};
else
{
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
}
void modify(int u,int l,int r,int d)
{
if(tr[u].l>=l&&tr[u].r<=r)
{
tr[u].sum+=(LL)(tr[u].r-tr[u].l+1)*d;
tr[u].add+=d;
}
else
{
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) modify(u<<1,l,r,d);
if(r>mid) modify(u<<1|1,l,r,d);
pushup(u);
}
}
LL query(int u,int l,int r)
{
if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
LL sum=0;
if(l<=mid) sum+=query(u<<1,l,r);
if(r>mid) sum+=query(u<<1|1,l,r);
return sum;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>w[i];
build(1,1,n);
char op[2];
int l,r,d;
while(m--)
{
cin>>op>>l>>r;
if(*op=='C')
{
cin>>d;
modify(1,l,r,d);
}
else
{
cout<<query(1,l,r)<<endl;
}
}
return 0;
}
Treap
int n;
struct Node{
int l,r;
int key,val;
int cnt,size;
}tr[N];
int root,idx;
void pushup(int p)
{
tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].cnt;
}
int get_node(int key)
{
tr[++idx].key=key;
tr[idx].val=rand();
tr[idx].cnt=tr[idx].size=1;
return idx;
}
void zig(int &p)//右旋
{
int q=tr[p].l;
tr[p].l=tr[q].r,tr[q].r=p,p=q;
pushup(tr[p].r),pushup(p);
}
void zag(int &p)
{
int q=tr[p].r;
tr[p].r=tr[q].l,tr[q].l=p,p=q;
pushup(tr[p].l),pushup(p);
}
void build()
{
get_node(-INF),get_node(INF);
root=1,tr[root].r=2;
pushup(root);
if(tr[1].val<tr[2].val) zag(root);
}
void insert(int &p,int key)
{
if(!p) p=get_node(key);
else if(tr[p].key==key) tr[p].cnt++;
else if(tr[p].key>key)
{
insert(tr[p].l,key);
if(tr[tr[p].l].val>tr[tr[p].r].val) zig(p);
}
else
{
insert(tr[p].r,key);
if(tr[tr[p].r].val>tr[tr[p].l].val) zag(p);
}
pushup(p);
}
void remove(int &p,int key)
{
if(!p) return;
if(tr[p].key==key)
{
if(tr[p].cnt>1) tr[p].cnt--;
else if(tr[p].l||tr[p].r)
{
if(!tr[p].r||tr[tr[p].l].val>tr[tr[p].r].val)
{
zig(p);
remove(tr[p].r,key);
}
else
{
zag(p);
remove(tr[p].l,key);
}
}
else p=0;
}
else if(tr[p].key>key) remove(tr[p].l,key);
else remove(tr[p].r,key);
pushup(p);
}
int get_rank_by_key(int p,int key)
{
if(!p) return 0;
if(tr[p].key==key) return tr[tr[p].l].size+1;
if(tr[p].key>key) return get_rank_by_key(tr[p].l,key);
return tr[tr[p].l].size+tr[p].cnt+get_rank_by_key(tr[p].r,key);
}
int get_key_by_rank(int p,int rank)
{
if(!p) return INF;
if(tr[tr[p].l].size>=rank) return get_key_by_rank(tr[p].l,rank);
if(tr[tr[p].l].size+tr[p].cnt>=rank) return tr[p].key;
return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);
}
int get_prev(int p,int key)
{
if(!p) return -INF;
if(tr[p].key>=key) return get_prev(tr[p].l,key);
return max(tr[p].key,get_prev(tr[p].r,key));
}
int get_next(int p, int key) // 找到严格大于key的最小数
{
if (!p) return INF;
if (tr[p].key <= key) return get_next(tr[p].r, key);
return min(tr[p].key, get_next(tr[p].l, key));
}
int main()
{
build();
cin>>n;
while(n--)
{
int op,x;
cin>>op>>x;
if(op==1) insert(root,x);
else if(op==2) remove(root,x);
else if(op==3) cout<<get_rank_by_key(root,x)-1<<endl;
else if(op==4) cout<<get_key_by_rank(root,x+1)<<endl;
else if(op==5) cout<<get_prev(root,x)<<endl;
else
{
cout<<get_next(root,x)<<endl;
}
}
return 0;
}
矩阵乘法
void mul(int c[][N],int a[][N],int b[][N])
{
static int t[N][N];
memset(t, 0, sizeof t);
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
for(int k=0;k<N;k++)
t[i][j]=(t[i][j]+(LL)a[i][k]*b[k][j])%m;
memcpy(c,t,sizeof t);
}
int main()
{
cin>>n>>m;
int f1[N][N]={1,1,1,0};
int a[N][N]={
{0,1,0,0},
{1,1,1,0},
{0,0,1,1},
{0,0,0,1},
};
int k=n-1;
while(k)
{
if(k&1) mul(f1,f1,a);
mul(a,a,a);
k>>=1;
}
cout << (((LL)n * f1[0][2] - f1[0][3]) % m + m) % m << endl;
}
数位dp
int f[N][N];//以j结尾 的i位不降数
void init()
{
for(int i=0;i<10;i++) f[1][i]=1;
for(int i=2;i<N;i++)
for(int j=0;j<=9;j++)
for(int k=j;k<=9;k++)
f[i][j]+=f[i-1][k];
}
int dp(int n)
{
if(!n) return 1;
vector<int> nums;
while(n) nums.push_back(n%10),n/=10;
int res=0,last=0;
for(int i=nums.size()-1;i>=0;i--)
{
int x=nums[i];
for(int j=last;j<x;j++)//枚举最高位时，是最高位填0~x
res+=f[i+1][j];
if(x<last) break;
last =x;//然后是最高位填x，last设为x 枚举下一位的填last~x的情况
if(!i) res++;//正常走到最后没有break
}
return res;
}
int main()
{
init();
int a,b;
while(cin>>b>>a)
cout<<dp(a)-dp(b-1)<<endl;
return 0;
}
//
const int N =20,P=1e9+7;
typedef long long LL;
//本题要求符合要求的数的 个数 平方和 一次方和 才能状态转移
struct F{
int s0,s1,s2;
}f[N][10][7][7];//有i位 最高位是j 数本身模7的余数 各位数之和模7余数
int power7[N],power9[N];//预处理10的i次方模7 和1e9+7的结果
int mod(LL x,LL y)
{
return (x%y+y)%y;
}
void init()
{
for(int i=0;i<=9;i++)
{
if(i==7) continue;
auto &v=f[1][i][i%7][i%7];
v.s0++;
v.s1+=i;
v.s2+=i*i;
}
LL power=10;
for(int i=2;i<N;i++,power*=10)
for(int j=0;j<=9;j++)
{
if(j==7) continue;
for(int a=0;a<7;a++)
for(int b=0;b<7;b++)
for(int k=0;k<=9;k++)
{
if(k==7) continue;
auto &v1=f[i][j][a][b],&v2=f[i-1][k][mod(a-j*(power%7),7)][mod(b-j,7)];
v1.s0 = mod(v1.s0 + v2.s0, P);
v1.s1 = mod(v1.s1 + v2.s1 + j * (power % P) % P * v2.s0, P);
v1.s2 = mod(v1.s2 + j * j * (power % P) % P * (power % P) % P * v2.s0 + v2.s2 + 2 * j * power % P * v2.s1, P);
}
}
power9[0]=power7[0]=1;
for(int i=1;i<N;i++)
{
power7[i]=power7[i-1]*10%7;
power9[i]=(LL)power9[i-1]*10ll%P;
}
}
F get(int i,int j,int a,int b)
{
int s0=0,s1=0,s2=0;
for(int x=0;x<7;x++)
for(int y=0;y<7;y++)
if(x!=a&&y!=b)
{
auto v=f[i][j][x][y];
s0 = (s0 + v.s0) % P;
s1 = (s1 + v.s1) % P;
s2 = (s2 + v.s2) % P;
}
return {s0,s1,s2};
}
int dp(LL n)
{
if(!n) return 0;
LL backup_n=n%P;
vector<int> nums;
while(n) nums.push_back(n%10),n/=10;
int res=0;
LL last_a=0,last_b=0;//前面的数本身（后面的先默认是0） 各位数之和模7余数
for(int i=nums.size()-1;i>=0;i--)
{
int x=nums[i];
for(int j=0;j<x;j++)
{
if(j==7) continue;
int a=mod(-last_a %7 *power7[i+1],7);//如果这一层数本身(i+1~0位) 余数是a 这个数选上j之后就与7有关
int b=mod(-last_b,7);//如果这一层(i+1~0位)各位数之和是b 则这一位选上j之后就与7有关
auto v=get(i+1,j,a,b); //余数不等于a且不等于b
res=mod(
res+
(last_a % P) * (last_a % P) % P * power9[i + 1] % P * power9[i + 1] % P * v.s0 % P+
2 * last_a % P * power9[i + 1] % P * v.s1+
v.s2
,P);
}
if(x==7) break;
last_a=last_a*10+x;
last_b+=x;
if(!i&&last_a%7&&last_b%7) res=(res+backup_n*backup_n)%P;
}
return res;
}
int main()
{
init();
int T;
cin>>T;
while(T--)
{
LL l,r;
cin>>l>>r;
cout<<mod(dp(r)-dp(l-1),P)<<endl;
}
return 0;
}