4月AT杂题

AtCoder Beginner Contest 296

D - M<=ab

题意：求最小的正整数，不小于 \(m\)，且能被表示为两个不大于 \(n\) 的正整数的数，不存在输出 -1。\(n,m\le10^{12}\)。

直接枚举 \(a\)，计算最小的满足 \(ab\ge m\) 的 \(b\)，如果 \(a>b\) 则后面的情况一定是重复的。时间复杂度 \(\text{O}(\sqrt m)\)。最好用 __int128 。

E - Transition Game

题意：给一个 \(n\) 个点 \(n\) 条形如 \(i\rightarrow a_i\) 的有向边的图，求有多少个点在环中（包括自环）。\(n,a_i\le2\times10^5\)。

\(\text{tarjan}\) 缩点或者拓扑找环即可。

F - Simultaneous Swap

题意：给你两个数组 \(a,b\)。可以进行任意次如下操作，问最后是否能使 \(a,b\) 数组相等：选择互不相等的 \(i,j,k\)，交换 \(a_i,a_j\) 和 \(b_i,b_k\)。\(n\le2\times10^5\)。

先特判掉数字种类不同的情况。然后有两个结论：\(1.\) 如果数组中存在相同元素则一定可以；\(2.\) 如果两数组逆序对数量奇偶性相同则答案为可以，否则不行。

可以发现操作四次就是选择 \((i,j,k,l)\)，交换 \(b_i,b_j\) 和 \(b_k,b_l\)。我们可以发现若存在两个元素相同，那么我们就可以通过四次操作交换任意两个位置的元素。并且当逆序对数量奇偶性相同则一定 Yes。

G - Polygon and Points

题意：给定凸多边形，多次询问一个点在多边形内部/外部/边上。\(n,m\le2\times10^5\)。

前置知识：一点点蒜几：如果 \(\vec{P}\times\vec{Q}>0\)，则 \(\vec{P}\) 在 \(\vec{Q}\) 的顺时针方向；如果 \(<0\)，则 \(\vec{P}\) 在 \(\vec{Q}\) 的逆时针方向；如果 \(=0\)，则 \(\vec{P}\) 与 \(\vec{Q}\) 同向或反向。

蒜几板子，但我不会蒜几。考虑把凸包分成几个三角形，类似这样：

这样我们就可以二分找到点所在的三角形，然后判断点与线段的关系即可。注意特判点在 \(p_{0}p_{1},p_{0}p_{n-1}\) 上的情况。