#P18772. [2027年国家集训队互测] Chrysanthemum

[2027年国家集训队互测] Chrysanthemum

Chrysanthemum

题目背景

花园里的菊花长歪了,需要修剪。

题目描述

给定整数 kk,以及 nn 行 nn 列的 01 矩阵 aa,其中 n=4k+3n=4k+3。它描述一个有 nn 个顶点的无向完全图:对 i≠ji\ne j,ai,ja_{i,j} 表示边 (i,j)(i,j) 的颜色。保证 ai,j=aj,ia_{i,j}=a_{j,i},ai,i=0a_{i,i}=0。1 为黑色,0 为白色。

一次操作,需要选择中心 cc 和恰好 2k+12k+1 个互不相同且不等于 cc 的顶点组成集合 SS,将 cc 与 SS 之间的所有边颜色翻转。这些边组成一朵“菊花”。请输出若干次操作,使所有边颜色都变为 0。操作次数越少,得分越高。使用不超过 4k+4=20044k+4=2004 次操作即可获得满分。

输入格式

第一行一个整数 kk。接下来 nn 行,每行一个长度为 nn 的 01 字符串,第 ii 行第 jj 个字符表示 ai,ja_{i,j}。

输出格式

第一行一个非负整数 xx,表示操作次数。接下来 xx 行,每行一个长度为 nn 的字符串,按顺序描述一次操作。第 jj 个字符的含义为:2 表示顶点 jj 是中心;1 表示被选中;0 表示未被选中。每行必须恰好包含一个 2、2k+12k+1 个 1 和 2k+12k+1 个 0。

样例 1

输入:

2
00111100000
00000011110
10000000000
10000000000
10000000000
10000000000
01000000000
01000000000
01000000000
01000000000
00000000000

输出:

2
21111100000
12000011110

此例 k=2,n=11k=2,n=11,仅用于说明题意。第一次中心为 1,选中 2、3、4、5、6;第二次中心为 2,选中 1、7、8、9、10。边 (1,2)(1,2) 先由白翻黑、再由黑翻白,其余黑边各恰好翻转一次,因此两次后全白。

完整样例附件

完整样例输入与输出见下表。

样例 输入 答案文件 限制
1 chrysanthemum1.in chrysanthemum1.ans 上面的样例
2 chrysanthemum2.in chrysanthemum2.ans 子任务1,全黑
3 chrysanthemum3.in chrysanthemum3.ans 子任务2,随机
4 chrysanthemum4.in chrysanthemum4.ans 子任务3,一般

样例 2~4 的 .ans 文件内容为占位值 0,并非相应输入的合法方案。可参考以下合法满分方案:样例1、样例2、样例3、样例4。

数据范围与子任务

所有正式测试数据均满足 k=500,n=2003k=500,n=2003,每次操作选择 1001 条边。

子任务 分值 特殊限制
1 10 所有边初始均为黑色
2 40 边的颜色随机生成
3 50 无特殊限制

评分方式

以下规则适用于正式数据。设操作次数为 xx。若格式或操作不合法,或操作后仍有黑边,该点得0分。否则得分占该点满分的比例如下:

条件 得分比例
x≤2004x\le2004 100%100\%
2004<x≤20202004<x\le2020 [90−5log⁡2(x−2004)]%[90-5\log_2(x-2004)]\%
x>2020x>2020 max⁡{0,70−(x−2020)/60}%\max\{0,70-(x-2020)/60\}\%

log⁡2\log_2 表示以2为底的对数。每个测试点的实际得分向下取整,满分判定不受影响。