Educational Codeforces Round 77 (Rated for Div. 2)

作者: ffacs 分类: Codeforces 发布时间: 2019-12-31 03:42

A

有k个集合,往一个集合里装x个物品的花费是x*x,求装n个物品的最小花费

解法

\((a_1^2+a_2^2.....a_k^2)\),其中\(\sum_{i=1}^{k} a_i\)是定值。肯定让每一维尽量相等。

\((x + 1)^2 + (y - 1)^2 = x^2 + 2x + 1 + y^2 - 2y + 1 = (x^2 + y^2) + 2(x - y + 1) < x^2 + y^2\)

B

两个数\(a,b\),每次选一个正整数\(x\),使得\(a:=a-x,b:=b-2x\)或者\(a:=a-2x,b:=b-x\),问能否使a,b同时变为0

解法

考虑每次都选\(x=1\),也就是求解 \[f(x)=\left\{ \begin{aligned} 2*x+y=a\\x+2*y=b\end{aligned}\right.\] x和y要求为非负整数,求解一下条件即可

C

在长度为\(10^{100}\)的数轴上,给你三个数字,\(r,b,k \le 1e^9\)。r的倍数染成红,b的倍数染成蓝色,公倍数可以任选红蓝。其它点不染色。把这些染色的点按坐标大小从小到大排列,如果有连续k个是相同颜色就输了,否则就赢了。问能否赢。

解法

首先只用考虑到\(lcm(r,b)\)。因为是循环的。然后数字小的肯定就密集,数字大的就稀疏,所以我们在公倍数上肯定是染大的数字。假设\(a<=b\),问题转化为两个相邻的b的倍数中间最多能有几个a的倍数。那我们肯定是希望区间中的第一个a的倍数离左端点越近越好。\(a*x=b*y+k\),求k的最小值。根据裴蜀定理是\(gcd(a,b)\)。那么只要验证\(b+gcd(a,b)+(k-1)*a\)\(2*b\)的关系即可

D

题意太长省略

解法

先分类讨论,然后画折线代表路径,发现是区间合并地扫雷最优。但是代码写了很久才写对

bool check(int mid){
    int mn=hero[m-mid+1],pos=0,mx=-1,nowt=n+1;
    for(int i=1;i<=k;i++) {
        if(node[i].v<=mn) continue;
        if (node[i].l > mx) { 
            nowt += (mx - pos+1) * 2;
            pos = node[i].l;
        }
        mx = max(mx,node[i].r);
    }
    nowt+=(mx-pos+1)*2;
    if(nowt<=t) return true;
    return false;
}

发表评论

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