Ryz的鬼题

蚂蚁(ant)
【题目描述】
小 R 种了一棵苹果树,这棵树上有 n 个节点(标号从 0 到 n-1),有 n-1 条树枝连接这
n 个节点,这 n 个节点相互连通。每条树枝的长度为 1。
苹果树上的每一个节点上生长着一个苹果,这个苹果散发着香味。在 0 时刻,第 i 个
节点的苹果散发香味的浓郁度为 s[i],以后每过一个单位时间,香味的浓郁度就会增加 a[i]。
苹果树上还有一只蚂蚁,在 0 时刻时,这只蚂蚁在 0 号节点,在第 i 时刻,它会朝着
第 i 时刻时香味最浓郁的节点方向走 1 个单位长度。
(如果两个节点的浓郁度相同,则标号
较大的节点被认为是香味更浓郁的)
。如果在第 i 时刻,蚂蚁所处的位置已经是香味最浓郁
的节点了,那么它会选择在原地休息。
现在,小 R 有 m 个问题,他想知道在第 t[i]个时刻蚂蚁的位置。
【输入格式】
第一行 2 个整数 n,m,表示点数和询问数。
第二行 n 个整数,表示每个节点的初始香味浓郁度 s[i]。
第三行 n 个整数,表示每个节点的香味浓郁度的增加值 a[i]。
接下来 n-1 行,每行三个整数 s,t,表示 s 和 t 之间有一条边。
最后一行 m 个整数,表示 m 个询问。
【输出格式】
对于每个询问输出一行答案,表示在 t[i]时刻蚂蚁的位置。
【样例输入】
3 4
6 3 1
0 6 7
0 1
0 2
1 2 3 4
【样例输出】
0
1
0
2
【样例解释】
在 0 时刻时,0 号节点的香味最浓郁,蚂蚁原地休息,因此在 1 时刻蚂蚁仍在 0 号点
在 1 时刻时,1 号节点的香味最浓郁,蚂蚁向 1 号节点走去,因此在 2 时刻蚂蚁在 1 号点
在 2 时刻时,2 号节点的香味最浓郁,蚂蚁向 2 号节点走去,因此在 3 时刻蚂蚁在 0 号点
在 3 时刻时,2 号节点的香味最浓郁,蚂蚁向 2 号节点走去,因此在 4 时刻蚂蚁在 2 号点

【数据规模和约定】
对于 100%的数据 n<=100000,m<=100000,0<=a[i]<=10^6,0<=s[i]<=10^15,0<=t[i]<=10^9

这个题我一开始傻逼的以为是一个动态点分治,然后打了一个暴力,准备拿来对拍;

打着打着发现这是一个半平面交啊,我迟疑了一下,说好的数据结构呢???怎么没有一题要打数据结构

但是在没有办法了,于是只能拿计算几何幼儿园级别的水平硬着头皮敲了一个半平面交+暴力转移,然后调了半天,各种细节

实在是调不出来,只能再次滚粗

考完之后出题人很震惊,说T1只要是个人都应该写得出来吧!!!

好吧其实的确是的,但不过对于这道很操的细节题我也是不想说话

大体思路是这样的:

苹果的香味是一个关于时间的一次函数(很显然吧)

然后其实是要求每一个时刻苹果香味最大的苹果在哪里,并向其移动

这就很像水平可见直线了,在每个直线能被看到的那段时间就表示是会向那个点移动

(注意还有一个与水平可见直线不一样的地方:交点必须在x轴正半轴,被坑了好久;)(貌似半平面交要加一堆特判???,我记得我的斜率优化不是这样的啊!!!)

然后我们考虑到t有10^9级别,那我们就不能暴力跳了,先把询问离线排序

接着我们可以在半平面交中找出所有转折点(直线的交点),然后两个交点的每一段分段处理

在每一段上用倍增快速跳.

附上代码:

#include<iostream>

#include<cstdio>

#include<cstring>

#include <vector>

#include <algorithm>

#define int long long

using namespace std;

const int N=100050;

