[已解决]梦想星际舰队第25关 && FCOI #9 第六题涂色游戏题解【原创】

zhangjinxuan

梦想星际舰队第25关 && FCOI #9 题解

第六题：涂色游戏

题目描述

涂色游戏的游戏界面是一个 n 行 m 列的网格图，起初每一个格子都是颜色 "0"（颜色用数字代替，这里只有 0，1）。

每一次操作你都可以选择如下的任意一种：

1. 选择一行，把这一行涂成颜色“1”；
2. 选择一列，把这一列涂成颜色“0”；
这里的涂色都会覆盖原有的颜色。

请问如何操作才能把网格变成最终想要的状态（状态会通过数组形式给你）？

输入格式
第一行两个整数 n,m。

接下来 n 行，每行 m 个整数，第 i 行 j 列的整数表示 i 行 j 列需要涂成的颜色，只有 0 和 1 这两个数字。

输出格式
第一行一个整数，表示你需要操作的次数。

接下来，每一次的操作，你都要详细地指明，是哪一个操作（1或2，上有指明），操作了哪一行（列），第 i+1 行表示第 i 次操作。

例如下面就是先将第 2 行染成颜色 1，再将第 3 列染成颜色 0，最后将第 1 行染成颜色 1 的一个输出示例：

1. 3
   
2. 1 2
   
3. 2 3
   
4. 1 1

复制代码

你输出的第一个数字必须是 1 或 2，第二个数字不得超过行或列的实际范围，否则会视为 0 分。

如果无解，输出一行 -1。

输入输出样例
输入 #1

1. 3 3
   
2. 0 0 1
   
3. 0 1 1
   
4. 1 1 1

复制代码

输出 #1

1. 5
   
2. 1 1
   
3. 2 2
   
4. 1 2
   
5. 2 3
   
6. 1 3

复制代码

输入 #2

1. 4 4
   
2. 0 1 1 1
   
3. 0 1 0 0
   
4. 0 1 1 1
   
5. 0 1 0 0

复制代码

输出 #2

1. 8
   
2. 2 2
   
3. 1 2
   
4. 1 4
   
5. 2 3
   
6. 2 4
   
7. 1 1
   
8. 1 3
   
9. 2 1

复制代码

数据范围
1≤x1<x2≤10^9 ,1≤y1<y2≤10^9

其他说明
本题目为 zhangjinxuan 原创题目。
测试链接：https://www.luogu.com.cn/problem/U330607

答案与解析

游客，如果您要查看本帖隐藏内容请回复

[/hide]

最佳答案

月排行榜 / 总排行榜

额外减小

2023-8-25 20:01:32

诶嘿嘿，硬是用STL（没用任何算法）搞出来了

1. #include <cstdio>
   
2. #include <algorithm>
   
3. #include <set>
   
4. using namespace std;
   
5. //膜拜[url=home.php?mod=space&uid=1292144]@zhangjinxuan[/url] dalao %%%orz
   
6. //%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   
7. //我这个蒟蒻被zhangjinxuan,mushezi,yuanhao,sfqxx薄纱啦！！！
   
8. //FCOI please do not ak me!!!
   
9. 
   
10. //谢谢zhangjinxuan大佬提供特殊约定~
    
11. 
    
12. typedef struct{
    
13.         int row;
    
14.         int count;
    
15. }hh; //统计各行的0的数目
    
16. 
    
17. inline bool cmp(hh a,hh b)
    
18. {
    
19.         return a.count<b.count;
    
20. }
    
21. 
    
22. inline void out_row(bool *sz,int col_max)
    
23. {
    
24.     for(int i=0;i<col_max;i++)
    
25.     {
    
26.         printf("%d.",sz[i]);
    
27. 
    
28. 
    
29.     }
    
30.    
    
31. 
    
32. }
    
33. 
    
34. int main()
    
