2018.9青岛网络预选赛(B)

传送门

•参考资料

  [1]:ACM-ICPC 2018 青岛赛区网络预赛 B. Red Black Tree (LCA、二分)

•题意 

  给出一棵树,根节点为1。

  每条边有一个权值,树上有红色结点 m 个,其花费为 0 ,其余为黑色;

  每个黑色结点的花费为其到最近红色祖先的经过的路径权值之和。

  有 q 次询问,每次给出一个点集;

  问将树上任意一个结点涂成红色结点后,点集中所有点的花费的最大值的最小是多少。

•题解

  相关变量解释:

    sum : 每次询问中询问的点集个数

    a[  ]  : 存储每次询问到的点集

    costR[i] : 结点 i 距其最近红色祖先的花费

  预处理每个点到根的距离cost、到最近红色祖先的距离 costR 和 ST 表。

  对于每次询问,将a[ ] 按 costR 从大到小排序,在 0~costR[a[0]] 范围内二分答案;

  对所有大于答案的点求它们的公共祖先(利用ST表可以O(1)求两点的公共祖先),将其涂红;

  之后计算每个大于答案的点的新花费是否小于答案。

•Code

 #include<iostream>
#include<vector>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
#define pb push_back
#define ll long long
#define mem(a,b) (memset(a,b,sizeof a))
const int maxn=1e5+; int n,m,q;
//===============Restore Graph============
struct Node
{
int to;
ll w;
Node(int to,int w):to(to),w(w){}
};
vector<Node >G[maxn];
void addEdge(int u,int v,int w)
{
G[u].pb(Node(v,w));
G[v].pb(Node(u,w));
}
//=========================================
int vs[*maxn];//欧拉序列,范围区间为 [1,total]
int depth[*maxn];//欧拉序列对应的深度序列
int pos[maxn];//pos[i] : 结点 i 再欧拉序列中第一次出现的位置
ll cost[maxn];//cost[i] : 结点 i 距根据点的距离
ll costR[maxn];//costR[i] : 结点 i 距最近红色祖先结点的距离,初始化为 -1
int total;//欧拉序列的大小
void dfs(int u,int f,int dep,ll dis)
{
vs[++total]=u;
depth[total]=dep;
pos[u]=total;
cost[u]=dis;
for(int i=;i < G[u].size();++i)
{
Node e=G[u][i];
if (e.to == f)
continue;
costR[e.to]=(costR[e.to] == ? :costR[u]+e.w);
dfs(e.to,u,dep+,dis+e.w);
vs[++total]=u;
depth[total]=dep;
}
}
//==================RMQ======================
struct Node2
{
int mm[ * maxn];
int dp[ * maxn][];
void ST()
{
int n=total;
mm[] = -;
for (int i = ; i <= n; i++)
{
mm[i]=((i&(i-))==) ? mm[i - ] + :mm[i - ];
dp[i][]=i;
}
for (int j=;j <= mm[n];j++)
for (int i=;i+(<<j)- <= n;i++)
if(depth[dp[i][j - ]] < depth[dp[i+(<<(j-))][j-]])
dp[i][j]=dp[i][j-];
else
dp[i][j]=dp[i+(<<(j-))][j-];
}
int Lca(int u, int v)
{
u=pos[u],v=pos[v];
if (u > v)
swap(u, v);
int k = mm[v-u+];
if(depth[dp[u][k]] <= depth[dp[v-(<<k)+][k]])
return vs[dp[u][k]];
return vs[dp[v-(<<k)+][k]];
}
}_rmq;
//==========================================
int a[maxn];
int sum;
bool cmp(int a, int b)
{
return costR[a] > costR[b];
}
bool Check(ll x)
{
if(costR[a[]] <= x)
return true;
int lca=a[];
for(int i=;i < sum;i++)
{
if(costR[a[i]] <= x)
break;
lca=_rmq.Lca(lca,a[i]);
}
for(int i = ;i < sum;i++)
{
if(costR[a[i]] <= x)
return true;
if(cost[a[i]]-cost[lca] > x)
return false;
}
return true;
}
void Solve()
{
dfs(,-,,);
_rmq.ST();
while(q--)
{
scanf("%d",&sum);
for (int i=;i < sum; i++)
scanf("%d",&a[i]);
sort(a,a+sum,cmp);
ll l=,r=costR[a[]];
while(l < r)
{
ll mid=(l+r)/;
if(Check(mid))
r=mid;
else
l=mid + ;
}
printf("%lld\n",l);
}
}
void init()
{
mem(costR,-);
total=;
for(int i=;i < maxn;++i)
G[i].clear();
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
init();
scanf("%d%d%d",&n,&m,&q);
while(m--)
{
int red;
scanf("%d",&red);
costR[red]=;
}
costR[]=;
for(int i=;i<n;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addEdge(u,v,w);
}
Solve();
}
return ;
}

