【做题】neerc2017的A、C、I、L

A - Archery Tournament

一开始往化简公式的方向去想，结果没什么用。

考虑与一条垂线相交的圆的个数。不难YY，当圆的个数最多时，大概就是这个样子的:

我们稍微推一下式子，然后就能发现其个数不超过\(O(\log C)\)，其中\(C\)为坐标范围（即1e9）。

接下来的事情就简单了，我们把数据离散化后就能用线段树查询过某一条垂线的所有圆了，再暴力判断是哪一个就可以了。

时间复杂度\(O(n \log ^2 n)\)。

#include <bits/stdc++.h>

#define sqr(x) (1ll * (x) * (x))

using namespace std;

const int N = 400010;

struct circle {

  int x,y;

  bool inside(int a,int b) {

    return sqr(x - a) + sqr(b - y) < sqr(y);

  }

} cir[N];

int n;

struct data {

  int tp,x,y;

} dat[N];

vector<int> tmp,ins;

set<int> q[N << 2];

void modify(int l,int r,int v,int sgn,int x=1,int lp=1,int rp = n) {

  if (l > rp || r < lp) return;

  if (lp >= l && rp <= r) {

    if (sgn) q[x].insert(v);

    else q[x].erase(v);

    return;

  }

  int mid = (lp + rp) >> 1;

  modify(l,r,v,sgn,x<<1,lp,mid);

  modify(l,r,v,sgn,x<<1|1,mid+1,rp);

}

void add(int id,int sgn) {

  int l = lower_bound(tmp.begin(),tmp.end(),dat[id].x - dat[id].y) - tmp.begin() + 1;

  int r = upper_bound(tmp.begin(),tmp.end(),dat[id].x + dat[id].y) - tmp.begin();

  modify(l,r,id,sgn);

}

void query(int p,int x=1,int lp=1,int rp=n) {

  if (lp > p || rp < p) return;

  for (set<int>::iterator t = q[x].begin() ; t != q[x].end() ; ++ t)

    ins.push_back(*t);

  if (lp == rp) return;

  int mid = (lp + rp) >> 1;

  if (p <= mid) query(p,x<<1,lp,mid);

  else query(p,x<<1|1,mid+1,rp);

}

int doit(int a,int b) {

  ins.clear();

  int p = lower_bound(tmp.begin(),tmp.end(),a) - tmp.begin() + 1;

  query(p);

  for (int i = 0 ; i < (int)ins.size() ; ++ i) {

    if (cir[ins[i]].inside(a,b)) {

      add(ins[i],0);

      return ins[i];

    }

  }

  return -1;

}

int main() {

  scanf("%d",&n);

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

    scanf("%d%d%d",&dat[i].tp,&dat[i].x,&dat[i].y);

    if (dat[i].tp == 2)

      tmp.push_back(dat[i].x);

    else cir[i].x = dat[i].x, cir[i].y = dat[i].y;

  }

  sort(tmp.begin(),tmp.end());

  tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());

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

    if (dat[i].tp == 1)

      add(i,1);

    else printf("%d\n",doit(dat[i].x,dat[i].y));

  }

  return 0;

}

C - Connections

类比targan，我们考虑构造一棵dfs树。那么，单靠dfs树上的这些边，我们就能保证从根结点能到达任意一个结点。然后就只用让任意一个结点都能到达根结点就好了。于是我们在反图上以同样的点为根结点建dfs树（反图仍然强连通），把这两棵树并在一起，边数最多为\(2n-2\)，能满足本题要求。

