ARC149

有个弱智忘了有 arc 了，晚 10min 进场，我不说是谁

给定 $n,m$，求最大的正整数 $x$，满足 $x\le10^n,m|x$，且 $x$ 十进制表示中各数位均相同

$1\le n\le10^5,1\le m\le10^9$

最多只有 $9n$ 中可能的 $x$，我们可以预处理出形如 $11\cdots1$ 的数模 $m$ 的余数，然后暴力计算即可

给定两个长为 $n$ 的排列 $a_i,b_i$，你每次可以选择一个 $i$ 并执行 swap(a[i],a[i+1]), swap(b[i],b[i+1])

问两个排列的 LIS 长度之和最大是多少

$2\le n\le3\times10^5$

显然我们可以对任意 $i,j$ 执行 swap(a[i],a[j]),swap(b[i],b[j])

我们一定可以从 $a$ 中找出一个不在 LIS 上的下标，将这个下标换到一个使 $a$ 的 LIS 长度 $+1$ 的位置上，那么这样 $b$ 的 LIS 长度最多 $-1$，因此我们可以执行这项操作，一定不会更劣

也就是说最后 $a$ 的 LIS 长度为 $n$，那么答案就是此时 $b$ 的 LIS 长度

复杂度 $O(n\log n)$

构造一个 $n\times n$ 的网格，每个格子上写一个数，满足 $1\sim n^2$ 都恰好出现一次，并且任意两个四联通格子和不为质数

$3\le n\le1000$

考虑两个奇数加在一起一定是合数，两个偶数加在一起一定也是合数，那么我们上面填奇数，下面填偶数，这样只需要处理中间的交界处

我们考虑使用 $3$ 的倍数来做这件事情，我们将奇数中模 $3$ 余 $1$ 的数与偶数中模 $3$ 余 $2$ 的数放在边界处，这样的数一边大约有 $\frac{n^2}6$ 个，因此当 $n\ge6$ 时这种构造可行，对于 $n=3,4,5$ 时我们手动构造

数轴上有 $n$ 个点，坐标依次为 $x_1,x_2,\cdots,x_n$，有 $m$ 次操作，第 $i$ 次操作的属性为 $d_i$，一个属性为 $d$ 的操作会使每一个负半轴上的点向正方向移动 $d$ 的距离，使每一个正半轴上的点向负方向移动 $d$ 的距离（$0$ 上的点不变）

问每个点会不会到 $0$，如果会，输出最早到达 $0$ 的操作，否则输出最后的坐标

$1\le n\le3\times10^5,1\le x_n\le10^6$

我们直接对 $1\sim10^6$ 全部求出答案

考虑如果某一时刻有两个点的坐标为 $x$ 和 $-x$，那么这两个点之后的坐标一定一直互为相反数，因此我们可以放在一起计算

那么我们一开始是一个 $1\sim10^6$ 的连续段，如果经过操作后这个连续段跨过了 $0$，那么我们将比较短的那一边的数用长的那边的数计算，这样每一次操作后我们的数一定还是数轴一边的一个连续段，可以 $O(1)$ 维护

这样每个数对复杂度的贡献都是 $O(1)$（也即在被合并到另一边时贡献），总复杂度 $O(n+m)$