2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 F Color it

时间:2021-07-09 19:18:33

链接:https://www.nowcoder.com/acm/contest/163/F

来源:牛客网

2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 F Color it

时间限制:C/C++ 3秒,其他语言6秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld

题目描述

There is a matrix A that has N rows and M columns. Each grid (i,j)(0 ≤ i < N, 0 ≤ j < M) is painted in white at first.
Then we perform q operations:
For each operation, we are given (xc, yc) and r. We will paint all grids (i, j) that meets 2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 F Color it to black.
You need to calculate the number of white grids left in matrix A.

输入描述:

The first line of the input is T(1≤ T ≤ 40), which stands for the number of test cases you need to solve.
The first line of each case contains three integers N, M and q (1 ≤ N, M ≤ 2 x 104; 1 ≤ q ≤ 200), as mentioned above.
The next q lines, each lines contains three integers x

c

, y

c

 and r (0 ≤ x

c

 < N; 0 ≤ y

c

 < M; 0 ≤ r ≤ 10

5

), as mentioned above.

输出描述:

For each test case, output one number.

输入例子:
2
39 49 2
12 31 6
15 41 26
1 1 1
0 0 1
输出例子:
729
0

-->

示例1

输入

复制

2
39 49 2
12 31 6
15 41 26
1 1 1
0 0 1

输出

复制

729
0

题意还是比较简单的,给你n和m的格子让你去画圆,如果这个点在圆内,就要被染色,问你还剩多少点没有被染色

这个题目可以直接暴力扫描线,也就成了维护线段的并

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+;
vector<pair<int,int> >V[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
for(int i=; i<N; i++)V[i].clear();
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
for(int j=,x,y,r; j<q; j++)
{
scanf("%d%d%d",&x,&y,&r);
for(int i=max(,y-r),d; i<=min(m-,y+r); i++)
d=(sqrt(r*r-(y-i)*(y-i)+1e-)),V[i].push_back(make_pair(max(,x-d),min(x+d,n-)));
}
int s=n*m;
for(int i=; i<m; i++)
{
int l=V[i].size();
if(l>)
{
sort(V[i].begin(),V[i].end());
int r=-;
for(auto X:V[i])
{
if(X.second<=r)continue;
if(X.first>r) s-=X.second-X.first+;
else s-=X.second-r;
r=X.second;
}
}
}
cout<<s<<"\n";
}
return ;
}

2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 F Color it的更多相关文章

  1. 2018 ACM 国际大学生程序设计竞赛上海大都会部分题解

    题目链接 2018 ACM 国际大学生程序设计竞赛上海大都会 下午午休起床被同学叫去打比赛233 然后已经过了2.5h了 先挑过得多的做了 .... A题 rand x*n 次点,每次judge一个点 ...

  2. 2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 F Color it &lpar;扫描线&rpar;

    2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 F Color it (扫描线) 链接:https://ac.nowcoder.com/acm/contest/163/F来源:牛客网 时间 ...

  3. 2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 J Beautiful Numbers &lpar;数位DP&rpar;

    2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 J Beautiful Numbers (数位DP) 链接:https://ac.nowcoder.com/acm/contest/163/ ...

  4. 2018 ACM 国际大学生程序设计竞赛上海大都会赛

    传送门:2018 ACM 国际大学生程序设计竞赛上海大都会赛 2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛2018-08-05 12:00:00 至 2018-08-05 17:00:0 ...

  5. 2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 J Beautiful Numbers (数位dp)

    题目链接:https://ac.nowcoder.com/acm/contest/163/J 题目大意:给定一个数N,求区间[1,N]中满足可以整除它各个数位之和的数的个数.(1 ≤ N ≤ 1012 ...

  6. 2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 A,D

    A链接:https://www.nowcoder.com/acm/contest/163/A Fruit Ninja is a juicy action game enjoyed by million ...

  7. 2018 ACM 国际大学生程序设计竞赛上海大都会 F - Color it &lpar;扫描线&rpar;

    题意:一个N*M的矩形,每个点初始都是白色的,有Q次操作,每次操作将以(x,y)为圆心,r为半径的区域涂成黑点.求最后剩余白色点数. 分析:对每行,将Q次操作在该行的涂色视作一段区间,那么该行最后的白 ...

  8. 2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛-B-Perfect Numbers(完数)

    题目描述 We consider a positive integer perfect, if and only if it is equal to the sum of its positive d ...

  9. 2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛-K-Matrix Multiplication(矩阵乘法)

    题目描述 In mathematics, matrix multiplication or matrix product is a binary operation that produces a m ...

随机推荐

  1. 用php生成一个excel文件(原理)

    1.我们用php来生成一个excel文档来讲述其原理: excel2007里面的文档目录组成部分为: 2.我们使用ZipArchive()方法来生成一个简易的excel文件. 使用方法: 3.代码如下 ...

  2. Eclipse &ast;版本

    关于Eclipse的版本介绍, Eclipse Standard 该版本是eclipse最基础的版本,适合Java se个人开发者.或希望根据自己需求配置插件的开发者使用. Eclipse IDE f ...

  3. Lucas的数论&lpar;math&rpar;

    Lucas的数论(math) 题目描述 去年的今日,Lucas仍然是一个热爱数学的孩子.(现在已经变成业界毒瘤了> <) 在整理以前的试题时,他发现了这么一道题目:求\(\sum\limi ...

  4. ASP&period;NET MVC学习系列 WebAPI初探

    转自http://www.cnblogs.com/babycool/p/3922738.html 一.无参数Get请求 一般的get请求我们可以使用jquery提供的$.get() 或者$.ajax( ...

  5. Citrix 服务器虚拟化之六 Xenserver虚拟机创建与快照

    Citrix 服务器虚拟化之六  Xenserver虚拟机创建与快照 在Xenserver上可以创建Windows和Linux等虚拟机,Xenserver支持大部分的主流操作系统,可以使用 XenCe ...

  6. LwIP Application Developers Manual5---高层协议之DHCP&comma;AUTOIP&comma;SNMP&comma;PPP

    1.前言 本文主要讲述高层协议,包括DHCP 2.DHCP 2.1 从应用的角度看DHCP 你必须确保在编译和链接时使能DHCP,可通过在文件lwipopts.h里面定义LWIP_DHCP选项,该选项 ...

  7. 人生苦短之学习Python50本书籍(包涵基础、算法、机器学习、模块、爬虫框架、树莓派等)总有你想要的书籍

    很多小伙伴说想学习想学习但是没有学习书籍,我给大家分享一大波学习书籍,具体的可以自己往下翻 ​<"笨办法学"Python3> Zed Shaw 著 (2018年5月) ...

  8. redis 写磁盘出错 Can’t save in background&colon; fork&colon; Cannot allocate memory &lpar;转&rpar;

    查看 Redis 日志 发现系统在频繁报错: [26641] 18 Dec 04:02:14 * 1 changes in 900 seconds. Saving… [26641] 18 Dec 04 ...

  9. fcntl函数用法详解

    功能描述:根据文件描述词来操作文件的特性. #include <unistd.h> #include <fcntl.h>  int fcntl(int fd, int cmd) ...

  10. 对于ntp&period;conf的理解

    允许与我们的时间源同步时间,但是不允许源查询或修改这个系统上的服务. # Permit time synchronization with our time source, but do not # ...