构造大学习

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

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. ](https://qoj.ac/submission/1554556) ## [[POI 2011] LIZ-Lollipop](https://www.luogu.com.cn/problem/P3514) 欸不是你怎么在构造题单里 注意到如果 $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. ](https://www.luogu.com.cn/record/242029441) ## [Koishi Loves Construction](https://www.luogu.com.cn/problem/P3599) 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](https://www.luogu.com.cn/record/241933488) --- $$\text{THE\quad END}$$

文章操作

QOJ8233 Operator Precedence

相关推荐

评论

构造大学习