C. Triangles(枚举)

Problem - C - Codeforces

Gildong有一个方形板,由n行n列的方形单元格组成,每个单元格由一个数字(从0到9)组成,第i行第j列的单元格可用(,)表示,每个单元格的边长为1。Gildong喜欢大的东西,所以对于每一个数字d,他想找到一个三角形,这样:三角形的每个顶点都位于单元格的中心。三角形的每个顶点的数字都是d。三角形的至少一条边平行于板子的一条边。你可以假设一条长度为O的边平行于黑板的两边。三角形的面积最大。当然,他不能仅仅满足于找到这些三角形。因此,对于每一个数字d,他要把板子上一个格子的数字换成d,然后找到这样一个三角形。在处理完每个数字后,他把它变回原来的数字。求出他能为每一个数字做出的三角形的最大面积。注意,他可以把三角形的多个顶点放在同一个单元格上,这个三角形可以是简并三角形;即三角形的面积可以是0。另外,请注意,他可以将单元格的数字从d改为d。输入每个测试包含一个或多个测试用例。第一行包含测试用例的数量t (1 S t < 1000)。每个测试用例的第一行包含一个整数n (1 <n < 2000)——棋盘的行数和列数。每个测试用例的下n行都包含一个不带空格的n位数字字符串。第i行第j位是单元格在(i, j)处的数字。每个数字是0到9之间的一个字符。保证所有测试用例的n2和不超过4- 106。输出对于每个测试用例,打印一行10个整数。第i个整数是di-1乘以2后Gildong三角形的最大面积。

Example

input

Copy

5
3
000
122
001
2
57
75
4
0123
4012
3401
2340
1
9
8
42987101
98289412
38949562
87599023
92834718
83917348
19823743
38947912

output

Copy

4 4 1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 1 0 0
9 6 9 9 6 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
18 49 49 49 49 15 0 30 42 42

题解:
对于每个数字,我们可以找到他的最大最小x,y坐标

把同一个数字的x,y坐标储存到一起

 求最大三角形

首先第一个点是我们记录的x,y坐标,要想三角形最大,其中我们可以改变的点应该在四条底边上

这样我们就得到了两个点,已经得到一条边后,看这个点与之前我们记录数字最大最小的x,y坐标,得到高,求最大值即可(说的不是太清楚,代码很清楚)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
//#define int long long
int c[10];
int limit[11][5];
int x[10][4000050];
int y[10][4000040];
void solve()
{
	int n;
	cin >> n;
	for(int i = 0;i <= 9;i++)
	{
		limit[i][1] = 1e9;
		limit[i][2] = -99999;
		limit[i][3] = 1e9;
		limit[i][4] = -99999;
		c[i] = 0;
	}
	for(int i = 1;i <= n;i++)
	{
		for(int j = 1;j <= n;j++)
		{
			char kk;
			cin >> kk;
			int k = kk - '0';
			if(limit[k][1] > i)
			{
				limit[k][1] = i;
			}
			if(limit[k][2] < i)
			{
				limit[k][2] = i;
			}
			if(limit[k][3] > j)
			{
				limit[k][3] = j;
			}
			if(limit[k][4] < j)
			{
				limit[k][4] = j;
			}
			x[k][++c[k]] = i;
			y[k][c[k]] = j;
		}
	}
	for(int i = 0;i <= 9;i++)
	{
		if(c[i] <= 1)
		{
			cout << 0 <<" ";
			continue;
		}
		int ans = 0;
		for(int j = 1;j <= c[i];j++)
		{
			int tx = max(abs(n - x[i][j]),abs(x[i][j] - 1));
			int ty = max(abs(n - y[i][j]),abs(y[i][j] - 1));
			ans = max(ans,max(tx*abs(y[i][j] - limit[i][4]),tx*abs(y[i][j] - limit[i][3])));
			ans = max(ans,max(ty*abs(x[i][j] - limit[i][1]),ty*abs(x[i][j] - limit[i][2])));
		}
		cout << ans <<" ";
	}
	cout << '\n';
}

signed main()
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	int t = 1;
	cin >> t;
	while(t--)
	{
		solve(); 
	}
}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/9331.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

个人-计算机操作系统第六章

