海亮集训：01/03日
T1
T2
T3
T4
题意
构造一个长度为 \(n\) 的数列 \(a\)，其中 \(1\le a_i\le k\) 且 \(a\) 不降，即对于所有 \(1\le i \le n-1\)，\(a_i \le a_{i+1}\)。给出 \(m\) 个约束，有三种约束，其中：
\(1\;i\;x\)，表示 \(a_i \neq x\)
\(2\;i\;j\;x\)，表示 \(a_i+ a_j\le x\)
\(3\;i\;j\;x\)，表示 \(a_i+ a_j\ge x\)
现在有 \(t\) 组数据，要求你给出这个数列。无解输出 \(-1\)。
题解
发现这东西很像2-SAT状物，但是如果直接设 \((i,p)=0(or \space1)\) 表示 \(a_i=p(or\space a_i\neq p)\) 不太好办，因为你需要保证对于每一个 \(i\) 有且仅有一个 \(p\) 使得 \((i,p)=1\) 成立。
那怎么办呢？
修改下刚刚的定义，设 \((i,p)=0(or \space1)\) 表示 \([a_i\ge p]=0(or\space 1)\) 。
那么这下就好办了。不妨设 \((i,p,a)\to(j,q,b)\) 表示如果 \((i,p)=a\)，那么 \((j,q)=b\)。
首先按照定义，需要有：
\[\begin{cases}
(i,p,1)\to(i,p + 1,1)\\
(i,p+1,0)\to(i,p,0)
\end{cases}\\
\begin{cases}
(i,p,1)\to(i+1,p,1)\\
(i+1,p,0)\to(i,p,0)
\end{cases}\\
\]
然后对于三种操作有：
第一种 \((i,x)\)
\[\begin{cases}
(i,x,1)\to(i,x+1,1)\\
(i,x+1,0)\to(i,x,0)
\end{cases}
\]
第二种 \((i,j,x)\)
\[\begin{cases}
(i,p,1)\to(j,x-p+1,0)\\
(j,x-p+1,1)\to(i,p,0)
\end{cases}
\]
第三种 \((i,j,x)\)
\[\begin{cases}
(i,p+1,1)\to(j,x-p,1)\\
(j,x-p,1)\to(i,p+1,1)
\end{cases}
\]
证明显然。
然后跑 2-SAT 即可。