Codeforces Gym 100800L Telescope (二维树状数组或暴力水过)

2023-10-10 04:19:46

题目大意：

貌似这个题就是题目意思不太好懂...其实题目本身还是比较简单的

题意是给出一张照片(最多1000*1000的十六进制矩阵)

然后这是一个星体的照片, 并且告诉的是每个位置(x, y)的值是原来的矩阵中以(x, y)为中心的一个N*N的矩阵的值的平均值向下取整的结果

原矩阵中的值要么是0x0000要么是0xFFFF, 在矩阵以外的地方的值都考虑为0

问原来的矩阵中0xFFFF连通块的个数(连通只能上下左右相邻算连通)

比如样例2：

3 5 6

1C71 1C71 1C71 0000 0000 0000

1C71 1C71 1C71 1C71 1C71 1C71

0000 0000 0000 1C71 1C71 1C71

对应的原来的矩阵是：

0000 0000 0000 0000 0000 0000

0000 FFFF 0000 0000 0000 0000

0000 0000 0000 0000 0000 0000

0000 0000 0000 0000 FFFF 0000

0000 0000 0000 0000 0000 0000

FFFF的连通块个数是2个

大致思路：

理解题意之后这个题就知道怎么做了, 对给出的矩阵从左上角开始一排一排扫过去, 遇到非0值就将其作为星体光亮影响的最左上角处理即可

于是需要查询单点的值以及进行矩形范围内的区间修改, 用二维树状数组即可解决

当然这题暴力修改要修改的矩阵中的每一个值也是可以4s+水过的...

代码如下：

Result : Accepted Memory : 9996 KB Time : 389 ms

/** Author: Gatevin* Created Time:  2015/12/6 17:00:41* File Name: Yukinoshita_Yukino.cpp*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const double eps(1e-8);
typedef long long lint;int maz[1010][1010];
int N, n, X, Y;
bool wakanai[1010][1010];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
bool vis[1010][1010];
#define mp make_pair//单点查询区间修改
int C[1010][1010];
int lowbit(int x)
{return -x & x;
}int ask(int x, int y)
{int ret = 0;for(int i = x; i <= X; i += lowbit(i))for(int j = y; j <= Y; j += lowbit(j))ret += C[i][j];return ret;
}void modify(int x, int y, int val)//(1, 1)->(x, y)矩阵都增加val
{for(int i = x; i; i -= lowbit(i))for(int j = y; j; j -= lowbit(j))C[i][j] += val;return;
}void bfs(int sx, int sy)//标记找连通块
{vis[sx][sy] = 1;queue > Q;Q.push(mp(sx, sy));while(!Q.empty()){int nx = Q.front().first, ny = Q.front().second;Q.pop();for(int i = 0; i < 4; i++){int tx = nx + dx[i];int ty = ny + dy[i];if(tx <= 0 || tx > X || ty <= 0 || ty > Y) continue;if(wakanai[tx][ty] && !vis[tx][ty]){Q.push(mp(tx, ty));vis[tx][ty] = 1;}}}return;
}int main()
{scanf("%d %d %d", &n, &X, &Y);N = n;for(int i = 1; i <= X; i++)for(int j = 1; j <= Y; j++){scanf("%x", &maz[i][j]);maz[i][j] = (maz[i][j]*n*n + n*n - 1) / (0xFFFF);}for(int i = 1; i <= X; i++)for(int j = 1; j <= Y; j++)if(maz[i][j]){modify(i, j, maz[i][j]);modify(i - 1, j, -maz[i][j]);modify(i, j - 1, -maz[i][j]);modify(i - 1, j - 1, maz[i][j]);}for(int nx = 1; nx <= X; nx++)for(int ny = 1; ny <= Y; ny++){int val = ask(nx, ny);if(val){wakanai[nx + n/2][ny + n/2] = 1;modify(nx + n - 1, ny + n - 1, -1);modify(nx + n - 1, ny - 1, 1);modify(nx - 1, ny + n - 1, 1);modify(nx - 1, ny - 1, -1);}}memset(vis, 0, sizeof(vis));int cnt = 0;for(int i = 1; i <= X; i++)for(int j = 1; j <= Y; j++){if(wakanai[i][j] && !vis[i][j])bfs(i, j), cnt++;}printf("%d\n", cnt);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！

标签：技术

上一篇 > C语言将一个二维坐标存放在一个整数中
下一篇 > 二级c语言试题总结,二级C语言试题总结(八套)

Duilib中list控件支持ctrl和shif多行选中的实现

[ICML2015]Batch Normalization:Accelerating Deep Network Training by Reducing Internal Covariate Shif

win10系统微软输入法于eclipse ctrl+shif+f冲突间接处理办法

Codeforces Round #259 (Div. 2) B. Little Pony and Sort by Shif

读LDD3，内存映射与DMA--PAGE_SHIF…

VMware虚拟机安装XP【要先分区，再设置BOOT 启动CD，shif+上移】

更换iBus五笔的左与右Shif

sublime ctrl+shif+f 没用解决办法

idea 对 ctrl + z 的撤销是 ctrl + shif + z

计算机最早的设计师应用于,计算机应用基础选择题doc.doc

win10自带截图神器：Win+Shift+S

Python基础之文件目录操作

python简述目录_Python基础之文件目录操作(示例代码)

tp5 如何做数据采集

任务2-7(服务器字体+阿里巴巴矢量库)

html标签（1)：h1~h6,p,br,pre,hr

TI 电量计介绍与芯片选型指南

几款TI电源芯片简介

TI DSP芯片C2000系列读取FLASH数据

德州仪器(Ti)平台嵌入式开发基础

TI三相电机智能栅极驱动芯片特点分类

省选模拟（12.08） T3 圈圈圈圈圈圈圈圈

Hadoop生态圈技术栈（上）

大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之6.Impala交互式查询

小猿圈之Linux下Mysql 操作命令

大数据Hadoop生态圈常用面试题

大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之4.Hive DDL、DQL和数据操作

备战Noip2018模拟赛11（B组）T3 Monogatari 物语

【智能优化算法-圆圈搜索算法】基于圆圈搜索算法Circle Search Algorithm求解单目标优化问题附matlab代码

NYOJ 78 圈水池

递归问题跑道汽车绕圈问题 Python实现

Hadoop生态圈（三）：MapReduce

Codeforces Gym 100800L Telescope (二维树状数组 或 暴力水过)

相关文章

Codeforces Gym 100800L Telescope (二维树状数组或暴力水过)