当前位置: 首页 > news >正文

构造+贪心,CF 432E,Square Tiling

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

Problem - 432E - Codeforces


二、解题报告

1、思路分析

很简单的一个构造题

考虑字典序从左到右从上到下,所以我们正常遍历

对于当前格子如果空闲,那么找到一个能填的最小字符

然后检查该格子可扩展的最大边长为多少

然后将正方形填字符即可

2、复杂度

时间复杂度: O((MN)^2)空间复杂度:O(MN)

3、代码详解

 ​
#include <bits/stdc++.h>using i64 = long long;void solve() {int n, m;std::cin >> n >> m;std::vector<std::vector<int>> g(n, std::vector<int>(m));std::array<int, 5> dir { 1, 0, -1, 0, 1 };auto check = [&](int i, int j) -> int {if (g[i][j]) return g[i][j];for (int c = 1; c <= 26; ++ c) {bool f = true;for (int k = 0; k < 4; ++ k) {int ii = i + dir[k], jj = j + dir[k + 1];if (ii < 0 || ii >= n || jj < 0 || jj >= m) continue;if (g[ii][jj] == c) f = false;}if (f) return c;}return 0;};for (int i = 0; i < n; ++ i) {for (int j = 0; j < m; ++ j) {if (g[i][j]) continue;int c = check(i, j);int sz = 0;while (j + sz < m && i + sz < n && check(i, j + sz) == c) ++ sz;-- sz;for (int ii = i; ii <= i + sz; ++ ii)for (int jj = j; jj <= j + sz; ++ jj)g[ii][jj] = c;}}for (int i = 0; i < n; ++ i, std::cout << '\n') for (int j = 0; j < m; ++ j)std::cout << char(g[i][j] - 1 + 'A');
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int _ = 1;// std::cin >> _;while (_ --)solve();return 0;
}

http://www.lryc.cn/news/399407.html

相关文章:

  • 【Linux】任务管理
  • 计算机网络——常见问题汇总
  • Linux的世界 -- 初次接触和一些常见的基本指令
  • [AI 大模型] Meta LLaMA-2
  • Python3.6.6 OpenCV 将视频中人物标记或者打马赛克或加图片并保存为不同格式
  • Readiris PDF Corporate / Business v23 解锁版安装教程 (PDF管理软件)
  • .NET MAUI开源架构_2.什么是 .NET MAUI?
  • 认知偏差知识手册
  • SpringBoot后端代码基本逻辑
  • Python学生信息管理系统的设计与实现
  • 最优雅的PHP框架 Laravel
  • log4j2的日志框架(详细,springboot和异步日志的实现)
  • taocms 3.0.1 本地文件泄露漏洞(CVE-2021-44983)
  • SpringBoot实战:处理全局异常
  • pdf只要前几页,pdf中只要前几页怎么处理
  • 实变函数精解【4】
  • 【BUG】Python3|COPY 指令合并 ts 文件为 mp4 文件时长不对(含三种可执行源代码和解决方法)
  • AI克隆声音,基于函数计算部署GPT-Sovits语音生成模型
  • DP讨论——建造者模式
  • 【JavaScript】解决 JavaScript 语言报错:Uncaught SyntaxError: Unexpected token
  • oracle数据库的plsql免安装版安装
  • stm32使用通用定时器生成pwm
  • 老物件线上3D回忆展拓宽了艺术作品的展示空间和时间-深圳华锐视点
  • 对于多个表多个字段进行查询、F12查看网页的返回数据帮助开发、数据库的各种查询方式(多对多、多表查询、子查询等)。
  • 护网HW面试常问——组件中间件框架漏洞(包含流量特征)
  • 招投标数据采集:为企业决策提供数据支持
  • 02:项目二:感应开关盖垃圾桶
  • eNsp公司管理的网络NAT策略搭建
  • MUR2060CTR-ASEMI无人机专用MUR2060CTR
  • Manim的代码练习02:在manim中Dot ,Arrow和NumberPlane对象的使用