第六章 输入输出系统 一、章节习题 1、引入缓冲的主要目的______ A 改善CPU和I/O设备之间速度不匹配的情况 B 节省内存 C 提高CPU的利用率 D 提高I/O设备的效率 2、CPU输出数据的速度远远高于打印机的打印速度&#xff0c;为了解决这一矛盾&#xff0c;可采用_____。 A …

geth指定版本安装

下载源码 cd /usr/local git clone https://github.com/ethereum/go-ethereum.git 或者(mirror) git clone https://ghproxy.com/https://github.com/ethereum/go-ethereum.git拓展&#xff1a;如何git clone指定tag版本 git clone -b v1.10.5 https://github.com/ethereum/…

不要告诉同事你要离职!打算跳槽,新公司开出两倍薪资,私下告诉要好的同事,却被同事出卖给领导!...

职场上有真正的朋友吗&#xff1f;来看看这位网友的讲述&#xff1a;一位前同事本来打算跳槽&#xff0c;新公司开出的薪资是原来的两倍。她私下告诉了几位同事自己打算离职的消息&#xff0c;并跟同事们分享了工资翻倍的喜悦。可她万万没想到&#xff0c;两天之后的公司会议上…

Python 进阶指南(编程轻松进阶):十六、面向对象编程和继承

原文&#xff1a;http://inventwithpython.com/beyond/chapter16.html 定义一个函数&#xff0c;并从几个地方调用它&#xff0c;可以省去复制和粘贴源代码的麻烦。不复制代码是一个很好的实践&#xff0c;因为如果你需要修改它&#xff08;无论是为了修复一个错误还是添加新特…

在Linux系统下使用GDB调试C++程序【命令行调试与vscode编译器调试】

文章目录1. Linux下编译器&#xff0c;调试器安装2. GDB调试器介绍1. 概述2. 常用调试命令参数3. Linux下C命令行调试实战0. 安装超级终端Terminator1. 准备代码2. 进入调试模式3. 调试过程4. Linux下vscode使用cmake和gdb&#xff1a;5. 补充&#xff1a;关于vscode的一些标识…

ChatGPT遭多国调查,OpenAI凌晨就安全问题发文,GPT-5要暂缓?

最近&#xff0c;意大利宣布禁用 ChatGPT&#xff0c;因为 OpenAI 违反了意大利相关的隐私规则和数据保护法&#xff0c;出现了用户数据丢失情况&#xff0c;而且未向用户告知。 消息出来后&#xff0c;德国、法国、爱尔兰、西班牙等国的监管部门都表示正在密切关注 ChatGPT 的…

“智慧”的大楼,为啥落地这么难?

在5A级写字楼上班是什么感觉?      当你加班至凌晨,灯光和空调系统仍然会为你继续服务。      当你进入停车场,系统会自动引导至方便停车的空位。      当你点完外卖但无法抽身时,送餐机器人便会将午饭送到公司门口。    所谓5A,就是指建筑的高度智能化,它包含…

SND0611支持PWM调光功能的线性恒流LED驱动芯片 完美代替SLM411A 用于在各种LED照明产品

深力科电子SND0611支持PWM调光功能的线性恒流LED驱动芯片 完美代替SLM411A 用于在各种LED照明产品 SND0611 系列产品是用于产生单通道、高精度恒 流源的 LED 驱动芯片&#xff0c;在各种 LED 照明产品中 非常简单易用。具有宽输入电压范围、高输出精度、超 低 drop-out 压降、…

Python网络爬虫进阶扩展

学习爬虫不是一天就能学会的&#xff0c;得循序渐进的慢慢学透了&#xff0c;才能更好的做爬虫相关的工作。下面的爬虫有关的有些知识点肯定要学会。 1、如何使scrapy爬取信息不打印在命令窗口中 通常&#xff0c;我们使用这条命令运行自己的scrapy爬虫&#xff1a; scrapy c…

算法风险防控

算法风险防控是指在算法应用过程中&#xff0c;通过对算法应用场景、数据、模型和结果等多个方面的风险进行评估和控制&#xff0c;以保障算法应用的安全性、可靠性和合法性。以下是一些常见的算法风险防控措施&#xff1a; 数据风险防控&#xff1a;在算法应用中&#xff0c;…

Shader Graph6-Dot Product节点(中)

