ACM·大一下学习笔记

25.2.22

线段树1模板

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mid (l+r>>1)
const int N=1e5+5;
int a[N];
struct node{
int sum,lazy;
}t[N<<2];
void build(int x,int l,int r){
  if(l==r){t[x].sum=a[l];return;}
  build(x<<1,l,mid);
  build(x<<1|1,mid+1,r);
  t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
}
void down(int x,int l,int r){
  if(t[x].lazy){
      t[x<<1].lazy+=t[x].lazy;
      t[x<<1|1].lazy+=t[x].lazy;
      t[x<<1].sum+=t[x].lazy*(mid-l+1);
      t[x<<1|1].sum+=t[x].lazy*(r-mid);
      t[x].lazy=0;
  }
}
void update(int L,int R,int c,int x,int l,int r){
  if(L<=l&&r<=R){
      t[x].sum+=c*(r-l+1);
      t[x].lazy+=c;
      return;
  }
  down(x,l,r);
  if(mid>=L) update(L,R,c,x<<1,l,mid);
  if(mid+1<=R) update(L,R,c,x<<1|1,mid+1,r);
  t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
}
int query(int L,int R,int x,int l,int r){
  if(L<=l&&r<=R) return t[x].sum;
  if(L>r||R<l)return 0;
  down(x,l,r);
  return query(L,R,x<<1,l,mid)+query(L,R,x<<1|1,mid+1,r);
}
signed main(){
ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n,m,op,x,y,k;
  cin>>n>>m;
  for(int i=1;i<=n;i++) cin>>a[i];
  build(1,1,n);
  for(int i=1;i<=m;i++){
     cin>>op;
      if(op==1){cin>>x>>y>>k;update(x,y,k,1,1,n);}
      if(op==2){cin>>x>>y;cout<<query(x,y,1,1,n)<<endl;}
   }
}

线段树2模板

线段树用于维护满足结合律的区间信息

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define mid ((l+r)>>1)
const int N=1e5+5;
int a[N];
int n,q,mo,x,y,k,op;
struct node{
  int x,l,r,sum,add,mul;
}t[N<<2];
void build(int x,int l,int r){
  if(l==r) {t[x].sum=a[l];t[x].mul=1;return;}
  build(x<<1,l,mid);
  build(x<<1|1,mid+1,r);
  t[x].sum=(t[x<<1].sum+t[x<<1|1].sum)%mo;
  t[x].mul=1;
}
void down(int x,int l,int r){
  if(t[x].mul!=1||t[x].add!=0){
  	t[x<<1].sum=(t[x<<1].sum*t[x].mul%mo +t[x].add*(mid-l+1)%mo) %mo;
  	t[x<<1].add=(t[x<<1].add*t[x].mul%mo +t[x].add)%mo;
  	t[x<<1].mul=(t[x<<1].mul*t[x].mul)%mo;
  	t[x<<1|1].sum=(t[x<<1|1].sum*t[x].mul%mo +t[x].add*(r-mid)%mo) %mo;
  	t[x<<1|1].add=(t[x<<1|1].add*t[x].mul%mo +t[x].add)%mo;
  	t[x<<1|1].mul=(t[x<<1|1].mul*t[x].mul)%mo;
  	t[x].add=0,t[x].mul=1;
  }
}
void update_mul(int L,int R,int c,int x,int l,int r){
  if(L<=l&&r<=R){
  	t[x].sum=(t[x].sum*c)%mo;
  	t[x].add=(t[x].add*c)%mo;
  	t[x].mul=(t[x].mul*c)%mo;
  	return;
  }
  down(x,l,r);
  if(mid>=L) update_mul(L,R,c,x<<1,l,mid);
  if(mid+1<=R) update_mul(L,R,c,x<<1|1,mid+1,r);
  t[x].sum=(t[x<<1].sum+t[x<<1|1].sum)%mo;
}
void update_add(int L,int R,int c,int x,int l,int r){
  if(L<=l&&r<=R){
  	t[x].sum+=(r-l+1)*c;
  	t[x].add+=c;
  	return;
  }
  down(x,l,r);
  if(mid>=L) update_add(L,R,c,x<<1,l,mid);
  if(mid+1<=R) update_add(L,R,c,x<<1|1,mid+1,r);
  t[x].sum=(t[x<<1].sum+t[x<<1|1].sum)%mo;
}
int query(int L,int R,int x,int l,int r){
  if(L<=l&&r<=R) return t[x].sum;
  if(L>r||R<l) return 0;
  down(x,l,r);
  return (query(L,R,x<<1,l,mid)+query(L,R,x<<1|1,mid+1,r))%mo;
}
signed main(){
  cin>>n>>q>>mo;
  for(int i=1;i<=n;i++) cin>>a[i];
  build(1,1,n);
  for(int i=1;i<=q;i++){
  	cin>>op;
  	if(op==1){
  		cin>>x>>y>>k;
  		update_mul(x,y,k,1,1,n);
  	}
  	if(op==2){
  		cin>>x>>y>>k;
  		update_add(x,y,k,1,1,n);
  	}
  	if(op==3){
  		cin>>x>>y;
  		cout<<query(x,y,1,1,n)<<endl;
  	}
  }
}

25.2.23

P1198 [JSOI2008] 最大数

ST表（倒置）

为了支持插入尾部修改的操作，考虑倒置创建st表

st[i][j]表示区间[i-2^j+1,...,i]内的最值

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int a[N],q,mo,t=0,x,y,p=0,st[N][21];
char op;
void update(int x){
  st[x][0]=a[x];
  for(int i=1;(1<<i)<=x;i++)
  	st[x][i]=max(st[x][i-1],st[x-(1<<(i-1))][i-1]);
}
int find(int x){
  int l=p-x+1,r=p;
  int half_len=log2(r-l+1);
  int ans=max(st[p][half_len],st[l+(1<<half_len)-1][half_len]);
  t=ans;
  return ans;
}
signed main(){
  cin>>q>>mo;
  for(int i=1;i<=q;i++){
  	cin>>op>>x;
  	if(op=='A'){
  		a[++p]=(x+t)%mo;
  		update(p);
  	}else cout<<find(x)<<endl;
  }
}

线段树

#include<bits/stdc++.h>
#define int long long 
#define mid ((l+r)>>1)
using namespace std;
const int N=2e5+5;
int a[N],q,mo,n,t=0,x,p=0;
char op;
struct node{
  int l,r,m=0;
}tr[N<<2];
void update(int pos,int c,int x,int l,int r){
  if(pos==l&&l==r){tr[x].m=c;return;}
  if(mid>=pos) update(pos,c,x<<1,l,mid);
  if(mid+1<=pos) update(pos,c,x<<1|1,mid+1,r);
  tr[x].m=max(tr[x<<1].m,tr[x<<1|1].m);
}
int query(int L,int R,int x,int l,int r){
  if(L<=l&&r<=R) return tr[x].m;
  int a=-2e9,b=-2e9;
  if(L>r||R<l) return -2e9;
  return max(query(L,R,x<<1,l,mid),query(L,R,x<<1|1,mid+1,r));
}
signed main(){
  cin>>q>>mo;
  for(int i=1;i<=q;i++){
  	cin>>op>>x;
  	if(op=='A'){update(++p,(x+t)%mo,1,1,q);}
  	else{
  		t=query(p-x+1,p,1,1,q);
  		cout<<t<<endl;
  	}
  }
}

25.2.24

(线段树)区间最大子段和 [P4513 小白逛公园]

注意push的传参方式！！！

如果没加上&的话只传递了值(副本)，而没做到修改原变量。加上&传递地址。

想要将函数的返回值作为参数需要加上const

本题两个难点：

1.结构体变量中元素的设计和 push函数的书写规则

2.query函数中需要将查找的范围进行合并得到ans。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mid ((l+r)>>1)
const int N=5e5+5;
int a[N];
struct node{    
  int sum,lm,rm,mx;
}t[N<<2];
int n,m,k,x,y,p=N<<2;
void push(node& x,const node& y,const node& z){
  x.sum=y.sum+z.sum;
  x.lm=max(y.lm , y.sum+z.lm);
  x.rm=max(y.rm+z.sum , z.rm);
  x.mx=max(y.rm+z.lm , max(y.mx,z.mx));
}
void build(int x,int l,int r){
  if(l==r){t[x]={a[l],a[l],a[l],a[l]};return;}
  build(x<<1,l,mid);
  build(x<<1|1,mid+1,r);
  push(t[x],t[x<<1],t[x<<1|1]);
}
void update(int pos,int s,int x,int l,int r){
  if(pos==l&&l==r){t[x]={s,s,s,s};return;}
  if(mid>=pos) update(pos,s,x<<1,l,mid);
  if(mid+1<=pos) update(pos,s,x<<1|1,mid+1,r);
  push(t[x],t[x<<1],t[x<<1|1]);
}
node query(int L,int R,int x,int l,int r){
  if(L<=l&&r<=R) return t[x];
  if(L<=mid&&mid+1<=R){
      node res;
      push(res,query(L,R,x<<1,l,mid),query(L,R,x<<1|1,mid+1,r));
      return res;
  }
  if(mid>=L) return query(L,R,x<<1,l,mid);
  if(mid<=R) return query(L,R,x<<1|1,mid+1,r);
}
signed main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++) cin>>a[i];
  build(1,1,n);
  for(int i=1;i<=m;i++){
      cin>>k>>x>>y;
      if(k==1){
          if(x>y) swap(x,y);
          cout<<query(x,y,1,1,n).mx<<endl;
      }else{update(x,y,1,1,n);}
  }
}

25.2.25/26

(线段树)区间最大公约数 [CH4302 Interval GCD]

线段树用于维护满足结合律的区间信息。

图片上传失败，请重新上传

#include<bits/stdc++.h>
#define int long long
#define mid ((l+r)>>1)
const int N=5e5+5;
using namespace std;
int n,m,a[N],b[N],l,r,v;
char op;
struct node{
  int sum,d;//差分序列的区间和，最大公约数 
}t[N<<2];
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void pushup(node& x,node y,node z){
  x.sum=y.sum+z.sum;
  x.d=gcd(y.d,z.d); 
}
void build(int x,int l,int r){
  if(l==r){t[x].sum=t[x].d=b[l];return;}
  build(x<<1,l,mid);
  build(x<<1|1,mid+1,r);
  pushup(t[x],t[x<<1],t[x<<1|1]); 
}
void update(int pos,int c,int x,int l,int r){
  if(pos==l&&l==r){t[x].sum+=c;t[x].d+=c;return;}
  if(mid>=pos) update(pos,c,x<<1,l,mid);
  if(mid+1<=pos) update(pos,c,x<<1|1,mid+1,r);
  pushup(t[x],t[x<<1],t[x<<1|1]);
}
node query(int L,int R,int x,int l,int r){
  if(L<=l&&r<=R) return t[x];
  if(mid>=L) return query(L,R,x<<1,l,mid);
  if(mid+1<=R) return query(L,R,x<<1|1,mid+1,r);
  node tmp;
  pushup(tmp,query(L,R,x<<1,l,mid),query(L,R,x<<1|1,mid+1,r));
  return tmp;
}
signed main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++){
  	cin>>a[i];
  	b[i]=a[i]-a[i-1];
  }
  build(1,1,n);
  for(int i=1;i<=m;i++){
  	cin>>op;
  	if(op=='C'){
  		cin>>l>>r>>v;
  		update(l,v,1,1,n);
  		if(r+1<=n) update(r+1,-v,1,1,n);
  	}else{
  		cin>>l>>r;
  		node L,R;
  		L=query(1,l,1,1,n);
  		R=query(l+1,r,1,1,n);
  		cout<<gcd(L.sum,R.d)<<endl;
  	}
  }
}

25.2.27

P1438 无聊的数列(线段树+差分)

题目描述

维护一个数列 $a_i$ ，支持两种操作：

1 l r K D：给出一个长度等于 $r-l+1$ 的等差数列，首项为 $K$ ，公差为 $D$ ，并将它对应加到 $[l,r]$ 范围中的每一个数上。即：令 $a_l=a_l+K,a_{l+1}=a_{l+1}+K+D\ldots a_r=a_r+K+(r-l) \times D$ 。
2 p：询问序列的第 $p$ 个数的值 $a_p$ 。

输入格式

第一行两个整数数 $n,m$ 表示数列长度和操作个数。第二行 $n$ 个整数，第 $i$ 个数表示 $a_i$ 。接下来的 $m$ 行，每行先输入一个整数 $opt$ 。若 $opt=1$ 则再输入四个整数 $l\ r\ K\ D$ ；若 $opt=2$ 则再输入一个整数 $p$ 。

输出格式

对于每个询问，一行一个整数表示答案。

输入 #1

输出 #1

数据规模与约定

对于 $100\%$ 数据， $0\le n,m \le 10^5,-200\le a_i,K,D\le 200, 1 \leq l \leq r \leq n, 1 \leq p \leq n$ 。

图片上传失败，请重新上传

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define mid ((l+r)>>1)
const int N=1e5+5;
int n,m,op,x,y,k,delt,p,d[N];
struct node{
  int sum,lazy;
}t[N<<2];
void up(int x){t[x].sum=t[x<<1].sum+t[x<<1|1].sum;}
void build(int x,int l,int r){
  if(l==r){t[x].sum=d[l];return;}
  build(x<<1,l,mid);
  build(x<<1|1,mid+1,r);
  up(x);
}
void down(int x,int l,int r){
  if(t[x].lazy!=0){
  	t[x<<1].sum+=(mid-l+1)*t[x].lazy;
  	t[x<<1].lazy+=t[x].lazy;
  	t[x<<1|1].sum+=(r-mid)*t[x].lazy;
  	t[x<<1|1].lazy+=t[x].lazy;
  	t[x].lazy=0;
  }
}
void update(int L,int R,int c,int x,int l,int r){
  if(L<=l&&r<=R){t[x].lazy+=c;t[x].sum+=(r-l+1)*c;return;}
  down(x,l,r);
  if(mid>=L) update(L,R,c,x<<1,l,mid);
  if(mid+1<=R) update(L,R,c,x<<1|1,mid+1,r);
  up(x);
}
int query(int L,int R,int x,int l,int r){
  if(L<=l&&r<=R){return t[x].sum;}
  if(L>r||R<l) return 0;
  down(x,l,r);
  return query(L,R,x<<1,l,mid)+query(L,R,x<<1|1,mid+1,r);
}
signed main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++) cin>>d[i];
  for(int i=n;i>=1;i--) d[i]=d[i]-d[i-1];
  build(1,1,n);
  for(int i=1;i<=m;i++){
  	cin>>op;
  	if(op==1){
  		cin>>x>>y>>k>>delt;
  		update(x,x,k,1,1,n);
  		if(x+1<=y) update(x+1,y,delt,1,1,n);
  		if(y+1<=n) update(y+1,y+1,(x-y)*delt-k,1,1,n);
  	}else{
  		cin>>p;
  		cout<<query(1,p,1,1,n)<<endl;
  	}
  }
}

25.2.28

P4588 [TJOI2018] 数学计算(线段树操作省去求逆元操作)

P4588 [TJOI2018] 数学计算

小豆现在有一个数 $x$ ，初始值为 $1$ 。小豆有 $Q$ 次操作，操作有两种类型： 1 m：将 $x$ 变为 $x \times m$ ，并输出 $x \bmod M$ 2 pos：将 $x$ 变为 $x$ 除以第 $pos$ 次操作所乘的数（保证第 $pos$ 次操作一定为类型 1，对于每一个类型 1 的操作至多会被除一次），并输出 $x \bmod M$ 。

输入格式

一共有 $t$ 组输入。对于每一组输入，第一行是两个数字 $Q,M$ 。接下来 $Q$ 行，每一行为操作类型 $op$ ，操作编号或所乘的数字 $m$ （保证所有的输入都是合法的）。

输出格式

对于每一个操作，输出一行，包含操作执行后的 $x \bmod M$ 的值。

输入 #1
1
10 1000000000
1 2
2 1
1 2
1 10
2 3
2 4
1 6
1 7
1 12
2 7
输出 #1
2
1
2
20
10
1
6
42
504
84
对于 $20\%$ 的数据， $1 \le Q \le 500$ 。对于 $100\%$ 的数据， $1 \le Q \le 10^5$ ， $t \le 5, M \le 10^9$ ， $0 < m \leq 10^9$ 。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mid ((l+r)>>1)
const int N=1e5+5;
int x,y,op,q,T,mo;
int t[N<<2];
void up(int x){t[x]=(t[x<<1]*t[x<<1|1])%mo;}
void build(int x,int l,int r){
  t[x]=1;
  if(l==r) return;
  build(x<<1,l,mid);
  build(x<<1|1,mid+1,r);
}
void update(int pos,int c,int x,int l,int r){
  if(l==r) {t[x]=((c==0)?1:c);return;}
  if(mid>=pos) update(pos,c,x<<1,l,mid);
  else update(pos,c,x<<1|1,mid+1,r);
  up(x);
}
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>T;
  while(T--){
  	cin>>q>>mo;
  	build(1,1,q);
  	for(int i=1;i<=q;i++){
  		cin>>op>>x;
  		if(op==1) update(i,x,1,1,q);
  		else if(op==2) update(x,0,1,1,q);
  		cout<<t[1]%mo<<endl;
  	}
  }
}

P1253 扶苏的问题

P1253 扶苏的问题

给定一个长度为 $n$ 的序列 $a$ ，要求支持如下三个操作：

给定区间 $[l, r]$ ，将区间内每个数都修改为 $x$ 。

给定区间 $[l, r]$ ，将区间内每个数都加上 $x$ 。

给定区间 $[l, r]$ ，求区间内的最大值。

输入格式

