首页 > 其他分享 >P9170 [省选联考 2023] 填数游戏 题解

P9170 [省选联考 2023] 填数游戏 题解

时间:2024-02-09 18:11:41浏览次数:29  
标签:circ 省选 题解 void kMaxN id int Bob 联考

Description

众所周知,Alice 和 Bob 是一对好朋友。今天,他们约好一起玩游戏。

一开始,他们各自有一张空白的纸条。接下来,他们会在纸条上依次写 \(n\) 个 \([1,m]\) 范围内的正整数。等 Alice 写完,Bob 在看到 Alice 写的纸条之后开始写他的纸条

Alice 需要保证她写下的第 \(i\) 个数在集合 \(S_{i}\) 中,Bob 需要保证他写下的第 \(i\) 个数在集合 \(T_{i}\) 中。题目保证 \(1 \leq\left|S_{i}\right|,\left|T_{i}\right| \leq 2\) 。

Alice 喜欢相同,因此,她希望她写下的数与 Bob 写下的数对应位置相同的个数尽量多。Bob 喜欢不同,因此,他希望他写下的 \(n\) 个数 \(b_{1}, \ldots, b_{n}\) 互不相同。在此基础上,Bob 希望他写下的数与 Alice 写下的数对应位置相同的个数尽量少。

即设 Alice 写下的数为 \(a_{1}, \ldots, a_{n}\),Bob 写下的数为 \(b_{1}, \ldots, b_{n}\),记 \(X\) 为满足 \(1 \leq i \leq n, a_{i}=b_{i}\) 的下标 \(i\) 的个数,则

  • Alice 希望最大化 \(X,\)
  • Bob 在保证 \(b_{1}, \ldots, b_{n}\) 互不相同的前提下希望最小化 \(X\)。

你首先想知道 Bob 能否保证他写下的 \(n\) 个数互不相同。如果 Bob 能够做到,你想知道在双方均采取最优策略的前提下 \(X\) 的值会是多少。

\(n,m\leq 10^6,\sum n,\sum m\leq 1.5\times 10^6\)。

Solution

这题 Bob 在看到 Alice 写的纸条之后才开始写他的纸条!!

先做特殊性质 A。这个就是让你判断 \(b_1,\dots,b_n\) 能否互不相同。

考虑把所有 \(T_{i,0}\) 和 \(T_{i,1}\) 连边(如果 \(|T|=1\),就连一条 \(T_{i,0}\) 的自环),题目就转化为将一个图中的边定向,使得每个点的入度不超过 \(1\)。

容易发现对于每个连通块,如果边数大于点数就一定不合法,否则这个连通块是个树或者基环树,一定合法。


然后考虑怎么对一个基环树求答案。

容易发现基环树除掉环的边的方向是定好的,只有环上的边有两种可能。设环的大小为 \(k\)。

所以 Alice 就只要在这 \(k\) 条边对应的 \(k\) 个集合中每个集合选一个数,使得两种方向答案的 \(\min\) 值最大。

首先对于 \(|S_i\cap T_i|=0\) 的边,显然没有贡献。\(|S_i\cap T_i|=1\) 的边,肯定选择那个交的数,这相当于已经确定了选的数。\(|S_i\cap T_i|=2\) 的边,就只能对于两种方向的一种产生贡献。

设 \(c_u\) 表示已经确定的数中第一种方向已有的贡献,\(c_u\) 表示已经确定的数中第二种方向已有的贡献,\(c\) 表示待确定的集合数量。

那么答案就是:

\[\max_{i=0}^{c}{\left\{\min\{c_u+i,c_v+c-i\}\right\}} \]

这个暴力求就行了。

这一部分的时间复杂度:\(O(n)\)。


然后考虑树的情况。

显然定向方式就是选定一个点作为根的外向树。

对于交为 \(1\) 的边 \(u\to v\),如果 \(u\) 是交的数,那么根一定在 \(v\) 的子树里,否则根一定在 \(v\) 的子树外。

这一部分的贡献可以用 dfs 序上差分维护。

设 \(f_i\) 表示以 \(i\) 为根的答案。

然后题目转化为对于所有交为 \(2\) 的边 \(u\to v\),要选择把 \(v\) 子树内或子树外的 \(f\) 全加一,使得最后 \(\min\{f_1,\dots,f_n\}\) 最大。

观察可知如果两个点他们要将 \(f\) 加一的集合不交,则把这两个集合都换成原来的补集一定更优。

所以对于两个点 \(u,v\),如果 \(u\) 是 \(v\) 的祖先,那么不能出现 \(u\) 选子树外和 \(v\) 选子树内的情况。如果 \(u\) 不是 \(v\) 祖先,那么不能出现 \(u\) 和 \(v\) 都选子树外。

