一些想法
距离NOIP2018只剩下一个星期的时间了，通过这几天在长郡的考试，渐渐感觉还有好多东西自己还不够熟练，也有些东西到现在还不会，现将NOIP前的一些计划列在这里，希望能在考前把他们全部完成吧
一些模板
这里是NOIP可能会考的数据结构和算法的模板
字符串算法：
\(kmp\)
#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e6+100;
int n,m,nex[maxn],k,ok[maxn];
char a[maxn],b[maxn];
void getnex(){
nex[1]=0,k=0;
for(int i=2;i<=m;i++){
while(k&&b[i]!=b[k+1])
k=nex[k];
if(b[i]==b[k+1])
k++;
nex[i]=k;
}
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
scanf("%s%s",a+1,b+1);
n=strlen(a+1),m=strlen(b+1);
getnex();
for(int i=0,j=0;i<=n;i++){
while(j&&a[i+1]!=b[j+1])
j=nex[j];
if(a[i+1]==b[j+1])
j++;
if(j==m){
ok[i+2-m]=1;
j=nex[j];
}
}
for(int i=1;i<=n;i++)
if(ok[i])
printf("%d\n",i);
for(int i=1;i<=m;i++)
printf("%d ",nex[i]);
printf("\n");
return 0;
}
\(manacher\)
#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=3e7+100;
int p,r,a[maxn],ans,len;
char s[maxn],c[maxn];
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
scanf("%s",s+1);
len=strlen(s+1);
for(int i=1;i<=len;i++)
c[i*2]=s[i],
c[i*2-1]='#';
len=len*2+1;
c[len]='#';
c[0]='%';
for(int i=1;i<=len;i++){
if(i<r)
a[i]=min(r-i,p*2-i);
else
a[i]=1;
while(c[i-a[i]]==c[i+a[i]])
a[i]++;
if(a[i]+i>r)
r=i+a[i],p=i;
ans=max(ans,a[i]);
}
printf("%d\n",ans-1);
return 0;
}
\(AC\)自动机
#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e6+100,maxm=1e5+100;
struct AC{
struct node{
int fail,poi,son[26];
};
node d[maxm];
int cnt;
queue<int>q;
void clean(int x){
memset(d[x].son,0,sizeof(d[x].son));
d[x].fail=0;
d[x].poi=0;
}
void insert(char *s,int bh){
int len=strlen(s),now=0;
for(int i=0;i<len;i++){
int y=s[i]-'a';
if(!d[now].son[y]){
d[now].son[y]=++cnt;
clean(cnt);
}
now=d[now].son[y];
}
d[now].poi=bh;
}
void build(){
for(int i=0;i<26;i++)
if(d[0].son[i])
d[d[0].son[i]].fail=0,
q.push(d[0].son[i]);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=0;i<26;i++)
if(d[x].son[i])
d[d[x].son[i]].fail=d[d[x].fail].son[i],
q.push(d[x].son[i]);
else
d[x].son[i]=d[d[x].fail].son[i];
}
}
void query(char *s,int *ans){
int len=strlen(s),now=0;
for(int i=0;i<len;i++){
now=d[now].son[s[i]-'a'];
for(int i=now;i;i=d[i].fail)
ans[d[i].poi]++;
}
}
};
AC g;
int n,len,ans[300],tot;
char a[maxn],b[300][80];
void clean(){
memset(ans,0,sizeof(ans));
tot=0;
g.cnt=0;
g.clean(0);
}
int main(){
// freopen("2333.in","r",stdin);
//freopen(".out","w",stdout);
while(scanf("%d",&n)!=EOF){
if(n==0) break;
clean();
for(int i=1;i<=n;i++){
scanf("%s",a);
g.insert(a,++tot);
memcpy(b[tot],a,sizeof(a));
}
g.build();
scanf("%s",a);
g.query(a,ans);
int Ans=0;
for(int i=1;i<=tot;i++)
Ans=max(Ans,ans[i]);
printf("%d\n",Ans);
for(int i=1;i<=tot;i++)
if(Ans==ans[i])
printf("%s\n",b[i]);
}
return 0;
}
回文自动机
struct prt{
node d[maxn];
int lim,len,last,cnt;
int getfail(int x,char *s){
while(s[lim-d[x].len-1]!=s[lim])
x=d[x].fail;
return x;
}
void extend(int x,char *s){
int cur=getfail(last,s);
int now=d[cur].son[x];
if(!now){
now=++cnt;
d[now].fail=d[getfail(d[cur].fail,s)].son[x];
d[now].len=d[cur].len+2;
d[cur].son[x]=now;
}
d[now].siz++;
last=now;
}
void build(char *s){
d[1].len=-1;
d[0].fail=d[1].fail=1;
cnt=last=1;
len=strlen(s);
for(lim=0;lim<len;lim++)
extend(s[lim]-'a',s);
for(int i=cnt;i>=2;i--)
d[d[i].fail].siz+=d[i].siz,d[d[i].fail].siz%=P;
}
};
prt g;
后缀自动机
#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=2e6+100;
struct SAM{
struct node{
int len,siz,link,son[26];
};
node d[maxn];
int last,f,g,p,clo,cnt,c[maxn],a[maxn];
void clone(int x,int y,int z){
memcpy(d[x].son,d[y].son,sizeof(d[y].son));
d[x].link=d[y].link;
d[x].len=d[z].len+1;
}
void extend(int x){
f=++cnt;
d[f].len=d[last].len+1;
d[f].siz++;
g=last;
last=f;
while(~g&&!d[g].son[x])
d[g].son[x]=f,g=d[g].link;
if(g==-1){
d[f].link=0;
return;
}
p=d[g].son[x];
if(d[p].len==d[g].len+1){
d[f].link=p;
return;
}
clo=++cnt;
clone(clo,p,g);
d[f].link=d[p].link=clo;
while(~g&&d[g].son[x]==p)
d[g].son[x]=clo,g=d[g].link;
}
void build(char *s){
d[0].link=-1;
int len=strlen(s);
for(int i=0;i<len;i++)
extend(s[i]-'a');
}
int query(int len){
for(int i=1;i<=cnt;i++) c[d[i].len]++;
for(int i=1;i<=len;i++) c[i]+=c[i-1];
for(int i=cnt;i>=1;i--) a[c[d[i].len]--]=i;
int ans=0;
for(int i=cnt;i>=1;i--){
d[d[a[i]].link].siz+=d[a[i]].siz;
if(d[a[i]].siz>1)
ans=max(ans,d[a[i]].siz*d[a[i]].len);
}
return ans;
}
};
SAM g;
char a[maxn];
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
scanf("%s",a);
g.build(a);
printf("%d\n",g.query(strlen(a)));
return 0;
}
字符串\(hash\)
#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read(){
int ans=0,fh=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
fh=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
return ans*fh;
}
typedef unsigned long long ull;
const int maxn=1e4+100;
const ull base=131;
struct hash{
inline ull gethash(char *s){
ull ans=0;
for(int i=0,L=strlen(s);i<L;i++)
ans=(ans*base+s[i]);
return ans;
}
};
hash h;
int n;
ull a[maxn];
char s[maxn];
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%s",s),a[i]=h.gethash(s);
sort(a+1,a+n+1);
int ans=0;
for(int i=1;i<=n;i++)
if(a[i]!=a[i-1])
ans++;
printf("%d\n",ans);
return 0;
}
图论算法
缩点
#include<map>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read(){
int ans=0,fh=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
fh=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
return ans*fh;
}
typedef long long ll;
const int maxn=1e4+100,maxm=1e5+100;
queue<int>q;
struct grafh{
int u[maxm],v[maxm],nex[maxm],head[maxn],num;
void add(int x,int y){
v[++num]=y;
u[num]=x;
nex[num]=head[x];
head[x]=num;
}
}g,f;
int n,m,a,b,c[maxn],ans,p[maxn],sccno[maxn],scc_tot,siz[maxn],low[maxn],dfn[maxn],tim;
int du[maxn];
stack<int>st;
void tarjan(int x){
dfn[x]=low[x]=++tim;
st.push(x);
for(int i=g.head[x];i;i=g.nex[i]){
int y=g.v[i];
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else
if(!sccno[y])
low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
scc_tot++;
while(1){
int y=st.top();
st.pop();
sccno[y]=scc_tot;
siz[scc_tot]+=c[y];
if(y==x) break;
}
}
}
void rebuild(){
for(int i=1;i<=n;i++){
int x=sccno[i];
for(int j=g.head[i];j;j=g.nex[j]){
int y=sccno[g.v[j]];
if(x!=y)
f.add(x,y),du[y]++;
}
}
n=scc_tot;
}
void work(){
for(int i=1;i<=n;i++)
if(!du[i])
q.push(i);
while(!q.empty()){
int x=q.front();
q.pop();
ans=max(ans,p[x]+siz[x]);
for(int i=f.head[x];i;i=f.nex[i]){
int y=f.v[i];
p[y]=max(p[y],p[x]+siz[x]);
du[y]--;
if(!du[y]) q.push(y);
}
}
printf("%d\n",ans);
}
int main(){
//freopen(".out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
for(int i=1;i<=m;i++)
scanf("%d%d",&a,&b),g.add(a,b);
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i);
rebuild();
work();
return 0;
}
点双
边双
最小生成树
网络流
费用流
欧拉回路
混合图欧拉路
数论算法
exgcd
int exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1,y=0;
return a;
}
else{
int z=exgcd(b,a%b,y,x);
y-=a/b*x;
return z;
}
}
中国剩余定理
void crt(){
for(int i=1;i<=n;i++) lcm=lcm*p[i];
for(int i=1;i<=n;i++){
ll x=lcm/p[i];
ll y=poww(x,p[i]-2,p[i]);
ans=(ans+y*x%lcm*a[i]%lcm)%lcm;
}
printf("%lld\n",ans);
}
#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read(){
int ans=0,fh=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
fh=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
return ans*fh;
}
typedef long long ll;
const int maxn=1e6+100;
int n;
ll m[maxn],c[maxn];
inline ll C(ll a,ll b,ll p){
ll c=a*b-(ll)((long double)a*b/p+0.5)*p;
return c<0?c+p:c;
}
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1,y=0;
return a;
}
ll r=exgcd(b,a%b,y,x);
y-=a/b*x;
return r;
}
inline ll inv(ll a,ll b){
ll x,y;
ll r=exgcd(a,b,x,y);
while(x<0) x+=b;
return x;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld%lld",&m[i],&c[i]);
bool err=0;
for(int i=2;i<=n;i++){
if(i==14)
i=14;
ll m1=m[i-1],m2=m[i],c1=c[i-1],c2=c[i],t=gcd(m1,m2);
if((c2-c1)%t!=0){
err=1;
break;
}
m[i]=m1/t*m2;
c[i]=C(C(inv(m1/t,m2/t),(c2-c1),m[i])/t%(m2/t),m1,m[i])+c1;
c[i]=(c[i]%m[i]+m[i])%m[i];
}
if(!err) printf("%lld\n",c[n]);
else printf("-1\n");
return 0;
}
线性求逆元
void getinv(){
inv[1]=1;
for(int i=2;i<=n;i++)
inv[i]=1ll*(p-p/i)*inv[p%i]%p;
}
Lucas定理
#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read(){
int ans=0,fh=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
fh=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
return ans*fh;
}
typedef long long ll;
const int maxn=1e6+100;
ll jc[maxn],n,m,p;
void ycl(){
jc[0]=1;
for(ll i=1;i<=p;i++)
jc[i]=jc[i-1]*i%p;
}
inline ll poww(ll x,ll y){
ll base=1;
while(y){
if(y&1) base=base*x%p;
x=x*x%p;
y>>=1;
}
return base;
}
inline ll C(ll x,ll y){
if(x>y) return 0;
return jc[y]*poww(jc[x],p-2)%p*poww(jc[y-x],p-2)%p;
}
ll lucas(ll x,ll y){
if(x==0) return 1;
return C(x%p,y%p)*lucas(x/p,y/p)%p;
}
int main(){
int t=read();
while(t--){
scanf("%lld%lld%lld",&n,&m,&p);
ycl();
printf("%lld\n",lucas(n,n+m));
}
return 0;
}
欧拉筛
void Euler(){
vis[1]=1;
for(int i=2;i<=maxn-1;i++){
if(!vis[i])
p[++num]=i;
for(int j=1;j<=num&&p[j]*i<=maxn-1;j++){
vis[p[j]*i]=1;
if(i%p[j]==0) break;
}
}
}
数据结构
Splay
#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read(){
int ans=0,fh=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
fh=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
return ans*fh;
}
typedef long long ll;
struct Splay{
struct node{
int poi,lazy,siz;
node *son[2],*fa;
node(){
son[0]=son[1]=fa=NULL;
siz=1;
lazy=0;
}
}*root,*bj;
inline int query(node *x){
return x==NULL?0:x->siz;
}
inline int son(node *x){
return x->fa==NULL?0:x==x->fa->son[1];
}
void updata(node *x){
x->siz=x->son[0]==NULL?1:x->son[0]->siz+1;
x->siz+=x->son[1]==NULL?0:x->son[1]->siz;
}
void revise(node *x){
if(x==NULL) return;
x->lazy^=1;
swap(x->son[0],x->son[1]);
}
void pushdown(node *x){
if(!x->lazy) return;
x->lazy^=1;
revise(x->son[0]);
revise(x->son[1]);
}
void rotate(node *x){
node *f=x->fa;
node *g=f->fa;
int a=son(x),b=son(f);
f->son[a]=x->son[a^1];
if(x->son[a^1]!=NULL)
x->son[a^1]->fa=f;
x->son[a^1]=f;
f->fa=x;
x->fa=g;
if(g) g->son[b]=x;
else root=x;
updata(f),updata(x);
}
void splay(node *x,node *y){
while(x->fa!=y){
node *f=x->fa;
node *g=f->fa;
if(g!=y)
rotate(son(x)==son(f)?f:x);
rotate(x);
}
}
void insert(int k,int p,node *x){
int siz=query(x->son[0]);
if(siz+1==k){
int a=1;
node *f=x;
x=f->son[1];
while(x!=NULL)
f=x,x=f->son[0],a=0;
x=new node();
x->fa=f;
x->poi=p;
f->son[a]=x;
splay(x,NULL);
return;
}
if(siz+1>k) insert(k,p,x->son[0]);
else insert(k-siz-1,p,x->son[1]);
}
void access(int k,node *y,node *x){
pushdown(x);
int siz=query(x->son[0]);
if(siz+1==k){
splay(x,y);
bj=x;
return;
}
if(siz+1>k) access(k,y,x->son[0]);
else access(k-siz-1,y,x->son[1]);
}
void work(int l,int r){
access(l,NULL,root);
access(r+2,bj,root);
revise(root->son[1]->son[0]);
}
void print(node *x){
pushdown(x);
if(x->son[0]!=NULL) print(x->son[0]);
if(x->poi>0) printf("%d ",x->poi);
if(x->son[1]!=NULL) print(x->son[1]);
}
Splay(){
root=new node();
root->poi=-233;
insert(1,-666,root);
}
void ycl(int x){
for(int i=1;i<=x;i++)
insert(i,i,root);
}
}zhy;
int n,m,l,r;
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
scanf("%d%d",&n,&m);
zhy.ycl(n);
while(m--){
scanf("%d%d",&l,&r);
zhy.work(l,r);
}
zhy.print(zhy.root);
printf("\n");
return 0;
}
主席树
#include<map>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=2e5+100;
struct node{
int siz,l,r;
};
struct nod{
int l,r,bh,ans,k;
};
nod p[maxn];
node tre[maxn*30];
int n,m,z[maxn],num,tot,b[maxn],root[maxn],a[maxn];
map<int,bool>cz;
map<int,int>c;
bool cmp(nod x,nod y){
return x.r<y.r;
}
bool Cmp(nod x,nod y){
return x.bh<y.bh;
}
void build(int l,int r,int &now){
now=++tot;
if(l==r) return;
int mid=l+r>>1;
build(l,mid,tre[now].l);
build(mid+1,r,tre[now].r);
}
void insert(int x,int old,int &now,int l,int r){
now=++tot;
tre[now]=tre[old];
tre[now].siz++;
if(l==r) return;
int mid=l+r>>1;
if(x<=mid) insert(x,tre[old].l,tre[now].l,l,mid);
else insert(x,tre[old].r,tre[now].r,mid+1,r);
}
int query(int k,int l,int r,int old,int now){
if(l==r) return l;
int siz=tre[tre[now].l].siz-tre[tre[old].l].siz,mid=(l+r)>>1;
if(k<=siz) return query(k,l,mid,tre[old].l,tre[now].l);
return query(k-siz,mid+1,r,tre[old].r,tre[now].r);
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(!cz[a[i]]){
cz[a[i]]=1;
b[++num]=a[i];
}
}
sort(b+1,b+num+1);
for(int i=1;i<=num;i++)
c[b[i]]=i,z[i]=b[i];
for(int i=1;i<=n;i++)
a[i]=c[a[i]];
for(int i=1;i<=m;i++)
scanf("%d%d%d",&p[i].l,&p[i].r,&p[i].k),p[i].bh=i;
sort(p+1,p+m+1,cmp);
build(1,num,root[0]);
int now=0;
for(int i=1;i<=n;i++){
insert(a[i],root[i-1],root[i],1,num);
while(now<m&&p[now+1].r==i)
now++,p[now].ans=query(p[now].k,1,num,root[p[now].l-1],root[i]);
}
sort(p+1,p+m+1,Cmp);
for(int i=1;i<=m;i++)
printf("%d\n",z[p[i].ans]);
return 0;
}
LCT
st表
一些知识点
容斥原理
博弈论
各种DP
一些计划
整理好上面的模板
luogu刷题满300道(然而咕掉了)