[Codeforces]Round 656 div3 Solution(A-E)
本文最后更新于 189 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

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

前言

放假后的第一场比赛,深夜场。
Div3开小号打了,开始状态奇差,后来还可以,A-E都一发过了,没罚多少时,但开局不利,Rank没进500.
整体有一定的思维难度,质量不错的题目。

A

这次的 A 题做出人数比 B 题还少,卡了我20min……
给出$x = \max(a,b)$,$y = \max(a,c)$,$z = \max(b,c)$ 要求找到任意一组符合条件的 $a,b,c$

一开始想分类讨论没想清楚,后来官方发了个 Announcement 说输出顺序任意,就想到怎么打了。

首先可以确定最大的数,确定最大的数后,最大的数一定出现两次。

那么剩下那个数就是第二大的数,最小的数取 $1$ 即可。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
int T;
int a[4];
int main()
{
    read(T);
    while(T--)
    {
        for(int i = 1;i<=3;++i) read(a[i]);
        std::sort(a + 1,a + 4);
        int maxx = a[3];
        if(a[2] != a[3])
        {
            puts("NO");
            goto end;
        }
        puts("YES");
        printf("%d %d %d\n",maxx,a[1],1);
        end:;
    }
    return 0;
}

B

B 题的数据范围看上去似乎想让人用暴力,但其实是个 $O(n)$ 的结论题。

观察样例发现,只取序列中首次出现的数,就能还原数组。现在我们证明这个结论:

第一个数一定是原数组的第一个数。

将数组中所有出现的第一个数删除后,原先偏序不变。

随后问题即缩小成子问题,依次求解。

删除过程等价于打个值标记,每次取第一个数其实就是顺序遍历。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
int T,n;
const int maxn = 120;
int a[maxn],vis[maxn];
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        for(int i = 1;i<=n;++i) vis[i] = 0;
        for (int i = 1; i <= n * 2; ++i)
        {
            int x;
            read(x);
            if(!vis[x]) vis[x] = 1,printf("%d ",x);
        }
        putchar('\n');
    }
    return 0;
}

c

首先考虑 $b$ 数组的性质,要求每次取头尾元素,所取元素单调不减。

那么一定存在一个峰点,峰点左边元素单调不减,峰点右边元素单调不增。

否则,如果存在双峰点,那么某个峰点内侧的元素就会比其小,从而不满足要求。

那么解法就简单了,从后往前找到第一个峰点,从峰点向前找到第二个峰点,删除第二个峰点即其左边的元素即可。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 2e5 + 100;
int T,n;
int a[maxn],f[maxn];
int front[maxn],back[maxn];
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        for (int i = 1; i <= n; ++i) read(a[i]);
        int top = n;
        while(top > 1 && a[top - 1] >= a[top]) --top;
        int head = top;
        while(head > 1&& a[head - 1] <= a[head]) --head;
        printf("%d\n",head - 1);
    }
    return 0;
}

D

阅读题面,发现好串的定义就是在提示使用分治做法。

每次可以假设左边全是 $c$ 或右边全是 $c$,计算相应的代价,取最小值即可。

这样处理过程就像遍历一棵线段树一样,复杂度 $O(2n)$。

计算代价可以用前缀和快速处理。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
#define int long long
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 2e5 + 100;
char s[maxn];
int sum[maxn][26];
int T,n;
inline int solve(int l,int r,int c)
{
    if(l == r) return c != s[l];
    int mid = l + r >> 1;
    int left = solve(l,mid,c + 1),right = solve(mid + 1,r,c + 1);
    int lval = left + r - mid - (sum[r][c] - sum[mid][c]);
    int rval = right + (mid - l + 1) - (sum[mid][c] - sum[l - 1][c]);
    return std::min(lval,rval);
}
signed main()
{
    read(T);
    while(T--)
    {
        read(n);
        read(s + 1);
        for(int i = 1;i<=n;++i) s[i] -= 'a';
        for (int i = 1; i <= n; ++i) 
        {
            for (int j = 0; j < 26; ++j) sum[i][j] = sum[i - 1][j];
            sum[i][s[i]]++;
        }
        printf("%lld\n",solve(1,n,0));
    }
    return 0;
}

