LOJ 3161「NOI2019」I 君的探险「交互」「随机化」

LOJ #3161. 「NOI2019」I 君的探险

测试点 \(1\) 至 \(5\):

暴力,每次改变点 \(i\) 的状态,查看 \(i + 1...n\) 哪些点状态改变了,改变了说明有边。

注意 modify 只有 \(n - 1\) 次机会,请别碰 \(n - 1\) 号结点!!

可获得 \(20\ \rm pts\)。

测试点 \(6\) 至 \(9\):

数据保证 \(n\) 个点形成 \(n/2\) 个匹配,询问次数上界 \(n \log n\) 和 \(q \log n\)。

考虑整体二分,solve(l, r, ql, qr) 表示询问 \([ql,qr]\) 中答案在 \([l,r]\) 里,取中点 mid,每次修改 \(l...mid\),对于询问 \(x\),如果 \(x\in[l,mid]\) 和 \(x\) 状态改变这两个条件满足了恰好一个,说明 \(x\) 的连边在 \([l,mid]\) 中,递归到左边,其他递归到右边。

有个小问题是状态无法及时更新。即我们在修改 \([l,mid]\) 时,可能把 \([r + 1, n]\) 中的一些点状态改变了,而无法更新这个状态。没有关系,对于边 \((x,y),x<y\),我们分治到 \(x\) 时就统计答案。

结合前面的算法可获得 \(36\ \rm pts\)。

(好像我这个做法比较烦人,但 modify 次数为上界的一半)

测试点 \(10\) 至 \(11\)

数据保证形成树且父亲结点编号比儿子小,询问次数上界 \(n \log n\) 和 \(q \log n\)。

还是整体二分,考虑询问 \(x\),若 \(x\leq mid\) 直接分到右边,否则我们把 \([l,mid]\) modify 一次,看 \(x\) 是否为 \(1\),是则分到左边,否则分到右边。然后再把 \([l,mid]\) modify 回来。一开始脑抽了,没发现这样写只调用了区间长度次 modify,还以为有个二倍常数过不去。

结合前面的算法可获得 \(44\ \rm pts\)。

测试点 \(12\) 至 \(14\)

数据保证形成链,询问次数限制 \(10^7\)(相当于不 TLE 就行)。

考虑按二进制位做,对于第 \(k\) 位,把该位为 \(1\) 的结点 modify。询问完再改回去。

对于该位为 \(1\) 的结点:

  • 若查询的状态为 \(1\),说明两端该位 xor 为 \(0\)。
  • 若查询的状态为 \(0\),说明两端该位 xor 为 \(1\)。

该位为 \(0\) 的结点同理。这样我们就得到一个点所连两个点的 xor。

暴力询问与 \(0\) 相连的点,然后直接递推就能得到答案了。

结合前面的算法可获得 \(56\ \rm pts\)。

测试点 \(15\) 至 \(17\)

数据保证是树,询问次数 \(10^7\),允许 \(2m\) 次 check。

套有上面的二进制位方法可以求出每个点相邻点编号 xor 和,为了方便标号从 \(1\) 开始,\(u\) 的相邻结点异或和记做 \(p[u]\)。

我们维护一个队列 \(Q\),初始时加入 \(1,2,3,...,n\)。

每次取出队列的 front,记做 \(u\),通过 modify + query + modify 检查 \(u\) 和 \(p[u]\) 之间是否有边,若有边就 report,然后把 \(p[p[u]]\) 异或上 \(u\),让 \(p[u]\) 加入队列,再令 \(p[u] = 0\),也就是把这条边断了,一直做到队列为空。

由于某个叶子都会往上删,直到把所在连通块删完,做法正确。复杂度也是有保证的,初始 \(n\) 个点,每断一条边才会做 push 操作,也就是我们最多取 front \(n+m\) 次。

注意要判重边,因为可能有 \(u,v\) 互相删的情况。

另外我感觉使用 check 做也是 ok 的,没有仔细想。