第一行是两个整数，依次表示序列的长度 $n$ 和操作的个数 $q$ 。
第二行有 $n$ 个整数，第 $i$ 个整数表示序列中的第 $i$ 个数 $a_i$ 。
接下来 $q$ 行，每行表示一个操作。每行首先有一个整数 $op$ ，表示操作的类型。

若 $op = 1$ ，则接下来有三个整数 $l, r, x$ ，表示将区间 $[l, r]$ 内的每个数都修改为 $x$ 。

若 $op = 2$ ，则接下来有三个整数 $l, r, x$ ，表示将区间 $[l, r]$ 内的每个数都加上 $x$ 。

若 $op = 3$ ，则接下来有两个整数 $l, r$ ，表示查询区间 $[l, r]$ 内的最大值。

输出格式

对于每个 $op = 3$ 的操作，输出一行一个整数表示答案。

输入输出样例 #1

输入 #1
6 6
1 1 4 5 1 4
1 1 2 6
2 3 4 2
3 1 4
3 2 3
1 1 6 -1
3 1 6
输出 #1
7
6
-1
输入输出样例 #2

输入 #2
4 4
10 4 -3 -7
1 1 3 0
2 3 4 -4
1 2 4 -9
3 1 4
输出 #2
0
数据规模与约定

对于 $100\%$ 的数据， $1 \leq n, q \leq 10^6$ ， $1 \leq l, r \leq n$ ， $op \in \{1, 2, 3\}$ ， $|a_i|, |x| \leq 10^9$ 。

提示

请注意大量数据读入对程序效率造成的影响。

50POINTS
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mid ((l+r)>>1)
const int N=1e6+5;
int a[N],n,m,op,x,y,c;
struct node{
  int m,add,ex=1e17+5;
}t[N<<2];
void up(int x){
  t[x].m=max(t[x<<1].m,t[x<<1|1].m);
}
void build(int x,int l,int r){
  if(l==r){t[x].m=a[l];return;}
  build(x<<1,l,mid);
  build(x<<1|1,mid+1,r);
  up(x);
}
void down(int x){
  if(t[x].ex!=1e17+5){
  	t[x<<1].add=t[x<<1|1].add=0;
  	t[x<<1].ex=t[x<<1|1].ex = t[x<<1].m=t[x<<1|1].m=t[x].m= t[x].ex;
  	t[x].ex=0;
  }
  if(t[x].add!=0){
  	t[x<<1].add+=t[x].add;
  	t[x<<1].m+=t[x].add;
  	t[x<<1|1].add+=t[x].add;
  	t[x<<1|1].m+=t[x].add;
  	t[x].add=0;
  }
}
void change(int L,int R,int c,int x,int l,int r){
  if(L<=l&&r<=R){t[x].m=c;t[x].ex=c;t[x].add=0;return;}
  down(x);
  if(mid>=L) change(L,R,c,x<<1,l,mid);
  if(mid+1<=R) change(L,R,c,x<<1|1,mid+1,r);
  up(x);
}
void ad(int L,int R,int c,int x,int l,int r){
  if(L<=l&&r<=R){t[x].m+=c;t[x].add+=c;return;}
  down(x);
  if(mid>=L) ad(L,R,c,x<<1,l,mid);
  if(mid+1<=R) ad(L,R,c,x<<1|1,mid+1,r);
  up(x);
}
int query(int L,int R,int x,int l,int r){
  if(L<=l&&r<=R) return t[x].m;
  down(x);
  int ans=-1e9-5;
  if(mid>=L) ans=max(ans,query(L,R,x<<1,l,mid));
  if(mid+1<=R) ans=max(ans,query(L,R,x<<1|1,mid+1,r));
  return ans;
}
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n>>m;
  for(int i=1;i<=n;i++) cin>>a[i];
  build(1,1,n);
  for(int i=1;i<=m;i++){
  	cin>>op;
  	if(op==1){
  		cin>>x>>y>>c;
  		change(x,y,c,1,1,n);
  	}else if(op==2){
  		cin>>x>>y>>c;
  		ad(x,y,c,1,1,n);
  	}else if(op==3){
  		cin>>x>>y;
  		cout<<query(x,y,1,1,n)<<endl;
  	}
  }
}

25.3.5

P1020 [NOIP 1999 提高组] 导弹拦截

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

一行，若干个整数，中间由空格隔开。

输出格式

两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入输出样例

输入 #1
389 207 155 300 299 170 158 65
输出 #1
6
2
说明/提示

对于前 $50\%$ 数据（NOIP 原题数据），满足导弹的个数不超过 $10^4$ 个。该部分数据总分共 $100$ 分。可使用 $\mathcal O(n^2)$ 做法通过。
对于后 $50\%$ 的数据，满足导弹的个数不超过 $10^5$ 个。该部分数据总分也为 $100$ 分。请使用 $\mathcal O(n\log n)$ 做法通过。

对于全部数据，满足导弹的高度为正整数，且不超过 $5\times 10^4$ 。

此外本题开启 spj，每点两问，按问给分。

NOIP1999 提高组第一题

Q1.求最长不上升子序列。

Q2.求最少个数的不上升子序列不重叠覆盖。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int a[N],f[N],cnt,n;
//set<int> s;
int find1(int x){//最长不上升子序列
      int l=1,r=x,mid,ans=0;
      while(l<=r){
          mid=l+r>>1;
          if(f[mid]>=a[x]){ans=max(ans,mid);l=mid+1;}
          else r=mid-1;
      }
      return ans;
}
int find2(int x){//最长上升子序列
      int l=1,r=x,mid,ans=0;
      while(l<=r){
          mid=l+r>>1;
          if(f[mid]<a[x]){ans=max(ans,mid);l=mid+1;}
          else r=mid-1;
      }
      return ans;
}
signed main(){
      //cin>>n;for(int i=1;i<=n;i++) cin>>a[i];
      while(scanf("%lld",a+(++n))!=EOF);--n;
      for(int i=1;i<=n;i++){
          int pos=find1(i);
          cnt=max(cnt,pos+1);
          f[pos+1]=max(f[pos+1],a[i]);
      }
      cout<<cnt<<endl;
      //dilworth解法
      cnt=0;
      memset(f,0x3f,sizeof(f));
      for(int i=1;i<=n;i++){
          int pos=find2(i);
          cnt=max(cnt,pos+1);
          f[pos+1]=min(f[pos+1],a[i]);
      }
      cout<<cnt;
      //天梯赛的列车调度问题解法
      /*for(int i=1;i<=n;i++){
          auto it=s.lower_bound(a[i]);
          if(it==s.end()) s.insert(a[i]);
          else{
              s.erase(*it);
              s.insert(a[i]);
          }    
      }cout<<s.size();*/
}

25.3.12

最近感觉生活真的是被塞的...没什么激情面对。拖了将近一周的线段树二分终于de出bug了。

P2824 [HEOI2016/TJOI2016] 排序（线段树+二分）

题目描述

给出一个 $1$ 到 $n$ 的排列，现在对这个排列序列进行 $m$ 次局部排序，排序分为两种：

0 l r 表示将区间 $[l,r]$ 的数字升序排序

1 l r 表示将区间 $[l,r]$ 的数字降序排序

注意，这里是对下标在区间 $[l,r]$ 内的数排序。
最后询问第 $q$ 位置上的数字。

输入格式

输入数据的第一行为两个整数 $n$ 和 $m$ ， $n$ 表示序列的长度， $m$ 表示局部排序的次数。
第二行为 $n$ 个整数，表示 $1$ 到 $n$ 的一个排列。接下来输入 $m$ 行，每一行有三个整数 $\text{op},l,r$ ， $\text{op}$ 为 $0$ 代表升序排序， $\text{op}$ 为 $1$ 代表降序排序, $l,r$ 表示排序的区间。
最后输入一个整数 $q$ ，表示排序完之后询问的位置

输出格式

输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第 $q$ 位置上的数字。

输入输出样例 #1

输入 #1
6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3
输出 #1
5
说明/提示

河北省选2016第一天第二题。对于 $30\%$ 的数据， $n,m\leq 1000$ 对于 $100\%$ 的数据， $n,m\leq 10^5$ ， $1\leq q\leq n$

算是一道 ’线段树+二分‘ 的模板题了

由于将一个普通序列排序很慢，一次就需要nlogn的时间。操作m次，时复为O(mnlogn)，而n,m<=1e5肯定不允许。

我们试着把它转化为对01序列排序。先来考虑一个简单的问题：

如何将一个01序列排序？（logn的复杂度!!!）

对于这个问题，我们使用线段树来维护。查询一段区间内的1的个数记为cnt1，如果是升序，就将这段区间的[r-cnt1+1, r]都更改为1，将[l, r-cnt1]更改为0。降序则将[l, l+cnt1-1]更改为1，将[l+cnt, r]更改为0。这样我们就成功地把 排序转化为了区间查询和区间修改。

·首先二分答案mid。我们把原排列中大于等于mid的数都标记为1，小于mid的都标记为0。

·然后对于每个操作我们就将01序列排个序。最后如果第p个位子仍是1的话就是可行的。

·这个二分成立因为是满足单调性的：可以简单地假设一下，如果你二分的答案是1，那么原序列所有的值都转化为了1，所以最后肯定是true。如果二分一个值成立当且仅当这个位子的值大于等于mid，故如果check返回true，则l = mid+1，否则r = mid-1。

![6c59ac5a490bdbebe5e8e5e30d89180e](../Tencent Files/1832539553/nt_qq/nt_data/Pic/2025-03/Ori/6c59ac5a490bdbebe5e8e5e30d89180e.jpg)

有个很恶心的坑：

如果cnt=query(ll,rr,1,1,n);返回的cnt=0（即排序的区间均为0）时，会对下面update(rr-cnt+1,rr,1,1,1,n);的区间[rr-cnt+1,rr]造成影响.导致Runtime Error。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mid ((l+r)>>1)
const int N=1e5+5;
int n,m,q;
int a[N],op[N],L[N],R[N];
struct node{
  int l,r,sum,tag;
  //sum:区间1的个数
  //tag：-1表示区间无标记，0/1表示区间赋值0/1 
}t[N<<2];
void up(int x){t[x].sum=t[x<<1].sum+t[x<<1|1].sum;}
void down(int x){
  if(t[x].tag!=-1){
  	t[x<<1].sum=t[x].tag*(t[x<<1].r-t[x<<1].l+1);
  	t[x<<1|1].sum=t[x].tag*(t[x<<1|1].r-t[x<<1|1].l+1);
  	t[x<<1].tag=t[x<<1|1].tag=t[x].tag;
  	t[x].tag=-1;
  }
}
void build(int x,int l,int r,int val){
  if(l==r){t[x]={l,r,a[l]>=val?1:0,-1};return;}
  t[x].l=l;
  t[x].r=r;
  t[x].tag=-1;
  build(x<<1, l, mid, val);
  build(x<<1|1,mid+1,r,val);
  up(x);
}
void update(int L,int R,int k,int x,int l,int r){
  if(L<=l&&r<=R){
  	t[x].sum=k*(r-l+1);
  	t[x].tag=k;
  	return;
  }
  down(x);
  if(mid>=L) update(L,R,k,x<<1,l,mid);
  if(mid+1<=R) update(L,R,k,x<<1|1,mid+1,r);
  up(x);
}
int query(int L,int R,int x,int l,int r){
  if(R<l||L>r) return 0;
  if(L<=l&&r<=R) return t[x].sum;
  down(x);
  return query(L,R,x<<1,l,mid)+query(L,R,x<<1|1,mid+1,r);
}
bool check(int x){
  build(1,1,n,x);
  for(int i=1;i<=m;i++){
  	int ll=L[i],rr=R[i],cnt=query(ll,rr,1,1,n);
  	if(cnt==0) continue; 
  	if(op[i]==0){ 
  		update(ll,rr-cnt,0,1,1,n);
  		update(rr-cnt+1,rr,1,1,1,n);
  	}else{
  		update(ll,ll+cnt-1,1, 1,1,n);
  		update(ll+cnt,rr,0 ,1,1,n);
  	}
  }
  return query(q,q,1,1,n); 
}
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n>>m;
  for(int i=1;i<=n;i++) cin>>a[i];
  for(int i=1;i<=m;i++) cin>>op[i]>>L[i]>>R[i];
  cin>>q;
  int l=1,r=n,midd;
  while(l<=r){
  	mid=(l+r)>>1;
  	if(check(midd)){l=midd+1;}
  	else r=midd-1;
  }
  cout<<r;
}25.

25.3.17（复习最短路）

P4779 【模板】单源最短路径（标准版）

图片上传失败，请重新上传

dij

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e4+5;
int n,m,s;
int dis[N],vis[N];
struct edge{
  	int u,v,w;
};
vector<edge> e[N];
struct node{
      int id,dis;
      bool operator < (const node &a) const{return dis>a.dis;}
};
signed main(){
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
      cin>>n>>m>>s;
      for(int i=1;i<=m;i++){
         int u,v,w;
         cin>>u>>v>>w;
         e[u].push_back(edge{u,v,w});     
      }
      priority_queue<node> q;
      q.push(node{s,0});
      memset(dis,0x3f,sizeof(dis));
      memset(vis,0,sizeof(vis));
      dis[s]=0;
      while(!q.empty()){
         node a=q.top();q.pop();
         int now=a.id;
         if(vis[now]) continue;
         vis[now]=1;
         for(int i=0;i<e[now].size();i++){
             edge tmp=e[now][i];
             if(dis[tmp.v]>tmp.w+dis[tmp.u]){
                 dis[tmp.v]=tmp.w+dis[tmp.u];
                 q.push(node{tmp.v,dis[tmp.v]});
             }
         }
      }
      for(int i=1;i<=n;i++)
         cout<<dis[i]<<" ";
}

P1629 邮递员送信

题目描述

有一个邮递员要送东西，邮局在节点 $1$ 。他总共要送 $n-1$ 样东西，其目的地分别是节点 $2$ 到节点 $n$ 。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 $m$ 条道路。这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 $n-1$ 样东西并且最终回到邮局最少需要的时间。

输入格式

第一行包括两个整数， $n$ 和 $m$ ，表示城市的节点数量和道路数量。

第二行到第 $(m+1)$ 行，每行三个整数， $u,v,w$ ，表示从 $u$ 到 $v$ 有一条通过时间为 $w$ 的道路。

输出格式

输出仅一行，包含一个整数，为最少需要的时间。

输入输出样例 #1

输入 #1
5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6
5 4 2
输出 #1
83
说明/提示

对于 $30\%$ 的数据， $1 \leq n \leq 200$ 。

对于 $100\%$ 的数据， $1 \leq n \leq 10^3$ ， $1 \leq m \leq 10^5$ ， $1\leq u,v \leq n$ ， $1 \leq w \leq 10^4$ ，输入保证任意两点都能互相到达。

最短路裸题，”单源起点多源终点+多源起点单源终点“。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e3+5,M=1e5+5;
int n,m,x,y,z,ans=0;
int vis[N<<1],dis[N<<1];
struct edge{
int u,v,w;
};
vector<edge> pic[N<<1];
struct node{
int id,val;
bool operator<(const node&a)const{return val>a.val;}
};
void dij(int s){
priority_queue<node> q;
memset(vis,0,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
q.push({s,0});
while(!q.empty()){
  node a=q.top();q.pop();
  if(vis[a.id]) continue;
  vis[a.id]=1;
  for(int i=0;i<pic[a.id].size();i++){
      edge b=pic[a.id][i];
      if(dis[b.u]+b.w<dis[b.v]){
          dis[b.v]=dis[b.u]+b.w;
          q.push({b.v,dis[b.v]});
      }
  }
}
}

signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
  cin>>x>>y>>z;
  pic[x].push_back({x,y,z});
  pic[y+n].push_back({y+n,x+n,z});
}
dij(1);
for(int i=1;i<=n;i++) ans+=dis[i];
dij(n+1);
for(int i=n+1;i<=n<<1;i++) ans+=dis[i];
cout<<ans;
}

P3905 道路重建

题目描述

从前，在一个王国中，在 $n$ 个城市间有 $m$ 条道路连接，而且任意两个城市之间至多有一条道路直接相连。在经过一次严重的战争之后，有 $d$ 条道路被破坏了。国王想要修复国家的道路系统，现在有两个重要城市 $A$ 和 $B$ 之间的交通中断，国王希望尽快的恢复两个城市之间的连接。你的任务就是修复一些道路使 $A$ 与 $B$ 之间的连接恢复，并要求修复的道路长度最小。

输入格式

输入文件第一行为一个整数 $n\ (2<n\le 100)$ ，表示城市的个数。这些城市编号从 $1$ 到 $n$ 。

第二行为一个整数 $m\ (n-1\le m\le \dfrac{1}{2}n(n-1))$ ，表示道路的数目。

接下来的 $m$ 行，每行 $3$ 个整数 $i,j,k\ (1 \le i,j \le n,i\neq j,0<k \le 100)$ ，表示城市 $i$ 与 $j$ 之间有一条长为 $k$ 的道路相连。

接下来一行为一个整数 $d\ (1\le d\le m)$ ，表示战后被破坏的道路的数目。在接下来的 $d$ 行中，每行两个整数 $i$ 和 $j$ ，表示城市 $i$ 与 $j$ 之间直接相连的道路被破坏。

最后一行为两个整数 $A$ 和 $B$ ，代表需要恢复交通的两个重要城市。

输出格式

输出文件仅一个整数，表示恢复 $A$ 与 $B$ 间的交通需要修复的道路总长度的最小值。

