文章目录
CSP-S/NOIP 实用模版
前言
我已经AFO了，留下这些东西，希望对后人有用。收录了NOIP大纲内的实用算法模版（也许会更新），提供找得到的洛谷模板题链接，算法中带有我个人特色的写法有注释。同时欢迎大家光顾我的洛谷主页。祝你们在OI的道路上一帆风顺！
杂项
快读快写
inline int read(){
char c;
int t=0,k=1;
c=getchar();
while(c<'0'||c>'9'){
if(c=='-') k=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
t=t*10+c-'0';
c=getchar();
}
return k*t;
}
inline void write(__int128 x){
if(x/10) write(x/10);
putchar((x%10)^48);
return ;
}
关闭同步流
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//关闭同步流后scanf、put系列等非cin、cout读写禁用，爆零后果自负
归并排序求逆序对
int ok[MAXN],c[MAXN];//c是待排数组
inline void msort(int l,int r){
int mid=(l+r)/2;
if(l==r) return ;
else{//二分
msort(l,mid);
msort(mid+1,r);
}//然后二分合并
int i=l;//第一段下标初值
int j=mid+1;//第二段下标初值
int t=l;//合并后的下标
while(i<=mid&&j<=r){
if(c[i]>c[j]){//逆序对出现
ans+= mid-i+1;//求逆序对
ans%=MOD;
ok[t++]=c[j];
j++;
}
else{
ok[t++]=c[i];
i++;
}
}
while(i<=mid){
ok[t++]=c[i];
i++;
}
while(j<=r){
ok[t++]=c[j];
j++;
}
for(int k=l;k<=r;k++) c[k]=ok[k];
return ;
}//O(nlogn)
动态规划
最长公共子序列
#include<bits/stdc++.h>//实质就是把a[i]替换成a[i]在b数组中的位置后，再求最长不下降子序列
using namespace std;
#define MAXN 100005
int n,a[MAXN],b[MAXN],pos[MAXN],dp[MAXN];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
dp[i]=0x3f3f3f3f;
}
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
pos[b[i]]=i;
}
int len=0;
dp[0]=0;
for(int i=1;i<=n;i++){
if(pos[a[i]]>dp[len]) dp[++len]=pos[a[i]];
else{
int t=lower_bound(dp+1,dp+len+1,pos[a[i]])-dp;
dp[t]=pos[a[i]];
}
}
cout<<len;
return 0;
}//O(nlogn)
背包
注:强烈推荐**《背包九讲》，此处除树上背包外模版的空间复杂度都优化到了一维**。
01背包
for(int i=1;i<=m;i++){//m件物品
for(int j=t;j>=ti[i];j--){//背包容量为t
dp[j]=max(dp[j],dp[j-ti[i]]+a[i]);//每件物品体积为ti[i],价值为a[i]
}
}//O(n*V)
完全背包
for(int i=1;i<=m;i++){//变量名同上
for(int j=ti[i];j<=t;j++){
dp[j]=max(dp[j],dp[j-ti[i]]+a[i]);
}
}//O(n*V)
多重背包
while(n--){//原本n种物品，每件占体积wei，价值val，每种s件
int wei,val,s;
cin>>wei>>val>>s;
int t=1;
while(t<=s){//二进制优化，方法不唯一
cnt++;
w[cnt]=wei*t;
va[cnt]=val*t;
s-=t;
t*=2;
}
if(s>0){
cnt++;
w[cnt]=wei*s;
va[cnt]=val*s;
}
}
for(int i=1;i<=cnt;i++){//拆完后cnt件物品
for(int j=m;j>=w[i];j--){//跑01背包
dp[j]=max(dp[j],dp[j-w[i]]+va[i]);
}
}
树上背包(包含另外两种背包)
注:这边涵盖了有依赖的背包、分组背包、泛化物品
#include<bits/stdc++.h>
using namespace std;
#define ll long long//十年OI一场空，不开long long 见祖宗
const int N=305;
int n,m,wei[N],u;
vector<int> e[N];//邻接表存图
int dp[N][N];
void dfs(int x){//这边因为入度为0的点不唯一，我就把0节点作为父节点
vector<int> cost[N],val[N];
int cnt=0;
for(int i:e[x]){
dfs(i);
bool can=false;
for(int j=1;j<=m;j++){
if(dp[i][j]>0){
if(!can){
cnt++;
can=true;
}
cost[cnt].push_back(j);//泛化物品（背包套背包）
val[cnt].push_back(dp[i][j]);
}
else break;
}
}
if(x!=0){
//分组背包的循环顺序（由外到内） 组的编号 容量 组内物品
dp[x][0]=0;
dp[x][1]=wei[x];
for(int zsq=1;zsq<=cnt;zsq++){
for(int j=m;j>=1;j--){
for(int i=0;i<cost[zsq].size();i++){
if(j-cost[zsq][i]>=1){
dp[x][j]=max(dp[x][j],dp[x][j-cost[zsq][i]]+val[zsq][i]);
}
}
}
}
}
else{
dp[0][0]=0;
for(int zsq=1;zsq<=cnt;zsq++){
for(int j=m;j>=1;j--){
for(int i=0;i<cost[zsq].size();i++){
if(j-cost[zsq][i]>=0){
dp[x][j]=max(dp[x][j],dp[x][j-cost[zsq][i]]+val[zsq][i]);
}
}
}
}
}
return ;
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
memset(dp,0xcf,sizeof(dp));
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>u>>wei[i];
e[u].push_back(i);
}
dfs(0);
cout<<dp[0][m]<<"\n";
return 0;
}
数学
注：纯数论的模版近几年考得少，因此数学模版不全部展示。
欧拉筛&欧拉函数
int phi[40005],pri[40005],cnt;//phi存欧拉函数的值，pri存筛出来的质数
bool vis[40005];
inline void euler(int top){//top是所筛的范围的上限
phi[1]=1;
for(int i=2;i<=top;i++){
if(!vis[i]){
pri[++cnt]=i;
phi[i]=i-1;
}
for(int j=1;j<=cnt&&pri[j]*i<=top;j++){
vis[i*pri[j]]=true;
if(i%pri[j]==0){
phi[i*pri[j]]=phi[i]*pri[j];
break;
}
else phi[i*pri[j]]=phi[i]*phi[pri[j]];
}
}
}//O(n)
数据结构
ST表
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005];
int dp[100005][21];
void st_stable(){
for(int i=1;i<=n;i++) dp[i][0]=a[i];
for(int k=1;k<=21;k++){
for(int i=1;i+(1<<k)-1<=n;i++) dp[i][k]=max(dp[i][k-1],dp[i+(1<<(k-1))][k-1]);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
st_stable();
while(m--){
int l,r;
scanf("%d%d",&l,&r);
int s=(int)log2(r-l+1);
printf("%d\n",max(dp[l][s],dp[r-(1<<s)+1][s]));
}
return 0;
}
树状数组
区间修改单点查询版
#include<bits/stdc++.h>
using namespace std;
int n,m,c[500005];
int lowbit(int x){
return x&(-x);
}
void update(int pos,int num){
c[pos]+=num;
while(pos+lowbit(pos)<=n){
pos+=lowbit(pos);
c[pos]+=num;
}
return ;
}
int sum(int pos){
int res=c[pos];
while(pos-lowbit(pos)>=1){
pos-=lowbit(pos);
res+=pos[c];
}
return res;
}
int main(){
scanf("%d%d",&n,&m);
int a=0,b=0;
for(int i=1;i<=n;i++){
swap(a,b);
scanf("%d",&b);
update(i,b-a);
}
while(m--){
int type;
scanf("%d",&type);
if(type==1){
int x,y,k;
scanf("%d%d%d",&x,&y,&k);
update(x,k);
update(y+1,-k);
}
else{
int id;
scanf("%d",&id);
printf("%lld\n",sum(id));
}
}
return 0;
}
区间修改区间查询版
注：可过洛谷线段树1，即链接题目。
#include<bits/stdc++.h>
using namespace std;
#define MAXN 400010
typedef long long ll;
int n,m;
ll d[MAXN];
__int128 di[MAXN];
ll lowbit(ll x){
return x&(-x);
}
void update(int pos,ll num){//用树状数组维护 差 和 差*i
d[pos]+=num;
ll v=pos*num;
di[pos]+=v;
while(pos+lowbit(pos)<=n){
pos+=lowbit(pos);
d[pos]+=num;
di[pos]+=v;
}
}
__int128 sum(int pos){
__int128 ans=0;//带入公式
for(int i=pos;i>=1;i-=lowbit(i)) ans+=(pos+1)*d[i]-di[i];
return ans;
}
inline void write(__int128 x){//快写
if(x/10) write(x/10);
putchar((x%10)^48);
return ;
}
int main(){
scanf("%d%d",&n,&m);
ll a=0,b=0;
for(int i=1;i<=n;i++){//反正存差分，只要上一个和这一个就行
swap(a,b);//使a的值成为当前输入的上一个的值
scanf("%lld",&b);
update(i,b-a);//更新差分
}
while(m--){
int type,l,r,k;
scanf("%d",&type);
if(type==1){
scanf("%d%d%d",&l,&r,&k);
update(l,k);//区间修改
update(r+1,-k);
}
else{
scanf("%d%d",&l,&r);
__int128 res= sum(r)-sum(l-1);//区间查询
if(res<0){//__int128 的输出
printf("-");
res*=-1;
}
write(res);
printf("\n");
}
}
return 0;
}
二维树状数组
int lowbit(int x){return x&(-x);}
inline void update(int i,int j,int num){//加
for(int l=i;l<=n;l+=lowbit(l)){
for(int p=j;p<=m;p+=lowbit(p)){
c[l][p]+=num;
}
}
return ;
}
inline int sum(int i,int j){//求和
int res=0;
for(int l=i;l>=1;l-=lowbit(l)){
for(int p=j;p>=1;p-=lowbit(p)){
res+=c[l][p];
}
}
return res;
}
线段树
区间乘法&加法
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
int n,q,m,a[MAXN];
struct node{
long long l,r,addtag,multag,sum;//有乘有加，先乘后加
}tree[4*MAXN];//add,mul不完全覆盖都是先pushdown，在看左右子树
inline void pushdown(int i){ //son.sum=son.sum*father.mul+father.add*son.length
tree[i<<1].sum=(tree[i].multag*tree[i<<1].sum+tree[i].addtag*(tree[i<<1].r-tree[i<<1].l+1))%m;
tree[i<<1|1].sum=(tree[i].multag*tree[i<<1|1].sum+tree[i].addtag*(tree[i<<1|1].r-tree[i<<1|1].l+1))%m;
tree[i<<1].multag=(tree[i].multag*tree[i<<1].multag)%m;//son.mul*=father.mul
tree[i<<1|1].multag=(tree[i].multag*tree[i<<1|1].multag)%m;
tree[i<<1].addtag=(tree[i].multag*tree[i<<1].addtag+tree[i].addtag)%m;//先乘后加
tree[i<<1|1].addtag=(tree[i].multag*tree[i<<1|1].addtag+tree[i].addtag)%m;
tree[i].addtag=0; tree[i].multag=1;
return ;
}
inline void build(int i,int l,int r){
tree[i].l=l;
tree[i].r=r;
tree[i].addtag=0;
tree[i].multag=1;
if(l==r){tree[i].sum=a[l]%m;return;}
int mid=(l+r)/2;
build(i*2,l,mid);
build(i*2+1,mid+1,r);
tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%m;
return ;
}
inline void add(int i,int l,int r,long long k){//区间加法
if(tree[i].l>=l&&tree[i].r<=r){
tree[i].addtag=(tree[i].addtag+k)%m;
tree[i].sum=(tree[i].sum+k*(tree[i].r-tree[i].l+1))%m;
return ;
}
pushdown(i);
if(tree[i<<1].r>=l) add(i*2,l,r,k);
if(tree[i<<1|1].l<=r) add(i*2+1,l,r,k);
tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%m;
}
inline void mul(int i,int l,int r,long long k){//区间乘法
if(tree[i].l>=l&&tree[i].r<=r){
tree[i].multag=(tree[i].multag*k)%m;
tree[i].addtag=(tree[i].addtag*k)%m;
tree[i].sum=(tree[i].sum*k)%m;
return ;
}
pushdown(i);
if(tree[i<<1].r>=l) mul(i*2,l,r,k);
if(tree[i<<1|1].l<=r) mul(i*2+1,l,r,k);
tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%m;
}
inline long long search(int i,int l,int r){//区间求和
if(tree[i].l>=l&&tree[i].r<=r) return tree[i].sum;
pushdown(i);
long long ans=0;
if(tree[i<<1].r>=l) ans=(ans+search(i*2,l,r))%m;
if(tree[i<<1|1].l<=r) ans=(ans+search(i*2+1,l,r))%m;
return ans;
}
根号线段树
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define completecan t[i].l>=l&&t[i].r<=r&&( (t[i].minn-(long long)sqrt(t[i].minn) )==( t[i].maxn-(long long)sqrt(t[i].maxn) ))
#define complete t[i].l>=l&&t[i].r<=r
#define lr i<<1
#define rr i<<1|1
long long n,m,a[MAXN];
struct node{
int l,r;
long long maxn,minn,sum,substruction;
}t[MAXN*4];
inline void up(int i){
t[i].sum=t[lr].sum+t[rr].sum;
t[i].minn=min(t[lr].minn,t[rr].minn);
t[i].maxn=max(t[lr].maxn,t[rr].maxn);
}
inline void build(int i,int l,int r){
t[i].l=l;
t[i].r=r;
t[i].substruction=0;
if(r==l){
t[i].sum=t[i].minn=t[i].maxn=a[l];
return ;
}
int mid=(l+r)/2;
build(lr,l,mid);
build(rr,mid+1,r);
up(i);
}
inline void pushdown(int i){
if(t[i].substruction!=0){
t[lr].sum-=(t[lr].r-t[lr].l+1)*t[i].substruction;
t[rr].sum-=(t[rr].r-t[rr].l+1)*t[i].substruction;
t[lr].substruction+=t[i].substruction;
t[rr].substruction+=t[i].substruction;
t[lr].minn-=t[i].substruction;
t[lr].maxn-=t[i].substruction;
t[rr].minn-=t[i].substruction;
t[rr].maxn-=t[i].substruction;
t[i].substruction=0;
}
return ;
}
inline void sqrt_tree(int i,int l,int r){//区间开平方
if(completecan){
long long temp=t[i].minn-(long long)sqrt(t[i].minn);
t[i].substruction+=temp;
t[i].sum-=temp*(t[i].r-t[i].l+1);
t[i].maxn-=temp;
t[i].minn-=temp;
return ;
}
pushdown(i);
if(t[lr].r>=l) sqrt_tree(lr,l,r);
if(t[rr].l<=r) sqrt_tree(rr,l,r);
up(i);
return ;
}
inline long long search(int i,int l,int r){//区间求和
if(complete) return t[i].sum;
pushdown(i);
long long s=0;
if(t[lr].r>=l) s+=search(lr,l,r);
if(t[rr].l<=r) s+=search(rr,l,r);
return s;
}
int main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
build(1,1,n);
scanf("%lld",&m);
while(m--){
int k,l,r;
scanf("%d%d%d",&k,&l,&r);
if(l>r) swap(l,r);
if(k==1) printf("%lld\n",search(1,l,r));
else sqrt_tree(1,l,r);
}
return 0;
}
动态开点线段树
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls tr[i].lr
#define rs tr[i].rr
#define getmid int mid=(t_l+t_r)>>1;
const int N=8e6+5;
const int M=1e5+5;
int cnt,n,m,lim,towl[M],towr[M],w[M],pos;
ll blood;
struct node{
int lr,rr;
ll sum,tag;
}tr[N];
inline void pushdown(int i,int t_l,int t_r){
if(tr[i].lr==0){
cnt++;
ls=cnt;
tr[cnt].sum=0;
tr[cnt].tag=0;
tr[cnt].lr=tr[cnt].rr=0;
cnt++;
rs=cnt;
tr[cnt].sum=0;
tr[cnt].tag=0;
tr[cnt].lr=tr[cnt].rr=0;
}
getmid
tr[ls].sum+=(ll)(mid-t_l+1)*tr[i].tag;
tr[ls].tag+=tr[i].tag;
tr[rs].sum+=(ll)(t_r-mid)*tr[i].tag;
tr[rs].tag+=tr[i].tag;
tr[i].tag=0;
return ;
}
inline void add(int i,int t_l,int t_r,int l,int r,int num){//区间加法
if(t_l>=l&&t_r<=r){
tr[i].sum+=(ll)(t_r-t_l+1)*num;
tr[i].tag+=num;
return ;
}
pushdown(i,t_l,t_r);
getmid
if(mid>=l) add(ls,t_l,mid,l,r,num);
if(mid+1<=r) add(rs,mid+1,t_r,l,r,num);
tr[i].sum=tr[ls].sum+tr[rs].sum;
return;
}
inline ll sum(int i,int t_l,int t_r,int l,int r){//区间求和
if(t_l>=l&&t_r<=r) return tr[i].sum;
pushdown(i,t_l,t_r);
getmid
ll res=0;
if(mid>=l) res+=sum(tr[i].lr,t_l,mid,l,r);
if(mid+1<=r) res+=sum(rs,mid+1,t_r,l,r);
return res;
}
int main(){
cnt=1;//注意初始化！
tr[1].sum=0;
tr[1].tag=0;
tr[1].lr=tr[1].rr=0;
return 0;
}
树上问题
树的直径
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,u,v,ans,d[N];
vector<int> e[N];
inline void dfs(int pos,int fa){
for(int i:e[pos]){
if(i==fa) continue;
dfs(i,pos);
ans=max(ans,d[pos]+d[i]+1);
d[pos]=max(d[pos],d[i]+1);
}
return ;
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
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);
cout<<ans<<endl;
return 0;
}
换根DP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,c[N],sumofc[N],u,v,dis[N];
vector<int> e[N];
void dfs(int x,int f){
sumofc[x]=c[x];
for(int i:e[x]){
if(i==f) continue;
dfs(i,x);
sumofc[x]+=sumofc[i];
dis[x]+=sumofc[i]+dis[i];
}
return ;
}
int ans;
void dp(int x,int f){
// 原来 x兄弟结点多走的 x结点少走的
if(f!=0) dis[x]=dis[f]+sumofc[1]-sumofc[x]-sumofc[x];
ans=min(ans,dis[x]);
for(int i:e[x]){
if(i==f) continue;
dp(i,x);
}
return ;
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
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<=n;i++) cin>>c[i];
dfs(1,0);
ans=LONG_LONG_MAX;
dp(1,0);
cout<<ans<<"\n";
return 0;
}
LCA
#include<bits/stdc++.h>
using namespace std;
const int N=500005;
int n,s,x,y,m,a,b,fa[N][35],depth[N];
vector<int> e[N];
void dfs(int pos,int f){
depth[pos]=depth[f]+1;
fa[pos][0]=f;
for(int i=1;i<=30;i++) fa[pos][i]=fa[fa[pos][i-1]][i-1];
for(int i:e[pos]){
if(i==f) continue;
dfs(i,pos);
}
return ;
}
int lca(int u,int v){
if(depth[u]<depth[v]) swap(u,v);
for(int i=30;i>=0;i--){
if(depth[fa[u][i]]>=depth[v]){
u=fa[u][i];
}
}
if(u==v) return u;
for(int i=30;i>=0;i--){
if(fa[u][i]!=fa[v][i]){
u=fa[u][i];
v=fa[v][i];
}
}
return fa[u][0];
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m>>s;
for(int i=1;i<n;i++){
cin>>x>>y;
e[x].push_back(y);
e[y].push_back(x);
}
dfs(s,0);
while(m--){
cin>>a>>b;
if(a==b) cout<<a<<"\n";
else cout<<lca(a,b)<<"\n";
}
return 0;
}
树上差分
点权
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e4+5;
int n,k,cf[N],u,v,fa[N][35],depth[N];
vector<int> e[N];
void dfs(int x,int f){
depth[x]=depth[f]+1;
fa[x][0]=f;
for(int i=1;i<=30;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i:e[x]){
if(i==f) continue;
dfs(i,x);
}
return ;
}
inline int lca(int a,int b){
if(depth[a]<depth[b]) swap(a,b);
for(int i=30;i>=0;i--){
if(depth[fa[a][i]]>=depth[b]){
a=fa[a][i];
}
}
if(a==b) return a;
for(int i=30;i>=0;i--){
if(fa[a][i]!=fa[b][i]){
a=fa[a][i];
b=fa[b][i];
}
}
return fa[a][0];
}
int ans=0;
int dfs2(int x,int f){
int tmp=0;
for(int i:e[x]){
if(i==f) continue;
tmp+=dfs2(i,x);
}
tmp+=cf[x];
ans=max(ans,tmp);
return tmp;
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<n;i++){
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1,0);
while(k--){
int t1,t2;
cin>>t1>>t2;
int LCA=lca(t1,t2);
cf[t1]++;
cf[t2]++;
cf[LCA]--;
cf[fa[LCA][0]]--;
}
dfs2(1,0);
cout<<ans<<"\n";
return 0;
}
边权
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,cnt[N],c1[N],c2[N],u,v,cf[N],depth[N],fa[N][35];
struct node{
int fr,to,next,id;
}e[N<<1];
int pre[N],k;
inline void add(int fr,int to,int id){
k++;
e[k].id=id;
e[k].fr=fr;
e[k].to=to;
e[k].next=pre[fr];
pre[fr]=k;
}
void dfs(int x,int f){
depth[x]=depth[f]+1;
fa[x][0]=f;
for(int i=1;i<=30;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=pre[x];i;i=e[i].next){
if(e[i].to==f) continue;
dfs(e[i].to,x);
}
return ;
}
inline int lca(int a,int b){
if(depth[a]<depth[b]) swap(a,b);
for(int i=30;i>=0;i--){
if(depth[fa[a][i]]>=depth[b]){
a=fa[a][i];
}
}
if(a==b) return a;
for(int i=30;i>=0;i--){
if(fa[a][i]!=fa[b][i]){
a=fa[a][i];
b=fa[b][i];
}
}
return fa[a][0];
}
int dfs2(int x,int f){
int tmp=0;
for(int i=pre[x];i;i=e[i].next){
if(e[i].to==f) continue;
int ttt=dfs2(e[i].to,x);
cnt[e[i].id]+=ttt;
tmp+=ttt;
}
return tmp+cf[x];
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n-1;i++){
cin>>u>>v>>c1[i]>>c2[i];
add(u,v,i);
add(v,u,i);
}
dfs(1,0);
for(int i=2;i<=n;i++){
int LCA=lca(i,i-1);
cf[i]++;
cf[i-1]++;
cf[LCA]-=2;
}
dfs2(1,0);
int ans=0;
for(int i=1;i<n;i++){
ans+=min(cnt[i]*c1[i],c2[i]);
}
cout<<ans<<"\n";
return 0;
}
Kruskal
Kruskal最小生成树
#include<bits/stdc++.h>
using namespace std;
int n,m,father[5005];
long long ans;
int cnt;
struct node{
int a,b,w;
} edge[200005];
bool cmp(node t1,node t2){
return t1.w<t2.w;
}
int f(int x){
if(father[x]==x) return x;
father[x]=f(father[x]);
return father[x];
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) father[i]=i;
for(int i=1;i<=m;i++) cin>>edge[i].a>>edge[i].b>>edge[i].w;
sort(edge+1,edge+1+m,cmp);
bool can=false;
for(int i=1;i<=m;i++){
int fa=f(edge[i].a);
int fb=f(edge[i].b);
if(fa!=fb){
father[fa]=fb;
ans+=edge[i].w;
cnt++;
if(cnt>=n-1){
can=true;
break;
}
}
}
if(can) cout<<ans;
else cout<<"orz";
return 0;
}
Kruskal重构树
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
const int M=3e5+5;
bool vis[N<<1];
int n,m,fa[N<<1],wei[N<<1],tot,cnt;
vector<int> ed[N<<1];
struct node{
int fr,to,wei;
}e[M];
bool operator < (node t1,node t2){
return t1.wei<t2.wei;
}
inline int f(int x){
if(fa[x]==x) return x;
fa[x]=f(fa[x]);
return fa[x];
}
int ffa[N<<1][30],depth[N<<1];
void dfs(int u,int f_a){
vis[u]=true;
depth[u]=depth[f_a]+1;
ffa[u][0]=f_a;
for(int i=1;i<=29;i++) ffa[u][i]=ffa[ffa[u][i-1]][i-1];
for(int i:ed[u]) dfs(i,u);
}
int lca(int u,int v){
if(depth[u]<depth[v]) swap(u,v);
for(int i=29;i>=0;i--){
if(depth[ffa[u][i]]>=depth[v]){
u=ffa[u][i];
}
}
if(u==v) return v;
for(int i=29;i>=0;i--){
if(ffa[u][i]!=ffa[v][i]){
u=ffa[u][i];
v=ffa[v][i];
}
}
return ffa[u][0];
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>e[i].fr>>e[i].to>>e[i].wei;
tot=n;
for(int i=1;i<=n+n;i++) fa[i]=i;
sort(e+1,e+1+m);
for(int i=1;i<=m;i++){
int f_a=f(e[i].fr);
int f_b=f(e[i].to);
if(f_a==f_b) continue;
tot++;
wei[tot]=e[i].wei;
fa[f_a]=tot;
fa[f_b]=tot;
ed[tot].push_back(f_a);
ed[tot].push_back(f_b);
cnt++;
if(cnt>=n-1) break;
}
for(int i=tot;i>=1;i--){
if(vis[i]) continue;
dfs(i,0);
}
int q;
cin>>q;
while(q--){
int a,b;
cin>>a>>b;
if(f(a)!=f(b)) cout<<"impossible\n";
else cout<<wei[lca(a,b)]<<"\n";
}
return 0;
}
图论
单源最短路
Dijkstra
typedef pair<int,int> PII ;
int n,m,s;
int dis[100005];
bool vis[100005];
struct node{
int from,to,value,next;
} edge[500005];
int pre[500005],k;
void add(int fr,int d,int va){//采用链式前向星存图
k++;
edge[k].from=fr;
edge[k].to=d;
edge[k].value=va;
edge[k].next=pre[fr];
pre[fr]=k;
}
void diji(){
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
priority_queue< PII,vector<PII>,greater<PII> > q;
q.push({0,s});
while(q.size()){
int distance=q.top().first;
int pos=q.top().second;
q.pop();
if(vis[pos]==true) continue;
vis[pos]=true;
for(int i=pre[pos];i!=0;i=edge[i].next){
if(distance+edge[i].value<dis[edge[i].to]){
dis[edge[i].to]=distance+edge[i].value;
q.push({distance+edge[i].value,edge[i].to});
}
}
}
}
spfa
int dis[100005];
bool vis[100005];
void spfa(){
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
vis[s]=true;
queue<int> q;
q.push(s);
while(!q.empty()){
int head=q.front();
for(int i=pre[head];i!=0;i=edge[i].next){//链式前向星存的图
if(edge[i].value+dis[head]<dis[edge[i].to]){
dis[edge[i].to]=edge[i].value+dis[head];
if(!vis[edge[i].to]){
vis[edge[i].to]=true;
q.push(edge[i].to);
}
}
}
vis[head]=false;
q.pop();
}
}
全源最短路
Floyd
int n,m,g[105][105];
int main(){
memset(g,0x3f,sizeof(g));
cin>>n>>m;
for(int i=1;i<=n;i++) g[i][i]=0;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;//无向图双向建边
g[u][v]=min(g[u][v],w);
g[v][u]=min(g[v][u],w);
}
for(int k=1;k<=n;k++){//中转点一定在最外层
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<g[i][j]<<' ';
}
cout<<endl;
}
return 0;
}
Johnson
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int N=3e4+5;
const int M=6e4+5;
int n,m,u,v,w;
struct node{
int fr,to,next,wei;
}e[M<<1];
int k,pre[M<<1];
inline void add(int fr,int to ,int va){
k++;
e[k].fr=fr;
e[k].to=to;
e[k].wei=va;
e[k].next=pre[fr];
pre[fr]=k;
return ;
}
bool vis[N];
ll h[N],dis[N];
int cnt[N];
inline void spfa(){
for(int i=0;i<=n;i++) h[i]=1e12;
queue<int> q;
q.push(0);
h[0]=0;
vis[0]=true;
while(!q.empty()){
int head=q.front();
q.pop();
vis[head]=false;
for(int i=pre[head];i!=0;i=e[i].next){
if(e[i].wei+h[head]<h[e[i].to]){
h[e[i].to]=e[i].wei+h[head];
cnt[e[i].to]=cnt[head]+1;
if(cnt[e[i].to]>n){
puts("-1\n");
exit(0);
}
if(!vis[e[i].to]){
q.push(e[i].to);
vis[e[i].to]=true;
}
}
}
}
}
inline void diji(int s){
priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int>> > q;
memset(vis,0,sizeof(vis));
for(int i=0;i<=n;i++) dis[i]=1e12;
dis[s]=0;
q.push({0,s});
while(!q.empty()){
int head=q.top().second,di=q.top().first;
q.pop();
if(vis[head]) continue;
vis[head]=true;
for(int i=pre[head];i!=0;i=e[i].next){
if(di+e[i].wei<dis[e[i].to]){
dis[e[i].to]=di+e[i].wei;
q.push({dis[e[i].to],e[i].to});
}
}
}
}
signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
add(u,v,w);
}
for(int i=1;i<=n;i++) add(0,i,0);
spfa();
for(int i=1;i<=k;i++){
if(e[i].fr==0) continue;
e[i].wei+=h[e[i].fr]-h[e[i].to];
}
for(int i=1;i<=n;i++){
diji(i);
ll ans=0;
for(int j=1;j<=n;j++){
if(dis[j]>=1e12) ans+=(ll)j*1000000000;
else if(i==j) continue;
else ans+=(ll)j*(dis[j]+h[j]-h[i]);
}
cout<<ans<<endl;
}
return 0;
}
Kahn拓扑排序
#include<bits/stdc++.h>
using namespace std;
int n,din[101];//din存入度
vector<int> family[101],tp;
bool kahn(){
queue<int> q;
for(int i=1;i<=n;i++){
if(din[i]==0) q.push(i);
}
while(!q.empty()){
int head=q.front();
q.pop();
tp.push_back(head);
for(auto i:family[head]){
if(--din[i]==0) q.push(i);
}
}
return (tp.size()==n)? true : false ;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int a;
while(cin>>a){
if(a==0) break;
family[i].push_back(a);
din[a]++;
}
}
if(!kahn()) puts("-1");
else{
for(auto i:tp) printf("%d ",i);
}
return 0;
}
Tarjan
割边
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m;
int pre[N],k;
struct node{
int from,to,next,di;
}edge[N];
void add(int fr,int d,int dif){
k++;
edge[k].from=fr;
edge[k].to=d;
edge[k].di=dif;
edge[k].next=pre[fr];
pre[fr]=k;
}
set<pair<int,int> > s;
int dfn[N],low[N],num;
void tarjan(int id,int differ){
dfn[id]=low[id]=++num;
for(int i=pre[id];i!=0;i=edge[i].next){
if(edge[i].di==differ) continue ;//双向建边需要防止走回头路，我没有通过下标按位异或的方式，而是给每条边打上标记，标记为输入顺序
int y=edge[i].to;
if(dfn[y]==0){
tarjan(y,edge[i].di);
low[id]=min(low[id],low[y]);
if(low[y]>dfn[id]){
s.insert({min(id,y),max(id,y)}); //set去重+排序一步到位
}
}
else low[id]=min(low[id],dfn[y]);
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
add(u,v,i);
add(v,u,i);
}
tarjan(1,-1);
for(auto i:s) cout<<i.first<<' '<<i.second<<endl;
return 0;
}
割点
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
struct node{
int from,to,next,dif;
}e[N*2];
int pre[N*2],k;
inline void add(int fr,int d,int dif){
k++;
e[k].from=fr;
e[k].to=d;
e[k].dif=dif;
e[k].next=pre[fr];
pre[fr]=k;
}
int num,dfn[N],low[N],root;
set<int> s;
inline void tarjan(int x,int dif){
dfn[x]=low[x]=++num;
int flag=0;
for(int i=pre[x];i!=0;i=e[i].next){
if(e[i].dif==dif) continue;//双向建边需要防止走回头路，我没有通过下标按位异或的方式，而是给每条边打上标记，标记为输入顺序
int y=e[i].to;
if(!dfn[y]){
tarjan(y,e[i].dif);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]){
flag++;
if(x!=root||flag>1) s.insert(x);//我爱set
}
}
else low[x]=min(low[x],dfn[y]);
}
return ;
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
add(u,v,i);
add(v,u,i);
}
for(int i=1;i<=n;i++){
if(dfn[i]!=0) continue;
root=i;
tarjan(i,-1);
}
cout<<s.size()<<endl;
for(int i:s) cout<<i<<' ';
return 0;
}
边双连通分量
#include<bits/stdc++.h>
using namespace std;
#define MAXN 500005
#define M 2000005
int n,m;
struct node{
int from,to,next,difference;
}e[M*2];
int k,pre[M*2];
void add(int fr,int d,int dif){
k++;
e[k].difference=dif;
e[k].from=fr;
e[k].to=d;
e[k].next=pre[fr];
pre[fr]=k;
}
int dfn[MAXN],low[MAXN],num;
bool can[M*2];
void tarjan(int x,int di){
dfn[x]=low[x]=++num;
for(int i=pre[x];i!=0;i=e[i].next){
if(e[i].difference==di) continue;//双向建边需要防止走回头路，我没有通过下标按位异或的方式，而是给每条边打上标记，标记为输入顺序
int y=e[i].to;
if(!dfn[y]){
tarjan(y,e[i].difference);
low[x]=min(low[x],low[y]);
if(low[y]>dfn[x]) can[e[i].difference]=true;
}
else low[x]=min(low[x],dfn[y]);
}
return ;
}
bool vis[MAXN];
int ans=0,len[MAXN];
vector<int> a;
void dfs(int pos){
if(vis[pos]) return ;
vis[pos]=true;
len[ans]++;
a.push_back(pos);
for(int i=pre[pos];i!=0;i=e[i].next){
if(can[e[i].difference]||vis[e[i].to]) continue;
dfs(e[i].to);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v,i);
add(v,u,i);
}
for(int i=1;i<=n;i++){
if(dfn[i]!=0) continue;
tarjan(i,-1);
}
for(int i=1;i<=n;i++){
if(vis[i]) continue;
else{
ans++;
dfs(i);
}
}
printf("%d\n",ans);
int now=-1;
for(int i=1;i<=ans;i++){
printf("%d ",len[i]);
while(len[i]--){
now++;
printf("%d ",a[now]);
}
printf("\n");
}
return 0;
}
点双连通分量
#include<bits/stdc++.h>
using namespace std;
#define MAXN 500005
#define M 2000005
int n,m;
struct node{
int from,to,next,difference;
}e[M*2];
int k,pre[M*2];
void add(int fr,int d,int dif){
k++;
e[k].difference=dif;
e[k].from=fr;
e[k].to=d;
e[k].next=pre[fr];
pre[fr]=k;
}
int dfn[MAXN],low[MAXN],num;
bool cut[MAXN];
stack<int> s;
vector<int> a[MAXN];
int ans=0;
void tarjan(int x,int di){
dfn[x]=low[x]=++num;
s.push(x);
for(int i=pre[x];i!=0;i=e[i].next){
if(e[i].difference==di) continue;//双向建边需要防止走回头路，我没有通过下标按位异或的方式，而是给每条边打上标记，标记为输入顺序
int y=e[i].to;
if(!dfn[y]){
tarjan(y,e[i].difference);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]){
ans++;
while(s.top()!=y){
a[ans].push_back(s.top());
s.pop();
}
s.pop();
a[ans].push_back(y);//a存储每一个点双连通分量
a[ans].push_back(x);
}
}
else low[x]=min(low[x],dfn[y]);
}
return ;
}
bool reach[MAXN];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v,i);
add(v,u,i);
if(u!=v) reach[u]=reach[v]=true;
}
for(int i=1;i<=n;i++){
if(dfn[i]!=0) continue;
else if(reach[i]==0){//孤立点特判
ans++;
a[ans].push_back(i);
}
else tarjan(i,-1);
}
printf("%d\n",ans);
for(int i=1;i<=ans;i++){
printf("%d ",a[i].size());
for(auto j:a[i]) printf("%d ",j);
printf("\n");
}
return 0;
}
强连通分量
#include<bits/stdc++.h>
using namespace std;
const int N=10005;
const int M=100005;
int n,m;
struct node{
int from,to,next;
}e[M];
int k,pre[M];
void add(int fr,int d){
k++;
e[k].from=fr;
e[k].to=d;
e[k].next=pre[fr];
pre[fr]=k;
}
bool in[N];
stack<int> s;
int low[N],dfn[N],num;
int ans;
vector<int> a[N];
int mm[N];
void tarjan(int x){
dfn[x]=low[x]=++num;
s.push(x);
in[x]=true;
for(int i=pre[x];i!=0;i=e[i].next){
int y=e[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(in[y]) low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
ans++;
while(s.top()!=x){
a[ans].push_back(s.top());//a存储每个强连通分量
in[s.top()]=false;
mm[s.top()]=ans;//mm[i]表示i号点所在的分量的编号
s.pop();
}
a[ans].push_back(x);
s.pop();
mm[x]=ans;
in[x]=false;
}
}
bool vis[N];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
for(int i=1;i<=n;i++){
if(dfn[i]!=0) continue;
else tarjan(i);
}
printf("%d\n",ans);
for(int i=1;i<=n;i++){
if(vis[i]) continue;
sort(a[mm[i]].begin(),a[mm[i]].end());
for(auto j:a[mm[i]]){
vis[j]=true;
printf("%d ",j);
}
printf("\n");
}
return 0;
}
缩点
#include<bits/stdc++.h>
using namespace std;
const int N=10005;
const int M=100005;
int n,m,wei[N];
struct node{
int from,to,next;
}e[M];
int pre[M],k;
inline void add(int fr,int d){
k++;
e[k].from=fr;
e[k].to=d;
e[k].next=pre[fr];
pre[fr]=k;
}
int dfn[N],low[N],num;
stack<int> s;
bool in[N];
int mm[N],ans,res[N];
void tarjan(int x){//先在旧图跑强连通分量
dfn[x]=low[x]=++num;
s.push(x);
in[x]=true;
for(int i=pre[x];i!=0;i=e[i].next){
int y=e[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(in[y]) low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x]){
ans++;
while(s.top()!=x){
res[ans]+=wei[s.top()];
mm[s.top()]=ans;
in[s.top()]=false;
s.pop();
}
s.pop();
res[ans]+=wei[x];//res存每个分量的点权和
mm[x]=ans;//存每个点所在的强连通分量
in[x]=false;
}
}
int din[N];
node e2[M];
int pre2[M],k2;
inline void add2(int fr,int d){//存放新图所用的前向星
k2++;
e2[k2].from=fr;
e2[k2].to=d;
e2[k2].next=pre2[fr];
pre2[fr]=k2;
}
int dfs(int pos){
int temp=0;
for(int i=pre2[pos];i!=0;i=e2[i].next) temp=max(temp,dfs(e2[i].to));
return res[pos]+temp;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&wei[i]);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
for(int i=1;i<=n;i++){
if(dfn[i]!=0) continue;
tarjan(i);
}
for(int i=1;i<=m;i++){
if(mm[e[i].from]==mm[e[i].to]) continue;
else{
din[ mm[e[i].to] ]++;
add2(mm[e[i].from],mm[e[i].to]);
}
}
int final=0;
for(int i=1;i<=ans;i++){
if(din[i]!=0) continue;
else{
final=max(final,dfs(i));
}
}
printf("%d",final);
return 0;
}
二分图
二分图判定
#include<bits/stdc++.h>
using namespace std;
vector<int> a[100005];
int color[100005],n,m;
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
a[u].push_back(v);
a[v].push_back(u);
}
queue<int> q;
int ans=0;
for(int i=1;i<=n;i++){
if(color[i]) continue;
color[i]=1;
q.push(i);
int cnt1=1,cnt2=0;
while(!q.empty()){
for(int j:a[q.front()]){
if(!color[j]){
color[j]=3-color[q.front()];
q.push(j);
if(color[j]==1) cnt1++;
else cnt2++;
}
else if(color[q.front()]==color[j]){
cout<<"Impossible";
return 0;
}
}
q.pop();
}
ans+=min(cnt1,cnt2);
}
cout<<ans;
return 0;
}
匈牙利算法
#include<bits/stdc++.h>
using namespace std;
vector<int> g[505];
int n,m,e;
int vis[505],match[505];
inline bool dfs(int fr,int dif){
if(vis[fr]==dif) return false;
vis[fr]=dif;
for(int i:g[fr]){
if(!match[i]||dfs(match[i],dif)){
match[i]=fr;
return true;
}
}
return false;
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m>>e;
while(e--){
int u,v;
cin>>u>>v;
g[u].push_back(v);
}
int ans=0;
for(int i=1;i<=n;i++){
if(dfs(i,i)) ans++;
}
cout<<ans<<endl;
return 0;
}
字符串
字符串哈希
#include<bits/stdc++.h>
using namespace std;
int n,cnt;
bool vis1[1000005],vis2[1000005],vis3[1000005];
long long b1[1505],b2[1505],b3[1505];
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
b1[0]=b2[0]=b3[0]=1;
for(int i=1;i<=1500;i++){
b1[i]=b1[i-1]*3%1000003;
b2[i]=b2[i-1]*3%999907;
b3[i]=b3[i-1]*3%995959;
}
while(n--){
string s;
cin>>s;
int len=s.size();
long long t1=0,t2=0,t3=0;
for(int i=0;i<=len-1;i++){
t1=(t1+s[i]*b1[len-i-1]%1000003)%1000003;
t2=(t2+s[i]*b2[len-i-1]%999907)%999907;
t3=(t3+s[i]*b3[len-i-1]%995959)%995959;
}
if(!vis1[t1]||!vis2[t2]||!vis3[t3]){
cnt++;
vis1[t1]=vis2[t2]=vis3[t3]=true;
}
}
cout<<cnt<<endl;
return 0;
}
KMP
#include<bits/stdc++.h>
using namespace std;
int len1,len2;
string s1,s2;
int my_next[1000005];
inline void my_get_next(){
int t1=0,t2=-1;
my_next[0]=-1;
while(t1<len2){
if(t2==-1||s2[t1]==s2[t2]) my_next[++t1]=++t2;
else t2=my_next[t2];
}
}
inline void kmp(){
int t1=0,t2=0;
while(t1<len1){
if(t2==-1||s1[t1]==s2[t2]){
t1++;
t2++;
}
else t2=my_next[t2];
if(t2==len2){
cout<<t1-len2+1<<endl;
t2=my_next[t2];
}
}
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>s1>>s2;
len1=s1.size();
len2=s2.size();
my_get_next();
kmp();
for(int i=1;i<=len2;i++) cout<<my_next[i]<<' ';
return 0;
}
字典树
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m;
int tree[N][30],cnt,wordcnt[N];
bool wordend[N];
string ans[4];
inline void add(string s){
int len=s.size(),root=0;
for(int i=0;i<len;i++){
int id=s[i]-'a';
if(!tree[root][id]) tree[root][id]=++cnt;
root=tree[root][id];
}
wordend[root]=true;
}
inline int query(string s){
int len=s.size();
int root=0;
for(int i=0;i<len;i++){
int id=s[i]-'a';
if(!tree[root][id]) return 1;
root=tree[root][id];
}
if(wordend[root]){
if(wordcnt[root]==0){
wordcnt[root]++;
return 3;
}
else return 2;
}
else return 1;
}
int main(){
ans[1]="WRONG\n";
ans[2]="REPEAT\n";
ans[3]="OK\n";
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
string zsq;
while(n--){
cin>>zsq;
add(zsq);
}
cin>>m;
while(m--){
cin>>zsq;
cout<<ans[query(zsq)];
}
return 0;
}
留给后人的忠告
标签：信息学,return,int,模版,pos,cin,++,奥赛,ans From： https://blog.csdn.net/Alicezsq/article/details/144171381十年OI一场空，不开long long见祖宗。
多测不清空，爆零两行泪。
暴力要打满，偏分要写上。
Codeblocks支持abs(__int128类型)，CCF用的std c++ 14 不支持
#define 慎用，有时编译器不报错，但显示爆空间
最后5min立刻停止打代码，检查freopen
最后一点：放平心态，相信自己！！！