构造大学习

· · 个人记录

构云依山峦，
造水绕青山，
题山环绿水，
纯月照高楼，
史日照山冈。

QOJ8233 Operator Precedence

观察一下，发现上面的式子的最大值是 10^{10} 左右，下面的最大值是 10^{25} 左右，说明下面的连乘中一定有很多 1

于是我们构造 \forall i \in [1, n - 1], a_{2i} = 2, a_{2_i+1}=-1，于是：

a_1\times(a_2+a_3)\times(a_4+a_5)\times\cdots\times(a_{2n-2}+a_{2n-1})\times a_{2n}=a_1a_{2n}

令 a_1=1，则 a_{2n}=3-n，对 n=3 特判即可

ACed.

[POI 2011] LIZ-Lollipop

欸不是你怎么在构造题单里

注意到如果 k 有解，那么 k-2 也有解。因为令 k 的解是 [l, r]，如果 a_l=2 或 a_r=2，那么直接缩一位变成 [l+1,r] 或 [l,r-1] 就是 k - 1 的解，否则就表示 a_l=a_r=1，那么 [l+1,r-1] 就是 k-1 的解

于是乎找到最大的偶数解和奇数解，然后依次按照上述方法递归，就求出了所有情况的解，遂发现最大偶数解和最大奇数解其中一个是全局，另一个就是除去 [1, l] 或 [r, n] 剩下的序列，这里的 l, r 表示最左和最右的 1

ACed too.

Koishi Loves Construction

task1：注意到 n\equiv 0 \pmod{n}，所以 n 一定要在首位，再注意到当 n 为奇数时，总和 \frac{n(n+1)}{2}\equiv0\pmod{n}，所以奇数除了 1 都无解，而偶数构造一个 0, 1, -1, 2, -2,\cdots 的序列就行

task2：首先还是 n 一定要在末位，注意到若 n 是大于 4 的合数，那么一定 \exist \text{ }p,q<n,pq\equiv0\pmod{n}，n=4 时特判，其余的根据原根的性质，g^0, g^1, g^2, g^3,\cdots, g^{n-2} 对 n 取模都不同，前缀积就变成了 g^{p_1}, g^{p_1+p_2}, g^{p_1+p_2+p_3}, \cdots，所以按照task1 构造即可

also ACed

\text{THE\quad END}