NOI Online 2022

本文主要是介绍NOI Online 2022，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

P8251 [NOI Online 2022 提高组] 丹钓战

给出长度为 \(n\) 的数列，每个元素是一个二元组 \((a_i,b_i)\)。同时有一个栈 \(S\)，向栈中加入元素 \((a_i,b_i)\) 时会一直弹出满足 \(a_i=a_j\) 或 \(b_i\geq b_j\) 的栈顶元素 \((a_j,b_j)\)，然后将其加入 \(S\) 中。

若一个二元组加入 \(S\) 后满足 \(S\) 仅有其一个元素，则称其为 "成功的"。

有 \(q\) 个询问，每次询问区间 \([l,r]\) 的二元组依次入栈，会有几个是 "成功的"。询问独立。

\(n,q\leq 5\times 10^5\)。

我们模拟题意先花费 \(\Theta(n)\) 的时间对整个数列进行一次操作，那么元素 \(x_i\) 入栈后分为两种情况：

1. 此时 \(S\) 仅有 \(x_i\) 一个元素，那么无论询问取哪个区间，\(x_i\) 都是成功的。

2. 此时 \(S\) 有多于一个元素，设此时 \(S\) 中 \(x_i\) 下方阻挡它成功的元素为 \(x_j\)，\(j<i\)，那么 \(x_i\) 在询问时成功当且仅当 \(x_j\) 不在询问区间中。

所以在模拟时我们可以维护出一个 \(\mathrm{f}[i]=j\)，若 \(x_i\) 成功则 \(\mathrm{f}[i]=0\)。

询问转化为询问一个区间中有多少元素小于区间左端点。可以主席树维护。

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

P8252 [NOI Online 2022 提高组] 讨论

给出 \(n\) 个集合，求这 \(n\) 个集合是否存在两个集合是交叉关系。

\(n\leq 10^6\)，所有集合中的元素个数 \(\leq 2\times 10^6\)，元素的值域为 \(n\)。

设 \(A,B\) 满足交叉关系则 \(A\cap B\neq\emptyset\)，\(A\nsubseteq B\) 且 \(B\nsubseteq A\)。也就是存在交且不包含。

我们按照集合大小从大到小遍历，维护一个 \(\mathrm{map}[x]\) 表示元素 \(x\) 当前所遍历到的最小的所属集合，初始为 \(0\)。

设当前集合为 \(S_i\)，若 \(\forall x\in S_i,\ \mathrm{map}[x]=0\)，那么这表示 \(S_i\) 与之前的所有集合都没有交。

若 \(\forall x\in S_i,\ \mathrm{map}[x]\) 都相等，那么这表示 \(S_i\) 中的所有元素都被另一个更大的集合所包含，意味着 \(S_i\) 被之前的一个集合包含了。

否则若 \(\mathrm{map}[x]\) 中有不同的，我们随意取出两个，设这两个跟 \(S_i\) 有交的集合为 \(A,B\)，\(|A|\geq|B|\)，那么 \(S_i,B\) 就是一组解。

证明，显然 \(A,B\) 要么没有交，要么互相包含。

这篇关于NOI Online 2022的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！