•出现的问题

  1、用 vector 存储图比用 链式前向星存储图要慢

    (1)vector :

2018.9青岛网络预选赛(B)

    (2)链式前向星:

2018.9青岛网络预选赛(B)

  2、平常一直在用的RMQ会超时

 //=====================RMQ===================
struct Node1
{
int dp[][*maxn];
void Preset()
{
for(int i=;i < *maxn;++i)
dp[][i]=i;
}
void ST()
{
int k=log(total)/log();
for(int i=;i <= k;++i)
for(int j=;j <= (total-(<<i)+);++j)
if(depth[dp[i-][j]] > depth[dp[i-][j+(<<(i-))]])
dp[i][j]=dp[i-][j+(<<(i-))];
else
dp[i][j]=dp[i-][j];
}
int Lca(int u,int v)
{
u=pos[u],v=pos[v];
if(u > v)
swap(u,v);
int k=log(v-u+)/log();
if(depth[dp[k][u]] > depth[dp[k][v-(<<k)+]])
return vs[dp[k][v-(<<k)+]];
return vs[dp[k][u]];
}
}_rmq;
//===========================================

TLE

 //==================RMQ======================
struct Node2
{
int mm[ * maxn];
int dp[ * maxn][];
void ST()
{
int n=total;
mm[] = -;
for (int i = ; i <= n; i++)
{
mm[i]=((i&(i-))==) ? mm[i - ] + :mm[i - ];
dp[i][]=i;
}
for (int j=;j <= mm[n];j++)
for (int i=;i+(<<j)- <= n;i++)
if(depth[dp[i][j - ]] < depth[dp[i+(<<(j-))][j-]])
dp[i][j]=dp[i][j-];
else
dp[i][j]=dp[i+(<<(j-))][j-];
}
int Lca(int u, int v)
{
u=pos[u],v=pos[v];
if (u > v)
swap(u, v);
int k = mm[v-u+];
if(depth[dp[u][k]] <= depth[dp[v-(<<k)+][k]])
return vs[dp[u][k]];
return vs[dp[v-(<<k)+][k]];
}
}_rmq;
//==========================================

AC

  3、cost[ ] 很有用,如果 Check( ) 中不加    

      if(cost[a[i]]-cost[lca] > x)
        return false;

    会返回 WA,具体为什么,明天再好好想想%%%%%%%%%

 


分割线:2019.5.8

  中石油的这场重现赛又让我回想起了这道题留下的疑惑;

  现在再想想这道题,思路清晰了些许;

  一些不理解的地方瞬间顿悟了;

  ST表处理RMQ中,会多次求解 log2(x),这种算式是比较耗时的,我们预处理出所需的log2(x);

logTwo[i]=log2(i);

  如何预处理呢?

  首先想一下,三位数的二进制数的最大值为 111(2),四位数的二进制数的最小值为 1000(2)

  两者的关系是 (111)&(1000) = 0 , 而对于任意三位二进制数 x,y ,(x&y) != 0;

  有了这个关系后,就可以这么预处理了:

logTwo[]=-;
for(int i=;i <= n;++i)
logTwo[i]=(i&(i-)) == ? logTwo[i-]+:logTwo[i-];

  这就是之前一直不理解的ST表加速的地方;

•Code

 #include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define INFll 0x3f3f3f3f3f3f3f3f
