首页 > 代码库 > 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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。