| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1328510 | liwuyou | Art Class (IOI13_artclass) | C++20 | 0 ms | 0 KiB |
#include <algorithm>
#include <vector>
using namespace std;
int style(int H, int W, int R[500][500], int G[500][500], int B[500][500]) {
const int COLOR_THRESHOLD = 50; // 颜色相似度阈值（曼哈顿距离）
const int BLACK_THRESHOLD = 80; // 黑色判断阈值（RGB均小于此值）
const int LARGE_BLOCK_AREA = 2000; // 大色块最小面积（约45x45）
const int HUGE_BLOCK_AREA = 15000; // 超大色块最小面积（约122x122）
const int LINE_AREA_MIN = 20; // 线条的最小像素数
const int LINE_AREA_MAX = 1000; // 线条的最大像素数
const float LINE_COMPACTNESS = 0.2f; // 紧凑度 = 面积 / 外接矩形面积，小于此值视为线条
int total_pixels = H * W;
vector<int> parent(total_pixels);
for (int i = 0; i < total_pixels; ++i)
parent[i] = i;
// 带路径压缩的并查集查找
auto find = [&](int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
// 第一遍：合并相邻相似颜色（四连通）
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j) {
int id = i * W + j;
// 检查左边像素
if (j > 0) {
int left_id = i * W + (j - 1);
int dist = abs(R[i][j] - R[i][j - 1]) + abs(G[i][j] - G[i][j - 1]) + abs(B[i][j] - B[i][j - 1]);
if (dist < COLOR_THRESHOLD) {
int rl = find(left_id);
int rr = find(id);
if (rl != rr)
parent[rr] = rl;
}
}
// 检查上边像素
if (i > 0) {
int up_id = (i - 1) * W + j;
int dist = abs(R[i][j] - R[i - 1][j]) + abs(G[i][j] - G[i - 1][j]) + abs(B[i][j] - B[i - 1][j]);
if (dist < COLOR_THRESHOLD) {
int ru = find(up_id);
int rr = find(id);
if (ru != rr)
parent[rr] = ru;
}
}
}
}
// 统计每个区域的信息
vector<int> area(total_pixels, 0);
vector<int> sumR(total_pixels, 0), sumG(total_pixels, 0), sumB(total_pixels, 0);
vector<int> minX(total_pixels, W), maxX(total_pixels, -1);
vector<int> minY(total_pixels, H), maxY(total_pixels, -1);
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j) {
int id = i * W + j;
int root = find(id);
area[root]++;
sumR[root] += R[i][j];
sumG[root] += G[i][j];
sumB[root] += B[i][j];
if (j < minX[root])
minX[root] = j;
if (j > maxX[root])
maxX[root] = j;
if (i < minY[root])
minY[root] = i;
if (i > maxY[root])
maxY[root] = i;
}
}
// 分析区域特征
int max_area = 0; // 最大区域面积
int large_color_blocks = 0; // 非黑色大色块数量
int black_line_count = 0; // 黑色线条数量
int total_regions = 0; // 总区域数
for (int r = 0; r < total_pixels; ++r) {
if (area[r] == 0)
continue;
total_regions++;
if (area[r] > max_area)
max_area = area[r];
// 计算平均颜色
int avgR = sumR[r] / area[r];
int avgG = sumG[r] / area[r];
int avgB = sumB[r] / area[r];
bool is_black = (avgR < BLACK_THRESHOLD && avgG < BLACK_THRESHOLD && avgB < BLACK_THRESHOLD);
// 计算外接矩形面积和紧凑度
int bbox_w = maxX[r] - minX[r] + 1;
int bbox_h = maxY[r] - minY[r] + 1;
int bbox_area = bbox_w * bbox_h;
float compactness = static_cast<float>(area[r]) / bbox_area;
if (is_black) {
// 黑色区域：检查是否为线条
if (area[r] >= LINE_AREA_MIN && area[r] <= LINE_AREA_MAX && compactness < LINE_COMPACTNESS) {
black_line_count++;
}
} else {
// 非黑色区域：检查是否为较大色块
if (area[r] >= LARGE_BLOCK_AREA) {
large_color_blocks++;
}
}
}
// 印象派特征：统计上半部分深绿、下半部分黄绿、角落天空色
int halfH = H / 2;
int quarterW = W / 4;
int quarterH = H / 4;
int deep_green_upper = 0, upper_total = 0;
int yellow_green_lower = 0, lower_total = 0;
int sky_corner = 0, corner_total = 0;
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j) {
int r = R[i][j], g = G[i][j], b = B[i][j];
if (i < halfH) {
upper_total++;
// 深绿色：G为主，略暗，R和B较小
if (g > 100 && g > r + 20 && g > b + 20 && g < 200)
deep_green_upper++;
} else {
lower_total++;
// 黄绿色：G和R都较大，B小
if (g > 150 && r > 100 && g > b + 20 && r > b + 20)
yellow_green_lower++;
}
// 左上角或右上角
if (i < quarterH && (j < quarterW || j >= W - quarterW)) {
corner_total++;
// 天空色：蓝灰或亮黄
bool sky = (b > 150 && r > 100 && r < 200 && g > 100 && g < 200) || // 蓝灰
(r > 220 && g > 220 && b < 150); // 亮黄
if (sky)
sky_corner++;
}
}
}
float upper_deep_green_ratio = (upper_total > 0) ? static_cast<float>(deep_green_upper) / upper_total : 0;
float lower_yellow_green_ratio = (lower_total > 0) ? static_cast<float>(yellow_green_lower) / lower_total : 0;
float corner_sky_ratio = (corner_total > 0) ? static_cast<float>(sky_corner) / corner_total : 0;
// 决策树判断风格
// 1. 超大色块 → 色块组合画
if (max_area > HUGE_BLOCK_AREA) {
return 4;
}
// 2. 黑色线条 + 大色块 → 新造型主义现代画
if (black_line_count >= 1 && large_color_blocks >= 1) {
return 1;
}
// 3. 上半部分深绿、下半部分黄绿、角落有天空 → 印象派风景画
if (upper_deep_green_ratio > 0.1 && lower_yellow_green_ratio > 0.1 && corner_sky_ratio > 0.05) {
return 2;
}
// 4. 区域数量多且平均面积小 → 表现派细节组合画
float avg_area = static_cast<float>(total_pixels) / total_regions;
if (total_regions > 2000 && avg_area < 100) {
return 3;
}
// 默认返回（理论上不会执行到这里，但为保证完整性返回3）
return 3;
}