输入 #1
3
2
1 2 1
2 3 2
1
1 2
1 3
输出 #1
1
floyd中转点概念的理解
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=205,INF=0x3f3f3f3f3f3f3f3f;
int n,m,q,u,v,w;
int a[N][N],t[N];
void floyd(int x){
for(int i=0;i<n;i++)
  for(int j=0;j<n;j++)
      a[i][j]=min(a[i][j],a[i][x]+a[x][j]);
}
signed main(){
   ios::sync_with_stdio(false);
   cin.tie(0);
   cin>>n>>m;
   memset(a,0x3f,sizeof(a));
   for(int i=0;i<n;i++) a[i][i]=0;
   for(int i=0;i<n;i++) cin>>t[i];
   for(int i=0;i<m;i++){
          cin>>u>>v>>w;
          a[u][v]=a[v][u]=w;
   }
   cin>>q;
   int p=0;//t[n]=1e9;
   for(int o=0;o<q;o++){
          cin>>u>>v>>w;
          while(t[p]<=w&&p<n) floyd(p++);
          if(t[u]>w||t[v]>w||a[u][v]==INF) cout<<-1<<endl;
          else cout<<a[u][v]<<endl;
   }
}

图片上传失败，请重新上传

3.19

SPFA模板

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e4+5,INF=(1<<31)-1;
int n,m,s,u,v,w;
struct edge{
    int u,v,w;
};
queue<int> q;
vector<edge> g[N];
int vis[N];
int dis[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        g[u].push_back({u,v,w});
    }
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++) dis[i]=INF;
    dis[s]=0;
    vis[s]=1;q.push(s);
    while(!q.empty()){
        int now=q.front();q.pop();
        vis[now]=0;
        for(auto nex:g[now]){
            if(dis[nex.v]>dis[nex.u]+nex.w){
                dis[nex.v]=dis[nex.u]+nex.w;
                if(vis[nex.v]==0) q.push(nex.v);
            }
        }
    }
    for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
}

如何优雅地卡SPFA

（「笔记」如何优雅地卡 Sp***ckyblock - 博客园)：

上述**“菊花图”**即可卡SPFA，原因：每次搜一遍前面的点都会把k+1的点放到队列里但k+1点因为本身出度很大导致很慢，会导致时间复杂度变成O(mn).

最长路P1807

题目描述

设 $G$ 为有 $n$ 个顶点的带权有向无环图， $G$ 中各顶点的编号为 $1$ 到 $n$ ，请设计算法，计算图 $G$ 中 $1, n$ 间的最长路径。

输入格式

输入的第一行有两个整数，分别代表图的点数 $n$ 和边数 $m$ 。

第 $2$ 到第 $(m + 1)$ 行，每行 $3$ 个整数 $u, v, w$ （ $u<v$ ），代表存在一条从 $u$ 到 $v$ 边权为 $w$ 的边。

输出格式

输出一行一个整数，代表 $1$ 到 $n$ 的最长路。

若 $1$ 无法到达 $n$ ，请输出 $-1$ 。

输入 #1
2 1
1 2 1
输出 #1
1
说明/提示

【数据规模与约定】

对于 $20\%$ 的数据， $n \leq 100$ ， $m \leq 10^3$ 。

对于 $40\%$ 的数据， $n \leq 10^3$ ， $m \leq 10^{4}$ 。

对于 $100\%$ 的数据， $1 \leq n \leq 1500$ ， $0 \leq m \leq 5 \times 10^4$ ， $1 \leq u, v \leq n$ ， $-10^5 \leq w \leq 10^5$ 。

法一：SPFA
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e3+5,INF=(1<<31)-1;
int n,m,s,u,v,w;
struct edge{
  int u,v,w;
};
queue<int> q;
vector<edge> g[N];
int vis[N];
int dis[N];
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin>>n>>m;
  for(int i=1;i<=m;i++){
      cin>>u>>v>>w;
      g[u].push_back({u,v,-w});
  }
  memset(vis,0,sizeof(vis));
  for(int i=1;i<=n;i++) dis[i]=INF;
  dis[1]=0;
  vis[1]=1;q.push(1);
  while(!q.empty()){
      int now=q.front();q.pop();
      vis[now]=0;
      for(auto nex:g[now]){
          if(dis[nex.v]>dis[nex.u]+nex.w){
              dis[nex.v]=dis[nex.u]+nex.w;
              if(vis[nex.v]==0) q.push(nex.v);
          }
      }
  }
  if(dis[n]==INF) cout<<-1<<endl;
  else cout<<-dis[n]<<endl;
}
法2：拓扑排序

负环

负环的定义：一条边权之和为负数的回路。

如果用SPFA判断负环超时了可以想起Var说过的话：

其实大部分题用sqrt(n)能骗过，奇淫技巧（这肯定是错的，但是好多题能过，如果被卡时间的话）

P3385 【模板】负环

题目描述

给定一个 $n$ 个点的有向图，请求出图中是否存在从顶点 $1$ 出发能到达的负环。负环的定义是：一条边权之和为负数的回路。

输入格式

本题单测试点有多组测试数据。

输入的第一行是一个整数 $T$ ，表示测试数据的组数。对于每组数据的格式如下：第一行有两个整数，分别表示图的点数 $n$ 和接下来给出边信息的条数 $m$ 。接下来 $m$ 行，每行三个整数 $u, v, w$ 。

若 $w \geq 0$ ，则表示存在一条从 $u$ 至 $v$ 边权为 $w$ 的边，还存在一条从 $v$ 至 $u$ 边权为 $w$ 的边。

若 $w < 0$ ，则只表示存在一条从 $u$ 至 $v$ 边权为 $w$ 的边。

输出格式

对于每组数据，输出一行一个字符串，若所求负环存在，则输出 YES，否则输出 NO。

输入 #1
2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8
输出 #1
NO
YES
说明/提示

数据规模与约定

对于全部的测试点，保证：

$1 \leq n \leq 2 \times 10^3$ ， $1 \leq m \leq 3 \times 10^3$ 。

$1 \leq u, v \leq n$ ， $-10^4 \leq w \leq 10^4$ 。

$1 \leq T \leq 10$ 。

提示

请注意， $m$ 不是图的边数。

注意本题只是找从1出发能到达的负环。

如果是全图判负环应该是开始时把所有点入队。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e3+5;
int n,m,u,v,w,t;
struct edge{
  int u,v,w;
};
vector<edge> g[N];
int vis[N],dis[N],cnt[N];
void spfa(){
  queue<int> q;
  vis[1]=1;q.push(1);dis[1]=0;
  while(!q.empty()){
  	int now=q.front();q.pop();
  	vis[now]=0;
  	for(auto nex:g[now]){
  		if(dis[nex.v]>dis[nex.u]+nex.w){
  			dis[nex.v]=dis[nex.u]+nex.w;
  			if(vis[nex.v]==0){
  				vis[nex.v]=1;
  				cnt[nex.v]=cnt[nex.u]+1;   
  				q.push(nex.v);
  				if(cnt[nex.v]>=n){cout<<"YES"<<endl;return;}
  			}
  		}
  	}
  }
  cout<<"NO"<<endl;
}
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin>>t;
  while(t--){
  	memset(vis,0,sizeof(vis));
  	memset(dis,0x3f,sizeof(dis));
  	memset(cnt,0,sizeof(cnt));
  	cin>>n>>m;
  	for(int i=1;i<=m;i++){
  		cin>>u>>v>>w;
  		if(w<0) g[u].push_back({u,v,w});
  		else{
  			g[u].push_back({u,v,w});
  			g[v].push_back({v,u,w});
  		}
  	}
  	spfa(); 
  	for(int i=1;i<=n;i++) g[i].clear();
  }
}	

25.3.20

P1144 最短路计数（无向无权图最短路用BFS）

题目描述

给出一个 $N$ 个顶点 $M$ 条边的无向无权图，顶点编号为 $1\sim N$ 。问从顶点 $1$ 开始，到其他每个点的最短路有几条。

输入格式

第一行包含 $2$ 个正整数 $N,M$ ，为图的顶点数与边数。

接下来 $M$ 行，每行 $2$ 个正整数 $x,y$ ，表示有一条连接顶点 $x$ 和顶点 $y$ 的边，请注意可能有自环与重边。

输出格式

共 $N$ 行，每行一个非负整数，第 $i$ 行输出从顶点 $1$ 到顶点 $i$ 有多少条不同的最短路，由于答案有可能会很大，你只需要输出 $ans \bmod 100003$ 后的结果即可。如果无法到达顶点 $i$ 则输出 $0$ 。

输入输出样例 #1

输入 #1
5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5
输出 #1
1
1
1
2
4
说明/提示

$1$ 到 $5$ 的最短路有 $4$ 条，分别为 $2$ 条 $1\to 2\to 4\to 5$ 和 $2$ 条 $1\to 3\to 4\to 5$ （由于 $4\to 5$ 的边有 $2$ 条）。

对于 $20\%$ 的数据， $1\le N \le 100$ ；
对于 $60\%$ 的数据， $1\le N \le 10^3$ ；
对于 $100\%$ 的数据， $1\le N\le10^6$ ， $1\le M\le 2\times 10^6$ 。
#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=1e6+5;
const int mo=100003;
int n,m,u,v;
int dis[N],vis[N],cnt[N];
vector<int> g[N];
queue<int> q;

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin>>n>>m;
  for(int i=1;i<=m;i++){
  	cin>>u>>v;
  	g[u].push_back(v);
  	g[v].push_back(u);
  }
  dis[1]=0;
  vis[1]=1;
  q.push(1);
  cnt[1]=1;
  while(!q.empty()){
  	int u=q.front();q.pop();
  	for(auto v:g[u]){
  		if(vis[v]==0){
  			dis[v]=dis[u]+1;
  			cnt[v]=cnt[u];
  			vis[v]=1;
  			q.push(v);
  		}
  		else if(dis[v]==dis[u]+1)
  			cnt[v]=(cnt[v]+cnt[u])%mo;
  	}
  }
  for(int i=1;i<=n;i++) cout<<cnt[i]<<endl;
}

25.3.21

航线（春联1.1005）(二维最短路模板题)

图片上传失败，请重新上传

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
const int dx[4]={0,-1,0,1};
const int dy[4]={1,0,-1,0};
//0=左，1=上，2=右，3=下
const int INF=(1LL<<60)-1;
int n,m,t[N],d[N];
int dis[N][4],vis[N][4];
struct node{
  int val,pos,dir;
  bool operator <(const node &x)const{return val>x.val;}
};
int encode(int x,int y){return (x-1)*m+y;}
pair<int,int> decode(int id){return {(id-1)/m+1,(id-1)%m+1};}
bool check(int x,int y){return x>0&&x<=n&&y>0&&y<=m;}
void dij(){
  int sta=encode(1,1),end=encode(n,m);
  //init()
  for(int i=1;i<=n*m;++i)
  	for(int j=0;j<4;j++){
  		dis[i][j]=INF;
  		vis[i][j]=0;
  	}
  priority_queue<node> q;
  dis[sta][0]=t[sta];
  q.push({0,sta,0});
  while(!q.empty()){
  	node now=q.top();q.pop();
  	int pos=now.pos,dir=now.dir;
  	if(vis[pos][dir]) continue;
  	vis[pos][dir]=1;
  	for(int i=0;i<4;++i){
  		//如果转向更优则更新
  		if(dis[pos][dir]+d[pos]>=dis[pos][i]) continue;
  		dis[pos][i]=dis[pos][dir]+d[pos];
  		q.push({dis[pos][i],pos,i});
  	}
  	auto [x,y]=decode(pos);
  	x+=dx[dir],y+=dy[dir];
  	int tmp_pos=encode(x,y);
  	if(check(x,y)&&dis[pos][dir]+t[tmp_pos]<dis[tmp_pos][dir]){
  		dis[tmp_pos][dir]=dis[pos][dir]+t[tmp_pos];
  		q.push({dis[tmp_pos][dir],tmp_pos,dir});
  	}
  }
  cout<<dis[end][3]<<endl;
}
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;cin>>T;
  while(T--){
  	cin>>n>>m;
  	for(int i=1;i<=n;++i)
  		for(int j=1;j<=m;++j)
  			cin>>t[encode(i,j)];
  	for(int i=1;i<=n;++i)
  		for(int j=1;j<=m;++j)
  			cin>>d[encode(i,j)];
  	dij();
  }
}

学博弈论导致的（春联2.1006）

博弈论，猜结论

假设红宝石1元钱，蓝宝石2元钱，宝盒4元钱。

那么问题等价于：

桌上有r+2b+4m元钱，Alice Bob轮流取钱，每次可以取1~3元，问最后谁胜。

经典结论：若（r+2b+4m）mod4==0则Bob胜，否则Alice胜利。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int r,b,m,cnt;
signed main(){
  int T;cin>>T;
  while(T--){
  	cin>>r>>b>>m;
  	cnt=r+2*b;
  	if(cnt%4==0) cout<<"Bob"<<endl;
  	else cout<<"Alice"<<endl;
  }
}

25.3.22

P11591 [NordicOI 2024] Anime Shops（无向无权图多源最短路，BFS，O(n+m))

P11591 [NordicOI 2024] Anime Shops

翻译自 NordicOI 2024 A。

题目描述

有 $n$ 个城市和 $m$ 条连接了两个城市的双向道路。有 $k$ 个城市有动漫商店。对于每个城市，求出从这个城市出发到除自己以外的另一个有动漫商店的城市的最小距离。

输入格式

第一行输入三个整数 $n,m,k$ 。第二行 $k$ 个整数，表示有动漫商店的城市的编号。接下来 $m$ 行，每行两个数 $a,b$ ，表示有一条连接城市 $a$ 和 $b$ 的道路。

输出格式

输出一行 $n$ 个整数，其中第 $i$ 个数表示从城市 $i$ 出发到达另一个有动漫商店的城市的最小距离。如果没有这样的城市，输出 -1。

输入 #1
9 6 4
2 4 5 7
1 2
1 3
1 8
2 4
3 4
5 6
输出 #1
1 1 1 1 -1 1 -1 2 -1
子任务分值特殊性质

$1$ $23$ $1 \le k \le n \le 1000$ ， $0 \le m \le 2000$

$2$ $16$ $1 \le k \le n \le 10^5$ ， $m=n-1$ ，每条路连接城市 $i$ 和 $i+1$

$3$ $61$ $1 \le k \le n \le 10^5$ ， $0 \le m \le 2 \cdot 10^5$

无权无向图，显然用到 bfs最优。但是因为求 n 次会寄，所以考虑只做一次的办法。

以下将有动漫商店的点记为关键点，其它点记为非关键点。然后直接搜，搜到哪个非关键点就能直接知道非关键点的答案了。所以重点在于如何处理关键点的答案。考虑a[i]来记录点i的最近关键点的编号（对于非关键点k，a[k]=0,同时说明如果a[k]==0则该点还未处理过。对于关键点k，a[k]=k，用来维护非关键点的a[]）。

设当前点为u，a[u]存储u的最近关键点id（上一轮已经处理完），对于u的一个直连点v来说：如果a[v]==0,即未处理过，则a[v]=a[u]，ans[v]=dis[v]=dis[u]+1,同时进队。如果a[v]==a[u]，则不需要处理，直接跳过。如果a[v]!=a[u]并且a[v]!=0，则此时来借机处理两点各自最近的关键点的距离：ans[a[u]]=min(ans[a[u]],dis[u]+dis[v]+1); ans[a[v]]=min(ans[a[v]],dis[u]+dis[v]+1);。形象地说，整个 bfs 的过程像是 k 个关键点开始，每次向外扩展“领地”。

时间复杂度 O(n+m)，因为每一次都恰好有一个非关键点被占领，并且每个非关键点最多被占领一次。

PS:至于为什么要用dis[]和ans[]两个数组来存，否则只用dis[]存储会出现关键点一开始赋0，但是后续a[v]!=a[u]并且a[v]!=0时就无法利用取min来处理关键点的最短距离。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
const int INF=0x3f3f3f3f3f3f3f;
int n,m,k,u,v,tmp;
int dis[N],a[N],ans[N];
vector<int> e[N];
queue<int> q;
void bfs(){
  while(!q.empty()){
      int u=q.front();q.pop();
      for(auto v:e[u]){
          if(a[v]==0){
              ans[v]=dis[v]=dis[u]+1;
              a[v]=a[u];
              q.push(v);
          }else{
              if(a[v]==a[u]) continue;
              ans[a[u]]=min(ans[a[u]],dis[u]+dis[v]+1);
              ans[a[v]]=min(ans[a[v]],dis[u]+dis[v]+1);
          }
      }
  }
}
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin>>n>>m>>k;
  memset(dis,0x3f,sizeof(dis));
  memset(ans,0x3f,sizeof(ans));
  for(int i=1;i<=k;i++){
      cin>>tmp;
      a[tmp]=tmp;
      dis[tmp]=0;
      q.push(tmp);
  }
  for(int i=1;i<=m;i++){
      cin>>u>>v;
      e[u].push_back(v);
      e[v].push_back(u);
  }
  bfs();
  for(int i=1;i<=n;i++){
      if(ans[i]<INF) cout<<ans[i]<<" ";
      else cout<<-1<<" ";
  }
}

子任务	分值	特殊性质
$1$	$23$	$1 \le k \le n \le 1000$ ， $0 \le m \le 2000$
$2$	$16$	$1 \le k \le n \le 10^5$ ， $m=n-1$ ，每条路连接城市 $i$ 和 $i+1$
$3$	$61$	$1 \le k \le n \le 10^5$ ， $0 \le m \le 2 \cdot 10^5$

次短路

P2865 [USACO06NOV] Roadblocks G

题目描述