时间复杂度\(O(n)\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n,m,a[N],b[N],ned[N],vis[N];

struct edge {

  int la,b,id;

};

struct tree {

  edge con[N << 1];

  int tot,fir[N];

  void add(int from,int to,int num) {

    con[++tot] = (edge) {fir[from],to,num};

    fir[from] = tot;

  }

  void init() {

    tot = 0;

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

      fir[i] = 0;

  }

  void dfs(int pos) {

    vis[pos] = 1;

    for (int i = fir[pos] ; i ; i = con[i].la) {

      if (vis[con[i].b]) continue;

      ned[con[i].id] = 1;

      dfs(con[i].b);

    }

  }

} g,ig;

int main() {

  int T;

  scanf("%d",&T);

  while (T --) {

    scanf("%d%d",&n,&m);

    g.init();

    ig.init();

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

      scanf("%d%d",&a[i],&b[i]), g.add(a[i],b[i],i), ig.add(b[i],a[i],i), ned[i] = 0;

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

      vis[i] = 0;

    g.dfs(1);

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

      vis[i] = 0;

    ig.dfs(1);

    for (int i = 1, j = 1 ; i <= m && j <= m - 2 * n ; ++ i)

      if (!ned[i]) printf("%d %d\n",a[i],b[i]), ++ j;

  }

  return 0;

}

I - Interactive Sort

首先一个重要的性质：数据随机。

考虑通过偶数比较来把奇数排序。假如我们把任意一个偶数与所有奇数比较，那么我们就能够把奇数分成两组，并且得出这个偶数是什么。把一些数随机地分为两组，这与快速排序十分相似。因此，我们希望能避免把每个偶数都与所有奇数比较。

假设我们现在已经把奇数分为\(k\)组，那么，对于我们新取出的一个偶数\(x\)，其中至少有\(k-1\)组满足其中所有元素都大于（或小于）\(x\)。然而，具体地确定被\(x\)划分的是哪一组是很困难的，因为那一组有的元素大于\(x\)，有的小于。那我们不妨就只确定到两组，这个可以用二分实现。然后我们就把两组划分为三组。

这个算法本质就是快速排序，只不过多了二分查找。

然后粗糙计算一下询问次数的常数。把两组划分为三组相较于把一组划分为两组大概是2倍常数，二分查找估计为常数加1。快排期望复杂度的常数是2，故这个算法的常数可以认为是5。对于\(n=5000\)，常数为5的\(O(n \log n)\)次询问，不会超出本题的限制。

时间复杂度上，暴力维护分组是\(O(n^2)\)的，可以用数据结果做到\(O(n \log^2 n)\)。

#include <bits/stdc++.h>

#define gc() getchar()

using namespace std;

const int N = 10010;

struct data {

  int l,r;

} dat[N];

int n,cnt,a[N],tmp[N],tcnt,ans[N];

int ask(int x,int y) {

  char tmp;

  printf("? %d %d\n",x,y);

  fflush(stdout);

  for (tmp = gc() ; tmp != '<' && tmp != '>' ; tmp = gc());

  return tmp == '<';

}

int main() {

  int l,r,mid,p,num;

  scanf("%d",&n);

  for (int i = 1 ; i <= (n+1)/2 ; ++ i) a[i] = i;

  dat[1] = (data) {1,(n+1)/2};

  cnt = 1;

  for (int i = 1 ; i <= n/2 ; ++ i) {

    l = 1, r = cnt;

    while (l + 1 < r) {

      mid = (l + r) >> 1;

      if (ask(i,a[dat[mid].l])) r = mid;

      else l = mid;

    }

    p = dat[l].l;

    num = tcnt = 0;

    for (int j = dat[l].l ; j <= dat[l].r ; ++ j)

      if (ask(i,a[j])) tmp[++tcnt] = a[j];

      else a[p++] = a[j], num ++;

    for (int j = 1 ; j <= tcnt ; ++ j)

      a[p+j-1] = tmp[j];

    if (num != 0 && num != dat[l].r - dat[l].l + 1) {

      ans[i] = (num + dat[l].l-1) << 1;

      ++ cnt;

      for (int j = cnt ; j >= l + 2 ; -- j)

	      dat[j] = dat[j-1];

      dat[l+1] = (data) {dat[l].l + num,dat[l].r};

      dat[l] = (data) {dat[l].l,dat[l].l + num - 1};

      continue;

    }

    if (l == r) {

      ans[i] = n;

      continue;

    }

    p = dat[r].l;

    num = tcnt = 0;

    for (int j = dat[r].l ; j <= dat[r].r ; ++ j)

      if (ask(i,a[j])) tmp[++tcnt] = a[j];

      else a[p++] = a[j], num ++;

    for (int j = 1 ; j <= tcnt ; ++ j)

      a[p+j-1] = tmp[j];

    ans[i] = (num + dat[r].l - 1) << 1;

    if (num == 0 || num == dat[r].r - dat[r].l + 1) continue;

    ++ cnt;

    for (int j = cnt ; j >= r + 2 ; -- j)

      dat[j] = dat[j-1];

    dat[r+1] = (data) {dat[r].l + num,dat[r].r};

    dat[r] = (data) {dat[r].l,dat[r].l + num - 1};

  }

  printf("!");

  for (int i = 1 ; i <= n/2 ; ++ i)

    printf(" %d",ans[i]);

  for (int i = 1 ; i <= (n+1)/2 ; ++ i)

    ans[a[i]] = (i<<1) - 1;

  for (int i = 1 ; i <= (n+1)/2 ; ++ i)

    printf(" %d",ans[i]);

  puts("");

  return 0;

}

L - Laminar Family

这题有多个做法，这里仅涉及我本人的做法。

我们考虑按长度从大到小枚举路径，那么当我们枚举到路径\(k\)时，我们就不需要考虑\(k\)包含其他路径的情况，因为能被\(k\)包含的路径还没加进来。那么，\(k\)这一条路径要么已经完全被其他另一条路径覆盖了，要么完全没被覆盖。于是，我们枚举路径时对这条路径上的所有结点都染色（不同路径的颜色不同），那么答案是Yes就等价于，对于所有路径，它上面的结点在染上它的颜色之前的颜色都是相同的（或都没有颜色）。这个可以用树链剖分+线段树实现。

时间复杂度\(O(n \log ^2 n)\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

struct edge {

  int la,b;

} con[N << 1];

int tot,fir[N];

void add(int from,int to) {

  con[++tot] = (edge) {fir[from],to};

  fir[from] = tot;

}

int fa[N],sz[N],hson[N],top[N],dfn[N],dep[N],cnt,n,m,ans;

void dfs_init(int pos) {

  dep[pos] = dep[fa[pos]] + 1;

  sz[pos] = 1;

  for (int i = fir[pos] ; i ; i = con[i].la) {

    if (con[i].b == fa[pos]) continue;

    fa[con[i].b] = pos;

    dfs_init(con[i].b);

    sz[pos] += sz[con[i].b];

    if (sz[con[i].b] > sz[hson[pos]])

      hson[pos] = con[i].b;

  }

}

void dfs_build(int pos,int tp) {

  top[pos] = tp;

  dfn[pos] = ++cnt;

  if (hson[pos]) dfs_build(hson[pos],tp);

  for (int i = fir[pos] ; i ; i = con[i].la) {

    if (con[i].b == fa[pos] || con[i].b == hson[pos])

      continue;

    dfs_build(con[i].b,con[i].b);

  }

}

int lca(int x,int y) {

  while (top[x] != top[y]) {

    if (dep[top[x]] < dep[top[y]]) swap(x,y);

    x = fa[top[x]];

  }

  if (dep[x] > dep[y]) swap(x,y);

  return x;

}

struct node {

  int tag,val;

} t[N << 2];

inline void puttag(int x,int v) {

  t[x].tag = v;

  t[x].val = v;

}

void push_down(int x) {

  if (!t[x].tag) return;

  puttag(x<<1,t[x].tag);

  puttag(x<<1|1,t[x].tag);

  t[x].tag = 0;

}

inline int merge(int x,int y) {

  if (x == -2) return y;

  if (y == -2) return x;

  if (x == -1 || y == -1) return -1;

  if (x != y) return -1;

  return x;

}

void push_up(int x) {

  if (t[x].tag) push_down(x);

  t[x].val = merge(t[x<<1].val,t[x<<1|1].val);

}

void modify(int l,int r,int v,int x=1,int lp=1,int rp=n) {

  if (l > rp || r < lp) return;

  if (lp >= l && rp <= r)

    return (void)(puttag(x,v));

  int mid = (lp + rp) >> 1;

  push_down(x);

  modify(l,r,v,x<<1,lp,mid);

  modify(l,r,v,x<<1|1,mid+1,rp);

  push_up(x);

}

int query(int l,int r,int x=1,int lp=1,int rp=n) {

  if (l > rp || r < lp) return -2;

  if (lp >= l && rp <= r)

    return t[x].val;

  int mid = (lp + rp) >> 1;

  push_down(x);

  return merge(query(l,r,x<<1,lp,mid),query(l,r,x<<1|1,mid+1,rp));

}

bool doit(int x,int y,int id) {

  int res = 1, tmp = -2;

  while (top[x] != top[y]) {

    if (dep[top[x]] < dep[top[y]]) swap(x,y);

    tmp = merge(tmp,query(dfn[top[x]],dfn[x]));

    if (tmp == -1) res = 0;

    modify(dfn[top[x]],dfn[x],id);

    x = fa[top[x]];

  }

  if (dep[x] < dep[y]) swap(x,y);

  tmp = merge(tmp,query(dfn[y],dfn[x]));

  if (tmp == -1) res = 0;

  modify(dfn[y],dfn[x],id);

  return res;

}

struct data {

  int u,v,len;

  bool operator < (const data& x) const {

    return len > x.len;

  }

} dat[N];

int main() {

  int a,b,c;

  scanf("%d%d",&n,&m);

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

    scanf("%d%d",&a,&b);

    add(a,b);

    add(b,a);

  }

  dfs_init(1);

  dfs_build(1,1);

  for (int i = 1 ; i <= m ; ++ i) {

    scanf("%d%d",&a,&b);

    c = lca(a,b);

    dat[i] = (data) {a,b,dep[a] + dep[b] - 2 * dep[c]};

  }

  sort(dat+1,dat+m+1);

  ans = 1;

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

    ans &= doit(dat[i].u,dat[i].v,i);

  if (ans) puts("Yes");

  else puts("No");

  return 0;

}

小结：还有好几道题根本没法补……感觉自己缺少创造性的思维，也许是应该多做这种类型的题目了。

巴特西

【做题】neerc2017的A、C、I、L

A - Archery Tournament

C - Connections

I - Interactive Sort

L - Laminar Family

最新文章

热门文章