来自FallDream的博客，未经允许，请勿转载，谢谢。
-------------------------------------------------------
大家好，我是一个假人。在学习OI的过程中，我凭借自己的努力，成功发明出了大顶的dij，并且帮助自己在cf和模拟赛上多过了 -2 道题。发明算法真美妙！
--------------------------------------------------------
不说了，D题因为dij打成大顶的挂了，血都吐出来了。A题瞎特判fst了，神tm只有bc还能70多名. 都是假的。
A.给定a,b,c,d,求是否有y满足 y=a*x1+b=c*x2+d且x1,x2属于N a,b,c,d<=100
数据范围这么小，瞎暴力一下呗。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
#define ll long long
#define INF 2000000000
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
} int a,b,c,d;
bool mark[]; int main()
{
a=read();b=read();c=read();d=read();
for(int i=;i<=;i++)
mark[b+i*a]=;
for(int j=;j<=;j++)
if(mark[d+j*c])return *printf("%d",d+j*c);
puts("-1");
return ;
}
B.给定n个序列，每个序列有ki个数，问是否每个序列都有两个数满足x1=-x2 n，K<=10000
题解：..............
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
#define ll long long
#define INF 2000000000
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
} int n,m;
int s[]; int main()
{
n=read();m=read();
for(int i=;i<=m;i++)
{
int k=read();bool yes=false;
for(int j=;j<=k;j++)
{
int x=read();if(x<)x=(-x)+n;
if(i==s[(x+n-)%(n*)+]){yes=true;}
s[x]=i;
}
if(!yes)return *puts("YES");
}
puts("NO");
return ;
}
C.有n个点，两个人。两个人分别有k1,k2个数，他们玩一个游戏。轮流进行，每个人可以选择一个数并且把棋子前移这么多格，到达1号点胜利，问两个人分别从2-n开始是否必胜，必败或者会循环。
n<=7000
题解：正向的dp明显不行，我们考虑倒着dp。一个情况必胜当且仅当能转移到一个对方必败的区域，必败当且仅当到达的所有区域都是对方必胜的。显然第一个和第二个人从一号点出发是必败的，我们开一个队列，每次都向后转移，如果目前要转移的状态是必败，那么直接把能转移到的情况改成必胜，加入队列；否则我们开两个r数组，记录一下每一个点的出度，开始为k1/k2,从必胜的情况转移到它时把它度数-1，如果它的度数变成了0，说明它肯定必败了，可以更新一下加入队列。一直这么做就可以了，最后没有被dp到的就是循环的点。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<queue>
#include<algorithm>
#define ll long long
#define INF 2000000000
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
} int f1[],f2[];
int n,k1,k2;
int s[],s2[],r[],r2[];
struct node{
int x,k;
};
queue<node> q; int main()
{
n=read();k1=read();
f1[]=f2[]=;
for(int i=;i<=k1;i++)
{
s[i]=read()%n;
}
k2=read();
for(int j=;j<=k2;j++)
{
s2[j]=read()%n;
}
for(int i=;i<=n;i++)r[i]=k1,r2[i]=k2;r[]=r2[]=INF;
q.push((node){,});q.push((node){,});
while(!q.empty())
{
node x=q.front();q.pop();
//cout<<x.x<<" "<<x.k<<endl;
if(x.k==)
{
for(int i=;i<=k2;i++)
{
int np=(x.x+n-s2[i]-)%n+;
// cout<<x.x<<" "<<x.k<<" "<<f1[x.x]<<" "<<np<<" "<<endl;
if(f2[np])continue;
if(f1[x.x]==)
{
r2[np]--;
if(!r2[np])
f2[np]=-f1[x.x],q.push((node){np,});
}
else
{
f2[np]=-f1[x.x];
q.push((node){np,});
}
}
}
else
{
for(int i=;i<=k1;i++)
{
int np=(x.x+n-s[i]-)%n+;
// cout<<x.x<<" "<<x.k<<" "<<f2[x.x]<<" "<<np<<" "<<endl;
if(f1[np])continue;
if(f2[x.x]==)
{
r[np]--;
if(!r[np])
f1[np]=-f2[x.x],q.push((node){np,});
}
else
{
f1[np]=-f2[x.x];
q.push((node){np,});
}
}
}
}
for(int i=;i<=n;i++)
{
if(f1[i]==)cout<<"Win ";
else if(f1[i]==) cout<<"Lose ";
else cout<<"Loop ";
}
puts("");
for(int i=;i<=n;i++)
{
if(f2[i]==)cout<<"Win ";
else if(f2[i]==) cout<<"Lose ";
else cout<<"Loop ";
}
return ;
}
D.有n个点，m条路径。每条路径可以从一个点到一个点，也可以从一个区间到一个点，也可以从一个点到一个区间，都有一定的费用。求从s号点到达其他点的最小距离。 n,m<=100000
题解：很明显题目是一道最短路，但是我们没法对区间全部连边。所以我们很容易想到开两个线段树，用最多log个点表示区间。
我们用一棵线段树，只能往上走，表示它所在的区间，另一棵线段树只能往下走，表示它走到了这个区间，第二棵树的对应节点向第一棵连边。这样之后，单点的路径直接见，点到区间的从第一个树连第二个树的对应log个节点，区间到点的直接第一棵内连。 最后，堆优化的dij， 节点最多2*2*n,复杂度4nlogn
我真tm要吐血了，还有十分钟时候打完了，交上去wa了，不服，看到两点钟，不知道哪里挂了，只好滚去睡觉。第二天迷迷糊糊就去学校了，在ditoly大神的指导下猛然发现dij写成了大顶的，改改就过了，上次也这样，我真的是#(@!*(*#&!(#
我好菜啊都不会
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<queue>
#include<algorithm>
#define ll long long
#define INF 200000000000000000LL
#define MAXN 800000
#define MN 400000
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
} int n,m,s,cnt=;
ll d[MAXN+];
struct node{
ll x;int k;
bool operator <(const node &y) const
{
return x>y.x;
}
};
int top,id[MAXN+],head[MAXN+],num[MAXN+];
priority_queue<node> q;
struct edge{
int to,next;ll w;
}e[];
bool mark[MAXN+]; void ins(int f,int t,int w)
{
e[++cnt]=(edge){t,head[f],w};head[f]=cnt;
// cout<<"ins"<<f<<" "<<t<<" "<<w<<endl;
} void get(int k,int l,int r,int lt=,int rt=n)
{
if(l==lt&&r==rt){id[++top]=k;return;}
int mid=lt+rt>>;
if(r<=mid) get(k<<,l,r,lt,mid);
else if(l>mid) get(k<<|,l,r,mid+,rt);
else
{get(k<<,l,mid,lt,mid);get(k<<|,mid+,r,mid+,rt);}
} void dij()
{
d[num[s]]=;q.push((node){,num[s]});
while(!q.empty())
{
node now=q.top();q.pop();
if(mark[now.k]) continue;mark[now.k]=;
for(int i=head[now.k];i;i=e[i].next)
if(d[now.k]+e[i].w<d[e[i].to])
{
d[e[i].to]=d[now.k]+e[i].w;
q.push((node){d[e[i].to],e[i].to});
}
}
} void build(int k,int l,int r)
{
ins(k+MN,k,);
// cout<<"build"<<k<<" "<<l<<" "<<r<<endl;
if(l==r) {num[l]=k;return;}
int mid=l+r>>;
ins(k<<,k,);ins(k<<|,k,);
ins(k+MN,(k<<)+MN,);ins(k+MN,(k<<|)+MN,);
build(k<<,l,mid);build(k<<|,mid+,r);
} int main()
{
n=read();m=read();s=read();memset(d,,sizeof(d));
build(,,n);
for(int i=;i<=m;i++)
{
int t=read();
if(t==)
{int l=read(),r=read(),w=read();ins(num[l],num[r]+MN,w);}
else
{
int v=read(),l=read(),r=read(),w=read();
top=;get(,l,r);
for(int j=;j<=top;j++)
if(t==)
ins(num[v],id[j]+MN,w);
else
ins(id[j],num[v]+MN,w);
}
}
dij();
for(int i=;i<=n;i++)
d[num[i]]=min(d[num[i]],d[num[i]+MN]);
for(int i=;i<=n;i++)if(d[num[i]]>=INF)d[num[i]]=-;
for(int i=;i<=n;i++)
printf("%lld ",d[num[i]]);
return ;
}
E.给定n个数si,你要对这个序列分段，并且对于每个k(1<=k<=n)求出每段最多有k种不同的数的时候的最小分段数。 1<=si<=n<=100000
做法1：我们考虑每次暴力跳，跳的次数最多n*(1+1/2+1/3+1/4....+1/n)是nlogn，跳的方法我们可以用主席树倒着插入来维护对于每一个节点，后面的有贡献的节点，这样的话我们每次主席树上找k大就可以啦，复杂度nlog^2n
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<queue>
#include<algorithm>
#define MN 5000000
#define MM 100000
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
} int n,cnt=;
struct TREE{
int l,r,x;
}T[MN+];
int s[MM+],size[MM+],rt[MM+],last[MM+]; void ins(int x,int nx,int k,int ad)
{
int mid,l=,r=n;T[nx].x=T[x].x+ad;
while(l<r)
{
mid=l+r>>;
if(k<=mid)
{
T[nx].r=T[x].r;T[nx].l=++cnt;
x=T[x].l;nx=T[nx].l;r=mid;
}
else
{
T[nx].l=T[x].l;T[nx].r=++cnt;
x=T[x].r;nx=T[nx].r;l=mid+;
}
T[nx].x=T[x].x+ad;
// cout<<"ins"<<x<<" "<<nx<<" "<<k<<" "<<ad<<endl;
}
} int query(int x,int rk,int l=,int r=n)
{
//cout<<"query"<<x<<" "<<rk<<" "<<l<<" "<<r<<" "<<T[T[x].l].x<<endl;
if(l==r) return l;
int mid=l+r>>;
if(rk<=T[T[x].l].x) return query(T[x].l,rk,l,mid);
else return query(T[x].r,rk-T[T[x].l].x,mid+,r);
} int main()
{
n=read();
for(int i=;i<=n;i++)s[i]=read();
for(int i=n;i;i--)
{
rt[i]=++cnt;size[i]=size[i+]+;
if(last[s[i]])
{
int x=++cnt;
size[i]--;ins(rt[i+],x,last[s[i]],-);
ins(x,rt[i],i,);
}
else ins(rt[i+],rt[i],i,);
last[s[i]]=i;
}
for(int i=;i<=n;i++)
{
int pos=,ans=;
while(pos<=n)
{
ans++;
if(size[pos]<=i)pos=n+;
else pos=query(rt[pos],i+);
// cout<<pos<<" "<<ans<<endl;getchar();
}
printf("%d ",ans);
}
return ;
}
做法2:暴力算前根号n个，然后剩下的分最多根号n个块，每一块内算出所有数字的出现次数，然后你会得到n^0.5条分界线，你每次暴力推这些分界线，一条分界线最多被推n次，复杂度n^1.5
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<queue>
#include<algorithm>
#define DITOLY 320
#define MN 100000
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
} int num[DITOLY+][MN+],s[MN+],n,cnt=,tot=,size,mark[MN+],g[MN+];
int answer[MN+],type[DITOLY+]; int main()
{
n=read();size=sqrt(n);
for(int i=;i<=n;i++)s[i]=read();
for(int j=;j<=size;j++)
{
int kind=,ans=;++tot;
for(int i=;i<=n;i++)
{
if(mark[s[i]]==tot) {if(j==size)num[cnt+][s[i]]++;continue;}
mark[s[i]]=tot;kind++;
if(kind>j){if(j==size)g[++cnt]=i-;ans++;kind=;++tot;mark[s[i]]=tot;};
if(j==size) num[cnt+][s[i]]++,type[cnt+]++;
}
if(kind) ans++;if(j==size)g[++cnt]=n;
printf("%d ",ans);
}
for(int i=size+;i<=n;i++)
{
for(int j=;j<cnt;j++)
{
if(g[j]>=n) {cnt=j+;break;}
while(g[j]<n&&type[j]+(num[j][s[g[j]+]]==)<=i)
{
g[j]++;if(++num[j][s[g[j]]]==) type[j]++;
if(!--num[j+][s[g[j]]]) type[j+]--;
}
}
while(cnt>&&g[cnt-]==n) cnt--;
printf("%d ",cnt);
}
return ;
}