[Codeforces]Educational Codeforces Round 85 赛后总结
本文最后更新于 288 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

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

前言

好久没有打比赛了,周五考完文化课之后看到有深夜场,想了想就打了。
最后只做出来4题,排名一千左右。
在此写一个总结,如有必要也会发布单题题解。咕咕咕

A. Level Statistics

题目传送门

签到题,有点小坑。

题意

一个人在玩游戏,给出若干个状态,以 $(p_i,c_i)$ 来表示他现在进行了 $p_i$ 次游戏,通关了 $c_i$ 次。

解法

很显然,对于每个状态,有如下限制:

  1. $c_i \leq p_i$,因为通关次数不可能比游戏次数还多。
  2. $c_i – c_{i-1} \leq p_i – p_{i-1}$,相对于上次的状态,增加的通关次数不可能比增加的游戏次数多。
  3. $c_{i-1} \leq c_i,p_{i-1} \leq p_i$,时间顺序,无需多说。

有一个坑点就是状态是按时间顺序给出的。只有愚蠢的笔者才会看不懂描述跳这个坑吧
所以并不需要按通关次数等等进行排序。

Code

给出比赛时代码。

#include <cstdio>
#include <algorithm>
using namespace std;
template<typename T>
void read(T &r)
{
    static char c;r=0;
    for(c=getchar();c>'9'||c<'0';c=getchar());
    for(;c>='0'&&c<='9';r=(r<<1)+(r<<3)+(c^48),c=getchar());
}
const int maxn = 110;
int T;
int n;
struct node
{
    int p,c;
}a[maxn];
bool cmp(const node &a,const node &b)
{
    if(a.c == b.c)
        return a.p < b.p;
    return a.c < b.c;
}
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        for(int i = 1;i<=n;++i)
            read(a[i].p),read(a[i].c);
        for(int i = 1;i<=n;++i)
        {
            if(a[i].c > a[i].p)
            {
                puts("NO");
                goto end;
            }
            if(a[i].c < a[i-1].c)
            {
                puts("NO");
                goto end;
            }
            if(a[i].p < a[i-1].p)
            {
                puts("NO");
                goto end;
            }
            if(a[i].c - a[i-1].c > a[i].p - a[i-1].p)
            {
                puts("NO");
                goto end;
            }
        }
        puts("YES");
        end:;
    }
    return 0;
}

B. Middle Class

题目传送门

水题,没啥难度。

题意

给出一堆人,可以从中选出一部分人,将其总财富均分。
定义财富多于 $x$ 的为中产阶级。
问最多有多少中产阶级。

解法

显然要劫富济贫,而总财富需求与人数线性相关。
于是按财富排降序。
计算出假定前 $i$ 个人都是中产所需的总财富。
计算出当前总财富。
两者相比较,如果当前总财富可以满足则继续向下枚举。

Code

给出比赛时代码。

#include <cstdio>
#include <algorithm>
using namespace std;
template<typename T>
void read(T &r)
{
    static char c;r=0;
    for(c=getchar();c>'9'||c<'0';c=getchar());
    for(;c>='0'&&c<='9';r=(r<<1)+(r<<3)+(c^48),c=getchar());
}
const int maxn = 1e5 + 10;
int T,n,x;
int a[maxn];
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        read(x);
        for(int i = 1;i<=n;++i)
            read(a[i]);
        sort(a+1,a+1+n);
        long long now = 0;
        long long need = 0;
        int ans = 0;
        for(int i = n;i;--i)
        {
            now += a[i];
            need += x;
            if(now < need)
            {
                printf("%d\n",ans);
                goto end;
            }
            ++ans;
        }
        if(ans == n)
            printf("%d\n",ans);
        else if(ans == 0)
            puts("0");
        end:;
    }
    return 0;
}

CF1334C Circle of Monsters

题目传送门

思考一会可以得到结论的贪心题。

题意

给出一圈怪兽,每个怪兽有两个属性 $a_i,b_i$,分别代表生命值和死亡后对下一个怪兽的伤害值。
要求最少造成多少伤害就可以杀光怪兽。

解法

首先有一个显然的结论:按顺序杀一定最优。

因为每个怪兽所受到伤害只有两个来源:

  1. 直接造成伤害
  2. 前一个怪兽死亡造成伤害

而开始造成伤害后,因为这只怪兽一定要死,那么肯定是先杀前面一个能更省力。

按顺序杀光怪兽的话,枚举开始点,直接模拟显然是一种可行的做法。
但模拟复杂度 $O(n^2)$ 无法通过,可以用预处理降复杂度。

设 $c_i$ 为前一只怪兽死后,这只怪兽还剩余的血量。
有 $c_i = a_i – b_{i-1}$,边界特殊处理一下即可。

那么求出 $c$ 的总和,记为 $csum$。
假定现在从第 $i$ 只怪兽开始杀,那么:
从 $csum$ 中减去 $c_i$,再加上 $a_i$,即为当前情况的总花费伤害。

复杂度降低到 $O(n)$,可以通过。

Code

给出比赛时的代码。

