题解 P7141 【[THUPC2021 初赛]棋盘】

· · 题解

题外话：

没错我就是那个考场错了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:顺便修了一下题解不清的地方。