我好像完全没做过啥构造题啊 =_=,这一场有一道就顺手补一下吧。
对于这种神秘的构造题,我们发现样例完全没有意义,它一定不会告诉你真正的构造方案。
一般而言,我们最终给出的构造方案总是更强一点点。对于这道题而言,比方说我们可以加一个限制:对于一个和为正的子区间 \([l,r]\) 而言,\([l,r\dots n]\) 都是和为正的区间。
怎么想到这样的东西的呢?其实就是一个增量构造,我们假装自己手里已经有了一个答案 \((n',k')\),我们考虑往后面再加上一个新的数得到一个新的 \(k\),我们发现让 \(k\) 不变(设成一个大的负数)或者加 \(n'\) (设成一个大的正数)都是方便做的。
这样的话,我们可以把 \(k\) 分解成若干个位置,它们设成大的正数,别的位置设成大的负数就可以了。
标签:设成,CF1809C,构造,一个,正数,我们 From: https://www.cnblogs.com/PYD1/p/17253157.html