目录

M-SOLUTIONS Programming Contest 2020

A - Kyu in AtCoder

题目大意

给出一个$x$,根据$x$除以200的结果输出不同的结果

数据范围

$400 \le x \le 1999$

解题思路

水题,若干个if即可解决

B - Magic 2

题目大意

给出$A,B,c$,每次操作可以把某个数乘以2,问能不能再$K$次操作以内实现$A < B < C$

数据范围

$1 \le A,B,C,K \le 7$

解题思路

水题,直接模拟即可

C - Marks

题目大意

有$n$个正整数$A_i$,从第$K + 1$个开始,每次询问这个数以及前$K-1$个数的乘积是否比前$K$个数的乘积要大

数据范围

$1 \le n \le 200000$,$1 \le K \le N-1$,$1 \le A_i \le 10^9$

解题思路

本质上是询问第$i$个数和第$i-K$个数哪个大,直接$O(n)$解决

D - Road to Millionaire

题目大意

你一开始有1000块钱,现在给出每天一股的价格,问$n$天后你最多有多少钱

数据范围

$1 \le n \le 80$,$100 \le A_i \le 200$

解题思路

经典贪心,每天先尽量卖出,如果明天的价格比今天高就再买入

E - M's Solution

题目大意

n个城市,都在整点上。第i个城市住了$a_i$个人。一开始有x=0,y=0两条铁路。城市到铁路的距离为到所有铁路距离的最小值。问再建1-n条铁路后,所有人到铁路的距离之和最小是多少

数据范围

$n\le 15$

解题思路

显然,最优情况的每条铁路都必须要穿过一座城市。每座城市有没铁路,铁路横穿,铁路纵穿三种情况。$n\times 3^15$能过,直接搜索即可。

F - Air Safety

题目大意

给出若干个飞机的坐标及航向,每个飞机的速度相同,均为0.1格/s,问是否会发生相撞,如果是,最早的相撞发生在几秒后

数据范围

$1 \le n,X_i,Y_i \le 200000$

解题思路

对于某一个航向,记录有可能与它相撞的方向来的飞机,每一种情况开一个set维护一下,每次使用upper_bound查询,细节有点麻烦但是不难