2020-2021:teams:legal_string:组队训练比赛记录:contest16
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest16 [2021/08/20 22:05] lgwza [补题情况] |
2020-2021:teams:legal_string:组队训练比赛记录:contest16 [2021/08/28 08:50] (当前版本) jxm2001 [题解] |
||
|---|---|---|---|
| 行 7: | 行 7: | ||
| | B | 0 | 0 | 0 | | | B | 0 | 0 | 0 | | ||
| | C | 2 | 2 | 0 | | | C | 2 | 2 | 0 | | ||
| - | | D | 2 | 0 | 0 | | + | | D | 2 | 1 | 0 | |
| | E | 0 | 0 | 0 | | | E | 0 | 0 | 0 | | ||
| | G | 2 | 1 | 0 | | | G | 2 | 1 | 0 | | ||
| - | | I | 0 | 0 | 0 | | + | | I | 2 | 1 | 0 | |
| | J | 2 | 0 | 2 | | | J | 2 | 0 | 2 | | ||
| - | | K | 2 | 0 | 0 | | + | | K | 2 | 1 | 0 | |
| ====== 题解 ===== | ====== 题解 ===== | ||
| 行 558: | 行 558: | ||
| return 0; | return 0; | ||
| } | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== I. War of Inazuma (Hard Version) ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 要求给 $n$ 位二进制数染上黑白两色，使得黑白两色的二进制数个数不相等。同时每个二进制数向其他只有一位与自身不同的二进制数连边。 | ||
| + | |||
| + | 要求与每个二进制数相邻的同色二进制数不超过 $m=\lceil\sqrt n\rceil$。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 将二进制数写成一个 $\lceil\frac nm\rceil\times m$ 的矩阵，最后一行不足的位置补 $1$，然后将二进制数分为四类： | ||
| + | |||
| + | $A.$ 有奇数个 $1$，至少存在一行全为 $1$ | ||
| + | |||
| + | $B.$ 有偶数个 $1$，不存在一行全为 $1$ | ||
| + | |||
| + | $C.$ 有奇数个 $1$，不存在一行全为 $1$ | ||
| + | |||
| + | $D.$ 有偶数个 $1$，至少存在一行全为 $1$ | ||
| + | |||
| + | $A,B$ 染白色，$C,D$ 染黑色。下面证明方案合法： | ||
| + | |||
| + | 只考虑白色的合法性，黑色的合法性是对称的。 | ||
| + | |||
| + | 首先 $A$，$B$ 内部不连边，因为内部 $1$ 奇偶性相同所有至少有两个位置不同。 | ||
| + | |||
| + | 只有仅一行全 $1$ 的 $A$ 才能和 $B$ 连边，否则至少有两个位置不同。 | ||
| + | |||
| + | 对于 $A$ 仅一行全 $1$ 的数 $u$，为了和 $B$ 中的数 $v$ 连边，需要 $v$ 其他行与 $u$ 完全相同，然后 $v$ 在 $u$ 的全 $1$ 行只有一个位置是 $0$。 | ||
| + | |||
| + | 由于一行只有 $m$ 个数，于是这样的 $v$ 最多只有 $m$ 个。 | ||
| + | |||
| + | 对与 $B$ 中的每个数 $u$，为了和 $A$ 中的数 $v$ 连边，需要 $v$ 其他行与 $u$ 完全相同，然后仅某一行是全 $1$ 行。 | ||
| + | |||
| + | 由于只有 $\lceil\frac nm\rceil$ 行，因此这样的 $v$ 最多只有 $\lceil\frac nm\rceil\le m$ 个。 | ||
| + | |||
| + | 最后有 $A+C=B+D=2^{n-1},B+C=(2^m-1)^{\lceil\frac nm\rceil}$，于是 $A+B,C+D$ 都是奇数。 | ||
| + | |||
| + | 由于 $4\mid A+B+C+D$，于是 $A+B\neq C+D$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | bool check(int n,int m,int v){ | ||
| + | bool flag_cnt=false; | ||
| + | bool flag_one=false; | ||
| + | for(int i=0;i<n;i+=m){ | ||
| + | bool flag_line=true; | ||
| + | int r=min(n,i+m); | ||
| + | _for(j,i,r){ | ||
| + | int c=v&1; | ||
| + | flag_line&=c; | ||
| + | flag_cnt^=c; | ||
| + | v>>=1; | ||
| + | } | ||
| + | flag_one|=flag_line; | ||
| + | } | ||
| + | return flag_cnt^flag_one; | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),m=ceil(sqrt(n)); | ||
| + | _for(i,0,1<<n) | ||
| + | putchar('0'+check(n,m,i)); | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
| 行 1373: | 行 1442: | ||
| 显然根据 $a,b,s$ 奇偶性以及预处理组合数可以 $O(1)$ 计算 $h(a,b,s)$。 | 显然根据 $a,b,s$ 奇偶性以及预处理组合数可以 $O(1)$ 计算 $h(a,b,s)$。 | ||
| - | 然后总移动方案为 $h(a,1,s)$。利用容斥，首先我们减去非法序列为 ''L+.*'' 和 ''R+.*'' (非法序列均用正则表达式表示)的移动方案。 | + | 然后总移动方案为 $h(a,1,s)$。利用容斥，首先我们减去非法序列为 ''.*L+.*'' 和 ''.*R+.*'' (非法序列均用正则表达式表示)的移动方案。 |
| + | |||
| + | 设 $l(x)=-x,r(x)=2(n+1)-x$。 | ||
| + | |||
| + | 根据简单组合数学知识，不难发现 ''.*L+.*'' 代表的方案为 $h(a,l(1),s)$，''.*R+.*'' 代表的方案为 $h(a,r(1),s)$。 | ||
| - | 设 $l(x)=-x,r(x)=2(n+1)-x$。根据简单组合数学知识，不难发现 ''L+.*'' 代表的方案为 $h(a,l(1),s)$，''R+.*'' 代表的方案为 $h(a,r(1),s)$。 | + | 接下来我们需要补上减去非法序列为 ''.*L+R+.*'' 和 ''.*R+L+.*'' 的移动方案，分别为 $h(a,r(l(1)),s),h(a,l(r(1)),s)$。 |
| - | 接下来我们需要补上减去非法序列为 ''L+R+.*'' 和 ''R+L+.*'' 的移动方案，分别为 $h(a,r(l(1)),s),h(a,l(r(1)),s)$。依次类推，有 | + | 依此类推，有 |
| $$ | $$ | ||
2020-2021/teams/legal_string/组队训练比赛记录/contest16.1629468351.txt.gz · 最后更改: 2021/08/20 22:05 由 lgwza