贝茜把家搬到了一个小农场，但她常常回到 FJ 的农场去拜访她的朋友。贝茜很喜欢路边的风景，不想那么快地结束她的旅途，于是她每次回农场，都会选择第二短的路径，而不象我们所习惯的那样，选择最短路。贝茜所在的乡村有 R(1≤R≤105) 条双向道路，每条路都联结了所有的 N(1≤N≤5000) 个农场中的某两个。贝茜居住在农场 1，她的朋友们居住在农场 N（即贝茜每次旅行的目的地）。贝茜选择的第二短的路径中，可以包含任何一条在最短路中出现的道路，并且，一条路可以重复走多次。当然咯，第二短路的长度必须严格大于最短路（可能有多条）的长度，但它的长度必须不大于所有除最短路外的路径的长度。

输入格式

Line 1: Two space-separated integers: N and R

Lines 2:R+1: Each line contains three space-separated integers: A, B, and D that describe a road that connects intersections A and B and has length D (1 ≤ D ≤ 5000)

输出格式

Line 1: The length of the second shortest path between node 1 and node N0

输入 #1
4 4
1 2 100
2 4 200
2 3 250
3 4 100
输出 #1
450
说明/提示

Two routes: 1 -> 2 -> 4 (length 100+200=300) and 1 -> 2 -> 3 -> 4 (length 100+250+100=450)

法1思路：

从1做一次最短路存在dis1[]中，从n做一次最短路存在dis2[]中，从1到n的最短路长度为dis1[n](或者dis2[1]) 然后遍历每一条边(u,v,w): if(dis1[u]+w+dis2[v]>dis1[n]) ans=min(ans,dis1[u]+w+dis2[v])
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
const int INF=0x3f3f3f3f3f3f3f3f;
int r,n,u,v,w;
int dis1[N],vis[N],dis2[N];
struct edge{
int u,v,w;
};
struct node{
int val,id;
bool operator <(const node &x)const{return val>x.val;}
};
vector<edge> e[N];
priority_queue<node> q;
signed main(){
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   cin>>n>>r;
   for(int i=1;i<=r;i++){
          cin>>u>>v>>w;
          e[u].push_back({u,v,w});
          e[v].push_back({v,u,w});
   }
   memset(dis1,0x3f,sizeof(dis1));
   q.push({0,1});dis1[1]=0;
   while(!q.empty()){
          node now=q.top();q.pop();
          u=now.id;
          if(vis[u]) continue;
          vis[u]=1;
          for(auto edg:e[u]){
                v=edg.v,w=edg.w;
                if(dis1[u]+w<dis1[v]){
                    dis1[v]=dis1[u]+w;
                    q.push({dis1[v],v});
                }
          }
   }
   memset(dis2,0x3f,sizeof(dis2));
   q.push({0,n});dis2[n]=0;
   memset(vis,0,sizeof(vis));
   while(!q.empty()){
          node now=q.top();q.pop();
          u=now.id;
          if(vis[u]) continue;
          vis[u]=1;
          for(auto edg:e[u]){
                v=edg.v,w=edg.w;
                if(dis2[u]+w<dis2[v]){
                    dis2[v]=dis2[u]+w;
                    q.push({dis2[v],v});
                }
          }
   }
   int ans=INF;
   for(int u=1;u<=n;u++)
      for(auto edg:e[u]){
            v=edg.v,w=edg.w;
            if(dis1[u]+w+dis2[v]>dis1[n]) 
            	ans=min(ans,dis1[u]+w+dis2[v]);
      }
   cout<<ans;
}

25.3.26

P2657 [SCOI2009] windy 数

题目背景

windy 定义了一种 windy 数。

题目描述

不含前导零且相邻两个数字之差至少为 $2$ 的正整数被称为 windy 数。windy 想知道，在 $a$ 和 $b$ 之间，包括 $a$ 和 $b$ ，总共有多少个 windy 数？

输入格式

输入只有一行两个整数，分别表示 $a$ 和 $b$ 。

输出格式

输出一行一个整数表示答案。

输入 #1
1 10
输出 #1
9
输入 #2
25 50
输出 #2
20
数据规模与约定

对于全部的测试点，保证 $1 \leq a \leq b \leq 2 \times 10^9$ 。

法一：dp（数位dp）
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=12;
int a[N];
int f[N][10];//f[i][j]表示共有i位，且最高位数字为j的Windy数的个数
void init(){
  for(int i=0;i<=9;i++) f[1][i]=1;
  for(int i=2;i<N;i++)
  	for(int j=0;j<=9;j++)
  		for(int k=0;k<=9;k++)
  			if(abs(k-j)>=2) f[i][j]+=f[i-1][k];
}
int dp(int x){
  if(x==0) return 0;//特判,0不是windy数
  int len=0;
  while(x) a[++len]=x%10,x/=10;//把每一位抠出来存入数组
  int res=0,last=-2;
  for(int i=len;i>=1;--i){//从高位往低位枚举
  	int now=a[i];
  	for(int j=(i==len);j<now;++j)//第i位j，j从(i==cnt)到now-1
  		if(abs(j-last)>=2) res+=f[i][j];
  	if(abs(now-last)<2) break;
  	last=now;
  	if(i==1)    res++;//x本身(能运行到说明没有退出，即x本身满足条件)
  }
  //再考虑首位为0的情况
  for(int i=1;i<len;i++)
  	for(int j=1;j<=9;j++)
  		res+=f[i][j];
  return res;
}
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  init();
  int l,r;
  cin>>l>>r;
  cout<<dp(r)-dp(l-1);
}
法2：记忆化dfs(数位dp)

25.3.26

数位dp（记忆化dfs）

数位搜索

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=12;
int a[N],b[N],len;
void init(int x){
      len=0;
      while(x>0) a[++len]=x%10,x/=10; 
}
void dfs(int pos,bool limit){
      if(pos<=0){
        for(int i=len;i>=1;i--) cout<<b[i];
        cout<<" | ";
        return;
      }
      int max_num= limit?a[pos]:9;
      for(int i=0;i<=max_num;i++){
            b[pos]=i;
            dfs(pos-1,limit&&i==max_num);
      }
}
signed main(){
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
      int n;cin>>n;
      init(n);
      dfs(len,1);
}

输入：123
输出：
000 | 001 | 002 | 003 | 004 | 005 | 006 | 007 | 008 | 009 | 010 | 011 | 012 | 013 | 014 | 015 | 016 | 017 | 018 | 019 | 020 | 021 | 022 | 023 | 024 | 025 | 026 | 027 | 028 | 029 | 030 | 031 | 032 | 033 | 034 | 035 | 036 | 037 | 038 | 039 | 040 | 041 | 042 | 043 | 044 | 045 | 046 | 047 | 048 | 049 | 050 | 051 | 052 | 053 | 054 | 055 | 056 | 057 | 058 | 059 | 060 | 061 | 062 | 063 | 064 | 065 | 066 | 067 | 068 | 069 | 070 | 071 | 072 | 073 | 074 | 075 | 076 | 077 | 078 | 079 | 080 | 081 | 082 | 083 | 084 | 085 | 086 | 087 | 088 | 089 | 090 | 091 | 092 | 093 | 094 | 095 | 096 | 097 | 098 | 099 | 100 | 101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 |

记忆化数位dp习惯写法：

int a[15]; 存储上界的每一位数字，方便dfs使用
int dp[]; 记忆化
int dfs(当前dp到的位置pos, dp的一些状态... , pos之前的所有数是否到达上界) {
...
}
//dp里只存pos及以后的位置不受上界a约束的情况数
//如果受到上界约束，pos位置能填的最大数字需要通过a确定，继续递归枚举下一位

25.3.27

P2602 [ZJOI2010] 数字计数（记忆化数位dp）

题目描述

给定两个正整数 $a$ 和 $b$ ，求在 $[a,b]$ 中的所有整数中，每个数码(digit)各出现了多少次。

输入格式

仅包含一行两个整数 $a,b$ ，含义如上所述。

输出格式

包含一行十个整数，分别表示 $0\sim 9$ 在 $[a,b]$ 中出现了多少次。

输入 #1
1 99
输出 #1
9 20 20 20 20 20 20 20 20 20
数据规模与约定

对于 $30\%$ 的数据，保证 $a\le b\le10^6$ ；

对于 $100\%$ 的数据，保证 $1\le a\le b\le 10^{12}$ 。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int dp[15][15][2][2],dig,a[15],l,r;
int dfs(int pos,int cnt,int frt0,int limit){
  int res=0;
  if(pos<=0) return cnt;
  if(dp[pos][cnt][frt0][limit]!=-1) return dp[pos][cnt][frt0][limit];
  int up=limit?a[pos]:9;
  for(int i=0;i<=up;i++){
  	if(i==0&&frt0) res+=dfs(pos-1,cnt,1,0);
  	else res+=dfs(pos-1,cnt+(i==dig),0,limit&&(i==up));
  }
  dp[pos][cnt][frt0][limit]=res;
  return res;
}
int f(int x){
  memset(dp,-1,sizeof(dp));
  int len=0;
  while(x>0){a[++len]=x%10;x/=10;}
  return dfs(len,0,1,1);
}
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin>>l>>r;
  for(int i=0;i<=9;i++){
  	dig=i;
  	cout<<f(r)-f(l-1)<<" ";
  }
}

P8764 [蓝桥杯 2021 国 BC] 二进制问题（记忆化数位dp）

题目描述

小蓝最近在学习二进制。他想知道 $1$ 到 $N$ 中有多少个数满足其二进制表示中恰好有 $K$ 个 1。你能帮助他吗?

输入格式

输入一行包含两个整数 $N$ 和 $K$ 。

输出格式

输出一个整数表示答案。

输入 #1
7 2
输出 #1
3
说明/提示

对于 $30 \%$ 的评测用例, $1 \leq N \leq 10^{6}, 1 \leq K \leq 10$ 。对于 $60 \%$ 的评测用例, $1 \leq N \leq 2 \times 10^{9}, 1 \leq K \leq 30$ 。对于所有评测用例, $1 \leq N \leq 10^{18}, 1 \leq K \leq 50$ 。蓝桥杯 2021 国赛 B 组 H 题（C 组 J 题）。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,k,dp[100][100][2];
int a[100],len;
void init(int x){
  len=0;
  while(x>0){a[++len]=x%2;x>>=1;}
}
int dfs(int pos,int cnt,bool limit){
  if(pos<=0) return cnt==k;
  if(dp[pos][cnt][limit]!=-1) return dp[pos][cnt][limit];
  int res=0,up=limit?a[pos]:1;
  for(int i=0;i<=up;++i) res+=dfs(pos-1,cnt+(i==1),limit&&(i==up));
  dp[pos][cnt][limit]=res;
  return res;
}
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  memset(dp,-1,sizeof(dp));
  cin>>n>>k;
  init(n);
  cout<<dfs(len,0,1);
}

P8801 [蓝桥杯 2022 国 B] 最大数字 (数位+dfs搜索)

题目描述

给定一个正整数 $N$ 。你可以对 $N$ 的任意一位数字执行任意次以下 2 种操作:

将该位数字加 $1$ 。如果该位数字已经是 $9$ ，加 $1$ 之后变成 $0$ 。

将该位数字减 $1$ 。如果该位数字已经是 $0$ ，减 $1$ 之后变成 $9$ 。

你现在总共可以执行 $1$ 号操作不超过 $A$ 次， $2$ 号操作不超过 $B$ 次。请问你最大可以将 $N$ 变成多少?

输入格式

第一行包含 3 个整数： $N$ ， $A$ ， $B$ 。

输出格式

一个整数代表答案。

输入 #1
123 1 2
输出 #1
933
【样例说明】

对百位数字执行 $2$ 次 $2$ 号操作，对十位数字执行 $1$ 次 $1$ 号操作。

【评测用例规模与约定】

对于 $30 \%$ 的数据， $1 \leq N \leq 100 ; 0 \leq A, B \leq 10$ 对于 $100 \%$ 的数据, $1 \leq N \leq 10^{17} ; 0 \leq A, B \leq 100$ 蓝桥杯 2022 国赛 B 组 D 题。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int a,b,len,n;
string s,ans;
void dfs(int pos,int cnta,int cntb,string str){
  if(pos==n){ans=max(ans,str);return;}
  int x=9-(str[pos]-'0'),y=str[pos]-'0'+1;
  if(cnta+x<=a&&cntb+y<=b){
  	str[pos]='9';
  	dfs(pos+1,cnta+x,cntb,str);
  	dfs(pos+1,cnta,cntb+y,str);
  }
  else if(cnta+x<=a){str[pos]='9';dfs(pos+1,cnta+x,cntb,str);}
  else if(cntb+y<=b){str[pos]='9';dfs(pos+1,cnta,cntb+y,str);}
  else{str[pos]+=(a-cnta);dfs(pos+1,a,cntb,str);}
}
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin>>s>>a>>b;
  ans=s;
  n=s.size();
  dfs(0,0,0,s);
  cout<<ans;
}

P6218 [USACO06NOV] Round Numbers S (记忆化数位dp)

题目描述

如果一个正整数的二进制表示中， $0$ 的数目不小于 $1$ 的数目，那么它就被称为「圆数」。例如， $9$ 的二进制表示为 $1001$ ，其中有 $2$ 个 $0$ 与 $2$ 个 $1$ 。因此， $9$ 是一个「圆数」。请你计算，区间 $[l,r]$ 中有多少个「圆数」。

输入格式

一行，两个整数 $l,r$ 。

输出格式

一行，一个整数，表示区间 $[l,r]$ 中「圆数」的个数。

输入 #1
2 12
输出 #1
6
【数据范围】

对于 $100\%$ 的数据， $1\le l,r\le 2\times 10^9$ 。

【样例说明】

区间 $[2,12]$ ***有 $6$ 个「圆数」，分别为 $2,4,8,9,10,12$ 。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=35;
int l,r,ansl,ansr,len,a[N],dp[N][N][N][2][2];
void init(int x){
  len=0;
  while(x>0){a[++len]=x%2;x>>=1;}
}
int dfs(int pos,int cnt0,int cnt1,bool frt0,bool limit){
  if(pos<=0) return cnt0>=cnt1;
  if(dp[pos][cnt0][cnt1][frt0][limit]!=-1) return dp[pos][cnt0][cnt1][frt0][limit];
  int up=limit?a[pos]:1, res=0;
  for(int i=0;i<=up;i++){
  	if(frt0&&(i==0)) res+=dfs(pos-1,0,0,1,0);
  	else res+=dfs(pos-1,cnt0+(i==0),cnt1+(i==1),0,limit&&(i==up));
  }
  dp[pos][cnt0][cnt1][frt0][limit]=res;
  return res;
}
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin>>l>>r;
  memset(dp,-1,sizeof(dp));
  init(l-1);
  ansl=dfs(len,0,0,1,1);
  init(r);
  ansr=dfs(len,0,0,1,1);
  cout<<ansr-ansl;
}

数列计数（春联3.1001数位dp）

图片上传失败，请重新上传

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
const int M=35,mod=998244353;
int n,a[N],l[N],s[M],jud[M],dp[M][2][2];
int len1,len2,len,ans;
int dfs(int pos,bool frt0,bool limit){
  if(pos<=0) return 1;
  if(dp[pos][frt0][limit]!=-1) return dp[pos][frt0][limit];
  int up=limit?s[pos]:1, res=0;
  for(int i=0;i<=up;i++){
  	if(frt0&&(i==0)){res+=dfs(pos-1,1,limit&&(i==up));continue;}
  	if(i<=jud[pos]) res+=dfs(pos-1,0,limit&&(i==up));
  }
  dp[pos][frt0][limit]=res;
  return res;
}
void init(int x,int A){
  memset(dp,-1,sizeof(dp));
  len1=0;
  while(x>0){s[++len1]=x%2;x>>=1;}
  len2=0;
  while(A>0){jud[++len2]=A%2;A>>=1;}
  ans*=dfs(len1,1,1);
  ans%=mod;
}
void solve(){
  cin>>n;
  for(int i=1;i<=n;i++) cin>>a[i];
  for(int i=1;i<=n;i++) cin>>l[i];
  ans=1;
  for(int i=1;i<=n;i++) init(min(a[i],l[i]),a[i]);
  cout<<ans<<endl;
}
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;cin>>t;
  while(t--) solve();
}

25.3.28

P4124 [CQOI2016] 手机号码

题目描述

人们选择手机号码时都希望号码好记、吉利。比如号码中含有几位相邻的相同数字、不含谐音不吉利的数字等。手机运营商在发行新号码时也会考虑这些因素，从号段中选取含有某些特征的号码单独出售。为了便于前期规划，运营商希望开发一个工具来自动统计号段中满足特征的号码数量。工具需要检测的号码特征有两个：号码中要出现至少 $3$ 个相邻的相同数字；号码中不能同时出现 $8$ 和 $4$ 。号码必须同时包含两个特征才满足条件。满足条件的号码例如：13000988721、23333333333、14444101000。而不满足条件的号码例如：1015400080、10010012022。手机号码一定是 $11$ 位数，且不含前导的 $0$ 。工具接收两个数 $L$ 和 $R$ ，自动统计出 $[L,R]$ 区间内所有满足条件的号码数量。 $L$ 和 $R$ 也是 $11$ 位的手机号码。

输入格式

输入文件内容只有一行，为空格分隔的 $2$ 个正整数 $L,R$ 。

输出格式

输出文件内容只有一行，为 $1$ 个整数，表示满足条件的手机号数量。

输入 #1
12121284000 12121285550
输出 #1
5
说明/提示

样例解释：满足条件的号码： 12121285000、 12121285111、 12121285222、 12121285333、 12121285550。

数据范围： $10^{10}\leq L\leq R<10^{11}$ 。

依旧是瘤子写法。

