2019/07/31 做题记录
Elzat
2019-07-31 16:25:26
**不想再看到倍增和LCA了**
**这些题我也不想多说什么，看代码吧**
# [洛谷P3865](https://www.luogu.org/problem/P3865) 【模板】ST表
思想：**倍增**
### 预处理
$st[i][j]$表示从$i$开始的$2^{j}$个数的的最值
如$st[i][1]$表示的是$i$到$i+1$位置中两个数的最值
所以在转移时可以把当前的区间（平均）分成两个区间分别求最值
### 查询
首先求区间长度的$log_{2}$（设为$k$）
然后再基于左右端点分别查询
```cpp
#include<cstdio>
#include<algorithm>
#define maxn 500010
using namespace std;
int n;
int st[maxn][21];
int lg2[maxn];
void init()
{
for(int j = 1;(1 << j) <= n;j ++)
{
for(int i = 1;i + (1<<j) - 1 <= n;i ++)
{
st[i][j] = max(st[i][j-1],st[i +(1<<(j-1))][j-1]);
}
}
for(int i = 2;i <= n;i ++)
{
lg2[i] = lg2[i-1];
if((1 << (lg2[i] + 1)) == i) lg2[i] ++;
}
}
int query(int l,int r)
{
int k = lg2[r - l + 1];
return max(st[l][k],st[r - (1<<k) + 1][k]);
}
int main()
{
int m;
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i ++) scanf("%d",&st[i][0]);
init();
while(m --)
{
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",query(l,r));
}
return 0;
}
```
# [洛谷P3379](https://www.luogu.org/problem/P3379)【模板】最近公共祖先（LCA）
我用tarjan做的这道题（具体请看[这篇博客](http://www.cnblogs.com/JVxie/p/4854719.html)）
这里我只说一下针对这道题的改进
因为tarjan求最近公共祖先求出来的**顺序随机**且是在**所有询问输入完之后**去求的
那么就会想到用数组存储一下答案
但是看数据$N \leq 500000$
肯定不能用二维数组存了
那么我就新建了一个结构体$ques$
其中$u,v$表示有询问关系的两点
$num$表示该询问的序号（这是按顺序输出的关键）
$bro$表示与该询问内容相同的询问（因为在询问时要建双向边,而且询问$x,y$和$y,x$是相同的，所以在求到了其中一个之后另一个就不用求了）
$done$表示这个询问是否被求完了（默认$false$）
最后再用$ans$数组存起来就行了
```cpp
#include<cstdio>
using namespace std;
struct edge{
int u,v,w,next;
}e[1000010];
struct ques{
int u,v,next,num,bro;
bool done;
ques(){done = false;}
}E[1000010];
int ans[500010];
int head[500010],cnt,HEAD[500010],tot;
int f[500010],vis[500010];
void add(int u,int v)
{
e[++cnt].u = u;
e[cnt].v = v;
e[cnt].next = head[u];
head[u] = cnt;
}
void add_q(int u,int v,int num) //双向边，所以两个点有两次建边过程
{
E[++tot].u = u;
E[tot].v = v;
E[tot].next = HEAD[u];
HEAD[u] = tot;
E[tot].num = num;
E[tot].bro = tot + 1;
E[++tot].u = v;
E[tot].v = u;
E[tot].next = HEAD[v];
HEAD[v] = tot;
E[tot].num = num;
E[tot].bro = tot - 1;
}
int find(int x)
{
if(x != f[x]) return f[x] = find(f[x]);
return x;
}
void merge(int x,int y)
{
x = find(x);
y = find(y);
f[y] = x;
}
void dfs(int x,int fa) //tarjan
{
for(int i = head[x];i;i = e[i].next)
{
int v = e[i].v;
if(v != fa) //防止回到父亲
{
dfs(v,x);
merge(x,v);
vis[v] = 1;
}
}
for(int i = HEAD[x];i;i = E[i].next)
{
int v = E[i].v;
if(vis[v] && !E[i].done)//!E[i].done的理由：若该询问（或其兄弟询问）做完了就不用再存了
{
ans[E[i].num] = find(v);
E[i].done = true; //若该询问做完了
E[E[i].bro].done = true; //那么其兄弟询问也就做完了
}
}
}
int main()
{
int n,m,s;
scanf("%d%d%d",&n,&m,&s);
for(int i = 1;i < n;i ++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
f[i] = i;
}
f[n] = n;
for(int i = 1;i <= m;i ++)
{
int x,y;
scanf("%d%d",&x,&y);
add_q(x,y,i);
}
dfs(s,s);
for(int i = 1;i <= m;i ++)
printf("%d\n",ans[i]);
return 0;
}
```
# [洛谷P1613](https://www.luogu.org/problem/P1613) 跑路
整形$dis[i][j]$表示从$i$到$j$需要按跑路器的次数（也就是秒数，初始化无穷大）
布尔值$f[i][j][k]$表示$i$到$j$是否有长度为$2^{k}$的一条路
那么在输入$u,v$时 就可以设$dis[u][v] = 1$，$f[u][v][0]=true$（因为相邻两点距离为$1$，所以$u,v$间有一条长为$2^{0}$的路，所以只用按一次，也就是一秒就能从$u$到$v$）
那么再模仿$floyed$做一下假的“松弛”：
对于点$i$和$j$，如果有点$t$满足：
**$i$到$t$有一条长为$2^{k-1}$的路，$t$到$j$也有一条长为$2^{k-1}$的路，那么$i$到$j$就肯定有一条长为$2^{k}$的路（两条路相加），且因为该长度是$2$的次幂，所以只需按一次（用一秒）就能从$i$到$j$。**
最后再用真的$floyed$求一下最短路
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dis[55][55]; //floyed没跑了
bool f[55][55][100];
int main()
{
memset(dis,0x3f,sizeof(dis));
int n,m;
scanf("%d%d",&n,&m);
while(m --)
{
int u,v;
scanf("%d%d",&u,&v);
dis[u][v] = 1;
f[u][v][0] = true;
}
for(int k = 1;k <= 64;k ++)
for(int i = 1;i <= n;i ++)
for(int t = 1;t <= n;t ++)
for(int j = 1;j <= n;j ++)
{
if(f[i][t][k-1] && f[t][j][k-1])
{
f[i][j][k] = true;
dis[i][j] = 1;
}
}
for(int k = 1;k <= n;k ++)
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= n;j ++)
{
dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);
}
printf("%d",dis[1][n]);
return 0;
}
```
# [洛谷P1351](https://www.luogu.org/problem/P1351) 联合权值
因为两点间距离为$1$，所以**与同一个点连接的两点**肯定有联合权值
思路：
**用邻接表存储边 枚举所有点 若有两个或以上儿子就可以组合去求联合权值更新答案**
优化：**求每一段的和以及最大值，然后更新答案**
具体方法看洛谷题解
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int mod = 10007;
struct edge{
int v,next;
}e[400010];
int head[200010],cnt;
int w[200010];
void add(int u,int v)
{
e[++cnt].v = v;
e[cnt].next = head[u];
head[u] = cnt;
}
int main()
{
int n;
scanf("%d",&n);
for(int i = 1;i < n;i ++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
for(int i = 1;i <= n;i ++) scanf("%d",&w[i]);
int sum0,max0;
int maxn = 0,sum = 0;
for(int i = 1;i <= n;i ++)
{
int j = head[i]; //第一个儿子
sum0 = w[e[j].v] % mod; //预设一下这一段的和以及最大值
max0 = w[e[j].v];
for(j = e[j].next;j;j = e[j].next) //若有其他儿子就会进这个循环
{
int v = e[j].v;
sum = (sum + sum0 * w[v]) % mod;//这里利用乘法结合律，可省时间
maxn = max(maxn,max0 * w[v]);
sum0 = (sum0 + w[v]) % mod;
max0 = max(max0,w[v]);
}
}
printf("%d %d",maxn,(sum * 2) % mod);//最后的和要乘2
return 0;
}
```
# [洛谷P1967](https://www.luogu.org/problem/P1967) 货车运输
**步骤：**
1.求最大生成树
2.LCA（倍增求法）
3.在LCA过程中更新答案
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int inf = 0x3f3f3f;
struct edge{
int u,v,w,next;
}e[500010],E[500010];
int head[100010],cnt;
int fa[100010][21],w[100010][21];
int dep[100010],vis[100010];
void add(int u,int v,int w)
{
E[++cnt].u = u;
E[cnt].v = v;
E[cnt].w = w;
E[cnt].next = head[u];
head[u] = cnt;
}
//lca 初始化
void init(int n)
{
for(int j = 1;j <= 20;j ++)
{
for(int i = 1;i <= n;i ++)
{
fa[i][j] = fa[fa[i][j-1]][j-1];
w[i][j] = min(w[i][j-1],w[fa[i][j-1]][j-1]);
}
}
}
void dfs(int x) //预设最初的w和fa
{
vis[x] = 1;
for(int i = head[x];i;i = E[i].next)
{
int v = E[i].v;
if(vis[v]) continue;
dep[v] = dep[x] + 1;
fa[v][0] = x;
w[v][0] = E[i].w;
dfs(v);
}
}
void work(int n)
{
for(int i = 1;i <= n;i ++)
{
if(!vis[i])
{
dep[i] = 1;
dfs(i);
fa[i][0] = i;
w[i][0] = inf;
}
}
}
//并查集
int f[100010];
int find(int x)
{
if(f[x] != x) return f[x] = find(f[x]);
return x;
}
//最大生成树
bool cmp(edge a,edge b)
{
return a.w > b.w;
}
void kruskal(int n,int m)
{
sort(e+1,e+m+1,cmp);
for(int i = 1;i <= n;i ++) f[i] = i;
int k = 0;
for(int i = 1;i <= m;i ++)
{
int u = e[i].u,v = e[i].v,w = e[i].w;
if(find(u) != find(v))
{
add(u,v,w);
add(v,u,w);
v = find(v);
u = find(u);
f[v] = u;
k ++;
}
if(k == n - 1) break;
}
}
//lca
int lca(int x,int y)
{
if(find(x) != find(y)) return -1;
if(dep[x] < dep[y]) swap(x,y);
int ans = inf;
for(int j = 20;j >= 0;j --)
{
if(dep[fa[x][j]] >= dep[y])
{
ans = min(ans,w[x][j]);
x = fa[x][j];
}
}
if(x == y) return ans;
for(int j = 20;j >= 0;j --)
{
if(fa[x][j] != fa[y][j])
{
ans = min(ans,min(w[x][j],w[y][j]));
x = fa[x][j];
y = fa[y][j];
}
}
ans = min(ans,min(w[x][0],w[y][0]));
return ans;
}
int main()
{
int n,m,q;
scanf("%d%d",&n,&m);
for(int i = 1;i <= m;i ++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
e[i].u = u;
e[i].v = v;
e[i].w = w;
}
kruskal(n,m);
work(n);
init(n);
scanf("%d",&q);
for(int i = 1;i <= q;i ++)
{
int u,v;
scanf("%d%d",&u,&v);
printf("%d\n",lca(u,v));
}
return 0;
}
```
今天做题做的心累，不想写更详细的了，如不清楚就请看其他dalao的题解吧。
BY Elzat