#1996. 菊花

    ID: 1996 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest4604来源:qoj.ac数据:公开样例贪心

菊花

菊花

题目描述

标题: 菊花 - Problem - QOJ.ac

#21435. 菊花

Statistics

题目背景

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

题目描述

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

一次操作,需要选择中心 c 和恰好 2k+1 个互不相同且不等于 c 的顶点 S,将 c 与 S 之间的所有边颜色翻转。这些边组成一朵"菊花"。

请你输出若干次操作,使所有边颜色都变为 0。操作次数越少,得分越高。使用不超过 4k+4=2004 次操作即可获得满分。

输入格式

第一行一个整数 k。

接下来 n 行,每行一个长度为 n 的 01 字符串,第 i 行第 j 个字符表示 ai,j。

输出格式

第一行一个非负整数 x,表示操作次数。

接下来 x 行,每行一个长度为 n 的字符串,按顺序描述一次操作。第 j 个字符的含义如下:

  • 2:顶点 j 是中心。
  • 1:顶点 j 被选中。
  • 0:顶点 j 未被选中。

每行必须恰好包含一个 2、2k+1 个 1 和 2k+1 个 0。

样例 1

输入

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

输出

2
21111100000
12000011110

解释

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

样例 2

见附件中 chrysanthemum2.in 与 chrysanthemum2.ans。该样例满足子任务 1 的约束条件。

样例 3

见附件中 chrysanthemum3.in 与 chrysanthemum3.ans。该样例满足子任务 2 的约束条件。

样例 4

见附件中 chrysanthemum4.in 与 chrysanthemum4.ans。该样例满足子任务 3 的约束条件。

数据范围与子任务

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

下发文件包含全部 4 组样例(chrysanthemum1~4,其中样例 2、3、4 为 k=500 规模,每组子任务至少对应一组样例)以及 checker.cpp、testlib.h,全部位于压缩包根目录。

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

评分方式

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

条件 得分比例 x≤2004 100% 2004<x≤2020 [90−5log2(x−2004)]% x>2020 max{0,70−(x−2020)/60}%

其中 log2 表示以 2 为底的对数。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2
00111100000
00000011110
10000000000
10000000000
10000000000
10000000000
01000000000
01000000000
01000000000
01000000000
00000000000
2
21111100000
12000011110