Tip！：虽然数据保证了L,R都是十一位数，但因为计算前缀和(R)-(L-1)。故存在特殊情况：L取到1e11的时候。L-1只有十位数。需要特判！！！
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=12;
int l,r,a[N],dp[N][10][N][2][2][2][2],len;
void init(int x){
  len=0;
  while(x>0){a[++len]=x%10;x/=10;}
}
int dfs(int pos,int pre,int cnt,bool jud4,bool jud8,bool f,bool limit){
  if(jud4&&jud8) return 0;
  if(pos<=0) return f;
  if(pre>=0&&dp[pos][pre][cnt][jud4][jud8][f][limit]!=-1) 
  	return dp[pos][pre][cnt][jud4][jud8][f][limit];
  int res=0,up=limit?a[pos]:9;
  for(int i=0;i<=up;i++){
  	if(pos==len&&i==0) continue;
  	if(i==pre) res+=dfs(pos-1,pre,cnt+1,jud4||i==4,jud8||i==8,f||(cnt+1>=3),limit&&(i==up));
  	else res+=dfs(pos-1,i,1,jud4||i==4,jud8||i==8,f,limit&&(i==up));
  }
  if(pre>=0) dp[pos][pre][cnt][jud4][jud8][f][limit]=res;
  return res;
}
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int l,r;cin>>l>>r;
  int ans1,ans2;
  memset(dp,-1,sizeof(dp));
  init(l-1);
  ans1=(len<11)?0:dfs(len,-1,0,0,0,0,1);
  memset(dp,-1,sizeof(dp));
  init(r);
  if(len < 11)ans2 = 0;
  else ans2=dfs(len,-1,0,0,0,0,1);
  cout<<ans2-ans1;
}

25.4.1

P10424 [蓝桥杯 2024 省 B] 好数

题目描述

一个整数如果按从低位到高位的顺序，奇数位（个位、百位、万位……）上的数字是奇数，偶数位（十位、千位、十万位……）上的数字是偶数，我们就称之为“好数”。

给定一个正整数 $N$ ，请计算从 $1$ 到 $N$ 一共有多少个好数。

输入 #1
24
输出 #1
7
输入 #2
2024
输出 #2
150
样例 1 解释

$24$ 以内的好数有 $1,3,5,7,9,21,23$ ，一共 $7$ 个。

数据规模与约定

对于 $10\%$ 的测试数据， $1 \leq N \le 100$ 。

对于全部的测试数据， $1 \le N \leq 10^7$ 。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int len,a[10],dp[10][2][2],n;
void init(int x){
  memset(dp,-1,sizeof(dp));
  len=0;
  while(x>0){a[++len]=x%10;x/=10;}
}
int dfs(int pos,bool frt0,bool limit){
  if(pos<=0) return 1;
  if(dp[pos][frt0][limit]!=-1) return dp[pos][frt0][limit];
  int up=limit?a[pos]:9,res=0;
  for(int i=0;i<=up;i++){
      if(i==0&&frt0){res+=dfs(pos-1,1,0);continue;}
      if(pos&1 && i&1) res+=dfs(pos-1,0,limit&&(i==up));
      if((pos&1)==0&&(i&1)==0) res+=dfs(pos-1,0,limit&&(i==up));
  }
  dp[pos][frt0][limit]=res;
  return res;
}
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin>>n;
  init(n);
  cout<<dfs(len,1,1)-1;
}

25.4.2

B3883 [信息与未来 2015] 求回文数（加强版）

题目描述

一个正整数，正读和反读都相同的数为回文数，例如 $22,131,2442,37073,6,\cdots$ 。所有的 $1$ 位数都是回文数。

现给出一个正整数 $n$ ，求出 $[1,n]$ 中的回文数的个数。

输入格式

一个整数 $n$ 。

输出格式

一个整数，即 $1\sim n$ 中全部回文数的个数，答案对 $20091119$ 取模。

输入 #1
24
输出 #1
11
样例解释

在 $1$ 至 $24$ 中，回文数有 $1\sim 9,11,22$ ，共 $11$ 个。

数据范围

$1\le n\le10^{100}$ 。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
const int mod=20091119;
int n,len,a[105],sav[105],ans=0;
string s;
int ksm(int a,int b){
int res=1;
while(b){
  if(b&1) res=(res*a)%mod;
  b>>=1;
  a=(a*a)%mod;
}
return res;
}
bool check(){
for(int i=(len>>1)+1;i<=len;i++){
  if(a[i]>a[len+1-i]) return 0;
  else if(a[i]<a[len+1-i]) return 1;
}
return 1;
}
void init(string x){
len=0;
for(int i=x.size()-1;i>=0;i--){a[++len]=x[i]-'0';}
}
int dfs(int pos,bool limit){
if(pos<=(len>>1)){
  if(limit) return check();
  else return 1;
}
if(!limit) return ksm(10,(2*pos-len+1)/2);
int up=limit?a[pos]:9,res=0;
for(int i=0;i<=up;i++){
  if(i==0&&pos==len) continue;
  res+=dfs(pos-1,limit&&(i==up));
}
return res;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>s;
init(s);
sav[1]=sav[2]=9;
if(len>1) ans+=sav[1];
if(len>2) ans+=sav[2];
for(int i=3;i<=len-1;i++){
  sav[i]=(sav[i-2]*10)%mod;
  ans=(ans+sav[i])%mod;
}
ans=(ans+dfs(len,1))%mod;
cout<<ans;
}
这题真的...做了三天才AC。

Var哥说“感觉你可以学其他的了，数位dp做好久了。已经很熟了，题过不了都不是算法的问题”。

最近到底在干什么，干啥事情都拖拉，站在悬崖边上摇摇欲坠，感觉人也摇摇欲坠，调节调节自己精神状态吧，然后投入到一个人的世界里去。

25.4.4

【模板】整除分割

图片上传失败，请重新上传

区间之间遍历的写法

for(int l=1;l<=n;l=r){
  //省略执行部分
  r=min(k/(k/l),n);
  //计数部分
}

P2261 [CQOI2007] 余数求和

题目描述

给出正整数 $n$ 和 $k$ ，请计算 $G(n, k) = \sum_{i = 1}^n k \bmod i$ 其中 $k\bmod i$ 表示 $k$ 除以 $i$ 的余数。

输入格式

输入只有一行两个整数，分别表示 $n$ 和 $k$ 。

输出格式

输出一行一个整数表示答案。

输入 #1
10 5
输出 #1
29
样例 1 解释

$G(10, 5)=0+1+2+1+0+5+5+5+5+5=29$ 。

数据规模与约定

对于 $30\%$ 的数据，保证 $n , k \leq 10^3$ 。对于 $60\%$ 的数据，保证 $n, k \leq 10^6$ 。对于 $100\%$ 的数据，保证 $1 \leq n, k \leq 10^9$ 。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=1e5+5;
int n,k,l,r,res;
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>k;
res=n*k;
for(int l=1;l<=n;l=r+1){
  if(k/l==0) break;
  r=min(k/(k/l),n);
  res-=(k/l)*(r-l+1)*(l+r)/2;
}
cout<<res<<endl;
}

25.4.8

春联5.1008小凯想要MVP！[鸽巢原理]

图片上传失败，请重新上传

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=2e5+5;
set<int> s;
int n,m,a[N],sum=0;
bool flag;
void dfs(int p,int cnt){
  if(cnt==0){
  	if(s.count(sum)){flag=true;return;}
  	s.insert(sum);
  	return;
  }
  if(p>n) return;
  if(p+cnt<n/2) return;
  dfs(p+1,cnt);
  sum+=a[p];
  dfs(p+1,cnt-1);
  sum-=a[p];
}
void solve(){
  cin>>n>>m;
  for(int i=1;i<=n;i++) cin>>a[i];
  flag=false;
  sum=0;
  s.clear();
  if(n>=24){cout<<"YES"<<endl;return;}
  dfs(1,n/2);
  if(flag) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;cin>>t;
  while(t--) solve();
}

25.4.13

25蓝桥杯省B复盘

25.4.14

键帽（春联6.1009）[dp]

图片上传失败，请重新上传

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=1e6+5;
const int mod=1e9+7;
int n,m,s[N],k;
int ksm(int a,int b){
int ans=1;
while(b){
 if(b&1) ans=(ans*a)%mod;
 b>>=1;
 a=(a*a)%mod;
}
return ans;
}
void solve(){
cin>>n>>k;
if(n<=k){cout<<ksm(26,n)<<endl;return;}
int c=ksm(5,k+1);
s[0]=1;
for(int i=1;i<=k;i++) s[i]=(s[i-1]*26)%mod;
s[k+1]=(mod+26*s[k]-c)%mod;
for(int i=k+2;i<=n;i++)
  s[i]=(mod+26*s[i-1]%mod-c%mod*21%mod*s[i-k-2]%mod)%mod;
cout<<s[n]<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;cin>>t;
while(t--) solve();
}

关键在于`如何处理初始几项dp值`和`求值过程中的取模运算`。

ST表复习

