NOIp2018 复习笔记 OI知识
其实也没什么用啦，只是来占个坑
3367 【模板】并查集
就这么做啊 没什么其他的 就是可以做tarjan LCA和Kruskal的操作
//关键函数
int getfa(int t)
{
if(t==fa[t]) return t;
fa[t]=getfa(fa[t]);
return fa[t];
}
带权并查集（【POJ 1182】食物链）
题目摘录：
“1 X Y”，表示X和Y是同类
“2 X Y”，表示X吃Y
1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。
求假话数
这道题可以称得上是带权并查集的经典题
两种做法：
1.用经典的带权并查集来记录各种生物之间的关系
//完整代码如下
#include<cstdio>
#include<iostream>
using namespace std;
int fa[300000],h[300000],f[3001][2];
int getfa(int t){
if(fa[t]==t)
return t;
h[t]=(h[fa[t]]+h[t])%3;//三种情况，吃，被吃，同类
fa[t]=getfa(fa[t]);
return fa[t];
}
int read(){
int ee=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){ee=ee*10+ch-'0';ch=getchar();}
return ee;
}//快读
int main()
{
int n,m,a,b,p;
n=read();
m=read();
for(int i=1;i<=n;i++)
fa[i]=i;//初始化
int ans=0;
for(int i=1;i<=m;i++)
{
p=read(); a=read(); b=read();
int x=getfa(a),y=getfa(b);
if(p==2&&a==b)
{
ans++;
continue;//自己不能吃自己
}
if(a>n||b>n)
{
ans++;
continue;//不会有n以外的生物
}
if(x==y)//如果两个有关系
{
if(p==1)
if(h[a]!=h[b]){ans++;continue;} //同类不吃
if(p==2)
{
if(h[a]==1&&h[b]!=0) {ans++;continue;}
if(h[a]==2&&h[b]!=1) {ans++;continue;}
if(h[a]==0&&h[b]!=2) {ans++;continue;}//均不符合被吃条件
}
}
else//没关系
{
fa[x]=y;//合并
if(p==1) h[x]=(h[b]-h[a]+3)%3;//同类
if(p==2) h[x]=(h[b]-h[a]+4)%3;//吃与被吃
x=getfa(a); y=getfa(b);//很重要，更新
}
}
printf("%d",ans);
return 0;
}
2.三倍数组，记录关系（神奇，但是好像好理解一点）
//完整代码如下
#include<cstdio>
#include<iostream>
using namespace std;
int fa[150001];
int getfa(int t)
{
if(t==fa[t]) return t;
fa[t]=getfa(fa[t]);
return fa[t];
}
void merge(int xx,int yy)
{
int x=getfa(xx);
int y=getfa(yy);
fa[x]=y;
}
int main()
{
int n,m,x,y,p;
int num=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=3*n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&p,&x,&y);
if(x>n||y>n){
num++;
continue;
}
if(p==1)
{
if(getfa(x)==getfa(y+n)||getfa(x)==getfa(y+2*n)){
num++;
continue;//如果是吃或者被吃关系
}
merge(x,y);
merge(x+n,y+n);
merge(x+2*n,y+2*n);//如果不是，就说明是真话，更新
}
else
{
if(getfa(x)==getfa(y)||getfa(x)==getfa(y+n)){
num++;
continue;
}
merge(x,y+2*n);
merge(x+n,y);
merge(x+2*n,y+n);//如果不是，就说明是真话，更新
}
}
printf("%d",num);
}
二维并查集（信奥一本通 格子游戏）
最开始想的时候还是很反胃的
贴代码吧
#include<cstdio>
#include<iostream>
using namespace std;
struct b{
int x,y;
}f[250][250];
b find(b k)
{
if(k.x==f[k.x][k.y].x&&k.y==f[k.x][k.y].y) return k;
f[k.x][k.y]=find(f[k.x][k.y]);
return f[k.x][k.y];//二维寻找
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
f[i][j].x=i;
f[i][j].y=j;
}
}//二维初始化
int p,q;
char tt;
b n1,n2;
for(int i=1;i<=m;i++)
{
scanf("%d %d",&p,&q);
cin>>tt;
if(tt=='D')//往下画
{
n1=find(f[p][q]);
n2=find(f[p+1][q]);
}
if(tt=='R')//往右画
{
n1=find(f[p][q]);
n2=find(f[p][q+1]);
}
if (n1.x==n2.x&&n1.y==n2.y)
{
printf("%d",i);
return 0;
}
else
f[n1.x][n1.y]=n2;
}
printf("draw");
return 0;
}
1226 快速幂&取余运算
也一样啊，但是要温习，在考场上差点忘了。。。可以搭配快速乘使用，防止毒瘤出题人，可以利用费马小定理（仅限质数）求逆元$ {a^{mod-2}}$
//快速乘+快速幂
typedef long long ll;
ll ksc(ll a,ll b,ll p)
{
ll ans=0;
while(b)
{
if(b&1)
ans=(ans+a)%p;
a=(a<<1)%p;
b>>=1;
}
return ans;
}//快速乘尤其要注意
ll ksm(ll a,ll b,ll p)
{
if(a==0||b==0)
return 0;//特判，记住
ll ans=1;//初值要正确
while(b)
{
if(b&1)
ans=ksc(ans,a,p);
a=ksc(a,a,p);
b>>=1;
}
return ans;
}
矩阵快速幂
就说白了就是在矩阵乘法上做快速幂，首先回顾一下矩阵乘法怎么算
放图片了（我懒）
以(Febonacci)为例
//略简单，直接贴代码
#include<cstdio>
#include<iostream>
using namespace std;
const long long mod=1e9+7;
long long a[120][120],ans[120][120],n,k,tmp[120][120];
void square1()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
tmp[i][j]=ans[i][j],ans[i][j]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
ans[i][j]=(ans[i][j]+(a[i][k]*tmp[k][j])%mod)%mod;
}
void square2()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
tmp[i][j]=a[i][j],a[i][j]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
a[i][j]=(a[i][j]+(tmp[i][k]*tmp[k][j])%mod)%mod;
}
void POW_MOD(long long b)
{
while(b)
{
if(b&1)
square1();
b=b>>1;
square2();
}
}
int main()
{
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%lld",&a[i][j]);
ans[i][j]=a[i][j];
}
}
POW_MOD(k-1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
printf("%lld ",ans[i][j]);
printf("
");
}
return 0;
}
数学概率与期望
其实，我个人的理解吧，就是极限思想+加权平均数，好像就是期望了呢...
T1：FZOJ 2590
给出一个有向无环的连通图，起点为1终点为N，每条边都有一个长度。绿豆蛙从起点出发，走向终点。
到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K 。
现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？
这道题就是图上的一道期望计算。由于是期望，只能从叶子节点往父节点计算（我又不能未卜先知）所以一遍DFS就可以解决问题
贴代码
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct edge{
int w,to,nex;
}e[200020];
int cnt,n,m;
int head[200020],out[200020],vis[200020],end1[200020];
double f[200020];
void add(int a,int b,int c)
{
cnt++;
e[cnt].to=b;
e[cnt].w=c;
e[cnt].nex=head[a];
head[a]=cnt;
}
void dfs(int t)
{
if(!vis[t]) vis[t]=1;
else return ;
if(t==n)
end1[t]=1;
int num=0;
for(int i=head[t];i;i=e[i].nex)
{
dfs(e[i].to);
if(end1[e[i].to])
{
f[t]+=f[e[i].to]+e[i].w;
end1[t]=end1[e[i].to];
}
num++;
}
if(num)
f[t]/=num;
}
int main()
{
int x,y,z;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
dfs(1);
printf("%.2lf",f[1]);
return 0;
}
T2 NOIP2016 D1 T3 换教室
很容易可以思考到这是一道(DP) 那么就可以按照题目要求设状态为(f[i][j][k]),指表示考虑前 i 个时间段，已经申请了j 个教室的交换，且当前教室是否交换（k=1或0）
(f[i][j][0]=min(f[i][j][0],f[i-1][j][0]+w[c[i-1]][c[i]]);)
表示前一个教室没有申请;(f[i][j][0]=min(f[i][j][0],f[i-1][j][1]+w[d[i-1]][c[i]]*k[i-1]+w[c[i-1]][c[i]]*(1.0-k[i-1]));)
绿色表示前一个教室申请了也通过了，蓝色表示没有通过。
({f[i][j][1]=min(f[i][j][1],f[i-1][j-1][0]+k[i]*w[c[i-1]][d[i]]+(1.0-k[i])*w[c[i-1]][c[i]]);})//前一个不申请
(f[i][j][1]=min(f[i][j][1],f[i-1][j-1][1]+k[i-1]*k[i]*w[d[i-1]][d[i]])
//前一个选上了，后一个也选上了
(+k[i-1]*(1.0-k[i])*w[d[i-1]][c[i]])
// 前一个选上了，后一个没选上
贴代码谢谢
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,m,v,e;
int c[20010],d[20010],w[2001][2001];
double f[2001][2001][2];
double k[20001];
int main()
{
memset(w,63,sizeof w);
int xx,yy,zz;
scanf("%d%d%d%d",&n,&m,&v,&e);
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
for(int i=1;i<=n;i++)
scanf("%d",&d[i]);
for(int i=1;i<=n;i++)
scanf("%lf",&k[i]);
for(int i=1;i<=e;i++)
{
scanf("%d%d%d",&xx,&yy,&zz);
if(xx==yy) continue;
w[xx][yy]=w[yy][xx]=min(w[xx][yy],zz);
}
for(int q=1;q<=v;q++)
for(int i=1;i<=v;i++)
for(int j=1;j<i;j++)//无向图搜一半，大量节约时间
w[i][j]=w[j][i]=min(w[i][j],w[i][q]+w[q][j]);
for(int i=1;i<=v;i++)
w[i][i]=w[i][0]=w[0][i]=0;
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k<=1;k++)
f[i][j][k]=99999999;
f[1][1][1]=f[1][0][0]=0;
for(int i=2;i<=n;i++)
{
double cnt=w[c[i-1]][c[i]];
f[i][0][0]=f[i-1][0][0]+w[c[i-1]][c[i]];
for(int j=1;j<=min(m,i);j++)
{
f[i][j][0]=min(f[i-1][j][0]+cnt,f[i-1][j][1]+w[d[i-1]][c[i]]*k[i-1]+w[c[i-1]][c[i]]*(1-k[i-1]));
if(j!=0)
f[i][j][1]=min(f[i-1][j-1][0]+w[c[i-1]][d[i]]*k[i]+w[c[i-1]][c[i]]*(1-k[i]),f[i-1][j-1][1]+w[c[i-1]][c[i]]*(1-k[i-1])*(1-k[i])+w[c[i-1]][d[i]]*(1-k[i-1])*k[i]+w[d[i-1]][c[i]]*(1-k[i])*k[i-1]+w[d[i-1]][d[i]]*k[i-1]*k[i]);
}
}
double ans=99999999;
for(int i=0;i<=m;i++)
ans=min(ans,min(f[n][i][0],f[n][i][1]));
printf("%.2lf",ans);
return 0;
}
DFS序
T1 [poi2007]meg大都市[POI2007]MEG-Megalopolis
题目大意：给你一颗无根树，最开始都是“土路”，动态添加（将土路变为公路）和查询（从１开始到ｋ经过多少条土路）
第一次看到是很ＭＢ的，知道是一道数据结构毒瘤题，但是不会打啊，更何况是在树上
于是，我们可以用DFS序将其转化为一个区间上的问题，因为一条土路被删除，即其的子树上的所有节点数量都会-1，所以就可以用线段树/树状数组（差分数组）来维护
贴代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
int n,m,cnt,top,tim;
int t[500005],head[500005];
int st[250005],fa[250005],l[250005],r[250005];
struct data{int to,next;}e[500005];
void insert(int u,int v)
{e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;}
inline int lowbit(int x)
{return x&(-x);}
void update(int x,int val)
{
for(int i=x;i<=n+n;i+=lowbit(i))
t[i]+=val;
}
void ask(int x)
{
int ans=-1;
for(int i=x;i;i-=lowbit(i))
ans+=t[i];
printf("%d
",ans);
}
void dfs()
{
st[++top]=1;
while(top)
{
int now=st[top],f=fa[top--];
if(!l[now])
{
l[now]=++tim;
st[++top]=now;
for(int i=head[now];i;i=e[i].next)
{
if(e[i].to==f)continue;
st[++top]=e[i].to;
fa[top]=now;
}
}
else r[now]=++tim;
}
}
int main()
{
n=read();
for(int i=1;i<n;i++)
{
int u=read(),v=read();
insert(u,v);insert(v,u);
}
dfs();
for(int i=1;i<=n;i++)
printf("%d %d
",l[i],r[i]);
for(int i=1;i<=n;i++)
{update(l[i],1);update(r[i],-1);}
m=read();
for(int i=1;i<=n+m-1;i++)
{
int x,y;
char ch[5];
scanf("%s",ch);
if(ch[0]=='A')
{
x=read();y=read();
update(l[y],-1);update(r[y],1);
}
else
{x=read();ask(l[x]);}
}
return 0;
}
拓扑排序
好久没做忘玩老
在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：
1.每个顶点出现且只出现一次。
2.若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。
T1：POJ 3249 传送门
显然，DAG上的最短路径，由于题目数据太大，不便于用最短路径算法求解，故可使用(Toposort),然后按拓扑序进行更新。
贴代码
#pragma GCC optimize(2)
#include<stack>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ll;
struct edge{
int to,nex;
}e[2000010];
ll cnt;
int head[2000010];
stack<int>top;
void add(int a,int b)
{
cnt++;
e[cnt].to=b;
e[cnt].nex=head[a];
head[a]=cnt;
}
ll v[200010],dp[200010],n,m,x,y;
int in[200010],out[200010],vis[200010];
void topo(void)
{
for(int i=1;i<=n;i++)
if(!in[i]) top.push(i),vis[i]=1;
while(!top.empty())
{
int fr=top.top();
top.pop();
for(int i=head[fr];i;i=e[i].nex)
{
int w=e[i].to;
in[w]--;
if(dp[fr]+v[w]>dp[w]) dp[w]=dp[fr]+v[w];
if((!in[w])&&(!vis[w])) top.push(w),vis[w]=1;
}
}
}
int main()
{
while(scanf("%lld%lld",&n,&m)!=EOF)
{
cnt=0;
memset(in, 0, sizeof(in));
memset(out, 0, sizeof(out));
memset(head, -1, sizeof(head));
memset(vis, false, sizeof(vis));
for(int i=1;i<=n;i++)
scanf("%lld",&v[i]);
for(int i=1;i<=m;i++)
scanf("%lld%lld",&x,&y),add(x,y),++in[y],++out[x];
for(int i=1;i<=n;i++)
if(!in[i]) dp[i]=v[i];
else dp[i]=-(1<<30);
topo();
ll ans=-(1<<30);
for(int i=1;i<=n;i++)
if(!out[i]&&dp[i]>ans) ans=dp[i];
printf("%lld
",ans);
}
return 0;
}
Tarjan
神仙tarjan。。。