E

给定一个有向图,给一些无向边,要为无向边决定方向,使最终图是个有向无环图。

一开始想在原图上乱搜一通,然后试错法乱选方向,样例都没过去……

但可以发现,无论如何,都是从给定的有向图的性质入手。

如果原图含有环,一定是 NO,否则一定是 YES。

有向无环图才有拓扑排序,而如果最终图有拓扑排序,它就是有向无环图。

对原图进行拓扑排序,顺便判环。

对于每条无向边,按照拓扑排序的顺序决定方向即可。

代码写得乱了点。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
#ifdef DEBUG
    return getchar();
#endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template <typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 2e5 + 100, maxm = maxn << 1;
struct node
{
    int from, to, next, directed;
} E[maxm];
int head[maxn], tot;
inline void add(const int &x, const int &y, const int &t)
{
    E[++tot].next = head[x], E[tot].from = x, E[tot].to = y, E[tot].directed = t, head[x] = tot;
}
int T, n, m;
int in[maxn];
int q[maxn], qh, qt, id[maxn], vis[maxn], cnt, ans;
inline void topo()
{
    qh = 1, qt = 0;
    for (int i = 1; i <= n; ++i) if (!in[i]) q[++qt] = i;
    while (qt >= qh)
    {
        if(ans) return;
        int u = q[qh++];
        id[u] = ++cnt, vis[u]++;
        //        printf("inq:%d\n",u);
        for (int p = head[u]; p; p = E[p].next)
        {
            if (!E[p].directed) continue;
            int v = E[p].to;
            if (--in[v] == 0) q[++qt] = v;
            if (in[v] < 0) ans = 1;
            //            printf("in:%d %d\n",v,in[v]);
        }
    }
    //    for(int i = 1;i<=n;++i) printf("%d %d %d\n",i,id[i],vis[i]);
}
int main()
{
    read(T);
    while (T--)
    {
        ans = tot = cnt = 0;
        read(n), read(m);
        for (int i = 1; i <= n; ++i)
            vis[i] = head[i] = 0, in[i] = 0;
        for (int i = 1; i <= m; ++i)
        {
            int t, a, b;
            read(t), read(a), read(b);
            add(a, b, t);
            if (t)
                in[b]++;
        }
        topo();
        if(ans) {puts("NO"); goto end;}
        for (int i = 1; i <= n; ++i) if (!id[i] || vis[i] != 1){puts("NO");goto end;}
        puts("YES");
        for (int i = 1; i <= m; ++i)
        {
            if (E[i].directed) printf("%d %d\n", E[i].from, E[i].to);
            else if (id[E[i].from] < id[E[i].to]) printf("%d %d\n", E[i].from, E[i].to);
            else printf("%d %d\n", E[i].to, E[i].from);
        }
        continue;
    end:;
    }
    return 0;
}

F

这题赛中没做出来,现在也没来得及补正解,随便口胡两句。

该解法是错误的,第二个pretest就WA了QAQ

主要原因是看错题了。要求删除的叶子都在同一点上,我以为是任选……

以下解法看看就好,愚蠢的代码也贴上来吧。

每次删除恰好 $k$ 个叶子,很容易让人想到贪心。

如果一个节点恰好与 $x$ 个叶子相连,那么删除这 $x$ 个叶子后它将成为叶子。将这种即为一类点。

将所有一类点放入堆中,按 $x$ 升序排序。

也将所有与叶子相连的、不全与叶子相连的点放入堆中,优先级最低,即放在尾部。将这类点记为二类点。

选取 $k$ 个叶子时,从堆顶取出:

