首页 > 代码库 > Codeforces Round #392 (Div. 2)

Codeforces Round #392 (Div. 2)

D题,给出n,k,k是n进制数,但是大于十进制时,它的表示方法仍为十进制那种,比如16进制下的15,我们可以看成就是15,或者1|5,也就是1×16+5 = 21,让你求出能表达的最小十进制数

从后面往前面贪心的取,取越多越好

证明,一个数x和[x/10]相比较,[x/10]和x表示同一个进制的话,肯定是前者比较小,因为如果x取得最小的表示后,我们可以把x最后一位直接去掉,那得到的肯定比原来的小,所以贪心是可行的。

或者dp

dp[i]表示从0,i可以组成的最小十进制数是多少

dp[i] = min(dp[i],dp[j] * n + num[j][i])  j < i 且 num[j][i]要合法,合法就是指不能有前导0,除非它本身就是0,它还要严格小于n

 

F题,给出l,r,n,让你在l和r范围内取n个不同的数,使得这些数组成一个等比数列

设q = y/x,为了保证不重复算所以,gcd(x,y)==1

y != x

我们先假设y > x,因为y < x的情况和y > x是一样的,先算一种然后直接x2就行了

an = a1 * y ^ (n - 1) / x ^ (n - 1);

l <= a1 < an <= r

设d = a1 / x ^ (n - 1)

l <= d * x ^ (n - 1) < d * y ^ (n - 1) <= r

对于不同的x,y,取不同的d就有不同的方案, l / x ^ (n - 1) <= d <= r / y ^ (n - 1)

所以d就可以算出来了。

 

E题 未完

Codeforces Round #392 (Div. 2)