结合前面的算法可获得 \(68\ \rm pts\)。

测试点 \(18\) 到 \(25\)(正解)

好,现在非常高兴地告诉你前面的东西和正解没关系

类似测试点 \(6\) 到 \(9\) 做整体二分,先通过 random_shuffle 随机打乱结点编号,然后每个点仿照之前的方法“找父亲”,但要注意询问点的状态要消除了已 report 的点的影响。

我们每一轮把 check = 0 的结点加入询问, random_shuffle 后做上面所述的整体二分。

证明毫无头绪,网上也没什么资料。

结合前面的算法可获得 \(100\ \rm pts\)。

代码

实现了上述所有 subtask。

#include "explore.h"
#include <bits/stdc++.h>
#define pb push_back
#define rep(i, j, k) for(int i = j; i <= k; ++ i)
#define per(i, j, k) for(int i = j; i >= k; -- i)
using namespace std;

const int N = 2e5 + 10;

namespace task1 {

int st[N];
void main(int n) {
   rep(i, 0, n - 2) {
      modify(i);
      st[i] ^= 1;
      rep(j, i + 1, n - 1) {
         if(query(j) ^ st[j]) {
            st[j] ^= 1;
            report(i, j);
         }
      }
   }
}

}

namespace task2 {

int st[N], q[N], t1[N], t2[N];
bool use[N];
void solve(int l, int r, int ql, int qr) {
   if(ql > qr || l > r) return ;
   if(l == r) {
      rep(i, ql, qr) if(!use[min(q[i], l)]) {
         use[min(q[i], l)] = 1;
         report(q[i] - 1, l - 1);
         break ;
      }
      return ;
   }
   int mid = (l + r) >> 1;
   rep(i, l, mid) modify(i - 1);
   int T1 = 0, T2 = 0;
   rep(i, ql, qr) {
      bool diff = 0;
      if(st[q[i]] ^ query(q[i] - 1)) {
         st[q[i]] ^= 1; diff = 1;
      }
      if(diff ^ (l <= q[i] && q[i] <= mid)) t1[++ T1] = q[i];
      else t2[++ T2] = q[i];
   }
   rep(i, 1, T1) q[ql + i - 1] = t1[i];
   rep(i, 1, T2) q[ql + T1 + i - 1] = t2[i];
   solve(l, mid, ql, ql + T1 - 1);
   solve(mid + 1, r, ql + T1, qr);
}
void main(int n) {
   rep(i, 1, n) q[i] = i;
   solve(1, n, 1, n);
}

}

namespace task3 {

int st[N], q[N], t1[N], t2[N];
void solve(int l, int r, int ql, int qr) {
   if(ql > qr || l > r) return ;
   if(l == r) {
      rep(i, ql, qr) {
         report(l - 1, q[i] - 1);
      }
      return ;
   }
   int mid = (l + r) >> 1, T1 = 0, T2 = 0;
   rep(i, l, mid) modify(i - 1);
   rep(i, ql, qr) {
      if(q[i] <= mid || query(q[i] - 1)) t1[++ T1] = q[i];
      else t2[++ T2] = q[i];
   }
   rep(i, l, mid) modify(i - 1);
   rep(i, 1, T1) q[ql + i - 1] = t1[i];
   rep(i, 1, T2) q[ql + T1 + i - 1] = t2[i];
   solve(l, mid, ql, ql + T1 - 1);
   solve(mid + 1, r, ql + T1, qr);
}
void main(int n) {
   report(0, 1);
   rep(i, 3, n) q[i] = i;
   solve(1, n, 3, n);
}

}