一、Dot Product可以实现褪色的效果&#xff0c;等价与desaturation节点&#xff0c;据说性能比直接使用Desaturation节点有提升&#xff0c;未经过测试。 打开Unity&#xff0c;新建Shader Graph&#xff0c;x0.2126&#xff0c;y0.7152x&#xff0c;z0.0722 UE中是这样的 二…

linux 远程连接MySQL错误“plugin caching_sha2_password could not be loaded”的解决办法乱码

网上有两种解决办法&#xff0c;一种就是升级sqlyog&#xff0c;一种是修改mysql默认身份验证插件。 升级SQLyog 第一种就不用说了&#xff0c;SQLyog-13.1.6-0.x64是默认支持mysql8.0以上身份验证&#xff0c;把低版本的sqlyog升级到13.1.6就可以解决。 修改身份验证插件 首先…

国产台灯哪个品牌比较好?2023分享国内护眼灯排名

台灯已经是最常见的照明灯具&#xff0c;所以近些年受到许多青少年、家长的青睐&#xff0c;如果问国产台灯哪个牌子比较好&#xff1f;我会告诉你&#xff0c;在我使用的十几款护眼台灯中&#xff0c;比较优秀的是南卡护眼台灯Pro、明基MindDuo2 、雷士行星 、京东京造 星云台…

如何访问EMC VPLEX

本文介绍如何访问EMC的VPLEX虚拟化存储网关&#xff0c;下面的方法适用于VPLEX VS2系统&#xff0c;但也适用于VS6系统&#xff0c;只是VS6的管理控制台MMCS和VS2物理上不一样&#xff0c;但实质上是相同的&#xff0c;也都提供了一样的网络端口和IP地址。如果对VS6有问题&…

或许能用 ChatGPT 插件实现财富自由

文章目录或许能用 ChatGPT 插件实现财富自由1. 认识一下1.1 是什么1.2 怎么用2. 举个例2.1 Wolfram2.2 Browsing3. 怎么做到的4. 财富自由4.1 生活类插件4.2 品牌推广类5. 限制或许能用 ChatGPT 插件实现财富自由 我们知道&#xff0c;当前 ChatGPT 最大的局限性就是模型训…

【kubernetes-工具篇】K9S详解-宝藏k8s界面工具

K9S简介 K9s是一个命令行界面&#xff08;CLI&#xff09;工具&#xff0c;用于管理Kubernetes集群。它是一个流行的开源工具&#xff0c;可以帮助Kubernetes管理员和开发人员轻松管理他们的Kubernetes集群。在本文中&#xff0c;我们将简单介绍K9s的概念、功能和如何使用它。…

代码不熟没关系,让AI替你写

程序员早已不是一个陌生的群体&#xff0c;但程序、代码相对普通人而言&#xff0c;看着还是比较深奥难懂&#xff0c;但自从有了ChatGPT&#xff0c;不少对此有兴趣的外行人士&#xff0c;也能轻松写出代码了&#xff0c;比如让ChatGPT写一个贪吃蛇游戏&#xff0c;按它给出的…

Wallpaper:基于Typecho的壁纸头像站主题

简介&#xff1a; 该主题是本人的一个头像壁纸站点的主题&#xff0c;这个站最初是女朋友要让和她用情侣头像和壁纸&#xff0c;跑到网上转了一圈都没找到一个专门的情侣头像壁纸站&#xff0c;只在知乎某个答案下找到一些情侣头像&#xff0c;而情侣壁纸就更难找了&#xff0…

ChatGPT基础知识系列之一文说透ChatGPT

ChatGPT基础知识系列之一文说透ChatGPT OpenAI近期发布聊天机器人模型ChatGPT,迅速出圈全网。它以对话方式进行交互。以更贴近人的对话方式与使用者互动,可以回答问题、承认错误、挑战不正确的前提、拒绝不适当的请求。高质量的回答、上瘾式的交互体验,圈内外都纷纷惊呼。 …

html+css+JavaScript+json+servlet的社区系统(手把手教学)

目录 课前导读&#xff1a; 一、系统前期准备 二、前端代码的编写 三、登陆页面简介 四、注册页面 五、社区列表页 六、社区详情页 七、社区发帖页 八、注销 九、访问链接 登陆页面http://175.178.20.77:8080/java106_blog_system/login.html 总结&#xff1a; 课前…
最新文章