Contest1261 - 成都东软学院2016年ACM冬季校赛热身赛 - 题解

心已赠人 2022-07-14 03:49 266阅读 0赞

##    Problem A: A piece of cake  Time Limit: 1 Sec   Memory Limit: 128 MB   Submit: 215   Solved: 57   \[ [Submit][]\]\[ [Status][]\]\[ [BBS][]\] ##

## Description ##

有一天，MM在做老师布置的界面设计作业的时候，他想给屏幕的一块矩形区域涂上某种颜色，于是他思考当鼠标点击某个点时，电脑是如何判断该填充那一块呢？这一想法就引起他的注意。在一个平面直角坐标系，给你鼠标点击的点的坐标和一个矩形，让你判断鼠标点击的点跟矩形的位置关系。为了简化这个问题，保证矩形的四条边分别平行于x轴，y轴。

## Input ##

第一行只有一个整数T(T <= 150)，代表共有T种情况。

接下对于每种情况，均有两行数据：

第一行有两个整数Px Py，以空格分隔，代表点的坐标(Px,Py).

第二行有四个整数Ax Ay Bx By，以空格分隔，代表矩形左下角的坐标(Ax,Ay)和右上角的坐标(Bx,By).

所有的坐标均为区间\[0,100\]内的整数,且Ax<Bx，Ay<By

## Output ##

对于每种情况仅输出一行：

1. 如果点在矩形外部，请输出”Outside”

2. 如果点正好在矩形的边上，请输出”On”

3. 如果点在矩形内部，请输出”Inside”

所有输出都不包含引号。

## Sample Input ##

338 730 7 52 6655 19 13 54 8474 6773 66 76 68

## Sample Output ##

OnOutsideInside

题目大意：

在一个二维坐标系当中，给你一个矩形（分别与x轴和y轴平行）的左下角点A和右上角点B的坐标，然后给你一个点P的坐标，问你点P与矩形的关系（外部，内部，边上）

如下图

![Image 1][]

题目思路：

显然可以根据坐标找到三种情况对应的关系：在内部，Px要在Ax与Bx之间，Py要在Ay与By之间不能相等     ，，，在边上，Px等于Ax或Bx并且Py在Ay与By之间可以相等或Py等于Ay或By并且Px在Ax与Bx之间可以相等，，else 就是在外部

AC代码：自己打

## Problem B: Alyona and copybooks ##

Time Limit: 1 Sec   Memory Limit: 128 MB  
Submit: 164   Solved: 10  
\[ [Submit][Submit 1]\]\[ [Status][Status 1]\]\[ [BBS][BBS 1]\]

## Description ##

Little girl Alyona is in a shop to buy some copybooks for school. She study four subjects so she wants to have equal number of copybooks for each of the subjects. There are three types of copybook's packs in the shop: it is possible to buy one copybook for a rubles, a pack of two copybooks for b rubles, and a pack of three copybooks for c rubles. Alyona already has n copybooks.

What is the minimum amount of rubles she should pay to buy such number of copybooks k that n + k is divisible by 4? There are infinitely many packs of any type in the shop. Alyona can buy packs of different type in the same purchase.

## Input ##

The only line contains 4 integers n, a, b, c (1 ≤ n, a, b, c ≤ 109).

## Output ##

Print the minimum amount of rubles she should pay to buy such number of copybooks k that n + k is divisible by 4.

## Sample Input ##

1 1 3 4

6 2 1 1

## Sample Output ##

## HINT ##

In the second example Alyuna can buy a pack of 2 copybooks for b = 1 ruble. She will have 8 copybooks in total.

这题是上次codeforces的A题：  题目链接：[codeforces Round381div2 A][]

题目大意：

Alyona想要买一些习字帖从学校那里，商店有三种购买类型的供他选择，花a元一次性买1本，花b元一次性买2本，花c元一次性买3本。现在他手上有n本，他还想买k本使得（n+k）% 4 == 0  成立 最少需要花多少钱

题目思路：

这题很容易想到的是暴力从1本开始加，但是看下数据大小1e9 已经超时了，还有一种有技巧的暴力也很容易想到的，先求出最少需要的k，易得 ：  k = 4 -（n%4） 然后暴力k , k+n, k+2n , k+3n , k+4n,,,,,,   但是要加到多少呢？  如果不知道的其实可以加到1,2,3的最小公倍数6 也就是 k+6n  这样也可以，但是还有一种更简单的方法：这里我们先讨论下取    xn   时 a ,b , c 的情况  ：

k=1  ：

1, x=0  ：还需1本  那就是 a

2, x=1 ： 还需5本  那就是 a\*5 或 b+c 显然a\*5>a 所以就是 b+c

3, x=2 :   还需9本  那就是  c\*3

4, x=3  :   还需13本   这里无论你怎么加都要比之前的  a 或 b+c 或 c\*3  要大 因为系数比他打或还加了一个数

同理可得 k = 2  是  b 或 a\*2 或  c\*2 (x=1) 选其他的都要比这三个大 道理同上

k = 3  是  c 或 a\*3  或  a+b    选其他的都要比这三个大 道理同上

所以我们现在只需分类讨论 k 然后取对应k后面三种情况的最小值( 当k=0时就是0不需要了) 因为有个3c  所以要用  long long

AC代码：自己写