namespace task4 {

int p[N];
void get(int u, int la) {
   if(!(la ^ p[u])) return ;
   report(u, la ^ p[u]);
   get(la ^ p[u], u);
}
void main(int n) {
   for(int i = 0; (1 << i) < n; i ++) {
      rep(u, 0, n - 1) if(u >> i & 1) modify(u);
      rep(u, 0, n - 1) if((u >> i & 1) ^ query(u)) p[u] |= 1 << i;
      rep(u, 0, n - 1) if(u >> i & 1) modify(u);
   }
   modify(0);
   int u = -1, v = -1;
   rep(i, 1, n - 1) if(query(i)) u == -1 ? u = i : v = i;
   report(0, u); get(u, 0);
   if(~ v) {
      report(0, v); get(v, 0);
   }
}

}

namespace task5 {

int p[N];
map< pair<int, int>, bool > Map;
bool ins(int x, int y) {
   pair<int, int> p(min(x, y), max(x, y));
   if(Map[p]) return 0;
   return Map[p] = 1;
}
void main(int n) {
   for(int i = 0; (1 << i) <= n; i ++) {
      rep(u, 1, n) if(u >> i & 1) modify(u - 1);
      rep(u, 1, n) if((u >> i & 1) ^ query(u - 1)) p[u] |= 1 << i;
      rep(u, 1, n) if(u >> i & 1) modify(u - 1);
   }
   queue<int> q;
   rep(i, 1, n) q.push(i);
   while(q.size()) {
      int u = q.front(); q.pop();
      if(p[u] >= 1 && p[u] <= n && p[u] != u) {
         modify(p[u] - 1); int t = query(u - 1); modify(p[u] - 1);
         if(t && ins(u, p[u])) {
            report(u - 1, p[u] - 1);
            p[p[u]] ^= u;
            q.push(p[u]);
            p[u] = 0;
         }
      }
   }
}

}

namespace task6 {

int id[N], q[N], cnt, t1[N], t2[N];
bool use[N], st[N];
vector<int> g[N];
int calc(int u) {
   bool tg = query(id[u] - 1);
   for(int j = 0; j < (int) g[id[u]].size(); j ++) tg ^= st[g[id[u]][j]];
   return tg;
}
void solve(int l, int r, int ql, int qr) {
   if(ql > qr) return ;
   if(l == r) {
      rep(i, ql, qr) if(l != q[i]) {
         report(id[l] - 1, id[q[i]] - 1);
         g[id[l]].pb(id[q[i]]);
         g[id[q[i]]].pb(id[l]);
         cnt --;
      }
      return ;
   }
   int mid = (l + r) >> 1;
   rep(i, l, mid) if(!use[id[i]]) modify(id[i] - 1), st[id[i]] = 1;
   int T1 = 0, T2 = 0;
   rep(i, ql, qr) {
      if(q[i] <= mid || calc(q[i])) t1[++ T1] = q[i];
      else t2[++ T2] = q[i];
   }
   rep(i, l, mid) if(!use[id[i]]) modify(id[i] - 1), st[id[i]] = 0;
   rep(i, 1, T1) q[ql + i - 1] = t1[i];
   rep(i, 1, T2) q[ql + T1 + i - 1] = t2[i];
   solve(l, mid, ql, ql + T1 - 1);
   solve(mid + 1, r, ql + T1, qr);
}
void main(int n, int m) {
   srand(202021);
   cnt = m;
   rep(i, 1, n) id[i] = i;
   while(cnt) {
      random_shuffle(id + 1, id + n + 1);
      int qm = 0;
      rep(i, 1, n) if(!use[id[i]]) q[++ qm] = i;
      solve(1, n, 1, qm);
      if(cnt) rep(i, 1, n) if(!use[i] && check(i - 1)) use[i] = 1;
   }
}

}

void explore(int n, int m) {
   if(n <= 500) task1::main(n);
   else if(n % 10 == 8) task2::main(n);
   else if(n % 10 == 7) task3::main(n);
   else if(n % 10 == 6) task4::main(n);
   else if(n % 10 == 5) task5::main(n);
   else task6::main(n, m);
}
上一篇:从0开始写电商项目 vue+gin 前端&后端


下一篇:UOJ Round #11 简要题解