模板1&2
广搜
memset
//1、入队赋值
q[1] = a, f[a] = 0;
for(i=j=1; i<=j; i++){
x = q[i];
for(k=-1; k<=1; k+=2){
y = x + c[x]*k;
if(y < 1 || y > n) continue;
if(f[x]+1 < f[y]){
f[y] = f[x] + 1;
q[++j] = y;
}
}
}
q[1] = x*N + y, f[x][y] = 0;
for(i=j=1; i<=j; i++){
x = q[i]/N, y = q[i]%N;
for(k=0; k<4; k++){
xx = x+dx[k], yy = y+dy[k];
if(xx < 1 || xx > n || yy < 1 || yy > n) continue;
if( < ){
f[xx][yy] = ;
q[++j] = xx*N + yy;
}
}
}
//f[x][y][k&1] = k;
q[1] = x*1000001 + y * 101 + z, f[x][y][0] = 1;
for(i=j=1; i<=j; i++){
x = q[i]/1000001, y = q[i]%101, z = ;
for(k=0; k<4; k++){
xx = x+dx[k], yy = y+dy[k], zz = !z;
if(xx < 1 || xx > n || yy < 1 || yy > n) continue;
if(f[x][y][z] + 1 < f[xx][yy][zz]){
f[xx][yy][zz] = f[x][y][z] + 1;
q[++j] = x*1000001 + y * 101 + z;
}
}
}dp&倒搜
int dfs(int n, int m){
if(m < 0) return -1e9;
if(n == 0) return 0;
if(f[n][m] != f[0][0]) return f[n][m];
int p = dfs(n-1, m-a[n]) + v[n];
int q = dfs(n-1, m);
return f[n][m] = p>q ? p:q;
}
int dfs(int n){
int p, q=1;
if(!f[n]) return f[n];
for(int i=1; i<n; i++){
if(a[i] >= a[n]) continue;
p = dfs(i);
if(p+1 > q) q = p+1;
}
return f[n] = q;
}
int dfs(int n, int m){
int p, q=0;
if(f[n][m]) return;
if(a[n] != b[m]){
p = dfs(n-1, m);
q = dfs(n, m-1);
}
else p = dfs(n-1, m-1)+1;
return f[n][m] = p>q ? p:q;
}
int dfs(int l, int r){
int q=1e9, p;
if(l == r) return 0;
if(f[l][r] != -1) f[l][r];
for(int i=l; i<r; i++){
p = dfs(l, i) + dfs(i+1, r) + s[r] - s[l-1];
if(p < q) q = p;
}
return f[l][r] = q;
}
int dfs(int l, int r){
int q=1e9, p;
if(l == r) return 0;
if(f[l][r] != -1) f[l][r];
for(int i=l; i<r; i++){
p = dfs(l, i) + dfs(i+1, r) + s[r] - s[l-1];
if(p < q) q = p;
}
return f[l][r] = q;
}
int dfs(int n, int m){
int i, j, k;
if(m == 1) return s[1][n];
for(1=m; i<=n; i++){
f[n][m] = max(f[n][m], dfs(i-1, m-1) + a[i][n]);
}
return f[n][m];
}图论
1. tanxin
for(i=1; i<=n; i++){
k = 0;
for(j=1; j<=n; j++){
if(!u[j] && s[j]<s[k]) k = j;
}
u[k] = 0;
for(j=1; j<=n; j++){
if(s[k] + mp[k][j] < s[j]){
s[j] = s[k] + mp[k][j];
}
}
}
2. Bell
for(i=1; i<=n; i++){
k = 0;
for(j=1; j<=m; j++){
a = , b = , c = ;
if(s[a]+c < s[b]){
s[b] = s[a] + c;
k = 1;
}
}
if(k == 0) break;
}
3. Floyd
for(k=1; k<=n; k++){
for(i=1; i<=n; i++){
for(j=1; j<=n; j++){
mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
}
}
}线段树
区间修改： 建树： 二分建树，通过左右两边分治，在处理完子节点后记录父亲节点的信息
void build(ll p, ll l, ll r, ll x, ll y, ll z){
if(x<=l&&r<=y) d[p] += z*(r-l+1), f[p] += z;//找到就修改区间
else{
ll mid=l+r>>1, lc=p<<1, rc=p<<1|1;//mid和l和r是二分的部分，lc是左子节点，rc是右子节点
if(f[p]) xia(p, lc, rc, mid, l, r);//如果标记下放就下放
if(x <= mid) build(lc, l, mid, x, y, z);//如果x在[l,r]区间的左边就找左边
if(y > mid) build(rc, mid+1, r, x, y, z);//如果y在[l,r]区间的左边就找右边
d[p] = d[lc] + d[rc];//记录d[p]的值
}
}标记下放： 一种快速区间修改方式 可以在每次二分前让子树加上之前没加上的值
void xia(ll p, ll lc, ll rc, ll mid, ll l, ll r){
d[lc] += f[p]*(mid-l+1), d[rc] += f[p]*(r-mid+1);//左子树加等于左区间的个数乘以要修改的值
f[lc] += f[p], f[rc] += f[p], f[p] = 0;//把下放的内容向下一级推过去
}查询： 二分查询，如果找到整个区间返回，没找到且l!=r就将左右子树的和相加返回，递归返回
ll cha(ll p, ll l, ll r, ll x, ll y){
if(x<=l&&r<=y) return d[p];//如果整块在里面就返回整块
ll mid=l+r>>1, lc=p<<1, rc=p<<1|1, a=0;
if(f[p]) xia(p, lc, rc, mid, l, r);//如果标记下放就下放
if(x <= mid) a += cha(lc, l, mid, x, y);//如果x在[l,r]区间的左边就加上左边
if(y > mid) a += cha(rc, mid+1, r, x, y);//如果y在[l,r]区间的右边就加上右边
return a;//返回左右子树的和
}区间赋值： 建树： 二分建树，通过左右两边分治，在处理完子节点后记录父亲节点的信息
void build(ll p, ll l, ll r, ll x, ll y, ll z){
if(x<=l&&r<=y) d[p] = z*(r-l+1), f[p] = z;
else{
ll mid=l+r>>1, lc=p<<1, rc=p<<1|1;
if(f[p] != f[0]) xia(p, lc, rc, mid, l, r);
if(x <= mid) build(lc, l, mid, x, y, z);
if(y > mid) build(rc, mid+1, r, x, y, z);
d[p] = d[lc] + d[rc];
}
}标记下放： 一种快速区间修改方式 可以在每次二分前让子树加上之前没加上的值
void xia(ll p, ll lc, ll rc, ll mid, ll l, ll r){
d[lc] = f[p]*(mid-l+1), d[rc] = f[p]*(r-mid+1);
f[lc] = f[p], f[rc] += f[p], f[p] = f[0];//因为要赋的值可能为0，所以把f赋为无穷大
}查询： 二分查询，如果找到整个区间返回，没找到且l!=r就将左右子树的和相加返回，递归返回
ll cha(ll p, ll l, ll r, ll x, ll y){
if(x<=l&&r<=y) return d[p];
ll mid=l+r>>1, lc=p<<1, rc=p<<1|1, a=0;
if(f[p] != f[0]) xia(p, lc, rc, mid, l, r);
if(x <= mid) a += cha(lc, l, mid, x, y);
if(y > mid) a += cha(rc, mid+1, r, x, y);
return a;
}别忘记memset(f, 63, sizeof(f)) 区间最值： 标记下放和上面的区间修改有一点区别。d记录最大最小值不需要加上整个区间；
void xia(int p, int l, int r){
int m=l+r>>1, lc=p<<1, rc=p<<1|1;
d[lc] += f[p], d[rc] += f[p];//标记下放
f[lc] += f[p], f[rc] += f[p], f[p] = 0;
}建树和更新：pushup变成更改根的值为左右子节点的最值
void jia(int p,int i, int r, int x, int y, int z){
if(x<=l && r<=y) d[p] += z, f[p] += z;
else{//d记录区间最小值、f记录儿子还没加
int m=l+r>>1, lc=p<<1, rc=p<<1|1;
xia(p, l, r);
if(x <= m) jia(lc, l, m, x, y, z);
if(y > m) jia(rc, m+1, r, x, y, z);
d[p] = min(d[lc], d[rc]) + f[p];
}
}查询：返回左右区间的最值
int cha(int p,int l, int r, int x, int y){
if(x<=l&&r<=y) return d[p];//找到返回整个区间最值
int m=l+r>>1, lc=p<<1, rc=p<<1|1, a=1e9, b=1e9;
xia(p, l, r);
if(y > m) a = cha(rc, m+1, r, x, y);
if(x <= m) b = cha(lc, l, m, x, y);
return a>b?b:a;
}区间修改PLAS： 记录方式：开多一个下放数组记录乘的下放
ll mod, a[qiqian<<2], d[qiqian<<2], t[qiqian<<2], f[qiqian<<2];标记下放：用t数组记录乘下放情况，给1到n<<1赋初值1，乘先下放，(d*t+f)的标记，下放完后赋t[p]值为1，乘1不用下放，然后下放加的标记。
void xia(int p, int lc, int rc, int mid, int l, int r){
if(t[p] != 1){
d[lc] *= t[p], d[rc] *= t[p], f[lc] *= t[p], f[rc] *= t[p];
t[lc] *= t[p], t[rc] *= t[p], t[p] = t[0];
d[lc] %= mod, d[rc] %= mod, t[lc] %= mod, t[rc] %= mod, f[lc] %= mod, f[rc] %= mod;
}
if(f[p] != f[0]){
d[lc] += f[p]*(mid-l+1), d[rc] += f[p]*(r-mid);
f[lc] += f[p], f[rc] += f[p], f[p] = f[0];
d[lc] %= mod, d[rc] %= mod, f[lc] %= mod, f[rc] %= mod;
}
}建树和查询和加的函数和上面的一样。 乘：乘对加的标记也有影响。
void update2(int p, int l, int r, int x, int y, ll z){
if(x<=l&&r<=y){
d[p] *= z, f[p] *= z, t[p] *= z;
d[p] %= mod, f[p] %= mod, t[p] %= mod;
}
else{
int mid=l+r>>1, lc=p<<1, rc=p<<1|1;
xia(p, lc, rc, mid, l, r);
if(x <= mid) update2(lc, l, mid, x, y, z);
if(y > mid) update2(rc, mid+1, r, x, y, z);
d[p] = (d[lc] + d[rc]) % mod;
}
}树状数组
void add(int *arr int pos,int x){//单点修改-（区间修改）
while(pos<=n) arr[pos]+=x,pos+=lowbit(pos);
}
void modify(int l,int r,int x){//区间修改
add(d1,l,x),add(d1,r+1,-x),add(d2,l,x*l),add(d2,r+1,-x*(r+1));
}
int getsum(int *arr,int pos){//区间求和
int sum=0;
while(pos) sum+=arr[pos],pos-=lowbit(pos);
return sum;
}
int query(int l,int r){//区间查询
return asum[r]+r*getsum(d1,r)-getsum(d2,r)-(asum[l-1]+l*getsum(d1,l-1)-getsum(d2,l-1));
}查询最值
void build(int n){//建树
for(int i=1;i<=n;i++){
c[i]=a[i],int t=lowbit(i);
for(int j=1;j<t;j*=2) c[i]=max(c[i],c[i-j]);
}
}
void add(int pos,int x){//update
a[pos]=x;
while(pos<=n){
c[pos]=a[pos];int t=lowbit(i);
for(int j=1;j<t;j*=2) c[i]=max(c[i],c[i-j]);
pos+=lowbit(pos);
}
}
int query(int l,int r){//查询
int ans=a[r];
while(1){
ans=max(ans,num[r]); if(r==l) break; r--;
while(r-l>=lowbit(r)) ans=max(ans,c[r]),r-=lowbit(r);
}
return ans;
}