## Problem C: 我想睡觉 ##

Time Limit: 1 Sec   Memory Limit: 128 MB  
Submit: 548   Solved: 58  
\[ [Submit][Submit 2]\]\[ [Status][Status 2]\]\[ [BBS][BBS 2]\]

## Description ##

每当我很晚睡的时候，室友的呼噜声就响起了，这就导致我们睡得更晚了。现在我们设自己在没有呼噜声入睡的时间是a分钟，只有一个室友打呼噜在你旁边，你碰他(她)一下他(她)可以b分钟不打呼噜，现在求你至少一次性碰他(她)几下你才能睡着。

## Input ##

分别输入a(0<a<=10^9)和b(0<=b<=10^9)，多组输入。

## Output ##

对于每组a和b，如果你能睡得着那就输出至少需要一次性碰你室友几下，否则输出-1,占一行。

## Sample Input ##

10 4

3 2

## Sample Output ##

题目大意：你的室友打呼噜的时间是a分钟，你碰他一下可以减少他b分钟打呼噜的时间，问最少碰他几次才能使他不打呼噜

题目思路：这题也很容易想到的是暴力从1开始直到a<=0但是看下数据范围1e9 这样就超时了  显然不行 所以我们就会想到除法 直接 a/b 但是当a不能整除b时还要加一  也就是a%b!=0时  这里还有就是要特判 b=0时 无论你碰多少次都不能叫醒他

AC代码：自己写

## Problem D: 找朋友 ##

Time Limit: 3 Sec   Memory Limit: 128 MB  
Submit: 46   Solved: 4  
\[ [Submit][Submit 3]\]\[ [Status][Status 3]\]\[ [BBS][BBS 3]\]

## Description ##

小明有k个朋友在n\*n的二维的地图上，他从这个二维的地图上的一个点出发去找这k个朋友，小明只能上下左右四个方向行走，没走一步要花一分钟的时间，问你最少需要多少分钟才能找到这k个朋友。

## Input ##

每组数据第一行输入两个整数分别是n(2<=n<=100)和k(1<=k<=5)。接下来输入的是n\*n的一个矩阵，'.'代表可以走，'\#'代表墙，'1'代表小明的朋友，'@'是小明。(数据保证小明和他的朋友不会重合)，多组输入。

## Output ##

输出一个整数，如果小明能找到他所有的朋友输出最少需要多少分钟，否则输出-1。

## Sample Input ##

3 2

@.\#

11\#

\#\#\#

2 1

@\#

\#1

## Sample Output ##

\-1

题目大意：给你一张地图 ，你站在@的地方 1 的地方是你的朋友的地方 ，现在你要去找到你所有的朋友，你可以上下左右的移动，移动一次是一个单位时间不可以超出地图范围和走到‘\#’（墙）上 问你找到所有朋友所需的最少时间，如果不能找到就输出 -1

题目大意：这题如果用单纯的bfs或dfs指定要超时或超内存，所以这里要用到状态压缩bfs或者有技巧的bfs和dfs（我就是写的这种）

第一种 ：  因为最多只有5个朋友，所以每一个点的状态最多只有6种还有没有朋友的状态，所以只需开一个三维标记数组 vis\[105\]\[105\]\[1<<5+10\]  时间复杂度是 O(n\*m\*32)

第二种 ：我写的就是这种，先用个bfs找出所有1 并且编号和求出从起点到每个1的时间 如果这里朋友的个数小于了m  那就输出-1 否则  再用个bfs找出从第i个朋友到第j个朋友的距离遍历 i 从 1 - m  这样就预处理所有朋友之间的距离 因为最多只有5个 所有就可以直接dfs找出一条最小的距离 遍历 i从1-m 表示第一个先找i的最小时间 时间复杂度是O(n\*m\*m+m^(m+1))

[Submit]: http://acm.ccniit.com/JudgeOnline/submitpage.php?cid=1261&pid=0&langmask=1012
[Status]: http://acm.ccniit.com/JudgeOnline/problemstatus.php?id=2514
[BBS]: http://acm.ccniit.com/JudgeOnline/phpbb.php?pid=2514&cid=1261
[Image 1]: 
[Submit 1]: http://acm.ccniit.com/JudgeOnline/submitpage.php?cid=1261&pid=1&langmask=1012
[Status 1]: http://acm.ccniit.com/JudgeOnline/problemstatus.php?id=2527
[BBS 1]: http://acm.ccniit.com/JudgeOnline/phpbb.php?pid=2527&cid=1261
[codeforces Round381div2 A]: http://codeforces.com/contest/740/problem/A
[Submit 2]: http://acm.ccniit.com/JudgeOnline/submitpage.php?cid=1261&pid=2&langmask=1012
[Status 2]: http://acm.ccniit.com/JudgeOnline/problemstatus.php?id=2520
[BBS 2]: http://acm.ccniit.com/JudgeOnline/phpbb.php?pid=2520&cid=1261
[Submit 3]: http://acm.ccniit.com/JudgeOnline/submitpage.php?cid=1261&pid=3&langmask=1012
[Status 3]: http://acm.ccniit.com/JudgeOnline/problemstatus.php?id=2524
[BBS 3]: http://acm.ccniit.com/JudgeOnline/phpbb.php?pid=2524&cid=1261