博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【ECJTU_ACM 11级队员2012年暑假训练赛(8) - C - Asteroids】
阅读量:6539 次
发布时间:2019-06-24

本文共 1772 字,大约阅读时间需要 5 分钟。

B题要套一个数论的模版,注意m=1!! C题可以二分匹配,把行列看作点; 不能开百度,开谷歌搜题解,再次强调!一经发现,取消成绩!

ECJTU_ACM 11级队员2012年暑假训练赛(8)
4:30:00
 
 
A 
B 
C 
D 
E 
F 
G 
H 
I 
J 
K
C - Asteroids
Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u
     

Description

Bessie wants to navigate her spaceship through a dangerous asteroid field in the shape of an N x N grid (1 <= N <= 500). The grid contains K asteroids (1 <= K <= 10,000), which are conveniently located at the lattice points of the grid. 
Fortunately, Bessie has a powerful weapon that can vaporize all the asteroids in any given row or column of the grid with a single shot.This weapon is quite expensive, so she wishes to use it sparingly.Given the location of all the asteroids in the field, find the minimum number of shots Bessie needs to fire to eliminate all of the asteroids.

Input

* Line 1: Two integers N and K, separated by a single space. 
* Lines 2..K+1: Each line contains two space-separated integers R and C (1 <= R, C <= N) denoting the row and column coordinates of an asteroid, respectively.

Output

* Line 1: The integer representing the minimum number of times Bessie must shoot.

Sample Input

3 41 11 32 23 2

Sample Output

2

Hint

INPUT DETAILS: 
The following diagram represents the data, where "X" is an asteroid and "." is empty space: 
X.X 
.X. 
.X.
 
OUTPUT DETAILS: 
Bessie may fire across row 1 to destroy the asteroids at (1,1) and (1,3), and then she may fire down column 2 to destroy the asteroids at (2,2) and (3,2).

FAQ | About Virtual Judge |   |   | 
All Copyright Reserved ©2010-2012   TEAM 
Anything about the OJ, please ask in the  , or contact author:
Server Time: 
 
 
==============================================================================================
未解。。。。

转载于:https://www.cnblogs.com/ismdeep/archive/2012/08/13/2635969.html

你可能感兴趣的文章
windows核心编程-互斥器(Mutexes)
查看>>
纯手工打造漂亮的垂直时间轴,使用最简单的HTML+CSS+JQUERY完成100个版本更新记录的华丽转身!...
查看>>
java 为啥变量名前要加个m?
查看>>
探索Android中的Parcel机制(上)
查看>>
c++ 类型定义
查看>>
C#开发微信门户及应用(5)--用户分组信息管理
查看>>
怎样实现前端裁剪上传图片功能
查看>>
程序员提高工作效率的15个技巧【Facebook】
查看>>
ffmpeg+SDL2实现的视频播放器「退出、暂停、播放」
查看>>
2011/7/3 第二次评审
查看>>
Openvswitch手册(2): OpenFlow Controller
查看>>
Cocos2d-JS项目之二:studio基础控件的使用
查看>>
tar解压
查看>>
inheritprototype原型继承封装及综合继承最简实例
查看>>
【磁耦隔离接口转换器】系列产品选型指南
查看>>
Apriori 关联算法学习
查看>>
二叉树、红黑树、伸展树、B树、B+树
查看>>
Junit核心——测试集(TestSuite)
查看>>
MVPArms官方首发一键生成组件化,体验纯傻瓜式组件化开发
查看>>
Log4j_学习_00_资源帖
查看>>