题目名称 2959. [SYOI 2018] 消消乐
输入输出 eli.in/out
难度等级 ★★☆
时间限制 1000 ms (1 s)
内存限制 32 MB
测试数据 20 评测插件
题目来源 2018-09-14
开放分组 全部用户
提交状态
分类标签
HtBest 二分图 匈牙利算法
通过:1, 提交:10, 通过率:10%
GravatarHtBest 100 0.999 s C++
Gravatarサイタマ 100 1.557 s C++
Gravatarサイタマ 100 5.559 s C++
Gravatarサイタマ 90 3.339 s C++
Gravatarサイタマ 40 1.158 s C++
Gravatarサイタマ 30 1.520 s C++
Gravatarサイタマ 20 1.534 s C++
Gravatar无言 0 0.000 s C++
Gravatar无言 0 0.000 s C++
Gravatarサイタマ 0 0.114 s C++
关于 消消乐 的讨论
r神和小b太强啦
GravatarHtBest
2018-09-14 21:43 1楼
COGS 的 Bug:没交题的时候也可以允许查看的提交代码,链接会指向莫名其妙的地方。
GravatarWHZ0325
2018-09-15 22:40 2楼
回复 @WHZ0325 : 链接会指向全网最后一次提交的代码
GravatarHtBest
2018-09-18 11:43 3楼

2959. [SYOI 2018] 消消乐

★★☆   输入文件:eli.in   输出文件:eli.out   评测插件
时间限制:1 s   内存限制:32 MB

【题目描述】

rqy神在和小b比赛玩一个名为“消消乐”的游戏,在一个 $n\times m$ 的棋盘上,一些棋子分布在格点上,游戏玩家有一个名为超蓝光波的武器,可以消除一行或者一列的所有棋子,使用超蓝光波需要耗费一点能量,消除完所有的棋子之后,花费能量越少得分越高。 rqy神为了超过排名第一的小b,夺得荣誉称号“天下第一”,他需要寻求你的帮助,他希望知道最少需要使用多少次“超蓝光波”,以及在哪行、哪列使用。

【输入格式】

第一行两个正整数 $n(n\le 2000)$,$m(m\le 2000)$;

接下来 $n$ 行,每行 $m$ 个字符,表示棋盘,其中“.”表示该处没有棋子,“*”表示该处有棋子,棋子个数 $\le 100000$。

【输出格式】

第一行输出一个正整数,表示最少需要使用的“超蓝光波”次数。

第二行 $N+1$ 个正整数,第一个数为 $N$,表示需要消掉的行数,从小到大输出每个需要消除的行号。

第三行 $M+1$ 个正整数,第一个数为 $M$,表示需要消掉的列数,从小到大输出每个需要消除的列号。

如果有多种情况,任意输出一种即可。

【样例输入】

3 4
.*..
**.*
..*.

【样例输出】

3
3 1 2 3
0

【提示】

手动链表:下一题 [SYOI 2018] 国政议事

【来源】

SYOI 2018