集训模拟赛10
前言
又发现了许多需要学习的东西……
NO.1 BZOJ 4281 LCA（不知道叫什么名字 ）
Description
给定一棵有\(n\)个点的无根树，相邻的点之间的距离为\(1\)，一开始你位于\(m\)点。之后你将依次收到\(k\)个指令，每个指令包含两个整数\(d\)和\(t\)，你需要沿着最短路在\(t\)步之内（包含\(t\)步）走到\(d\)点，如果不能走到，则停在最后到达的那个点。请在每个指令之后输出你所在的位置。
Input
第一行包含三个正整数\(n,m,k(1\le m\le n\le 1000000,1\le k\le 1000000)\)。
接下来\(n-1\)行，每行包含两个正整数\(x,y(1\le x,y\le n)\)，描述一条树边。
接下来\(k\)行，每行两个整数\(d\),\(t\)\((1\le d\le n,0\le t\le 10^9)\)，描述一条指令。
Output
输出一行，包含\(k\)个正整数，即执行每条指令后你所在的位置。
样例
样例输入
3 1 2
1 2
2 3
3 4
1 1
样例输出
3 2
分析
这个题原本的题目是\(LCA\)，考试的时候就变成了”不知道叫什么名字 “，然后就……，其实就是求\(LCA\)的板子，就是有一些卡常，加一下快读快写就行。
我们每一次求出\(d\)和上一次位置的\(LCA\)，然后找出两个点之间的距离，如果大于\(t\)，那么分成两种情况：
1.上一次位置到最近公共祖先的距离大于\(t\)，我们就可以直接从\(d\)向上走\(t\)个。
2.上一次位置到最近公共祖先距离小于\(t\)，那么就是总距离减去\(t\)，然后从\(d\)向上走减完的距离。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
int f[maxn][23],dis[maxn],deep[maxn],head[maxn];
struct Node{
int v,next;
}e[maxn<<1];
int tot,n,m,d,t,k;
inline int read(){//快读
int s=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=s*10+ch-'0';
ch=getchar();
}
return s*f;
}
void Add(int x,int y){//建边
e[++tot].v = y;
e[tot].next = head[x];
head[x] = tot;
}
void dfs(int now,int fa){//求出每个点的深度
f[now][0]=fa;
deep[now]=deep[fa]+1;
for(int i=1;(1<<i)<=deep[now];i++){
f[now][i]=f[f[now][i-1]][i-1];
}
for(int i=head[now];i;i=e[i].next){
if(fa!=e[i].v) dfs(e[i].v,now);
}
}
int lca(int x,int y){//倍增求lca
int ans=0;
if(deep[x]>deep[y]) swap(x,y);
int len=deep[y]-deep[x],k=0;
while(len){
if(len & 1){
y=f[y][k];
}
++k;
len>>=1;
}
if(x==y) return x;
for(int i=20;i>=0;i--){
if(f[x][i]==f[y][i]) continue;
x=f[x][i];
y=f[y][i];
}
return f[x][0];
}
int js(int x,int d){//计算向上走完能走的距离之后的位置
for(int i=20;~i;i--){
if((1<<i)<=d){
x=f[x][i];
d-=(1<<i);
}
}
return x;
}
void write(int x){//快写
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
int main(){
n=read();
m=read();
k=read();
int pre = m;
for(int i=1;i<n;++i){
int x=read();
int y=read();
Add(x,y);
Add(y,x);
}
dfs(1,1);
for(int i=1;i<=k;++i){
d=read();
t=read();
int z=lca(d,pre);
if(deep[pre]-deep[z]>=t)pre = js(pre,t);//从上个位置到lca的距离大于t
else if(deep[d]+deep[pre]-2*deep[z]<=t)pre = d;//能到达d点
else {
t=deep[d] + deep[pre]-2*deep[z]-t;//上个位置到lca距离小于t但是到不了d
pre = js(d,t);
}
write(pre);
printf(" ");
}
return 0;
}
NO.2 虫洞
题目描述
\(N\)个虫洞，M条单向跃迁路径。从一个虫洞沿跃迁路径到另一个虫洞需要消耗一定量的燃料和\(1\)单位时间。虫洞有白洞和黑洞之分。设一条跃迁路径两端的虫洞质量差为\(delta\)。
从白洞跃迁到黑洞，消耗的燃料值减少\(delta\)，若该条路径消耗的燃料值变为负数的话，取为\(0\)。
从黑洞跃迁到白洞，消耗的燃料值增加\(delta\)。
路径两端均为黑洞或白洞，消耗的燃料值不变化。
作为压轴题，自然不会是如此简单的最短路问题，所以每过\(1\)单位时间黑洞变为白洞，白洞变为黑洞。在飞行过程中，可以选择在一个虫洞停留\(1\)个单位时间，如果当前为白洞，则不消耗燃料，否则消耗\(s_i\) 的燃料。现在请你求出从虫洞\(1\)到\(N\)最少的燃料消耗，保证一定存在\(1\)到\(N\)的路线。
输入格式
第\(1\)行：\(2\)个正整数\(N,M\)
第\(2\)行：\(N\)个整数，第\(i\)个为\(0\)表示虫洞\(i\)开始时为白洞，\(1\)表示黑洞。
第\(3\)行：\(N\)个整数，第\(i\)个数表示虫洞\(i\)的质量\(w_i\)。
第4行：\(N\)个整数，第\(i\)个数表示在虫洞i停留消耗的燃料\(s_i\)。
第\(5..M+4\)行：每行\(3\)个整数，\(u,v,k\)，表示在没有影响的情况下，从虫洞\(u\)到虫洞\(v\)需要消耗燃料\(k\)。
输出格式
一个整数，表示最少的燃料消耗。
样例
样例输入
4 5
1 0 1 0
10 10 100 10
5 20 15 10
1 2 30
2 3 40
1 3 20
1 4 200
3 4 200
样例输出
130
样例解释
按照\(1\to 3\to 4\)的路线。
数据范围与提示
对于\(30\%\)的数据： \(1\le N\le 100,1\le M\le 500\)
对于\(60\%\)的数据： \(1\le N\le 1000,1\le M\le 5000\)
对于\(100\%\)的数据： \(1\le N\le 5000，1\le M\le 30000\)
其中\(20\%\)的数据为\(1\le N\le 3000\)的链
\(1\le u,v\le N, 1\le k,w_i,s_i\le 200\)
分析
因为黑白洞之间可以相互转化，所以我们用分层图处理，因为每一次走过之后都会白变黑，黑变白，所以如果是同种，就应该从黑到白，从白到黑建一个边，边权为输入的边权。因为可以等待，所以把每个点从白到黑连边，边权为\(0\)，从黑到白也一样，但是边权应该是\(s_i\)。我们还需要建两边黑白不同的边，按照要求建边就行了，还是因为每一次走过之后都会白变黑，黑变白，所以虽然是两边不同，建边的时候还是要统一颜色建边，然后跑最短路就行了。
值得注意的是：如果开始是黑洞，那么应该从第二层开始最短路。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e4+10;
int head[maxn];
struct Node{
int v,next,val;
}e[maxn*10];
int tot;
int dis[maxn],vis[maxn],s[maxn],w[maxn],jl[maxn];
void Add(int x,int y,int val){//建边
e[++tot].v = y;
e[tot].next = head[x];
head[x] = tot;
e[tot].val = val;
}
priority_queue<pair<int,int> >q;
int n,m;
void Dij(int x){//最短路
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[x] = 0;
q.push(make_pair(0,x));
while(!q.empty()){
int y = q.top().second;
q.pop();
if(vis[y])continue;
vis[y] = 1;
for(int i=head[y];i;i=e[i].next){
int v=e[i].v;
if(dis[v]>dis[y]+e[i].val){
dis[v] = dis[y]+e[i].val;
q.push(make_pair(-dis[v],v));
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&jl[i]);
}
for(int i=1;i<=n;++i){
scanf("%d",&w[i]);
}
for(int i=1;i<=n;++i){
scanf("%d",&s[i]);
}
for(int i=1;i<=m;++i){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if(jl[x] == jl[y]){//两边是同一个颜色，因为会变，所以应该到不同颜色建边
Add(x,y+n,z);//加n后是黑色
Add(x+n,y,z);
}
else {//两边颜色不同，简便要相同，按要求处理边权即可
int val = abs(w[x]-w[y]);
Add(x+n,y+n,z+val);
Add(x,y,max(z-val,0));
}
}
for(int i=1;i<=n;++i){//等待的时候简便
Add(i,i+n,0);
Add(i+n,i,s[i]);
}
if(jl[1] == 1){//开始是黑洞要从黑洞那一层开始
Dij(n+1);
}
else Dij(1);
cout<<min(dis[n],dis[2*n])<<endl;//取最小值
}
NO.3 图腾计数
题目描述
\(whitecloth\) 最近参观了楼兰图腾。图腾的所在地有一排\(N\)个柱子，\(N\)个柱子的高度恰好为一个\(1\)到\(N\)的排列，而楼兰图腾就隐藏在这些柱子中。
由于\(whitecloth\)弱爆了，他只知道图腾由\(3\)个柱子组成，这三个柱子组成了下凸或上凸的图形（>.<），所谓下凸，设三个柱子的高度从左到右依次为 \(h_1,h_2,h_3\)，那么\(h_1>h_2，h_3>h_2\)，上凸则满足\(h_1<h_2，h_3<h_2\)。
现在\(whitecloth\)也找不到图腾具体是哪三个柱子，他只想知道满足这两个形状的柱子有几组。
输入格式
第一行一个数\(