图片上传失败，请重新上传

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define int long long
const int mod=1e9+7;
const int N=1e5+5;
int n,q,l,r;
int f[N][20];//20取决于区间长度，f[i][j]表示左起点为i，区间长为(1<<j)的对应函数值	
   void init(){
   for(int i=1;i<=n;i++) cin>>f[i][0];
   for(int j=1;j<=20;j++)
      for(int i=1;i+(1<<j)-1<=n;i++)
          f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
signed main(){
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   cin>>n>>q;
   init();
   for(int i=1;i<=q;i++){
      cin>>l>>r;
      int k;
      k=log2(r-l+1);
      //for(k=1;(1<<k)<=r-l+1;k++);k--;
      cout<<max(f[l][k],f[r-(1<<k)+1][k])<<endl;
   }

}

英逃（春联6.1002）[ST+前缀和+二分]

图片上传失败，请重新上传

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
const int mod=1e9+7;
const int N=1e5+5;
int n,m,f[N][20],x,d[N];
void init(){
for(int j=1;j<=20;j++)
  for(int i=1;i+(1<<(j))-1<=n;i++)
      f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
bool check(int l,int len) {
  int r=l+len-1;
  int res=d[l-1]+d[n]-d[r+1];
  int k=log2(len);
  int m=max(f[l][k],f[r-(1<<k)+1][k]);
  if (l>1) res+=abs(f[l-1][0]-m);
  if (r<n) res+=abs(f[r+1][0]-m);
  return res<=x;
}
void solve(){
cin>>n>>x;
for(int i=1;i<=n;i++){
  cin>>f[i][0];
  d[i]=d[i-1]+abs(f[i][0]-f[i-1][0]);
  if(i==1) d[i]=0;
}  
d[n+1]=d[n];
if(d[n]<=x){cout<<0<<endl;return;}
init();
int ans=INF;
for(int l=1;l<=n;l++){
  int ll=1,rr=n-l+1,mid;
  while(ll<=rr){
      mid=ll+rr>>1;
      if(check(l,mid)){ans=min(ans,mid);rr=mid-1;}
      else ll=mid+1;
  }
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;cin>>t;
while(t--) solve();
}

25.4.15

【模板】LCA的st表求法(复习)

图片上传失败，请重新上传

时间复杂度：O((n+m)logn)

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=5e5+5;
int n,m,root,dep[N],st[N][20];
vector<int> e[N];
void dfs(int u,int fat,int d){
  dep[u]=d;
  st[u][0]=fat;
  for(int i=1;i<=19;i++)
      st[u][i]=st[st[u][i-1]][i-1];
  for(int v:e[u])
      if(v!=fat) dfs(v,u,d+1);
}
int query(int a,int b){
  if(dep[a]<dep[b]) swap(a,b);
  for(int i=19;i>=0;i--)
      if(dep[st[a][i]]>dep[b])
          a=st[a][i];
  for(int i=1;i<=dep[a]-dep[b];i++) a=st[a][0];
  if(a==b) return a;
  for(int i=19;i>=0;i--)
      if(st[a][i]!=st[b][i])
          a=st[a][i],b=st[b][i];
  return st[a][0];
}
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin>>n>>m>>root;
  int u,v;
  for(int i=1;i<n;i++){
      cin>>u>>v;
      e[u].push_back(v);
      e[v].push_back(u);
  }
  dfs(root,0,1);
  for(int i=1;i<=m;i++){
      cin>>u>>v;
      cout<<query(u,v)<<endl;
  }
}

FFT

P3803 【模板】多项式乘法（FFT）

这是一道多项式乘法模板题。

注意：本题并不属于中国计算机学会划定的提高组知识点考察范围。

题目描述

给定一个 $n$ 次多项式 $F(x)$ ，和一个 $m$ 次多项式 $G(x)$ 。

请求出 $F(x)$ 和 $G(x)$ 的卷积。

输入格式

第一行两个整数 $n,m$ 。

接下来一行 $n+1$ 个数字，从低到高表示 $F(x)$ 的系数。

接下来一行 $m+1$ 个数字，从低到高表示 $G(x)$ 的系数。

输出格式

一行 $n+m+1$ 个数字，从低到高表示 $F(x) \cdot G(x)$ 的系数

输入 #1
1 2
1 2
1 2 1
输出 #1
1 4 5 2
说明/提示

保证输入中的系数大于等于 $0$ 且小于等于 $9$ 。

对于 $100\%$ 的数据： $1 \le n, m \leq {10}^6$ 。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define int long long
const int mod=1e9+7;
const double PI=acos(-1);
const int N=4e6+5;
struct comp{
double x,y;
comp operator+(const comp& t)const{return {x+t.x, y+t.y};}
comp operator-(const comp& t)const{return {x-t.x, y-t.y};}
comp operator*(const comp& t)const{return {x*t.x-y*t.y, x*t.y+y*t.x};}
}a[N],b[N];
int r[N];
void FFT(comp a[],int n,int op){
for(int i=0;i<n;i++)//位逆序变换
  r[i]=(r[i>>1]>>1)+((i&1)?(n>>1):0);
for(int i=0;i<n;i++)
  if(i<r[i]) swap(a[i],a[r[i]]);
for(int i=2;i<=n;i<<=1){
  comp w1({cos(2*PI/i),sin(2*PI/i)*op});
  for(int j=0;j<n;j+=i){
      comp wk({1,0});
      for(int k=j;k<j+i/2;k++){
          comp x=a[k],y=a[k+i/2]*wk;
          a[k]=x+y;
          a[k+i/2]=x-y;
          wk=wk*w1;
      }
  }
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m; 
for(int i=0;i<=n;i++) cin>>a[i].x;
for(int i=0;i<=m;i++) cin>>b[i].x;
for(m=n+m,n=1;n<=m;n<<=1);
FFT(a,n,1);     FFT(b,n,1);
for(int i=0;i<n;i++) a[i]=a[i]*b[i];
FFT(a,n,-1);
for(int i=0;i<=m;i++) cout<<(int)(a[i].x/n+0.5)<<" ";
}

25.4.18

章鱼（春联6.1010) [树,LCA?]

![25966db8dbaaafb00a374e17ac9eb742](../Tencent Files/1832539553/nt_qq/nt_data/Pic/2025-04/Ori/25966db8dbaaafb00a374e17ac9eb742.png)

![0a725eb8bc9ff103b28cbf1e956a8257](../Tencent Files/1832539553/nt_qq/nt_data/Pic/2025-04/Ori/0a725eb8bc9ff103b28cbf1e956a8257.jpg)

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=2e5+5;
int n,u,v,fa[N],siz[N];
vector<int> e[N];
void dfs(int u,int fat){
fa[u]=fat;
siz[u]=1;
for(int v:e[u]){
  if(v==fat) continue;
  dfs(v,u);
  siz[u]+=siz[v];
}
}
void solve(){
cin>>n;
for(int i=1;i<n;i++){
  cin>>u>>v;
  e[u].push_back(v);
  e[v].push_back(u);
}
dfs(1,0);
for(int i=1;i<=n;i++){
  int sum1=0,sum=0,c;
  for(int v:e[i]){
      if(v==fa[i]) c=n-siz[i];
      else c=siz[v];
      sum+=sum1*c;
      sum1+=c;
  }
  int ftt=sum+n;
  int ans=ftt;
  for(int v:e[i]){
      if(v==fa[i]) c=n-siz[i];
      else c=siz[v];
      ans+=c*(ftt-c*(n-c));
  }
  cout<<ans<<" ";
}
cout<<endl;
for(int i=1;i<=n;i++) e[i].clear();
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;cin>>t;
while(t--) solve();
}

25.4.20

网格计数

图片上传失败，请重新上传

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int mod=998244353;
const int N=2e5+5;
int n,m,a[N];
int tt[N],intt[N];
void init_inff(){
tt[0]=intt[0]=1;
tt[1]=intt[1]=1;
for(int i=2;i<N;i++){
  tt[i]=i;
  intt[i]=(mod-mod/i)*intt[mod%i]%mod;
}
for(int i=2;i<N;i++){
  tt[i]=tt[i-1]*tt[i]%mod;
  intt[i]=intt[i-1]*intt[i]%mod;
}
}
int C(int n,int m){
if(n<0||m<0||m>n) return 0;
return tt[n]*intt[m]%mod*intt[n-m]%mod;
}
void solve(){
cin>>m>>n;
m-=1;
cout<<(mod+C(m,n)*C(m,n)%mod-C(m,n+1)*C(m,n-1)%mod)%mod<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;cin>>t;
init_inff();
while(t--) solve();
return 0;
}

25.4.21

【模板】Tarjan求强连通分量

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
const int mod=1e9+7;
const double PI=acos(-1);
const int N=1e4+5;
int n,m,cnt,dfs_clock,top,u,v;
int inst[N],dfn[N],low[N],st[N];//用数组st和top来实现栈
vector<int> e[N],V[N];
void tarjan(int x){
dfn[x]=low[x]=++dfs_clock;//盖戳，入栈
st[++top]=x;inst[x]=1;
for(int y:e[x]){
  if(!dfn[y]){//没访问过（树边）
      tarjan(y);
      low[x]=min(low[x],low[y]);
  }else if(inst[y]){//已访问且在栈中（返祖边或者横叉边）
      low[x]=min(low[x],dfn[y]);
  }//已访问但不在栈中（即已经属于另一个强连通分量且已处理）
}
if(low[x]==dfn[x]){//x为该SCC的根
  int y;cnt++;
  do{
      inst[y=st[top--]]=0;
      V[cnt].push_back(y);
  }while(x^y);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=m;i++){
  cin>>u>>v;
  e[u].push_back(v);
}
top=cnt=dfs_clock=0;
for(int i=1;i<=n;i++)
  if(!dfn[i]) tarjan(i);
//cout<<cnt;
return 0;
}

P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G

题目描述

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 $A$ 喜欢 $B$ ， $B$ 喜欢 $C$ ，那么 $A$ 也喜欢 $C$ 。牛栏里共有 $N$ 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。

输入格式

第一行：两个用空格分开的整数： $N$ 和 $M$ 。接下来 $M$ 行：每行两个用空格分开的整数： $A$ 和 $B$ ，表示 $A$ 喜欢 $B$ 。

输出格式

一行单独一个整数，表示明星奶牛的数量。

输入 #1
3 3
1 2
2 1
2 3
输出 #1
1
对于 $100\%$ 的数据， $1\le N\le10^4$ ， $1\le M\le5\times 10^4$ 。

首先，不难发现，如果这所有的牛都存在同一个强联通分量里。那么它们一定互相受欢迎。

那么，我们怎么来找明星呢。

很简单，找出度为0的强联通分量中的点。这样可以保证所有的人都喜欢它，但是它不喜欢任何人，所以说不存在还有人事明星。

此题还有一个特殊情况：

如果有两个点分别满足出度为零的条件，则没有明星，这样无法满足所有的牛喜欢他。

有了上边的解释，题目就不是那么难了，代码如下
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
const int mod=1e9+7;
const double PI=acos(-1);
const int N=1e4+5;
int n,m,cnt,dfs_clock,top,u,v;
int inst[N],dfn[N],low[N],st[N],id[N];//用数组st和top来实现栈
int s[N];
int outdgr[N];//缩点后编号为i的SCC的出度
vector<int> e[N],V[N];
void tarjan(int x){
dfn[x]=low[x]=++dfs_clock;//盖戳，入栈
st[++top]=x;inst[x]=1;
for(int y:e[x]){
  if(!dfn[y]){//没访问过（树边）
      tarjan(y);
      low[x]=min(low[x],low[y]);
  }else if(inst[y]){//已访问且在栈中（返祖边或者横叉边）
      low[x]=min(low[x],dfn[y]);
  }//已访问但不在栈中（即已经属于另一个强连通分量且已处理）
}
if(low[x]==dfn[x]){//x为该SCC的根
  int y;cnt++;
  do{
      inst[y=st[top--]]=0;
      id[y]=cnt;//记录属于哪个SCC
      V[cnt].push_back(y);
  }while(x^y);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=m;i++){
  cin>>u>>v;
  e[u].push_back(v);
}
for(int i=1;i<=n;i++) s[i]=i;

top=cnt=dfs_clock=0;
for(int i=1;i<=n;i++)
  if(!dfn[i]) tarjan(i);
for(int u=1;u<=n;u++)
  for(int v:e[u])
      if(id[u]!=id[v]) outdgr[id[u]]++;
int ans=0;
for(int i=1;i<=cnt;i++)
  if(!outdgr[i]){
      if(ans){cout<<0;return 0;}
      ans=V[i].size();
  }
cout<<ans;
return 0;
}

25.4.22

P2812 校园网络【[USACO]Network of Schools加强版】

图片上传失败，请重新上传

Tarjan缩点使得有环图变成无环图。

Q1(选择几所学校作为母机能覆盖)：Tarjan缩点后入度为零的SCC的个数

Q2(有向无环图中增加多少条边使得整体变成一个SCC)：考虑缩点后max(入读为0的点的个数，出度为0的点的个数） 特判：如果只有一个SCC则输出0

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
const int mod=1e9+7;
const double PI=acos(-1);
const int N=1e5+5;
int n,m,cnt,dfs_clock,top,u,v;
int inst[N],dfn[N],low[N],st[N],id[N];//用数组st和top来实现栈
int s[N];
int outdgr[N],indgr[N];//缩点后编号为i的SCC的出度
vector<int> e[N],scc[N];
void tarjan(int x){
dfn[x]=low[x]=++dfs_clock;//盖戳，入栈
st[++top]=x;inst[x]=1;
for(int y:e[x]){
  if(!dfn[y]){//没访问过（树边）
      tarjan(y);
      low[x]=min(low[x],low[y]);
  }else if(inst[y]){//已访问且在栈中（返祖边或者横叉边）
      low[x]=min(low[x],dfn[y]);
  }//已访问但不在栈中（即已经属于另一个强连通分量且已处理）
}
if(low[x]==dfn[x]){//x为该SCC的根
  int y;cnt++;
  do{
      inst[y=st[top--]]=0;
      id[y]=cnt;//记录属于哪个SCC
      scc[cnt].push_back(y);
  }while(x^y);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tmp;
cin>>n;
for(int i=1;i<=n;i++)
  while(cin>>tmp&&tmp!=0)
      e[i].push_back(tmp);
for(int i=1;i<=n;i++) s[i]=i;
top=cnt=dfs_clock=0;
for(int i=1;i<=n;i++)
  if(!dfn[i]) tarjan(i);
for(int u=1;u<=n;u++)
  for(int v:e[u])
      if(id[u]!=id[v]){
          outdgr[id[u]]++;
          indgr[id[v]]++;
      }
int indgr0=0,outdgr0=0;
for(int i=1;i<=cnt;i++){
  if(indgr[i]==0) indgr0++;
  if(outdgr[i]==0) outdgr0++;
}
if(cnt==1){cout<<indgr0<<endl<<0;return 0;}
cout<<indgr0<<endl<<max(outdgr0,indgr0);
return 0;
}

25.4.23

P3387 【模板】缩点（Tarjan的单连通分量）

题目描述

给定一个 $n$ 个点 $m$ 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

输入格式

第一行两个正整数 $n,m$ 。第二行 $n$ 个整数，其中第 $i$ 个数 $a_i$ 表示点 $i$ 的点权。第三至 $m+2$ 行，每行两个整数 $u,v$ ，表示一条 $u\rightarrow v$ 的有向边。

输出格式

共一行，最大的点权之和。

输入 #1
2 2
1 1
1 2
2 1
输出 #1
2
说明/提示

对于 $100\%$ 的数据， $1\le n \le 10^4$ ， $1\le m \le 10^5$ ， $0\le a_i\le 10^3$ 。

2024-11-1 添加了 hack 数据；

单连通分量【题号LUOGU3387 【题目]求有向图上一条点权和最大的链【思路】在一个单连通分量中，任意两点可相互到达，采取贪心策略一定会经过分量中的所有点。将有向图的单连通分量缩成一个点，权值为原来所有点权之和，得到的新图是DAG，然后在DAG上记忆化DP。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
const int mod=1e9+7;
const double PI=acos(-1);
const int N=1e5+5;
int w[N],ww[N];//w[]-原图点权 w1[]-缩点后的点权
int dfn[N],low[N],dfsid;//dfn[]-DFS时间戳 low[]-可到达的最小时间戳
int grp[N],grpid;//grp[i]-i属于哪个SCC
vector<int> st;//实现栈
vector<int> e[N],ee[N];
unordered_set<int> vis;
int pair_hash(int u,int v){return u*N+v;}
void tarjan(int u){
    dfn[u]=low[u]=++dfsid;
    st.push_back(u);
    for(int v:e[u]){
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(!grp[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        grp[u]=++grpid;
        ww[grpid]=w[u];
        while(st.back()!=u){
            grp[st.back()]=grpid;
            ww[grpid]+=w[st.back()];
            st.pop_back();
        }
        st.pop_back();
    }
}
int dp[N];
int dfs(int u){
    if(dp[u]!=-1) return dp[u];
    int tmp=0;
    for(int v:ee[u]) tmp=max(tmp,dfs(v));
    return dp[u]=tmp+ww[u];
}
int n,m,u,v,uu,vv,ans;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        e[u].push_back(v);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    for(int u=1;u<=n;u++){
        for(auto v:e[u]){
            uu=grp[u],vv=grp[v];
            if(uu!=vv&&vis.count(pair_hash(uu,vv))==0){
                vis.insert(pair_hash(uu,vv));
                ee[uu].push_back(vv);
            }
        }
    }
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=n;i++) ans=max(ans,dfs(i));
    cout<<ans;
    return 0;
}

B3609 [图论与代数结构 701] 强连通分量

题目描述

给定一张 $n$ 个点 $m$ 条边的有向图，求出其所有的强连通分量。

注意，本题可能存在重边和自环。

输入格式

第一行两个正整数 $n$ ， $m$ ，表示图的点数和边数。

接下来 $m$ 行，每行两个正整数 $u$ 和 $v$ 表示一条边。

输出格式

第一行一个整数表示这张图的强连通分量数目。

接下来每行输出一个强连通分量。第一行输出 1 号点所在强连通分量，第二行输出 2 号点所在强连通分量，若已被输出，则改为输出 3 号点所在强连通分量，以此类推。每个强连通分量按节点编号大小输出。

输入 #1
6 8
1 2
1 5
2 6
5 6
6 1
5 3
6 4
3 4
输出 #1
3
1 2 5 6
3
4
说明/提示

对于所有数据， $1 \le n \le 10000$ ， $1 \le m \le 100000$ 。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=1e5+5;
int n,m,u,v;
vector<int> e[N];
vector<int> st;
int inst[N],grp[N],grpid,dfn[N],low[N],dfsid;
int vis[N];
vector<int> SCC[N];
void tarjan(int u){
dfn[u]=low[u]=++dfsid;
st.push_back(u);
for(int v:e[u]){
  if(!dfn[v]){
      tarjan(v);
      low[u]=min(low[v],low[u]);
  }else if(!grp[v]){
      low[u]=min(low[u],dfn[v]);
  }
}
if(dfn[u]==low[u]){
  grp[u]=++grpid;
  SCC[grpid].push_back(u);
  while(st.back()!=u){
      SCC[grpid].push_back(st.back());
      grp[st.back()]=grpid;
      st.pop_back();
  }
  st.pop_back();
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=m;i++){
  cin>>u>>v;
  e[u].push_back(v);
}
for(int i=1;i<=n;i++) 
  if(!dfn[i]) tarjan(i);
cout<<grpid<<endl;
for(int i=1;i<=grpid;i++)
  sort(SCC[i].begin(),SCC[i].end());
for(int i=1;i<=n;i++){
  if(!vis[grp[i]]){
      vis[grp[i]]=1;
      for(int u:SCC[grp[i]])
          cout<<u<<" ";
      cout<<endl;
  }
}
return 0;
}

LCA(Tarjan)

![a4407f3d0e8ea12eca6ddc84e74d6b54](../Tencent Files/1832539553/nt_qq/nt_data/Pic/2025-04/Ori/a4407f3d0e8ea12eca6ddc84e74d6b54.png)

![b0c4982b6109d9979a7d9344341760d7](../Tencent Files/1832539553/nt_qq/nt_data/Pic/2025-04/Ori/b0c4982b6109d9979a7d9344341760d7.png)

时间复杂度：O(n+m)

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=5e5+5;
int n,m,u,v,root;
vector<int> e[N];
vector<pair<int,int>> query[N];
int fa[N],vis[N],ans[N];
int find(int u){
if(u==fa[u]) return u;
else return fa[u]=find(fa[u]);
}
void tarjan(int u){
vis[u]=1;
for(int v:e[u]){
  if(!vis[v]){
      tarjan(v);
      fa[v]=u;
  }
}
for(auto q:query[u]){
  int v=q.first,i=q.second;
  if(vis[v]) ans[i]=find(v);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m>>root;
for(int i=1;i<n;i++){
  cin>>u>>v;
  e[u].push_back(v);
  e[v].push_back(u); 
}
for(int i=1;i<=m;i++){
  cin>>u>>v;
  query[u].push_back({v,i});
  query[v].push_back({u,i});
}
for(int i=1;i<N;i++) fa[i]=i;
tarjan(root);
for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
}

【模板】高斯消元法

P3389 【模板】高斯消元法

题目背景

如果想要更好地测试高斯消元算法模板请在通过此题后尝试通过 SDOI2006 线性方程组这一题。

题目描述

给定一个线性方程组，对其求解。

$\begin{cases} a_{1, 1} x_1 + a_{1, 2} x_2 + \cdots + a_{1, n} x_n = b_1 \\ a_{2, 1} x_1 + a_{2, 2} x_2 + \cdots + a_{2, n} x_n = b_2 \\ \cdots \\ a_{n,1} x_1 + a_{n, 2} x_2 + \cdots + a_{n, n} x_n = b_n \end{cases}$

输入格式

第一行，一个正整数 $n$ 。

第二至 $n+1$ 行，每行 $n+1$ 个整数，为 $a_1, a_2, \dots ,a_n$ 和 $b$ ，代表一组方程。

输出格式

共 $n$ 行，每行一个数，第 $i$ 行为 $x_i$ （四舍五入保留 $2$ 位小数）。

如果不存在唯一解或无解，在第一行输出 No Solution.

输入 #1
3
1 3 4 5
1 4 7 3
9 3 2 2
输出 #1
-0.97
5.18
-2.39
说明/提示

本题 special judge 用于处理可能由于浮点数问题输出 -0.00 的情况。若某个 $x_i$ 的解四舍五入后是 0.00，那么你的程序输出 -0.00 和输出 0.00 都是正确的。

数据范围： $1 \leq n \leq 100, \left | a_i \right| \leq {10}^4 , \left |b \right| \leq {10}^4$ 。保证数据若有解则所有解均满足 $|x_i|\le 10^3$ ，且 $x_i\pm 10^{-6}$ 和 $x_i$ 四舍五入后的结果相同（即不会因为较小的精度误差导致四舍五入后的结果不同）。
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-6;
const int N=1e2+5;
int n,m;
double a[N][N];
int gauss(int n,int m){//n行m+1列的增广矩阵:a[0..n-1][0..n]
int r=0;//r:有效方程数(矩阵的秩),操作时的行下标
for(int c=0;c<m;++c){//遍历列 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;//若主元列为0，不考虑，当前全列为0
  //交换列主元t行与当前r行的数
  for(int j=c;j<=m;j++) swap(a[t][j],a[r][j]);
  for(int j=m;j>=c;j--) a[r][j]/=a[r][c];//使得主对角线系数均为1
  for(int i=r+1;i<n;i++)//与r+1~n-1进行消元
      if(fabs(a[i][c])>eps)
          for(int j=m;j>=c;j--)
              a[i][j]-=a[r][j]*a[i][c];
  ++r;             
}
for(int i=r;i<n;i++)
  if(fabs(a[i][m])>eps)
      return 2;//无解
if(r<m) return 1;//无穷多解    
for(int i=m-1;i>=0;i--)//回代求解方程
  for(int j=i+1;j<m;j++)
      a[i][m]-=a[j][m]*a[i][j];
return 0;//一般情况(有唯一确定解）             
}
signed main(){
cin>>n;
for(int i=0;i<n;i++)
  for(int j=0;j<=n;j++)
      cin>>a[i][j];
if(gauss(n,n)) cout<<"No Solution";
else for(int i=0;i<n;i++) printf("%.2lf\n",a[i][n]);
}

P2455 [SDOI2006] 线性方程组

题目描述

已知 $n$ 元线性一次方程组。

$\begin{cases} a_{1, 1} x_1 + a_{1, 2} x_2 + \cdots + a_{1, n} x_n = b_1 \\ a_{2, 1} x_1 + a_{2, 2} x_2 + \cdots + a_{2, n} x_n = b_2 \\ \cdots \\ a_{n,1} x_1 + a_{n, 2} x_2 + \cdots + a_{n, n} x_n = b_n \end{cases}$

请根据输入的数据，编程输出方程组的解的情况。

输入格式

第一行输入未知数的个数 $n$ 。
接下来 $n$ 行，每行 $n + 1$ 个整数，表示每一个方程的系数及方程右边的值。

输出格式

如果有唯一解，则输出解。你的结果被认为正确，当且仅当对于每一个 $x_i$ 而言结果值与标准答案值的绝对误差或者相对误差不超过 $0.01$ 。

如果方程组无解输出 $-1$ ；如果有无穷多实数解，输出 $0$ ；

输入 #1

输出 #1

x1=1.00
x2=0.00
x3=-1.00

【数据范围】
对于 $100\%$ 的数据， $1 \le n \le 50$ 。对于 $\forall 1\le i, j \le n$ ，有 $|a_{i, j}| \le 100$ ， $|b_i| \le 300$ 。

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-6;
const int N=1e2+5;
int n,m;
double a[N][N];
int gauss(int n,int m){//n行m+1列的增广矩阵:a[0..n-1][0..n]
int r=0;//r:有效方程数(矩阵的秩),操作时的行下标
for(int c=0;c<m;++c){//遍历列 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;//若主元列为0，不考虑，当前全列为0
  //交换列主元t行与当前r行的数
  for(int j=c;j<=m;j++) swap(a[t][j],a[r][j]);
  for(int j=m;j>=c;j--) a[r][j]/=a[r][c];//使得主对角线系数均为1
  for(int i=r+1;i<n;i++)//与r+1~n-1进行消元
      if(fabs(a[i][c])>eps)
          for(int j=m;j>=c;j--)
              a[i][j]-=a[r][j]*a[i][c];
  ++r;             
}
for(int i=r;i<n;i++)
  if(fabs(a[i][m])>eps)
      return 2;//无解
if(r<m) return 1;//无穷多解    
for(int i=m-1;i>=0;i--)//回代求解方程
  for(int j=i+1;j<m;j++)
      a[i][m]-=a[j][m]*a[i][j];
return 0;//一般情况(有唯一确定解）             
}
signed main(){
cin>>n;
for(int i=0;i<n;i++)
  for(int j=0;j<=n;j++)
      cin>>a[i][j];
int flag=gauss(n,n);
if(flag==1) cout<<0;
else if(flag==2) cout<<-1; 
else for(int i=0;i<n;i++) printf("x%d=%.2lf\n",i+1,a[i][n]);
}

25.4.26

最小生成树（MST）

Kruskal

按照边权升序排序（直接建边的数组）；遍历每一条边，只要两个端点不属于一个并查集就选上；如果选了n-1条边则保证最小生成树存在。

const int N=5e3+5;
const int M=2e5+5;
int n,m;
int s[N];
struct edge{
int u,v,w;
}edg[M];
bool cmp(edge x,edge y){return x.w<y.w;}
int find(int x){return s[x]==x?x:s[x]=find(s[x]);}
void merge(int x,int y){
  x=find(x);y=find(y);
  if(x!=y) s[x]=s[y];
}
bool jud(int x,int y){return find(x)==find(y);}
signed main(){
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
      cin>>n>>m;
      for(int i=1;i<=n;i++) s[i]=i;
      for(int i=1;i<=m;i++)
        cin>>edg[i].u>>edg[i].v>>edg[i].w;
      int cnt=0,sum=0;
      sort(edg+1,edg+m+1,cmp);
      for(int i=1;i<=m;i++){
        edge tmp=edg[i];
        if(!jud(tmp.u,tmp.v)){
            cnt++;
            sum+=tmp.w;
            merge(tmp.u,tmp.v);
        }
        if(cnt==n-1) break;
      }
      if(cnt<n-1) cout<<"orz";
      else cout<<sum;
      return 0;
}

25.4.27

Bitset

![f60d1be339418ce0f7f63d98847913a](../WeChat Files/wxid_8h8yrput2dqw22/FileStorage/Temp/f60d1be339418ce0f7f63d98847913a.png)

约数和

图片上传失败，请重新上传

vector<int> pri;
bool not_prime[N];
int g[N], f[N];

void pre(int n) {
g[1] = f[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!not_prime[i]) {
pri.push_back(i);
g[i] = i + 1;
f[i] = i + 1;
}
for (int pri_j : pri) {
if (i * pri_j > n) break;
not_prime[i * pri_j] = true;
if (i % pri_j == 0) {
  g[i * pri_j] = g[i] * pri_j + 1;
  f[i * pri_j] = f[i] / g[i] * g[i * pri_j];
  break;
}
f[i * pri_j] = f[i] * f[pri_j];
g[i * pri_j] = 1 + pri_j;
}
}
}

春联8（1001拼图游戏）

图片上传失败，请重新上传

考察压缩，思路类似于DP

正解：

bitset暴力解：

const int N=2e3+5;
int n,m,k,a[N][N];
bitset<N> b[N];
void solve(){
cin>>n>>m>>k;
int ans=0;
for(int i=1;i<=n;i++)
  for(int j=1;j<=m;j++) cin>>a[i][j];
for(int i=1;i<=m;i++)
  b[i].reset();
for(int i=1;i<=n;i++){
  bitset<N> res;
  res.reset();
  for(int j=1;j<=m;j++){
      b[j][a[i][j]]=1;
      res|=b[j];
      if(res.count()==k){
          ans+=m-j+1;
          break;
      }
  }
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;cin>>t;
while(t--) solve();
return 0;
}

25.4.28

春联8（1009能量网络）

图片上传失败，请重新上传

本质：将边缩成点后进行求最小生成树

难点：缩边成点后有m个点，理论上共有m*(m-1)/2条边，这个规模肯定会超时。

图片上传失败，请重新上传

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=1e5+5;
int n,m,u,v;
int s[N];
struct node{
int x,y,z,id;
//node operator +(const node&b)const&{return(node){x+b.x,y+b.y,z+b.z};} 
}tmp[N],poi[N];
struct edge{
int u,v,w;
}edg[3*N];
bool cmp(edge x,edge y){return x.w<y.w;}
bool cmpx(node a,node b){return a.x<b.x;}
bool cmpy(node a,node b){return a.y<b.y;}
bool cmpz(node a,node b){return a.z<b.z;}
int find(int x){return s[x]==x?x:s[x]=find(s[x]);}
void merge(int x,int y){
  x=find(x);y=find(y);
  if(x!=y) s[x]=s[y];
}
bool jud(int x,int y){return find(x)==find(y);}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>tmp[i].x>>tmp[i].y>>tmp[i].z;
for(int i=1;i<=m;i++){
  cin>>u>>v;
  poi[i].x=tmp[u].x+tmp[v].x;
  poi[i].y=tmp[u].y+tmp[v].y;
  poi[i].z=tmp[u].z+tmp[v].z;
  poi[i].id= s[i]=i;
}
sort(poi+1,poi+1+m,cmpx);
for(int i=1;i<m;i++)
  edg[i]={poi[i].id,poi[i+1].id, poi[i+1].x-poi[i].x};
sort(poi+1,poi+m+1,cmpy);
for(int i=1;i<m;i++)
  edg[i+(m-1)]={poi[i].id,poi[i+1].id, poi[i+1].y-poi[i].y};
sort(poi+1,poi+1+m,cmpz);
for(int i=1;i<m;i++)
  edg[i+2*(m-1)]={poi[i].id,poi[i+1].id, poi[i+1].z-poi[i].z};
sort(edg+1,edg+3*(m-1)+1,cmp);
int cnt=0,ans=0;
for(int i=1;i<=3*(m-1);i++){
  if(!jud(edg[i].u,edg[i].v)){
      cnt++;
      ans+=edg[i].w;
      merge(edg[i].u,edg[i].v);
  }
  if(cnt==m-1) break;
}
cout<<ans<<endl; 
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;cin>>t;
while(t--) solve();
return 0;
}

25.4.29

双指针判断是否为子序列

双指针搜，时复O(N)

25.4.30

字符串匹配数组（倒着遍历来处理跳跃查找的操作）

问题大意：原来为子串的字符串需要增加多少个字符来使得变成不是其子串。

思路：预处理一个匹配数组，每次询问的时候匹配即可。

实现：

nxt_id[i][j]:a[i]字符之后的第一个字符j(0<=j<26)的出现位置

dp[i]:若前i个字符与字符串完全匹配，则还需要增加几个字符

lst[i]:字符i上一次出现的位置

预处理：
memset(dp,0x3f,sizeof(dp));
dp[n+1]=0;
for(int j=0;j<k;j++) nxt_id[n+1][j]=lst[j]=n+1;
for(int i=n;i>=0;i--){
  for(int j=0;j<k;j++){
  	nxt_id[i][j]=lst[j];
  	dp[i]=min(dp[i],dp[nxt_id[i][j]]+1);
  }
  if(i!=0) lst[a[i]-'a']=i;
}
查询：
int q;cin>>q;
while(q--){
  string s;
  cin>>s;
  int id=0;
  for(int i=0;i<s.size();i++)
  	id=nxt_id[id][s[i]-'a'];
  cout<<dp[id]<<endl;
}

25.5.1(区间DP + 卡特兰数)

P1775石子合并（弱化版）

题目描述

设有 $N(N \le 300)$ 堆石子排成一排，其编号为 $1,2,3,\cdots,N$ 。每堆石子有一定的质量 $m_i\ (m_i \le 1000)$ 。现在要将这 $N$ 堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻。合并时由于选择的顺序不同，合并的总代价也不相同。试找出一种合理的方法，使总的代价最小，并输出最小代价。

输入格式

第一行，一个整数 $N$ 。

第二行， $N$ 个整数 $m_i$ 。

输出格式

输出文件仅一个整数，也就是最小代价。

输入 #1
4
2 5 3 1
输出 #1
22
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f3f3f3f3f
const int N=3e2+5;
int a[N],pre[N];
int dp[N][N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;cin>>n;
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=n;i++) dp[i][i]=0;
for(int i=1;i<=n;i++){
  cin>>a[i];
  pre[i]=pre[i-1]+a[i];
}
for(int len=2;len<=n;len++)
  for(int i=1;i+len-1<=n;i++){
      int j=i+len-1;
      for(int k=i;k<j;k++)
          dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+pre[j]-pre[i-1]);
  }
cout<<dp[1][n];
return 0;
}

P1880 [NOI1995] 石子合并

题目描述

在一个圆形操场的四周摆放 $N$ 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 $2$ 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出一个算法,计算出将 $N$ 堆石子合并成 $1$ 堆的最小得分和最大得分。

输入格式

数据的第 $1$ 行是正整数 $N$ ，表示有 $N$ 堆石子。

第 $2$ 行有 $N$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 堆石子的个数。

输出格式

输出共 $2$ 行，第 $1$ 行为最小得分，第 $2$ 行为最大得分。

输入 #1
4
4 5 9 4
输出 #1
43
54
说明/提示

$1\leq N\leq 100$ ， $0\leq a_i\leq 20$ 。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f3f3f3f3f
const int N=1e2+5;
int a[N],pre[N<<1];
int dp_m[N<<1][N<<1],dp_M[N<<1][N<<1];
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;cin>>n;
memset(dp_m,0x3f,sizeof(dp_m));
for(int i=1;i<=2*n;i++) dp_m[i][i]=dp_M[i][i]=0;
for(int i=1;i<=n;i++){
  cin>>a[i];
  pre[i]=pre[i-1]+a[i];
}
for(int i=1;i<=n;i++) pre[n+i]=pre[i]+pre[n];
for(int len=2;len<=n;len++)
  for(int i=1;i+len-1<=2*n-1;i++){
      int j=i+len-1;
      for(int k=i;k<j;k++){
          dp_m[i][j]=min(dp_m[i][j],dp_m[i][k]+dp_m[k+1][j]+pre[j]-pre[i-1]);
          dp_M[i][j]=max(dp_M[i][j],dp_M[i][k]+dp_M[k+1][j]+pre[j]-pre[i-1]);
      }
  }
int ans_m=INF,ans_M=0;
for(int i=1;i<=n;i++){
  ans_m=min(ans_m,dp_m[i][i+n-1]);
  ans_M=max(ans_M,dp_M[i][i+n-1]);
}
cout<<ans_m<<endl<<ans_M;
return 0;
}