如果 $x \leq k$,那么该节点会成为叶子,检查它的父亲是否能成为一类点,如果可以放入堆中,否则作为二类点放入堆中。

如果 $x > k$,那么该节点会取部分,且当前次取叶子成功。更新在堆中的状态。

用配对堆来维护即可。

#include <cstdio>
#include <ext/pb_ds/priority_queue.hpp>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
using namespace std;
using namespace __gnu_pbds;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 2e5 + 100;
int fa[maxn],sonnum[maxn],leafnum[maxn];
struct node
{
    int x,id,type;
    bool operator<(const node &that) const
    {
        if(this->type != that.type) return this->type > that.type;
        return leafnum[id] > leafnum[that.id];
    }
};
int T,n,k;
struct edge
{
    int to,next;
}E[maxn << 1];
int head[maxn],tot;
inline void add(const int &x,const int &y)
{
    E[++tot].next = head[x], head[x] = tot, E[tot].to = y;
}
__gnu_pbds::priority_queue<node,less<node>,pairing_heap_tag> q;
__gnu_pbds::priority_queue<node,less<node>,pairing_heap_tag>::point_iterator vis[maxn];
void dfs(int u)
{
    if (!head[u]) leafnum[fa[u]]++;
    for (int p = head[u]; p; p = E[p].next)
    {
        int v = E[p].to;
        if(v == fa[u]) continue;
        fa[v] = u,dfs(v);
        sonnum[u]++;
    }
    if(sonnum[u] == leafnum[u])
    {
        node t;
        t.x = leafnum[u],t.id = u,t.type = 0;
        vis[u] = q.push(t);
    }
    else if(leafnum[u]) 
    {
        node t;
        t.x = leafnum[u],t.id = u,t.type = 1;
        vis[u] = q.push(t);
    }
}
inline bool take(int now)
{
    while(!q.empty())
    {
        node u = q.top();
        if(now >= u.x)
        {
            //拿光当前点情况
            q.pop();
            now -= u.x;
            if(!u.type)
            {
                sonnum[u.id] = leafnum[u.id] = 0;
                int v = fa[u.id];
                leafnum[v]++;
                if(leafnum[v] == sonnum[v])
                {
                    node t;
                    t.x = leafnum[v],t.type = 0,t.id = v;
                    if(vis[v] == 0) vis[v] = q.push(t);
                    else q.modify(vis[v],t);
                }
                else if(leafnum[v] < sonnum[v])
                {
                    node t;
                    t.x = leafnum[v],t.type = 1,t.id = v;
                    if(vis[v] == 0) vis[v] = q.push(t);
                    else q.modify(vis[v],t);
                }
            }
            else sonnum[u.id] -= u.x, leafnum[u.id] -= u.x;
            if(now == 0) return true;
        }
        else
        {
            //部分取走情况
            leafnum[u.id] -= now, sonnum[u.id] -= now;
            node t;
            t.id = u.id, t.x = leafnum[u.id], t.type = u.type;
            if(vis[u.id] == 0) vis[u.id] = q.push(t);
            else q.modify(vis[u.id], t);
            return true;
        }
    }
    return false;
}
int main()
{
    read(T);
    while(T--)
    {
        tot = 0;
        read(n), read(k);
        for(int i = 1;i<=n;++i) vis[i] = 0,head[i] = 0,sonnum[i] = leafnum[i] = 0,fa[i] = 0;
        while(!q.empty()) q.pop();
        for (int i = 1; i < n; ++i)
        {
            int a, b;
            read(a), read(b);
            add(a, b), add(b, a);
        }
        dfs(1);
        int ans = 0;
        while(take(k)) ++ans;
        printf("%d\n",ans);
    }
    return 0;
}
本文标题:[Codeforces]Round 656 div3 Solution(A-E)
本文作者:Clouder
本文链接: https://www.codein.icu/cf1385/
转载请标明。
暂无评论

发送评论 编辑评论

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