题解：P15429 [IOI 2013] Art Class 艺术分类

· · 题解

考虑相邻两个像素，对于风格 3 和风格 4，明显 4 的差距要更小一些。为了减小颜色相近的两个像素的影响，我们取两个像素颜色欧几里得距离的平方为这两个像素的距离权值。对所有相邻像素的距离权值取平均值。容易发现样例风格 4 的平均权值 \le 200，而风格 3 的平均权值 \ge 2000，于是我们能精准区分出风格 3，风格 4 和剩下的图片。这一步的识别准确率在 98% 及以上。

submission

然后给前面区分 1 和 2 的限制就很宽松了，随便口胡发现 1 的颜色数似乎要少一些，观察样例发现 1 的颜色数几乎在 50000 以下，2 颜色数在 50000 以上。写这个区分可以获得 99.7 分。

submission WAx14

然后随便调一下参数，比如将第一步判断风格 3 的权值提高到 2500 就可以过了。当然仔细区分 1 和 2 肯定可以做到更好，只不过没有必要了，而且其它题解也有讲的清楚的。

submission WAx11

其实继续使用欧氏距离平方也可以很好判断风格 1 和风格 2。学习了 @sevenki 老师的题解后我发现，风格 2 绿色确实要偏多一些。于是我们发动人类智慧，尝试量化一张图有多绿。尝试后发现用当前像素和纯绿色（0,255,0）欧几里得距离平方的平均值可以非常好地区分样例中所有风格 1 和风格 2，取阈值 =57000，认为小于该阈值的图片偏绿属风格 2，否则属于风格 1。

然后就几乎做到了目前 qoj 上的最优解，只错了 3 个。

submission WAx3