const int Inf=2147483647;

vector<int> p[N];

int f[N][18],deep[N],ans[N];

int n,m,u,v,t[N],tn;

struct data {

  int id;

  long long s,a;

} a[100100],qu[100100];

struct query {

  int id,t;

} q[100100];

bool operator<(data a,data b) {

  return a.a < b.a;

}

bool operator<(query a,query b) {

  return a.t < b.t;

}

void dfs(int x) {

  for (int i=0;i<p[x].size();i++)

    if (f[p[x][i]][0]==-1) {

      f[p[x][i]][0]=x;

      deep[p[x][i]]=deep[x] + 1;

      dfs(p[x][i]);

    }

}

void pre_BZ() {

  for (int i=1;i<n;i++) f[i][0]=-1;

  f[0][0]=0;deep[0]=0;dfs(0);

  for (int i=1;i<18;i++)

    for (int j=0;j<n;j++)

      f[j][i]=f[f[j][i-1]][i-1];

}

int lca(int a,int b) {

  if (deep[a]>deep[b]) return lca(b,a);

  for (int j=17;j>=0;j--)

    if (deep[b]-(1<<j) >=deep[a])

      b=f[b][j];

  for (int j = 17;j >= 0;j--)

    if (f[a][j] != f[b][j])

      a=f[a][j],b=f[b][j];

  if (a != b) return f[a][0];

  return a;

}

int meeting(data &a,data &b) {

  if (a.a == b.a) {

    if (b.s>a.s||(b.s==a.s&&b.id>a.id)) return -1;

    return Inf;

  }

  int ans = (a.s-b.s)/(b.a - a.a) + 1;

  if ((a.s-b.s)%(b.a-a.a)==0&&b.id>a.id) ans--;

  if (ans<0) return -1;

  if (ans>Inf) return Inf;

  return ans;

}

void BPMJ() {

  sort(a,a+n);int tail=0,c1,c2;

  for (int i=0;i<n;i++) {

    while(tail>0) {

      c1=meeting(qu[tail],a[i]);

      if (c1<=0) {tail--;continue;}

      if(tail>1){c2=t[tail-2];if(c2>=c1){tail--;continue;}}

      break;

    }

    qu[++tail]=a[i];

    if(tail>1) t[tail-2]=c1;

  }

  tn=tail-1;

}

int jump(int a,int l) {

  for(int j=17;j>=0;j--)

    if (l>=(1<<j)) {

      a=f[a][j];

      l-=(1 << j);

    }

  return a;

}

int move(int st,int ed,int t) {

  int LCA=lca(st,ed);

  int l1=deep[st]-deep[LCA];

  int l2=deep[ed]-deep[LCA];

  if (t<=l1) return jump(st,t);

  if (t<=l1+l2) return jump(ed,l1+l2-t);

  return ed;

}

int gi(){

  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;

}

void work(){

  sort(q,q+m);int now=0,lastt=0,i=0,j=0;

  while (j<m) {

    if (t[i]<q[j].t&&i<tn) {

      now=move(now,qu[i+1].id,t[i]-lastt);

      lastt=t[i];i++;

    }

    else {

      now=move(now,qu[i+1].id,q[j].t-lastt);

      lastt=q[j].t;ans[q[j].id]=now;j++;

    }

  }

}

main() {

  freopen("ant.in","r",stdin);

  freopen("ant.out","w",stdout);

  n=gi(),m=gi();

  for(int i=0;i<n;i++) a[i].s=gi(),a[i].id=i;

  for(int i=0;i<n;i++) a[i].a=gi();

  for(int i=0;i<n-1;i++) {

    int u=gi(),v=gi();

    p[u].push_back(v);p[v].push_back(u);

  }

  for (int i=0;i<m;i++) q[i].t=gi(),q[i].id=i;

  pre_BZ();BPMJ();work();

  for (int i=0;i<m;i++) printf("%lld\n",ans[i]);

  return 0;

}

巴特西

Ryz的鬼题

最新文章

热门文章