#P18772. [2027年国家集训队互测] Chrysanthemum
[2027年国家集训队互测] Chrysanthemum
Chrysanthemum
题目背景
花园里的菊花长歪了,需要修剪。
题目描述
给定整数 ,以及 行 列的 01 矩阵 ,其中 。它描述一个有 个顶点的无向完全图:对 , 表示边 的颜色。保证 ,。1 为黑色,0 为白色。
一次操作,需要选择中心 和恰好 个互不相同且不等于 的顶点组成集合 ,将 与 之间的所有边颜色翻转。这些边组成一朵“菊花”。请输出若干次操作,使所有边颜色都变为 0。操作次数越少,得分越高。使用不超过 次操作即可获得满分。
输入格式
第一行一个整数 。接下来 行,每行一个长度为 的 01 字符串,第 行第 个字符表示 。
输出格式
第一行一个非负整数 ,表示操作次数。接下来 行,每行一个长度为 的字符串,按顺序描述一次操作。第 个字符的含义为:2 表示顶点 是中心;1 表示被选中;0 表示未被选中。每行必须恰好包含一个 2、 个 1 和 个 0。
样例 1
输入:
2
00111100000
00000011110
10000000000
10000000000
10000000000
10000000000
01000000000
01000000000
01000000000
01000000000
00000000000
输出:
2
21111100000
12000011110
此例 ,仅用于说明题意。第一次中心为 1,选中 2、3、4、5、6;第二次中心为 2,选中 1、7、8、9、10。边 先由白翻黑、再由黑翻白,其余黑边各恰好翻转一次,因此两次后全白。
完整样例附件
完整样例输入与输出见下表。
| 样例 | 输入 | 答案文件 | 限制 |
|---|---|---|---|
| 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。
数据范围与子任务
所有正式测试数据均满足 ,每次操作选择 1001 条边。
| 子任务 | 分值 | 特殊限制 |
|---|---|---|
| 1 | 10 | 所有边初始均为黑色 |
| 2 | 40 | 边的颜色随机生成 |
| 3 | 50 | 无特殊限制 |
评分方式
以下规则适用于正式数据。设操作次数为 。若格式或操作不合法,或操作后仍有黑边,该点得0分。否则得分占该点满分的比例如下:
| 条件 | 得分比例 |
|---|---|
表示以2为底的对数。每个测试点的实际得分向下取整,满分判定不受影响。