[Codeforces]671 div2题解
本文最后更新于 123 天前,其中的信息可能已经有所发展或是发生改变。

一道有趣的比赛


Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。
原文链接:https://www.codein.icu/cf1419/

C

既然 Killjoy 不能参加,那么问题等价于:重新分配数字,使得它们全都被感染。
可以发现,如果和恰好是 $x \times n$ ,一次即可。

还有,如果开始就有人感染,一次即可。如果开始全部人感染,零次即可。

否则两次,一次让一个人感染,下一次让全部人感染。

#include <cstdio>
const int maxn = 2e3 + 100;
int T,n,x,a[maxn];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&n,&x);
        int flag = 0,flag2 = 1;
        int sum = 0;
        for (int i = 1; i <= n; ++i) scanf("%d",a + i),flag |= (a[i] == x),flag2 &= (a[i] == x),sum += a[i];
        if(flag2) puts("0");
        else if(flag) puts("1");
        else if(sum == n * x) puts("1");
        else puts("2");
    }
    return 0;
}

D

考虑如何最大化。
显然是构造题。
奇数位置放大,偶数位置放小,为了尽量避免重复,让它们分别有序即可。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 100;
int n,a[maxn],b[maxn];
int main()
{
    scanf("%d",&n);
    for (int i = 1; i <= n; ++i) scanf("%d",a + i);
    sort(a + 1,a + 1 + n);
    int p1 = 1,p2 = n / 2 + 1;
    for (int i = 1; i <= n; ++i) 
    {
        if(i & 1) b[i] = a[p2++];
        else b[i] = a[p1++];
    }
    int ans = 0;
    for (int i = 2; i < n; ++i) if(b[i] < b[i+1] && b[i] < b[i-1]) ++ans;
    printf("%d\n",ans);
    for (int i = 1; i <= n; ++i) printf("%d ",b[i]);
    return 0;
}

E

先对原数进行质因数分解,写成 $n = \prod p_i^{k_i}$,显然最大次数就是 $p_i$ 的个数,考虑:
将质因数依次排列成环,相同的数显然符合,只需要在边界处保证即可。
$p_i,\ldots,p_i,p_{i+1},\ldots,p_{i+1}$
考虑拿出一个 $p_i$ 与 $p_{i+1}$,合成 $p_i \times p_{i+1}$,即可节省下这一次操作次数。
如果有很多个数,选定 $p_i$ 后连续一段都包含 $p_i$ 而不互质,在边界处接上 $p_i \times p_{i+1}$ 与 $p_i \times p_{i-1}$ 就能不花费任何代价。
而只有两个数的时候,缺乏中转点需要特判。
$k_1 = k_2 = 1$ 时,显然一次。
$k_1 > 1$ 或 $k_2 > 1$ 时,可以在交界处构造 $p_1 \times p_2$ 和 $p_1^2 \times p_2$ 或 $p_1 \times p_2^2$,而中间放满即可。

#include <algorithm>
#include <cstdio>
const int maxn = 2e5 + 100;
#define int long long
int T, n;
int d[maxn], cnt, used[maxn];
int k[maxn], pri[maxn], pcnt;
signed main()
{
    scanf("%lld", &T);
    while (T--)
    {
        scanf("%lld", &n);
        pcnt = cnt = 0;
        for (int i = 2; i * i <= n; ++i)
            if ((n % i) == 0) d[++cnt] = i, d[++cnt] = n / i;
        d[++cnt] = n;
        std::sort(d + 1, d + 1 + cnt), cnt = std::unique(d + 1, d + 1 + cnt) - d - 1;
        for (int i = cnt + 1; i <= cnt + 100; ++i) d[i] = 0;
        for (int i = 1; i <= cnt + 100; ++i) k[i] = pri[i] = used[i] = 0;
        int x = n;
        for (int i = 2; i * i <= n; ++i)
            if ((x % i) == 0)
            {
                pri[++pcnt] = i;
                while ((x % i) == 0) ++k[pcnt], x /= i;
            }
        if (x > 1) pri[++pcnt] = x, k[pcnt] = 1;
        for (int i = 1; i <= cnt + 10; ++i) used[i] = 0;
        if (pcnt == 2)
        {
            if (k[1] == 1 && k[2] == 1)
                printf("%lld %lld %lld\n1\n", pri[1], pri[1] * pri[2], pri[2]);
            else
            {
                if (k[1] == 1) std::swap(pri[1], pri[2]), std::swap(k[1], k[2]);
                printf("%lld ", pri[1]);
                for (int i = 1; i <= cnt; ++i)
                    if (d[i] != pri[1] && d[i] != pri[2] && d[i] != pri[1] * pri[2] && d[i] != pri[1] * pri[1] * pri[2])
                        printf("%lld ", d[i]);
                printf("%lld %lld %lld\n0\n", pri[1] * pri[2], pri[2], pri[1] * pri[1] * pri[2]);
            }
            continue;
        }
        pri[pcnt + 1] = pri[1];
        for (int i = 1; i <= pcnt; ++i)
            for (int j = 1; j <= cnt; ++j)
                if (d[j] == pri[i] || d[j] == pri[i] * pri[i + 1]) used[j] = 1;
        for (int i = 1; i <= pcnt; ++i)
        {
            printf("%lld ", pri[i]);
            for (int j = 1; j <= cnt; ++j)
                if (!used[j] && (d[j] % pri[i]) == 0)
                    printf("%lld ", d[j]), used[j] = 1;
            printf("%lld ", pri[i] * pri[i + 1]);
        }
        printf("\n0\n");
    }
    return 0;
}
本文标题:[Codeforces]671 div2题解
本文作者:Clouder
本文链接: https://www.codein.icu/cf1419/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