codetop题库（codeforces题库）



1、Educational codeforces Round 171 (Rated for Div2)

前三题（A, B, C）

A

You are given a coordinate plane and three integers X, Y, and K. Find two line segments ABand Csuch that

1. the coordinates of points A, B, C, and D are integers;
2. 0≤Ax,Bx,Cx,Dx≤X0≤Ax,Bx,Cx,Dx≤X and 0≤Ay,By,Cy,Dy≤Y0≤Ay,By,Cy,Dy≤Y;
3. the length of segment AB is at least KK;
4. the length of segment CD is at least KK;
5. segments AB and CD are perpendicular: if you draw lines that contain ABAB and CDCD, they will cross at a right angle.

Note that it's not necessary for segments to intersect. Segments are perpendicular as long as the lines they induce are perpendicular.

solution :

题目看似很复杂，其实理解后很简单，只需要特殊情况满足，就是找出min({n,a,b})，四个点正好构成一个正方形， 作为对角线， 即可满足题目条件！！！

B

You are given a strip divided into cells, numbered from left to right from 0 to 10^18. Initially, all cells are white.

You can perform the following operation: choose two white cells i and j, such that i≠j and |i−j|≤k, and paint them black.

A list aa is given. All cells from this list must be painted black. Additionally, at most one cell that is not in this list can also be painted black. Your task is to determine the minimum value of kk for which this is possible.

solution:

因为不管如何，要求k最小，且最多只有只有一个范围外的数可以涂黑，所以只能来两两分布

考虑两种情况 （1） n 为偶数时， 此时为了满足最多一个范围之外的被涂上颜色， 只能从头到尾分布， 每一组两个， 所以只需要找到两两一组的最大差值，即可

（2）n为奇数时， 选出一组数中一个数（下标得为偶数），单独存在，其他按照顺序两两分布，

这样就可以满足条件， 即找出不同数对应的值中的最小值

C

There is a shop that sells action figures near Monocarp's house. A new set of action figures will be released shortly; this set contains nn figures, the ii-th figure costs ii coins and is available for purchase from day ii to day nn.

For each of the nn days, Monocarp knows whether he can visit the shop.

Every time Monocarp visits the shop, he can buy any number of action figures which are sold in the shop (of course, he cannot buy an action figure that is not yet available for purchase). If Monocarp buys at least two figures during the same day, he gets a discount equal to the cost of the most expensive figure he buys (in other words, he gets the most expensive of the figures he buys for free).

Monocarp wants to buy exactly one 11-st figure, one 22-nd figure, ..., one nn-th figure from the set. He cannot buy the same figure twice. What is the minimum amount of money he has to spend?

solution:

这道题为了使总和最小，可以这么理解，先求出总和，然后再减去可以免单的值，为了使和最小，所以尽可能减去大值， 最好的方法就是一个小值和一个大值一起（用最小的值换取最大的值），然后从后往前遍历，用一个指针指向前方值，如果后指针对应的是1，就减去，并且前指针向后移（代表前后匹配），如果是0，前指针向前移，因为为了买到当天的东西，必须需要后一天来满足，所以就没有必要浪费前面的小值，可以留给后面的大值匹配

接下来还有两道简单思考题：

1、

Monocarp is playing a MMORPG. There are two commonly used types of currency in this MMORPG — gold coins and silver coins. Monocarp wants to buy a new weapon for his character, and that weapon costs nn silver coins. Unfortunately, right now, Monocarp has no coins at all.

Monocarp can earn gold coins by completing quests in the game. Each quest yields exactly one gold coin. Monocarp can also exchange coins via the in-game trading system. Monocarp has spent days analyzing the in-game economy; he came to the following conclusion: it is possible to sell one gold coin for aa silver coins (i. e. Monocarp can lose one gold coin to gain aa silver coins), or buy one gold coin for bb silver coins (i. e. Monocarp can lose bb silver coins to gain one gold coin).

Now Monocarp wants to calculate the minimum number of quests that he has to complete in order to have at least nn silver coins after some abuse of the in-game economy. Note that Monocarp can perform exchanges of both types (selling and buying gold coins for silver coins) any number of times.

题目意思： 打一次比赛那一枚金币， 1枚金币 = a 枚银币， b枚银币 =  1 枚金币， 需要n枚银币

solution:

如果 a >  b , 只需要赚取一枚即可！！！ 因为 可以无限兑换

反之， 需要 （n + a - 1） / a 次

Given a positive integer nn, find the maximum size of an interval [l,r] of positive integers such that, for every ii in the interval (i.e., l≤i≤r), n is a multiple of ii.

Given two integers l≤r, the size of the interval [l,r]is r−l+1 (i.e., it coincides with the number of integers belonging to the interval). ps:: n <= 10 ^ 18

题意思：找出n的最长连续因数区间段的长度

solution:

其实我也不知道为啥，但是可以多写几组数据，就会发现最长连续因数的长度是等于从1开始一直到最大的因数（连续）。

官方解释：若找到 [l,r]， 一定可以找到 一个 x (1 <= x <= r - l + 1)， 使区间段[l, r]变为[1,r - l + 1]，

通过找[l,r]里面的各自对应的因数，尽管顺序可能会发生变化

综上所述，cf 在我的观点看来，十分注重思维，注意题目的灵活性，多多练习，迅速找出题目的规律！！！！

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/rfx/34042.html