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

一场有趣的cf比赛

Before the Beginning

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

C

可以发现,答案一定是 $2$.
考虑将最大的与其他值合并,合并后得到新的最大值,然后依次合并,最终一定会得到 $2$.
特判 $n = 1$ 的情况。

int main()
{
    read(T);
    while(T--)
    {
        read(n);
        if(n == 1) printf("1\n");
        else
        { 
            puts("2");
            int last = n;
            for(int i = n - 1;i;--i) printf("%d %d\n",i,last),last = (i + last + 1) / 2;
        }
    }
    return 0;
}

A

给定 $n$,求 $3x + 5y + 7z = n$ 的一组解。
随便枚举一下。

int T,n;
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        for(int i = 0;3 * i <= n;++i)
            for(int j = 0;3 * i + 5 * j <= n;++j)
                for(int k = 0;3 * i + 5 * j + 7 * k <= n;++k)
                    if(3 * i + 5 * j + 7 * k == n) 
                    {
                        printf("%d %d %d\n",i,j,k);
                        goto end;
                    }
        printf("-1\n");
        continue;
        end:;
    }
    return 0;
}

B

可以发现,倒水一定是一杯全部倒入另一杯较好。
倒完一次之后,最小值一定是零,只需要最大化最大值即可。
将次大的不断倒入最大的。

int T,n,k;
long long a[maxn];
int main()
{
    read(T);
    while(T--)
    {
        read(n),read(k);
        for (int i = 1; i <= n; ++i) read(a[i]);
        std::sort(a + 1,a + 1 + n);
        long long ans = a[n];
        for (int i = 1; i <= k; ++i) ans += a[n - i];
        printf("%lld\n", ans);
    }
    return 0;
}

D

每次选择一个字符删除,然后删除前缀一整段相同的字符。
一整段字符会被一次删掉,此外还要额外删一个字符。
可以想到,如果选择的单个字符是整段中的一个的话,并不会使答案更劣。
因此优先挑选整段中的字符,直到整段被删成单个字符。
随后每次消耗两个单个字符。
考虑可能最后不足两个单个字符,发现没啥关系,答案照样记即可。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int maxn = 2e5 + 100;
int T,n;
char s[maxn];
int f[maxn],st[maxn],top,r[maxn];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        scanf("%s",s + 1);
        top = 0;
        for (int i = 1; i <= n; ++i)
        {
            f[i] = 1;
            if (s[i] == s[i - 1]) f[i] += f[i - 1], f[i - 1] = 0;
        }
        for (int i = 1; i <= n; ++i) if(f[i]) st[++top] = f[i],r[top] = i;
        int p = 1,now = 1,ans = 0;
        while(now <= top)
        {
            ++ans;
            if(p < now) p = now;
            while(p <= top && st[p] == 1) ++p;
            if(p <= top) --st[p],++now;
            else now += 2;
        }
        printf("%d\n",ans);
    }
    return 0;
}

E

交换相邻,容易想到逆序对。
对于样例的:

icpcsguru
urugscpci

考虑对于目标串中每个字符,来自原串的哪个字符。
目标串出现第 $i$ 次的某字符 $x$,一定是从原串中第 $i$ 次出现的字符 $x$ 移动来的。
要证明这个贪心结论的正确性

bad-prove

对于这么多种情况,按原序都不劣于按逆序。
感性理解一下。

那么就可以这样处理出目标串中每个字符来自于哪个位置,随后统计逆序对即可。

const int maxn = 5e5 + 100;
int n;
char s[maxn],t[maxn];
int sum[maxn];
inline int lowbit(int x){return x & -x;}
int ask(int x)
{
    int res = 0;
    for (; x > 0; x -= lowbit(x)) res += sum[x];
    return res;
}
void add(int x, int k) { for (; x <= n; x += lowbit(x)) sum[x] += k; }
queue<int> q[30];
int to[maxn];
int main()
{
    read(n);
    read(s + 1);
    for (int i = 1; i <= n; ++i) s[i] = s[i] - 'a' + 1, q[s[i]].push(i);
    for (int i = 1; i <= n; ++i) t[i] = s[n - i + 1];
    long long ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        to[i] = q[t[i]].front();
        q[t[i]].pop();
        ans += ask(n) - ask(to[i]);
        add(to[i],1);
    }
    printf("%lld\n",ans);
    return 0;
}

F

明明是 $O(n)$ 的贪心题,却用数据范围欺骗参赛者。
对于一波怪物,只有两个选择:扔掉上次剩下的弹夹,或是不扔。
如果上次剩余的子弹数量足够通过该关,那么就可以省下一个弹夹,否则必须扔掉上次的弹夹,而更换新的弹夹。

贪心结论:如果能不扔弹夹,就不扔弹夹。
对于一波怪物,如果剩余子弹不够,则必须扔。而剩余子弹够,可以选择扔或不扔。
如果扔了的话,是为了剩下更多的子弹给后面用。但是同样可以选择在后面子弹不足时再扔,能让那时拥有更多子弹。
因此总是不扔。

那么每波怪物最少需要多少剩余子弹,才能节省一个弹夹呢?
由于两波怪物端点可能会相交,因此定义:
$f(i)$ 为允许在 $(l_i,r_i]$ 中换弹,第 $i$ 波在 $l_i$ 处的最少剩余子弹。
计算需要多少子弹才能通过关卡,初始有 $need = a_i$
如果 $r_i = l_{i+1}$,那么 $need$ 还要加上 $f(i + 1)$

$f(i) = need – (r_i – l_i) \times k$,随后模拟贪心即可。

const int maxn = 2e3 + 100;
int n, k, l[maxn], r[maxn], a[maxn], f[maxn];
int main()
{
    read(n), read(k);
    for (int i = 1; i <= n; ++i) read(l[i]), read(r[i]), read(a[i]);
    for (int i = n; i; --i)
    {
        int need = a[i];
        if (r[i] == l[i + 1]) need += f[i + 1];
        if (1ll * (r[i] - l[i] + 1) * k < need) { puts("-1"); return 0; }
        f[i] = max(0ll, need - 1ll * (r[i] - l[i]) * k);
    }
    long long ans = 0;
    int now = k;
    for (int i = 1; i <= n; ++i)
    {
        if (now < f[i]) ans += now, now = k;
        ans += a[i];
        now = (((now - a[i]) % k) + k) % k;
    }
    printf("%lld\n", ans);
    return 0;
}
本文标题:[Codeforces]Educational Round96 题解
本文作者:Clouder
本文链接: https://www.codein.icu/cfedu96/
转载请标明。
暂无评论

发送评论 编辑评论

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