35. {
    
36.         set<int>rows;
    
37.         int n,m,cnt,ch,stepcnt=0;
    
38.         hh rs[2010];
    
39.         bool sz[2010][2010];
    
40.         scanf("%d%d",&n,&m);
    
41.     getchar();
    
42.         for(int i=0;i<n;i++)//hang
    
43.         {
    
44.                 cnt=0;
    
45.                 for(int j=0;j<m;j++)//lie
    
46.                 {
    
47.                         ch=getchar();
    
48.             //printf("%d.",ch);
    
49.                         if(ch=='0')
    
50.                         {
    
51.                                 sz[i][j]=false;
    
52.                                
    
53.                         }
    
54.                         else
    
55.                         {
    
56.                                 sz[i][j]=true;
    
57.                                 cnt++;
    
58.                         }
    
59.                         getchar();
    
60.                 }
    
61.         getchar();
    
62.                 rs[i].count=cnt;
    
63.                 rs[i].row=i;
    
64.                 stepcnt+=m-cnt;
    
65.         }
    
66.     sort(rs,rs+n,cmp);
    
67.     /*for(int k=0;k<n;k++)
    
68.     {
    
69.         out_row(sz[rs[k].row],m);
    
70.         putchar('\n');
    
71. 
    
72. 
    
73. 
    
74.     }*/
    
75.         stepcnt+=n;
    
76.     for(int i=0;i<n;i++)
    
77.         {
    
78.                 int r=rs[i].row;
    
79.                 for(int j=0;j<m;j++)
    
80.                 {
    
81.                         if(!sz[r][j])
    
82.             {
    
83.                 if(rows.count(j)==0 and i!=0)
    
84.                 {
    
85.                     printf("-1\n");
    
86.                     return 0;
    
87.                 }
    
88.                 if(i==0)rows.insert(j);
    
89.             }
    
90.                 }
    
91.         }
    
92.         printf("%d\n",stepcnt);
    
93.        
    
94.         for(int i=0;i<n;i++)
    
95.         {
    
96.                 int r=rs[i].row;
    
97.                 printf("1 %d\n",r+1);
    
98.                 for(int j=0;j<m;j++)
    
99.                 {
    
100.                         if(!sz[r][j])
     
101.             {
     
102.                 printf("2 %d\n",j+1);
     
103.                
     
104.             }
     
105.                 }
     
106.         }
     
107.        
     
108. }

复制代码

一个排序，排出每行的'0'的个数
然后用set看是否真包含。

跳转到最佳答案楼层

zhangjinxuan

好吧贪心怎么做QAQ

zhangjinxuan

鱼小二 发表于 2023-8-26 20:02

版主驾到

鱼小二

陆捌拾-

1

香蕉那个不拿拿

这是要不起的题

zhangjinxuan

额外减小 发表于 2023-8-25 20:51
行

zhangjinxuan

额外减小 发表于 2023-8-25 20:35
https://www.luogu.com.cn/discuss/525529
不可以，总司令 然后得一半的分

Fcr8 果篮(D)那道题也是，输出-1得45分，我都怀疑是彩蛋

额外减小

zhangjinxuan 发表于 2023-8-25 20:49
目前不方便，我半小时后给你

行

zhangjinxuan

额外减小 发表于 2023-8-25 20:49
那你能把我wa的那几个测试点的数据发我看看嘛

目前不方便，我半小时后给你

额外减小

zhangjinxuan 发表于 2023-8-25 20:47
没有

那你能把我wa的那几个测试点的数据发我看看嘛

额外减小

zhangjinxuan 发表于 2023-8-25 20:47
没有

eee

zhangjinxuan

额外减小 发表于 2023-8-25 20:46
你看出我代码哪错了吗

没有

额外减小

zhangjinxuan 发表于 2023-8-25 20:41
构造

你看出我代码哪错了吗

zhangjinxuan

额外减小 发表于 2023-8-25 20:33
如果随机生成数据的话，-1的几率应该是很高的，所以他是认真自己造的

构造

额外减小

https://www.luogu.com.cn/discuss/525529
不可以，总司令 然后得一半的分

额外减小

如果随机生成数据的话，-1的几率应该是很高的，所以他是认真自己造的

额外减小

额外减小 发表于 2023-8-25 20:31
对，我还想着不可以总司令能骗多少分来着

我现在知道为什么他没设多组数据了。

额外减小

sfqxx 发表于 2023-8-25 20:28
这道题甚至没有-1

对，我还想着不可以总司令能骗多少分来着

sfqxx

额外减小 发表于 2023-8-25 20:27
看来我是这题唯一一个AC的

这道题甚至没有-1

额外减小

看来我是这题唯一一个AC的

Quick_Sort

上线看看