Contest Info

practice link

Solutions

A. Find Square

签到题。

B. Unnatural Conditions

签到题。

C. Rectangles

签到题。

D. Order book

签到题。

E. Restore Array

签到题。

F. Make Symmetrical

题目大意：有三种操作，一种是往平面上加一个整点，一种是从平面上删去一个点，一种是询问一条过原点的直线，问有多少个点没有关于它的对称点。

题解：注意到对称的必要条件是到原点的距离相同，而到原点距离相同的整点数量非常少，对每种距离暴力维护即可。

G. Guess the number

题目大意：交互题。已知一个整数 \(x\) 在 \([1,M=10004205361450474]\) 内，每一次你可以询问 \(\le\min(x,10^{4})\) 个 \([1,M]\) 内严格递增的整数，交互器会告诉你 \(x\) 在这些数中，或者是在某个区间中。你至多可以询问 \(5\) 次，如果 \(x\) 在你询问的数中，游戏结束。

题解：容易发现若当前左边界为 \(l\)，那么我们至多问 \(\min(l,10^{4})\) 个数。

设 \(dp[i][j]\) 表示当前左边界为 \(l\)，还剩 \(j\) 次机会时最大能够问出的右边界为多少。因为我们至多问 \(10^{4}\) 个数，所以 \(i\) 只需 \(dp\) 到 \(10^{4}\) 即可。询问时结合 \(dp\) 值问即可。

H. Make Square

题目大意：给一个长度为 \(n\) 的数列 \(b\)，以及 \(q\) 个询问，每次给出一个区间 \([l,r]\)，求 \(\min_{l\le i<j\le r}f(b_{i}b_{j})\)。其中 \(f(x)\) 表示 \(x\) 中奇数次幂的质因子个数。

题解：首先将所有 \(b\) 中的平方因子去掉。

不妨考虑 \(b_{i}, b_{j}\) 的任意公因数 \(t\)，\(\frac{b_{i}}{t}\) 的质因子个数加上 \(\frac{b_{j}}{t}\) 的质因子个数在 \(t=\gcd(b_{i},b_{j})\) 时达到最小，且该最小值就是 \(f(b_{i}b_{j})\)。

离线处理询问，设当前 \(r=i\)。我们只需要对值域内每个的 \(t\)，维护 \([1,i]\) 中最右边的能表为 \(t\) 乘上 \(j\) 个质数的数的位置，以及使得答案为 \(k\) 的最左边的 \(l\) 即可。