25.5.2

峰值和（div2.C. Neo's Escape)

图片上传失败，请重新上传

问题化简后等价于：求一段数组中每一段峰的峰顶元素和

注意开头和结尾的细节即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=2e5+5;
int n,m,a[N];
void solve(){
   int n;
   cin>>n;
   bool sam=1;
   for(int i=1;i<=n;i++) cin>>a[i];
   for(int i=1;i<n;i++){
       if(a[i]!=a[i+1]){
           sam=0;
           break;
       }
   }
   if(sam){cout<<1<<endl;return;}
   int cnt=0;
   int pos=1;
   int up=0;
   while(pos<n){
       if(a[pos]<a[pos+1]){
           pos++;
           up=1;
       }else if(a[pos]==a[pos+1]){
           pos++;
       }else{
           up=0;
           cnt++;
           while(pos<n&&a[pos]>=a[pos+1]) pos++;
       }
   }
   if(up==1) cnt++;
   cout<<cnt<<endl;
}
signed main(){
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   int t;cin>>t;
   while(t--) solve();
   return 0;
}

25.5.7

线段树模板1和2复习

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f3f3f3f3f
#define rep(i,j,k) for (int i=j;i<=k;++i)
#define per(i,j,k) for (int i=j;i>=k;--i)
#define fi first
#define se second
#define mid  (l+r>>1)
const double eps=1e-6;
const int mod=1e9+7;
const double PI=acos(-1);
const int N=2e5+5;
int n,m,a[N],op,x,y,k;
struct node{
   	int sum,lazy=0;
}t[N<<2];
void build(int x,int l,int r){
       if(l==r){t[x].sum=a[l];return;}
       build(x<<1,l,mid);
       build(x<<1|1,mid+1,r);
       t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
}
void down(int x,int l,int r){
       if(t[x].lazy){
           t[x<<1].sum+=t[x].lazy*(mid-l+1);
           t[x<<1].lazy+=t[x].lazy;
           t[x<<1|1].sum+=t[x].lazy*(r-mid);
           t[x<<1|1].lazy+=t[x].lazy;
           t[x].lazy=0;
       } 
}
void update(int x,int l,int r,int L,int R,int k){
       if(L<=l&&r<=R){
           t[x].sum+=k*(r-l+1);
           t[x].lazy+=k;
           return;
       }
       down(x,l,r);
       if(L<=mid) update(x<<1,l,mid,L,R,k);
       if(mid+1<=R) update(x<<1|1,mid+1,r,L,R,k);
       t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
}
int query(int x,int l,int r,int L,int R){
       if(L<=l&&r<=R) return t[x].sum;
       if(L>r||R<l) return 0;
       down(x,l,r);
       return query(x<<1,l,mid,L,R)+query(x<<1|1,mid+1,r,L,R);
}
signed main(){
       ios::sync_with_stdio(false);
       cin.tie(nullptr);
       cin>>n>>m;
       rep(i,1,n) cin>>a[i];
       build(1,1,n);
       rep(i,1,m){
           cin>>op;
           if(op==1){
               cin>>x>>y>>k;
               update(1,1,n,x,y,k);
           }else if(op==2){
               cin>>x>>y;
               cout<<query(1,1,n,x,y)<<endl;
           }
       }
       return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f3f3f3f3f
#define rep(i,j,k) for (int i=j;i<=k;++i)
#define per(i,j,k) for (int i=j;i>=k;--i)
#define mid (l+r>>1)
#define fi first
#define se second
const double eps=1e-6;
const int mod=1e9+7;
const double PI=acos(-1);
const int N=1e5+5;
struct node{
   int sum,add,mul;
   }t[N<<2];
int n,m,L,R,q,op,k,a[N];
void build(int x,int l,int r){
   if(l==r){t[x]={a[l],0,1};return;}
       build(x<<1,l,mid);
       build(x<<1|1,mid+1,r);
       t[x]={(t[x<<1].sum+t[x<<1|1].sum)%m,0,1};
   }
void down(int x,int l,int r){
   if(t[x].mul!=1||t[x].add!=0){
          t[x<<1].sum=(t[x<<1].sum*t[x].mul+t[x].add*(mid-l+1))%m;
           t[x<<1|1].sum=(t[x<<1|1].sum*t[x].mul+t[x].add*(r-mid))%m;
           t[x<<1].mul=(t[x<<1].mul*t[x].mul)%m;
           t[x<<1|1].mul=(t[x<<1|1].mul*t[x].mul)%m;
           t[x<<1].add=(t[x<<1].add*t[x].mul+t[x].add)%m;
           t[x<<1|1].add=(t[x<<1|1].add*t[x].mul+t[x].add)%m;
           t[x].mul=1,t[x].add=0;
        }
   }
void update_add(int x,int l,int r){
   if(L<=l&&r<=R){
          t[x].sum+=k*(r-l+1);
           t[x].sum%=m;
           t[x].add=(t[x].add+k)%m;
           return;
        }
       down(x,l,r);
       if(mid>=L) update_add(x<<1,l,mid);
       if(mid<R) update_add(x<<1|1,mid+1,r);
       t[x].sum=(t[x<<1].sum+t[x<<1|1].sum)%m;
   }
void update_mul(int x,int l,int r){
   if(L<=l&&r<=R){
          t[x].sum=t[x].sum*k%m;
           t[x].mul=(t[x].mul*k)%m;
           t[x].add=t[x].add*k%m;
           return;
        }
       down(x,l,r);
       if(mid>=L) update_mul(x<<1,l,mid);
       if(mid<R) update_mul(x<<1|1,mid+1,r);
       t[x].sum=(t[x<<1].sum+t[x<<1|1].sum)%m;
   }
int query(int x,int l,int r){
   if(L<=l&&r<=R){return t[x].sum;}
       if(r<L||l>R){return 0;}
       down(x,l,r);
       return (query(x<<1,l,mid)+query(x<<1|1,mid+1,r))%m;
   }
signed main(){
   ios::sync_with_stdio(false);
       cin.tie(nullptr);
       cin>>n>>q>>m;
       rep(i,1,n) cin>>a[i];
       build(1,1,n);
       rep(i,1,q){
          cin>>op;
           if(op==1){
               cin>>L>>R>>k;
               update_mul(1,1,n);
           }else if(op==2){
               cin>>L>>R>>k;
               update_add(1,1,n);
           }else{
               cin>>L>>R;
               cout<<query(1,1,n)%m<<endl;
           }
        }
       return 0;
   }

容斥原理

int rongchi(int mul){
   int ans=0;
   for(int i=0;i<(1<<pri.size());i++){
       int multi=1,cnt=0;
       for(int j=0;j<pri.size();j++)
           if(i&(1<<j)){cnt++;multi*=p[j];}
       int cur=mul/multi;
       if(cnt&1) ans-=cur;
       else ans+=cur;
   }
   return ans;
}

25.5.10（矩阵快速幂，Lucas，Manacher)

25.5.11,12,13

Manacher题目总结

1.统计回文子串个数

春联9.1002

图片上传失败，请重新上传