#include <cstdio>
using namespace std;
template<typename T>
inline T _max(const T &a,const T &b){return a>b?a:b;}
template<typename T>
void read(T &r)
{
    static char c;r=0;
    for(c=getchar();c>'9'||c<'0';c=getchar());
    for(;c>='0'&&c<='9';r=(r<<1)+(r<<3)+(c^48),c=getchar());
}
const int maxn = 3e5 + 10;
int T,n;
long long a[maxn],b[maxn],c[maxn];
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        for(int i = 1;i<=n;++i)
            read(a[i]),read(b[i]);
        long long sum = 0;
        for(int i = 2;i<=n;++i)
            sum += (c[i] = _max(a[i] - b[i-1],0ll));
        sum += (c[1] = _max(a[1] - b[n],0ll));
        int minn = 1;
        long long ans = 1ll << 60;
        for(int i = 1;i<=n;++i)
        {
            long long ret = sum - c[i] + a[i];
            if(ret < ans)
                ans = ret;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

D. Minimum Euler Cycle

题目传送门

依然是贪心的题目。但笔者将其做成了找规律……

题意

给出一张包含 $n$ 个顶点的完全图。
要求出一条路径,使得每条边都经过恰好一次。(单向边)
并且要求经过顶点字典序最小。

解法

笔者先从贪心入手。
很显然从顶点 $1$ 出发,去往顶点 $2$。
此时可以回到顶点 $1$ 使得字典序最小,也可以选择去往其他顶点。
此时笔者考虑到回到顶点 $1$ 后可能无法完成图的遍历,因此暂时搁置了这个想法。

由于数据范围大,笔者猜想一定有规律可以快速求解。
所以笔者写了个 $O(n^2n!)$ 的暴力来打表。

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 50;
int n;
int vis[maxn][maxn];
int path[maxn];
int temp[maxn];
int maxt;
void dfs(int u,int t)
{
    temp[t] = u;
    maxt = t>maxt?t:maxt;
    bool over = true;
    for(int i = 1;i<=n;++i)
        for(int j = 1;j<=n;++j)
            if(i != j && !vis[i][j])
                over = false;
    if(over)
    {
        for(int i = 1;i<=maxt;++i)
            if(temp[i] < path[i])
            {
                for(int j = 1;j<=maxt;++j)
                    path[j] = temp[j];
                break;
            }
            else if(temp[i] > path[i])
                break;
        return;
    }
    for(int i = 1;i<=n;++i)
        if(i != u && !vis[u][i])
        {
            vis[u][i] = 1;
            dfs(i,t+1);
            vis[u][i] = 0;
        }
}
int main()
{
    memset(path,0x3f,sizeof(path));
    scanf("%d",&n);
    dfs(1,1);
    for(int i = 1;i<=maxt;++i)
        printf("%d ",path[i]);
    return 0;
}

打表后发现,字典序最小的路径如下形式:

n = 2: 
1 2 
1

n = 3: 
1 2 1 3
2 3
1

n = 4:
1 2 1 3 1 4
2 3 2 4
3 4
1
......

找到规律了,此时可以结合之前的贪心思路:
由顶点 $1$ 访问到其他点后,再回到顶点 $1$ 可以使得字典序最小。
依次访问到最后一点后,可以去往顶点 $2$ 使得字典序最小。
然后如法炮制,不断访问……
最后从最后的顶点再回到顶点 $1$。
刚好全部遍历一遍。

Code

代码实现上,笔者运用了前文的像金字塔一样的规律。
预处理出每层的节点数量,以判断所求左右端点在哪一层。
随后依次输出即可。
层内规律:
设节点在第 $k$ 层的第 $i$ 个节点,那么 $i$ 为奇数时,输出 $k$,否则输出 $k + \frac{i}{2}$。
最后一点是 $1$,特判一下即可。

#include <cstdio>
using namespace std;
template<typename T>
void read(T &r)
{
    static char c;r=0;
    for(c=getchar();c>'9'||c<'0';c=getchar());
    for(;c>='0'&&c<='9';r=(r<<1)+(r<<3)+(c^48),c=getchar());
}
const int maxn = 1e5 + 10;
int T;
long long n,l,r;
long long s[maxn];
long long f;
int main()
{
    read(T);
    while(T--)
    {
        bool flag = false;
        long long lp = 1,rp = 1;
        long long lp2;
        long long rp2;
        read(n);
        f = n * (n-1) + 1;
        read(l);
        read(r);
        for(int i = 1;i<=n;++i)
            s[i] = ((n-i) << 1) + s[i-1];
        if(l == s[n]+1)
        {
            flag = true;
            goto end;
        }
        if(r == s[n]+1)
        {
            flag = true;
            --r;
        }
        while(s[lp] < l)
            ++lp;
        while(s[rp] < r)
            ++rp;
        lp2 = l - s[lp-1];
        rp2 = r - s[rp-1];
        if(lp == rp)
        {
            for(int i = lp2;i<=rp2;++i)
            {
                if(i & 1)
                    printf("%lld ",lp);
                else
                    printf("%lld ",lp + (i>>1));
            }
            goto end;
        }
        for(long long i = lp2;i<=s[lp] - s[lp-1];++i)
        {
            if(i & 1)
                printf("%lld ",lp);
            else
                printf("%lld ",lp + (i>>1));
        }
        for(long long i = lp+1;i<rp;++i)
        {
            for(long long p = 1;p<=s[i] - s[i-1];++p)
            {
                if(p & 1)
                    printf("%lld ",i);
                else
                    printf("%lld ",i + (p>>1));
            }
        }
        for(long long i = 1;i<=rp2;++i)
        {
            if(i & 1)
                printf("%ld ",rp);
            else
                printf("%lld ",rp + (i >> 1));
        }
        end:
        if(flag)
            printf("1");
        printf("\n");
    }
    return 0;
}

End

打完 D 后只剩下半小时,笔者就放弃去睡觉了。
后续题目笔者可能会补题,有必要的会单独发题解。
咕咕咕

本文标题:[Codeforces]Educational Codeforces Round 85 赛后总结
本文作者:Clouder
本文链接: https://www.codein.icu/cfedu85/
转载请标明。

评论

  1. 龙王
    10月前
    2020-4-11 12:16:59

    我也要打比赛咕咕咕

发送评论 编辑评论

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