SiriBlog

siriyang的个人博客


  • 首页

  • 排行榜

  • 标签115

  • 分类37

  • 归档320

  • 关于

  • 搜索

CCF-CSP/201912-2回收站选址

发表于 2020-01-16 更新于 2021-10-29 分类于 计算机 , 算法题 , CCF-CSP 阅读次数: Valine:
本文字数: 2.6k 阅读时长 ≈ 2 分钟

CCF-CSP题目汇总

题目

编号: 201912-2

试题名称: 回收站选址

时间限制: 1.0s

内存限制: 512.0MB

题目背景

  开学了,可是校园里堆积了不少垃圾杂物。
  热心的同学们纷纷自发前来清理,为学校注入正能量~

题目描述

  通过无人机航拍我们已经知晓了n处尚待清理的垃圾位置,其中第 $i(1\le i\le n)$处的坐标为$(x_i,y_i)$,保证所有的坐标均为整数。
  我们希望在垃圾集中的地方建立些回收站。具体来说,对于一个位置$(x,y)$是否适合建立回收站,我们主要考虑以下几点:

  • $(x,y)$必须是整数坐标,且该处存在垃圾;
  • 上下左右四个邻居位置,即$(x,y+1)$、$(x,y-1)$、$(x+1,y)$和$(x-1,y)$处,必须全部存在垃圾;
  • 进一步地,我们会对满足上述两个条件的选址进行评分,分数为不大于4的自然数,表示在$(x\pm 1,y\pm 1)$四个对角位置中有几处存在垃圾。
    现在,请你统计一下每种得分的选址个数。

输入格式

  从标准输入读入数据。输入总共有n+1行。
  第1行包含一个正整数n,表示已查明的垃圾点个数。
  第1+i行$(1\le i\le n)$包含由一个空格分隔的两个整数x;和y,表示第i处垃圾的坐标。
  保证输入的n个坐标互不相同。

输出格式

  输出到标准输出。
  输出共五行,每行一个整数,依次表示得分为0、1、2、3和4的回收站选址个数。

样例数据

样例1输入

1
2
3
4
5
6
7
8
7
1 2
2 1
0 0
1 1
1 0
2 0
0 1

样例1输出

1
2
3
4
5
0
0
1
0
0

样例1解释

  如图所示,仅有(1,1)可选为回收站地址,评分为2。
样例2输入

1
2
3
2
0 0
-100000 10

样例2输出

1
2
3
4
5
0
0
0
0
0

样例2解释
  不存在可选地址。

样例3输入

1
2
3
4
5
6
7
8
9
10
11
12
11
9 10
10 10
11 10
12 10
13 10
11 9
11 8
12 9
10 9
10 11
12 11

样例3输出

1
2
3
4
5
0
2
1
0
0

样例3解释
  1分选址:(10,10)和(12,10);
  2分选址:(11,9)。

子任务

  • 测试点1和2,保证对于任意的i皆满足$0\le x_i,y_i \le 2$;
  • 测试点3、4和5,保证对于任意的i皆满足$0\le x_i,y_i \le 500$;
  • 测试点6、7和8,保证对于任意的i皆满足$0\le x_i,y_i\le 10^9$;
  • 测试点9和10,保证对于任意的i皆满足$|x_i|,|y_i|\le 10^9$,即坐标可以是负数。
      所有的测试点保证$1\le n\le 10^3$。

提示

本题中所涉及的坐标皆为整数,且保证输入的坐标两两不同。

解答

分析

  直接将坐标准换位字符串放到set中再进行判断是否存在目标点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <set>
#include <string>

using namespace std;

int main(int argc, char** argv) {

int res[5]={0};
set<string> s;
long in[1001][2];
int n;
char buffer[255];

cin>>n;

for(int i=0;i<n;i++){
cin>>in[i][0]>>in[i][1];
s.insert(string(to_string(in[i][0]))+","+string(to_string(in[i][1])));
}

for(int i=0;i<n;i++){
if(s.find(string(to_string(in[i][0]+1))+","+string(to_string(in[i][1])))!=s.end() &&
s.find(string(to_string(in[i][0]))+","+string(to_string(in[i][1]+1)))!=s.end() &&
s.find(string(to_string(in[i][0]-1))+","+string(to_string(in[i][1])))!=s.end() &&
s.find(string(to_string(in[i][0]))+","+string(to_string(in[i][1]-1)))!=s.end()){
int t=0;
if(s.find(string(to_string(in[i][0]+1))+","+string(to_string(in[i][1]+1)))!=s.end())t++;
if(s.find(string(to_string(in[i][0]+1))+","+string(to_string(in[i][1]-1)))!=s.end())t++;
if(s.find(string(to_string(in[i][0]-1))+","+string(to_string(in[i][1]+1)))!=s.end())t++;
if(s.find(string(to_string(in[i][0]-1))+","+string(to_string(in[i][1]-1)))!=s.end())t++;
res[t]++;
}
}

for(int i=0;i<5;i++){
cout<<res[i]<<endl;
}

return 0;
}
-------- 本文结束 感谢阅读 --------
相关文章
  • CCF-CSP:201409-3字符串匹配
  • CCF-CSP:201403-3命令行选项
  • CCF-CSP/201312-3最大的矩形
  • CCF-CSP:201403-2窗口
  • CCF-CSP:201403-1相反数
觉得文章写的不错的话,请我喝瓶怡宝吧!😀
SiriYang 微信支付

微信支付

SiriYang 支付宝

支付宝

  • 本文标题: CCF-CSP/201912-2回收站选址
  • 本文作者: SiriYang
  • 创建时间: 2020年01月16日 - 23时01分
  • 修改时间: 2021年10月29日 - 18时10分
  • 本文链接: https://blog.siriyang.cn/posts/20200116232748id.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
算法题 CCF-CSP
X-Data数据工程基础实践(六)
CCF-CSP:201912-1报数
  • 文章目录
  • 站点概览
SiriYang

SiriYang

努力搬砖攒钱买镜头的摄影迷
320 日志
33 分类
88 标签
RSS
GitHub E-Mail
Creative Commons
Links
  • 友情链接
  • 作品商铺

  1. 题目
    1. 题目背景
    2. 题目描述
    3. 输入格式
    4. 输出格式
    5. 样例数据
    6. 子任务
    7. 提示
  2. 解答
    1. 分析
    2. 代码
蜀ICP备19008337号 © 2019 – 2025 SiriYang | 1.7m | 25:41
0%