const int N=1e5+5;
int n,a[N],delt[N];
int s[N<<1];//修改串
int d[N<<1];//回文半径函数
int getstr(){//返回修改串后的长度
       int k=0;
       s[0]=1832539553,s[++k]=-INF;
       rep(i,1,n){
           s[++k]=delt[i];
           s[++k]=-INF;
       }
       s[k+1]=18858876509;
       return k;
}
void manacher(int n){
   //d[i]为回文半径,以i为中心的回文串长度为(d[i]-1)
       rep(i,1,n) d[i]=0;
       d[1]=1;
       for(int i=2,l=1,r=1;i<=n;i++){
           if(i<=r) d[i]=min(d[l+(r-i)],r-i+1);
           while(s[i-d[i]]==s[i+d[i]]) d[i]++;
           if(i+d[i]-1>r) l=i-d[i]+1,r=i+d[i]-1;
       }
}
void solve(){
       cin>>n;
       int ans=n;
       rep(i,1,n) cin>>a[i];
       rep(i,2,n) delt[i-1]=a[i]-a[i-1];
       n-=1;
       int len=getstr();
       manacher(len);
       rep(i,1,len)
           ans+=d[i]/2;
       cout<<ans<<endl;
}
signed main(){
       ios::sync_with_stdio(false);
       cin.tie(nullptr);
       int t;cin>>t;
       while(t--) solve();
       return 0;
}
/*1 3 5 2 4
 # 2 # 2 # -3 # 2 #
 1 2 2 2 1  4 1 2 1 
 0 1 1 1 0  2 0 1 0 
*/

2.求长回文子串长度

P3805 【模板】manacher

const int N=1.1e7+5;
char s[N<<1];//修改串
int d[N<<1];//回文半径函数
int getstr(string str){//返回修改串后的长度
   int k=0;
   s[0]='@',s[++k]='#';
   for(auto u:str){
       s[++k]=u;
       s[++k]='#';
   }
   s[k+1]='$';
   return k;
}
void manacher(int n){
   d[1]=1;
   for(int i=2,l,r=1;i<=n;i++){
       if(i<=r) d[i]=min(d[r-i+l],r-i+1);
       while(s[i-d[i]]==s[i+d[i]]) d[i]++;
       if(i+d[i]-1>r) l=i-d[i]+1,r=i+d[i]-1;
   }
}
signed main(){
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   string str;
   cin>>str;
   int len=getstr(str);
   manacher(len);
   int ans=0;
   rep(i,1,len) ans=max(ans,d[i]-1);
   cout<<ans;
   return 0;
}

3.最长双回文子串

const int N=1e5+5;
char s[N<<1];//修改串
int d[N<<1];//回文半径函数
int getstr(string str){//返回修改串后的长度
      int k=0;
      s[0]='@',s[++k]='#';
      for(auto u:str){
          s[++k]=u;
          s[++k]='#';
      }
      s[k+1]='$';
      return k;
}
void manacher(int n){
      d[1]=1;
      for(int i=2,l=1,r=1;i<=n;i++){
          if(i<=r) d[i]=min(d[r-i+l],r-i+1);
          while(s[i-d[i]]==s[i+d[i]]) d[i]++;
          if(i+d[i]-1>r) l=i-d[i]+1,r=i+d[i]-1;
      }
}
int pre[N<<1],suf[N<<1];
signed main(){
       ios::sync_with_stdio(false);
       cin.tie(nullptr);
       string ss;
       cin>>ss;
       int len=getstr(ss);
       manacher(len);
       rep(i,2,len) pre[i+d[i]-1]=max(pre[i+d[i]-1],d[i]-1);
       for(int i=len;i>=3;i-=2) pre[i-2]=max(pre[i-2],pre[i]-2);
       per(i,len-1,1) suf[i-d[i]+1]=max(suf[i-d[i]+1],d[i]-1);
       for(int i=1;i<=len-4;i+=2) suf[i+2]=max(suf[i+2],suf[i]-2);
       int ans=0;
       for(int i=3;i<=len-2;i+=2){
           ans=max(ans,pre[i]+suf[i]);
       }
       cout<<ans;
       return 0;
}

4.前k长回文字串长度乘积

[P1659 国家集训队] 拉拉队排练 - 洛谷

const int mod=19930726;
const int N=1e6+5;
int n,k;
int ksm(int a,int b,int c){
       int ans=1;
       while(b){
          if(b&1) ans=(ans*a)%c;
          b>>=1;
          a=(a*a)%c;
       }
       return ans;
}
string s;
int d[N];//回文半径函数
void manacher(int n){
      d[1]=1;
      for(int i=2,l=1,r=1;i<=n;i++){
          if(i<=r) d[i]=min(d[r-i+l],r-i+1);
          while(s[i-d[i]]==s[i+d[i]]) d[i]++;
          if(i+d[i]-1>r) l=i-d[i]+1,r=i+d[i]-1;
     }
}
int cnt[N];
   signed main(){
       ios::sync_with_stdio(false);
       cin.tie(nullptr);
       cin>>n>>k;
       cin>>s;
       s=" "+s;
       int sum=0;
       int ans=1;
       manacher(n);
       int up=0;
       rep(i,1,n){
           cnt[d[i]*2-1]++;
           up=max(up,d[i]*2-1);
       }
       for(int i=up;i>=1;i-=2){
           sum+=cnt[i];
           if(sum>=k){
               ans=ans*ksm(i,k,mod)%mod;
               k-=sum;
               break;
           }else{
               ans=ans*ksm(i,sum,mod)%mod;
               k-=sum;
           }
       }
       if(k>0) cout<<-1;
       else cout<<ans;
       return 0;
}

kmp

const int N=1e6+5;
int nxt[N];//模式串P[1,i]中最长相等前后缀的长度
int ls,lp;//ls:S的长度,lp:P的长度
string S,P;
void kmp(){
   cin>>S>>P;
   ls=S.size(),lp=P.size();
   S=" "+S,P=" "+P;
   nxt[1]=0;
   for(int i=2,j=0;i<=lp;i++){
       while(j&&P[i]!=P[j+1]) j=nxt[j];
       if(P[i]==P[j+1]) j++;
       nxt[i]=j;
   }
   for(int i=1,j=0;i<=ls;i++){
       while(j&&S[i]!=P[j+1]) j=nxt[j];
       if(S[i]==P[j+1]) j++;
       if(j==lp) cout<<i-lp+1<<endl;
       //按从小到大的顺序输出P在S中出现的位置
   }
   for(int i=1;i<=lp;i++) cout<<nxt[i]<<" ";
}
signed main(){
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   kmp();
   return 0;
}

1.最短循环节问题（洛谷P4391)

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
string s;
int nxt[N];
signed main(){
   ios::sync_with_stdio(false);
   cin.tie(0);
   int ls;
   cin>>ls;
   cin>>s;
   s=" "+s;
   nxt[1]=0;
   for(int i=2,j=0;i<=ls;i++){
       while(j&&s[i]!=s[j+1]) j=nxt[j];
       if(s[i]==s[j+1]) j++;
       nxt[i]=j;
   }
   cout<<ls-nxt[ls];
}

2.在S中不断删除P（洛谷P4824）

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f3f3f3f3f
#define rep(i,j,k) for (int i=j;i<=k;++i)
#define per(i,j,k) for (int i=j;i>=k;--i)
//#define mid (l+r>>1)
//#define ls x<<1
//#define rs x<<1|1
#define fi first
#define se second
//int up=*max_element(a+1,a+n+1);
const double eps=1e-6;
const int mod=1e9+7;
const double PI=acos(-1);
const int N=1e6+5;
int nxt[N];//模式串P[1,i]中最长相等前后缀的长度
int ls,lp;//ls:S的长度,lp:P的长度
int st[N],top=0;//栈，维护删除后的答案
int f[N];//f[i]:i能匹配到的最大p[j]位置的j
string S,P;
void kmp(){
    cin>>S>>P;
    ls=S.size(),lp=P.size();
    S=" "+S,P=" "+P;
    nxt[1]=0;
    for(int i=2,j=0;i<=lp;i++){
        while(j&&P[i]!=P[j+1]) j=nxt[j];
        if(P[i]==P[j+1]) j++;
        nxt[i]=j;
    }
    for(int i=1,j=0;i<=ls;i++){
        while(j&&S[i]!=P[j+1]) j=nxt[j];
        if(S[i]==P[j+1]) j++;
        f[i]=j;//记录i对应的j值
        st[++top]=i;//入栈
        if(j==lp){//匹配成功
            top-=lp;//栈里弹出元素
            j=f[st[top]];//更新j值
        }
    }
    for(int i=1;i<=top;i++) cout<<S[st[i]];
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    kmp();
    return 0;
}

25.5.20

随机数种子

mt19937_64 rg(random_device{}());

用法：

using ull=unsigned long long;
ull tmp=rg();

也可以用int来存

春联10.1009（最长区间乘积为平方数）

图片上传失败，请重新上传

法1：（随机映射 + 前缀异或）

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f3f3f3f3f
#define rep(i,j,k) for (int i=j;i<=k;++i)
#define per(i,j,k) for (int i=j;i>=k;--i)
#define fi first
#define se second
#define int long long
#define endl '\n'
const int M=1e6+5;
const int N=1e5+5;
using ull=unsigned long long;
mt19937_64 rg(random_device{}());
int n,m;
bitset<M> vis;
ull v[M];
pair<ull,int> a[N];
void solve(){
  cin>>n;
  int tmp,qzj=0;
  a[0]={0,0};
  rep(i,1,n){
  	cin>>tmp,qzj^=v[tmp];
  	a[i]={qzj,i};
  }
  sort(a,a+n+1);
  int ans_l=-2,ans_r=-1,l,r;
  for(l=0;l<=n;l=r+1){
  	for(r=l;r<n&&a[r+1].fi==a[l].fi;r++);
  	int p=a[l].se,q=a[r].se;
  	if(q-p>ans_r-ans_l) ans_l=p,ans_r=q;
  	else if(q-p==ans_r-ans_l&&(p<ans_l||ans_l<0)) ans_l=p,ans_r=q;
  }
  cout<<ans_l+1<<" "<<ans_r<<endl;
}
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  for(int i=2;i<M;i++)
  	if(!vis[i]){
  		v[i]=rg();
  		for(int j=i+i;j<M;j+=i){
  			v[j]=v[j/i]^v[i];
  			vis[j]=1;//标记合数
  		}
  	}
  int t;cin>>t;
  while(t--) solve();
  return 0;
}

预处理：O (M log log M)，其中 M 为筛法上限（1e6）。
单次查询：O (N log N)，主要来自排序操作。
总复杂度：O (M log log M + T・N log N)，适用于多组数据。

25.5.21

容斥原理

1.集合的并

![cc9b54b5e2425b23c02f2ed0373e4667](../Tencent Files/1832539553/nt_qq/nt_data/Pic/2025-05/Ori/cc9b54b5e2425b23c02f2ed0373e4667.png)

2.集合的交

![2bcaef5cedc2b5b5e45c8a4dff7d5897](../Tencent Files/1832539553/nt_qq/nt_data/Pic/2025-05/Ori/2bcaef5cedc2b5b5e45c8a4dff7d5897.png)

![0b67aacacf92c66517806b9a760ac070](../Tencent Files/1832539553/nt_qq/nt_data/Pic/2025-05/Ori/0b67aacacf92c66517806b9a760ac070.png)

25.5.22

拉格朗日插值公式

![d4c2d12c27e475bafa6e67adc04c194d](../Tencent Files/1832539553/nt_qq/nt_data/Pic/2025-05/Ori/d4c2d12c27e475bafa6e67adc04c194d.png)

const int mod=998244353;
const int N=2e3+5;
int ksm(int a,int b,int c){
  int ans=1;
  while(b){
     if(b&1) ans=(ans*a)%c;
     b>>=1;a=(a*a)%c;}
  return ans;
}
int n,k,ans=0;
int x[N],y[N];
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin>>n>>k;
  rep(i,1,n) cin>>x[i]>>y[i];
  rep(i,1,n){
  	int fz=y[i],fm=1;
  	rep(j,1,n){
  		if(i==j) continue;
  		fz=fz*(k-x[j]+mod)%mod;
  		fm=fm*(x[i]-x[j]+mod)%mod;
  	}
  	ans=(ans+(fz*ksm(fm,mod-2,mod))%mod)%mod;
  }
  cout<<ans<<endl;
  return 0;
}

25.5.25

（vp）重庆cpc13届

L.栈与重复

问题难点在于如何处理repeat操作：

1.repeat后sum<<1;

2.repeat后数组内元素复制一遍放入栈中。（操作会影响后续pop的操作）

考虑到N=2e5,即至多pop操作2e5次，则当栈的容量大于2e5后就不需要再进行复制操作了。

时间复杂度:O(m+2e5)
const int N=2e5+5;
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;cin>>n;
  vector<int> sta;
  string tmp;
  int num,sum=0;
  rep(i,1,n){
  	cin>>tmp;
  	if(tmp=="Push"){
  		cin>>num;
  		sta.push_back(num);
  		sum=(sum+num)%mod;
  		cout<<sum<<endl;
  	}else if(tmp=="Pop"){
  		sum=(sum-sta.back()+mod)%mod;
  		sta.pop_back();
  		cout<<sum<<endl;
  	}else{
  		sum=(sum<<1)%mod;
  		if(sta.size()<N){
  			//N=2e5;tot=1+2+4+...+2e5=2*N
  			int len=sta.size();
  			for(int i=0;i<len;i++) sta.push_back(sta[i]);
  		}
  		cout<<sum<<endl;
  	}
  }
  return 0;
}

H.连接

拓扑问题.

考虑从左边往右边对下面的各个数进行配对连线，若该点上方对应点没有贴着边界，则可以绕着已处理过的部分的右侧，未处理过的部分的左侧进行连线，而后的其他操作可以从这条线的右边和上方进行操作，

即对于没有贴边的点的操作对未处理过的部分没有任何影响。

只需判断贴边的点是否会出现数据二的交错连线情况
const int N=2e5+5;
int n,a[N],b[N],c[N],sav[N],tmp;
void solve(){
  cin>>n;
  rep(i,1,n){//上面
  	cin>>tmp;
  	b[tmp]=i;
  }
  rep(i,1,n) cin>>a[i];//下面
  rep(i,1,n) cin>>c[i];
  rep(i,1,n) sav[i]=b[a[i]];
  int mpos=0;
  rep(i,1,n){
  	if(c[sav[i]]==1){
  		if(mpos>sav[i]){
  			cout<<"No"<<endl;
  			return;
  		}
  		else mpos=sav[i];
  	}
  }
  cout<<"Yes"<<endl;
}

C.区域划分

构造题，为了使着色数最大，且相邻的不同区域的格子颜色不同(显然答案上界为n)

那么使每一个区域的格子都与其余区域的格子相邻，那么着色数最大为 n*n
const int N=1e3+5;
int n,m,a[N][N];
void solve(){
  cin>>n;
  rep(i,1,n){
  	int p=1;
  	rep(k,1,i){
  		int num=k;
  		while(num<=n){
  			a[i][p]=num;
  			num+=i;
  			p++;
  		}
  	}
  }
  rep(i,1,n){
  	rep(j,1,n) cout<<a[i][j]<<" ";
  	cout<<endl;
  }
}
构造一个如图的

B.列车

图片上传失败，请重新上传

map<int,int> mp;
void solve(){
  mp.clear();
  int l,r,c;
  cin>>n>>m;
  bool f1=false,f2=false;
  rep(i,1,m){
  	cin>>l>>r>>c;
  	mp[l]+=c;
  	mp[r]-=c;
  	if(l==1) f1=true;
  	if(r==n) f2=true;
  }
  if(!(f1&&f2)){cout<<0<<endl;return;}
  int ans=INF,cur=0;
  for(auto [pos,delt]:mp){
  	if(pos!=n){
  		cur+=delt;
  		ans=min(cur,ans);
  	}
  }
  cout<<ans<<endl;
}

ACM·大一下学习笔记

ACM·大一下学习笔记

25.2.22

线段树1模板

线段树2模板

线段树用于维护满足结合律的区间信息

25.2.23

P1198 [JSOI2008] 最大数

ST表（倒置）

线段树

25.2.24

(线段树)区间最大子段和 [P4513 小白逛公园]

注意push的传参方式！！！

如果没加上&的话只传递了值(副本)，而没做到修改原变量。加上&传递地址。

想要将函数的返回值作为参数需要加上const

本题两个难点：

1.结构体变量中元素的设计 和 push函数的书写规则

2.query函数中需要将查找的范围进行合并得到ans。

25.2.25/26

(线段树)区间最大公约数 [CH4302 Interval GCD]

线段树用于维护满足结合律的区间信息。

25.2.27

P1438 无聊的数列(线段树+差分)

题目描述

输入格式

输出格式

输入 #1

输出 #1

数据规模与约定

25.2.28

P4588 [TJOI2018] 数学计算(线段树操作省去求逆元操作)

P4588 [TJOI2018] 数学计算

输入格式

输出格式

输入 #1

输出 #1

P1253 扶苏的问题

P1253 扶苏的问题

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

数据规模与约定

提示

25.3.5

P1020 [NOIP 1999 提高组] 导弹拦截

题目描述

输入格式

输出格式

输入输出样例

输入 #1

输出 #1

说明/提示

25.3.12

P2824 [HEOI2016/TJOI2016] 排序（线段树+二分）

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

算是一道 ’线段树+二分‘ 的模板题了

有个很恶心的坑：

25.3.17（复习最短路）

P4779 【模板】单源最短路径（标准版）

dij

P1629 邮递员送信

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

最短路裸题，”单源起点多源终点+多源起点单源终点“。

1.结构体变量中元素的设计和 push函数的书写规则