luogu#P7218. [JOISC2020] 伝説の団子職人

    ID: 11227 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>2020Special Judge模拟退火随机贪心随机化JOI

[JOISC2020] 伝説の団子職人

题目背景

您是做团子带师,您太强了。

题目描述

您面前有一个 R×CR \times C 的网格,每一个格子里有一个团子,您可以横向,竖向,斜向地将三个连续的团子按顺序串起来,按顺序指可以串上中下,下中上之类的,但是不能串中下上,上下中之类的。

如果一串团子的颜色为绿,白,粉或者粉,白,绿,那么称这串团子叫 AK IOI 串。

求串最多 AK IOI 串的方法(我坚信做了几个 AK IOI 串就会 AK 几次 IOI)。

输入格式

第一行两个整数 R,CR,C 代表网格大小。
接下来 RR 行每行 CC 个字符代表网格:

  • P 代表粉色团子
  • W 代表白色团子
  • G 代表绿色团子

输出格式

RR 行每行 CC 个字符代表串好的网格:

  • 可以为 -|/\,代表一个团子串
  • 如果不是以上四种线,那么原样输出

输出文件应为 01.ans ~ 06.ans

3 4
PWGP
WGPW
GWPG
P-GP
WGP|
G-PG
3 4
PWWP
WWWW
PGGP
PWWP
W\/W
PGGP

提示

样例 1 解释

您做了 33 个 AK IOI 串。

样例 2 解释

您做了 22 个 AK IOI 串。

数据规模与约定

本题为提交答案题。

本题使用 Special Judge。

一共有 66 组数据,保证 3R,C5003 \le R,C \le 500,输入文件可在附加文件中得到,具体数据表格如下:

数据点 分数 SS 及格线 XX 良好线 YY 优秀线 ZZ
11 1515 4400044000 4700047000 4722047220
22 3900039000 4170041700 4198041980
33 4500045000 5100051000 5139051390
44 1800018000 1900019000 1912019120
55 2020 4300043000 4820048200 4862048620
66 4400044000 4600046000 4650046500

假设 NN 为得到的 AK IOI 串个数,那么评分标准为(四舍五入):

  • N<XN<X00
  • XN<YX \le N <YNX2(YX)×S\dfrac{N-X}{2(Y-X)} \times S
  • YN<ZY \le N < Z,$\left(\dfrac{1}{2}+\dfrac{N-Y}{2(Z-Y)}\right) \times S$ 分
  • ZNZ \le NSS

如果输出格式有误或输出无效,判 00 分。

说明

翻译自 第19回日本情報オリンピック 春季トレーニング合宿 Day4 B 伝説の団子職人