于是根据这两个性质可以得到选子树的点一定构成一个到根的链,然后 dfs 一边用线段树维护答案即可。

这一部分的时间复杂度:\(O(n\log n)\)。

所以总的时间复杂度就是 \(O(n\log n)\)。

Code

#include <bits/stdc++.h>

// #define int int64_t

namespace FASTIO {
char ibuf[1 << 21], *p1 = ibuf, *p2 = ibuf;
char getc() {
  return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template<class T> bool read(T &x) {
  x = 0; int f = 0; char ch = getc();
  while (ch < '0' || ch > '9') f |= ch == '-', ch = getc();
  while (ch >= '0' && ch <= '9') x = (x * 10) + (ch ^ 48), ch = getc();
  x = (f ? -x : x); return 1;
}
template<typename A, typename ...B> bool read(A &x, B &...y) { return read(x) && read(y...); }
 
char obuf[1 << 21], *o1 = obuf, *o2 = obuf + (1 << 21) - 1;
void flush() { fwrite(obuf, 1, o1 - obuf, stdout), o1 = obuf; }
void putc(char x) { *o1++ = x; if (o1 == o2) flush(); }
template<class T> void write(T x) {
  if (!x) putc('0');
  if (x < 0) x = -x, putc('-');
  char c[40]; int tot = 0;
  while (x) c[++tot] = x % 10, x /= 10;
  for (int i = tot; i; --i) putc(c[i] + '0');
}
void write(char x) { putc(x); }
void write(char *x) { while (*x) putc(*x++); }
void write(const char *x) { while (*x) putc(*x++); }
template<typename A, typename ...B> void write(A x, B ...y) { write(x), write(y...); }
struct Flusher {
  ~Flusher() { flush(); }
} flusher;
} // namespace FASTIO
using FASTIO::read; using FASTIO::putc; using FASTIO::write;

const int kMaxN = 1e6 + 5;

int n, m;
int cnt[kMaxN], fa[kMaxN], sz[kMaxN], cnted[kMaxN];
std::vector<int> s[kMaxN], t[kMaxN];
std::vector<std::pair<int, int>> G[kMaxN];

int find(int x) {
  return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void unionn(int x, int y) {
  int fx = find(x), fy = find(y);
  if (fx != fy) {
    fa[fx] = fy, sz[fy] += sz[fx], cnted[fy] += cnted[fx];
  }
  ++cnted[fy];
}

void addedge(int u, int v, int id) {
  G[u].emplace_back(v, id), unionn(u, v);
  if (u != v) G[v].emplace_back(u, id);
}

namespace Cycle {
int res, p[kMaxN], pid[kMaxN], dep[kMaxN];
bool vis[kMaxN], onc[kMaxN];
std::vector<int> circ, circ_v;

void clear() {
  std::fill_n(vis + 1, m, 0);
  std::fill_n(onc + 1, m, 0);
  std::fill_n(p + 1, m, 0);
}

void dfs1(int u, int fa, int faid) {
  p[u] = fa, dep[u] = dep[fa] + 1, vis[u] = 1;
  for (auto [v, id] : G[u]) {
    if (id == faid) continue;
    if (!vis[v]) {
      pid[v] = id, dfs1(v, u, id);
    } else if (dep[u] >= dep[v]) {
      for (int i = u; i != v; i = p[i]) {
        circ.emplace_back(pid[i]);
        circ_v.emplace_back(i);
        onc[i] = 1;
      }
      circ.emplace_back(id), onc[v] = 1, circ_v.emplace_back(v);
    }
  }
}

void dfs2(int u, int fa) {
  for (auto [v, id] : G[u]) {
    if (v == fa || onc[v]) continue;
    res += (v == s[id][0] || v == s[id].back());
    dfs2(v, u);
  }
}

int solve(int rt) {
  res = 0, circ.clear(), circ_v.clear(), dfs1(rt, 0, 0);
  for (auto x : circ_v) dfs2(x, 0);
  assert(circ.size() == circ_v.size());
  int cu = 0, cv = 0, c = 0;
  for (int i = 0; i < circ.size(); ++i) {
    if (cnt[circ[i]] == 1) {
      if (circ_v[i] == s[circ[i]][0] || circ_v[i] == s[circ[i]].back()) ++cu;
      else ++cv;
    } else if (cnt[circ[i]] == 2) {
      ++c;
    }
  }
  if (circ.size() == 1) c *= 2;
  return res + (abs(cu - cv) <= c ? (cu + cv + c) / 2 : std::min(cu, cv) + c);
}
} // namespace Cycle

namespace Tree {
struct SGT {
  int mi[kMaxN * 4], tag[kMaxN * 4];

  void pushup(int x) {
    mi[x] = std::min(mi[x << 1], mi[x << 1 | 1]);
  }

  void addtag(int x, int v) {
    mi[x] += v, tag[x] += v;
  }

  void pushdown(int x) {
    if (!tag[x]) return;
    addtag(x << 1, tag[x]), addtag(x << 1 | 1, tag[x]);
    tag[x] = 0;
  }

  void build(int x, int l, int r) {
    mi[x] = tag[x] = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
  }

  void update(int x, int l, int r, int ql, int qr, int v) {
    if (l > qr || r < ql) {
      return;
    } else if (l >= ql && r <= qr) {
      return addtag(x, v);
    }
    pushdown(x);
    int mid = (l + r) >> 1;
    update(x << 1, l, mid, ql, qr, v), update(x << 1 | 1, mid + 1, r, ql, qr, v);
    pushup(x);
  }
} sgt;

int res, dfnc;
int dfn[kMaxN], sz[kMaxN];

void dfs1(int u, int fa) {
  dfn[u] = ++dfnc, sz[u] = 1;
  for (auto [v, id] : G[u]) {
    if (v == fa) continue;
    dfs1(v, u);
    sz[u] += sz[v];
  }
}

void dfs2(int u, int fa) {
  for (auto [v, id] : G[u]) {
    if (v == fa) continue;
    if (cnt[id] == 1) {
      if (v == s[id][0] || v == s[id].back()) {
        sgt.update(1, 1, dfnc, 1, dfn[v] - 1, 1), sgt.update(1, 1, dfnc, dfn[v] + sz[v], dfnc, 1);
      } else {
        sgt.update(1, 1, dfnc, dfn[v], dfn[v] + sz[v] - 1, 1);
      }
    } else if (cnt[id] == 2) {
      sgt.update(1, 1, dfnc, 1, dfn[v] - 1, 1), sgt.update(1, 1, dfnc, dfn[v] + sz[v], dfnc, 1);
    }
    dfs2(v, u);
  }
}

void dfs3(int u, int fa) {
  res = std::max(res, sgt.mi[1]);
  for (auto [v, id] : G[u]) {
    if (v == fa) continue;
    if (cnt[id] == 2) {
      sgt.update(1, 1, dfnc, 1, dfn[v] - 1, -1);
      sgt.update(1, 1, dfnc, dfn[v] + sz[v], dfnc, -1);
      sgt.update(1, 1, dfnc, dfn[v], dfn[v] + sz[v] - 1, 1);
    }
    dfs3(v, u);
    if (cnt[id] == 2) {
      sgt.update(1, 1, dfnc, 1, dfn[v] - 1, 1);
      sgt.update(1, 1, dfnc, dfn[v] + sz[v], dfnc, 1);
      sgt.update(1, 1, dfnc, dfn[v], dfn[v] + sz[v] - 1, -1);
    }
  }
}

int solve(int rt) {
  res = dfnc = 0;
  dfs1(rt, 0);
  sgt.build(1, 1, dfnc);
  dfs2(rt, 0), dfs3(rt, 0);
  return res;
}
} // namespace Tree

void dickdreamer() {
  read(n, m);
  for (int i = 1; i <= m; ++i) {
    G[i].clear();
    fa[i] = i, sz[i] = 1, cnted[i] = 0;
  }
  Cycle::clear();
  for (int i = 1; i <= n; ++i) {
    int c;
    read(c);
    s[i].clear();
    for (int j = 1; j <= c; ++j) {
      int x;
      read(x);
      s[i].emplace_back(x);
    }
  }
  for (int i = 1; i <= n; ++i) {
    int c;
    read(c);
    cnt[i] = 0, t[i].clear();
    for (int j = 1; j <= c; ++j) {
      int x;
      read(x);
      t[i].emplace_back(x);
      for (auto y : s[i]) cnt[i] += (x == y);
    }
    if (c == 1) cnt[i] *= 2;
    if (c == 1) addedge(t[i][0], t[i][0], i);
    else addedge(t[i][0], t[i][1], i);
  }
  int ans = 0;
  for (int i = 1; i <= m; ++i) {
    if (i == find(i)) {
      if (cnted[i] > sz[i]) return void(write("-1\n"));
      else if (cnted[i] == sz[i]) ans += Cycle::solve(i);
      else ans += Tree::solve(i);
    }
  }
  write(ans, '\n');
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  int T = 1;
  read(T);
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

标签:circ,省选,题解,void,kMaxN,id,int,Bob,联考
From: https://www.cnblogs.com/Scarab/p/18012546

相关文章

  • P9478 [NOI2023] 方格染色题解
    题解对于行操作,列操作和对角线操作,实际上仅仅只是在对若干个矩形求面积并而已,这是裸的扫描线题,套用模板即可,此时注意到对角线操作实际上是\(O(n)\)量级的矩阵面积并,因此复杂度是\(O(n\logq+q\logq)\)的量级,只能获得95pts。显然,面积并具有交换性,我们先做\(O(q\logq)\)......
  • uoj839 龙门题字 题解
    题目链接点击打开链接题目解法呜呜呜,我考场上只会\(60\),不会优化,没救了要求字典序最大,不难想到一位一位钦定,那么我们现在的问题是判断\(ans_1,...,ans_i\)是否合法,记\(ok_{i,j}\)表示第\(i\)个修改在第\(j\)位是否可行(即\(x_{i,j}\geans_j\)),同时记\(cnt_i\)为第......
  • 2024大试牛刀5题解
    鼠鼠我鸭没学过前缀和的自己去补一下,这里不过多赘述(其实是我不想写)以第二组数据为例:类型0100体重2565先计算出不使用魔法时鸭鸭的重量,当作基础值\(ori=5\)。然后来看看对一段区间使用魔法会造成什么效果:类型0100体重2565变化a+2-5......
  • ABC338G题解
    也许是一个简单一点的做法?假如我们要求一个表达式的值,我们求的顺序显然是,按照加号划分为若干段,段内只有数字和乘号,计算出段内结果后全部加起来。称一个只有数字和乘号的表达式是基本表达式,我们将每个表达式的贡献拆分为若干个基本表达式之和,那么我们就可以枚举每个基本表达式,算......
  • CF516D Drazil and Morning Exercise 题解
    Description给定一棵\(n\)个点的树,边有边权。定义\(f_x=\max_{i=1}^n\text{dist}(x,i)\)。\(q\)次询问最大的满足\(\max_{x\ins}f_x-\min_{x\ins}f_x\lel\)的连通块\(s\)包含的点数。\(n\le10^5\),\(q\le50\)。Solution这里\(f_u\)显然可以用换......
  • CF1771F Hossam and Range Minimum Query 题解
    题目链接:CF或者洛谷比较不错的题,出现奇数次出现的这种问题,比较容易想到一种运算,那就是异或和运算。如果一个区间上一个数出现偶数次,则它对于异或和的贡献为\(0\),那么很显然,我们维护下区间异或和即可判断一个区间上是否存在出现奇数次的数。然后我们注意到\(1\oplus2\oplu......
  • CF1861E Non-Intersecting Subpermutations 题解
    简要题意一个长度为\(n\)的元素在\([1,k]\)的整数序列\(a\)的价值定义如下。初始\(i=1\),如果\(a_{i\simi+k-1}\)包含了\(1\simk\)的所有整数,则价值加\(1\),然后令\(i=i+k\)。如果没有包含\(1\simk\)的所有整数则\(i=i+1\),直到\(i\geqn-k+2\)时结束。......
  • CF1863F Divide, XOR, and Conquer 题解
    简要题意你有两个指针\(l,r\)初始时\(l=1,r=n\)。你可以操作若干次知道\(l=r\)。每次操作你可以选择一个整数\(k\in[l,r)\),记\(x=\bigoplus_{i=l}^ka_i,y=\bigoplus_{i=k+1}^ra_i\)。如果\(x\leqy\),你可以令\(l=k+1\)。如果\(x\geqy\),你可以令\(r=k\)。......
  • P9663 Permutation on Tree 题解
    考虑枚举一个\(x\in[1,n)\),将\(\leqx\)的看作\(0\),\(>x\)的看作\(1\),那么一个排列的贡献实际上就是\(\sum_{x=1}^{n-1}\sum[[p_i\leqx]+[p_{i+1}>x]=1]\)。那么问题转变为一个给定一棵树,每一个点有权值\(0\)或\(1\),求所有排布方案的贡献之和。设\(f_x\)表示......
  • P9697 Canvas 题解
    首先观察到有一个关键性质是\(1\leqx_i,y_i\leq2\)。那么我们贪心的考虑我们肯定会将\((x,y)=(1,1)\)的在一开始操作,\((x,y)=(2,2)\)的最后操作。也就是说现在没有固定的是\((x,y)=(1,2)\)和\((x,y)=(2,1)\)的。我们不妨令\((x,y)=(1,2)\),然后连边\((l,r)\)。然......