自动搬运

查看原文

来自洛谷，原作者为

	约瑟夫用脑玩 AFO

搬运于2025-08-24 22:26:59，当前版本为作者最后更新于2020-12-25 18:36:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题外话：

没错我就是那个考场错了51次的那个垫底队中做这道题的人(之一)。

考场难得看到一道可做(du)题，然后就陷入了奇奇怪怪的构造中。

题解：

题意已经很简洁了(好评)，就不再赘述。

由于限制的是每列多少个(差点看反差评)，于是来考虑行 $n$ 。

如果 $n$ 为偶数，每列都只能放 $\frac{n}{2}$ 个，与相邻的列无关，直接判断即可。

否则至少能放 $\frac{n}{2}$ 个，最多能放 $\frac{n}{2}+1$ 个，差异在于放在奇数位置上或偶数位置上。

如果 $\max{}a_i$ 超过了 $\frac{n}{2}+1$ 或小于 $\frac{n}{2}$ 了就不再考虑，这些可以特判。

我们称，满足 $a_i = \frac{n}{2}+1$ 的列 $i$ 叫做顶满了的列。

我们可以发现如果顶满了的列都在奇数列或偶数列，直接强制保证顶满的列都填奇数位置，由于其他列都未顶满， $\frac{n}{2}$ 个位置就够用了，对于每列从前往后交替(注：交替指奇偶位置交替)填即可，没有影响。

于是考虑某两个顶满的列 $i,j$ 满足 $i < j$ 满足 $j-i \equiv 1 \pmod{2}$ ，即中间行数为偶行。

此时如果你不进行操作，你强制两列都放奇数位置，中间的列就可能出现问题，更具体的，你需要将 $j-1$ 的奇数位置空出来，否则无法构造。

考虑构造一种方法让其空出来，由于原来不操作时，这些列是交替填的，我们希望让中间某两行打破这个交替。

那么我们就从后往前尽量让当前行不与上一行交替，可能会剩下一些必定交替，此时再正常的按交替的填，直到某两行打破交替，后面的构造就都会切换奇偶交替的状态了，使得 $j-1$ 的奇数位置能空出来。

如果从 $i$ 构造至 $j$ 都还没构造出来就可以输出 $\texttt{NO}$ 走人了，否则用相同的方法处理后面顶满的列即可。

还是放下核心代码吧qwq：

	//这是中间行的构造过程。
	for(k=lst+1;k<i;k++)
	{//lst:上一个顶满的列 i:当前顶满的列 且 (i&1)^(lst&1)。
		for(t=1,j=n-(((k-lst)&1)^1);t<=a[k]&&j>0;t++,j-=2)
		{//这里是尽量不交替
			if(ans[j][k-1])
			{
				break;
			}
			ans[j][k]=1;
		}
		for(j=((k-lst)&1)+1;t<=a[k];t++,j+=2)
		{//这里是必定交替
			if(ans[j][k-1])
			{
				writechar('N','o');
				pc(10,false);
				return output;
			}
			ans[j][k]=1;
		}
	}

Upd:较严重的笔误，对题解的理解有较大的影响，已修正。

Upd:顺便修了一下题解不清的地方。