Algorithms&Data Structures

Codeforces Round #615(Div. 3)集锦

A.Collecting Coins

题目大意:给出四个整数a b c n,判断是否存在A+B+C=n使得a+A=b+B=c+C

Solution

假设t=a+A=b+B=c+C,显然可以得出t>=max(a,b,c),通过a b ct的关系我们可以得到一个一元一次方程,剩下的就是判断该方程是否有正整数解

Code

B.Collecting Packages

题目大意:在直角坐标系中给出一些点,机器人起点在原点,只能向右或向上走,判断机器人能否走一趟就途径所有点,如果有输出字典序最小的路径

Solution

因为右比上字典序小,我们可以显然得出把给出的所有点按横坐标排序,这样得到的点就是按横坐标升序,若横坐标相同则纵坐标升序的一坨点了,然后判断当前点和上一个点的位置关系就能得到答案了

Code

C. Product of Three Numbers

题目大意:给出一个整数n,求能否找出不同的三个整数a b c,使得2<=a,b,c并且a*b*c=n,如果能输出任意一个解

Solution

任意正整数都能被质因数唯一分解,所以我们只需要把该数的所有质因数找出来就可以了,然后分类讨论即可

Code

D. MEX maximizing

题目大意:给出两个整数q x,进行q次操作,每次操作给出一个整数,可以选择将该整数变形为加或减x的整数倍,加入到初始为空的序列中,每次操作后求序列的mexmex为每个序列不在该序列中的最小整数

Solution

本题一开始想到一半没法继续了,看了别人的解法后恍然大悟,既然每个整数可以变形,那么我们可以得到所有数通过变形都可以限制在0x-1这个区间,那么我们只需要对0x-1这个区间内所有出现过的数进行计数,每次操作后统计整个区间的最小值就能实现,因为整个序列是动态加的一种状态,所以mex始终是单调不减的,所以我们只需要将mex逐渐递增并判断即可

Code

 

发表评论

邮箱地址不会被公开。 必填项已用*标注