const int maxn=1e5+; int n,m,q;
ll C[maxn];///C[i]:节点i到根节点1的花费
ll CR[maxn];///CR[i]:节点i到其最近的红色祖先节点的花费
int num;
int head[maxn];
struct Edge
{
int to;
ll w;
int next;
}G[maxn<<];
void addEdge(int u,int v,ll w)
{
G[num]={v,w,head[u]};
head[u]=num++;
}
struct LCA
{
int vs[maxn<<];///欧拉序列
int dep[maxn<<];///欧拉序列中的节点对应的深度序列
int pos[maxn<<];///pos[i]:节点i在欧拉序列中第一次出现的位置
int cnt;
int logTwo[maxn<<];///logTwo[i]:log2(i)
int dp[maxn<<][];///dp[i][j]:[i,i+2^j-1]深度最小的点的下标(欧拉序列中的下标)
void DFS(int u,int f,int depth,ll dist)
{
vs[++cnt]=u;
dep[cnt]=depth;
pos[u]=cnt;
C[u]=dist;
for(int i=head[u];~i;i=G[i].next)
{
int v=G[i].to;
ll w=G[i].w;
if(v == f)
continue;
CR[v]=min(CR[v],CR[u]+w);
DFS(v,u,depth+,dist+w);
vs[++cnt]=u;
dep[cnt]=depth;
}
}
void ST()
{
logTwo[]=-;
for(int i=;i <= cnt;++i)
{
dp[i][]=i;
///:后的语句写错了,刚开始写成了logTwo[i],debug了好一会
logTwo[i]=(i&(i-)) == ? logTwo[i-]+:logTwo[i-];
}
for(int k=;k <= logTwo[cnt];++k)
for(int i=;i+(<<k)- <= cnt;++i)
if(dep[dp[i][k-]] > dep[dp[i+(<<(k-))][k-]])
dp[i][k]=dp[i+(<<(k-))][k-];
else
dp[i][k]=dp[i][k-];
}
void lcaInit(int root)
{
cnt=;
DFS(root,root,,);
ST();
}
int lca(int u,int v)///返回节点u,v的LCA
{
u=pos[u];
v=pos[v]; if(u > v)
swap(u,v); int k=logTwo[v-u+];
if(dep[dp[u][k]] > dep[dp[v-(<<k)+][k]])
return vs[dp[v-(<<k)+][k]];
else
return vs[dp[u][k]];
}
}_lca; int qCnt;
int query[maxn<<]; bool Check(ll mid)
{
int lca=;///不满足条件的点的LCA
for(int i=;i <= qCnt;++i)
{
if(CR[query[i]] <= mid)
continue;
if(lca == )
lca=query[i];
else/// > mid的点LCA
lca=_lca.lca(lca,query[i]);
} for(int i=;i <= qCnt;++i)
{
if(CR[query[i]] <= mid)
continue; ///如果将lca点涂红后还不能使其 <= mid,返回false
if(C[query[i]]-C[lca] > mid)
return false;
}
return true;
}
void Solve()
{
_lca.lcaInit(); for(int i=;i <= q;++i)
{
scanf("%d",&qCnt); ll l=-,r=;
for(int j=;j <= qCnt;++j)
{
scanf("%d",query+j);
r=max(r,CR[query[j]]);
} while(r-l > )
{
ll mid=l+((r-l)>>);
if(Check(mid))
r=mid;
else
l=mid;
}
printf("%lld\n",r);
}
}
void Init()
{
num=;
mem(head,-);
mem(CR,INFll);///初始化为最大值
}
int main()
{
// freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin);
int test;
scanf("%d",&test);
while(test--)
{
Init();
scanf("%d%d%d",&n,&m,&q);
for(int i=;i <= m;++i)
{
int red;
scanf("%d",&red);
CR[red]=;
}
CR[]=;
for(int i=;i < n;++i)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addEdge(u,v,w);
addEdge(v,u,w);
}
Solve();
}
return ;
}
上一篇:8.Smarty的条件判断语句的写法


下一篇:node.js(连接mysql)