[Codeforces]Round 660 div2题解(A-D)
本文最后更新于 156 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

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

前言

补题。感觉这场有点水,ABCD都挺好做的。

A

至少3个近似素数的话,只要选定了3个,最后一个数就无限制了,因此可以考虑构造出3个必选的近似素数,剩下一个数做减法就可以求出来。
选择最小的三个:$6$ $10$ $14$ 即可,最后一个数为 $n – 30$。有个坑点是数不能重复,如果 $n – 30$ 等于前三者中某个数,就要换掉某个数,选用另外的近似素数,让最后一个数取其他值。则将 $14$ 改成 $15$ ,$n – 30$ 改成 $n – 31$ 即可。

#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 main()
{
    read(T);
    while(T--)
    {
        read(n);
        if(n <= 30) puts("No");
        else
        {
            puts("Yes");
            if(n == 36 || n == 40 || n == 44) printf("6 10 15 %d\n",n - 31);
            else printf("6 10 14 %d\n",n - 30);
        }
    }
    return 0;
}

B

贪心地高位填 $9$,而在低位一共要舍去 $n$ 位,填 $8$ 是性价比最高的,一个 $8$ 可以占四位,并且最高位为 $1$ 可能为 $r$ 做贡献,而如果填 $9$ 则尾数为 $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 f[5] = {0,0,2,4,8};
const int maxn = 2e5 + 100;
int T,n;
int a[maxn];
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        int x = n,cnt = 0;
        while(x > 0)
        {
            x -= 4,a[++cnt] = 8;
        }
        while(cnt < n) a[++cnt] = 9;
        for(int i = n;i;--i) printf("%d",a[i]);
        putchar('\n');
    }
    return 0;
}

C

先计算出 $sum(u)$ 为以 $u$ 为根的子树中 $\sum p$,那么经过该点的人数就是 $sum(u)$。
设该点有 $good(u)$ 个人心情好,则有:$good(u) – [sum(u) – good(u)] = h(u)$,进而可以解得 $good(u)$,如果无整数解则错误。
同时 $h(u)$ 的取值范围为 $[-sum(u),sum(u)]$。
然后由于心情只会变坏不会变好,$\sum good(u) \leq good(fa)$,依次判断即可。

#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 maxm = 4e5 + 100;
const int maxn = 2e5 + 100;
struct node
{
    int to,next;
}E[maxm];
int head[maxn],tot;
inline void add(const int &x,const int &y)
{
    E[++tot].next = head[x],E[tot].to = y,head[x] = tot;
}
int T,n,m;
int w[maxn],h[maxn],good[maxn];
int sum[maxn];
int flag;
void dfs(int u,int fa)
{
    sum[u] = w[u];
    for (int p = head[u]; p; p = E[p].next)
    {
        int v = E[p].to;
        if(v == fa) continue;
        dfs(v,u);
        sum[u] += sum[v];
    }
}
void dfs2(int u,int fa)
{
    if(h[u] < -sum[u] || h[u] > sum[u] || ((sum[u] + h[u]) & 1)) flag = 1;
    good[u] = (sum[u] + h[u]) / 2;
    int goodsum = 0;
    for (int p = head[u]; p; p = E[p].next)
    {
        int v = E[p].to;
        if(v == fa) continue;
        dfs2(v,u);
        goodsum += good[v];
    }
    if(goodsum > good[u]) flag = 1;
}
int main()
{
    read(T);
    while(T--)
    {
        read(n),read(m);
        flag = 0;
        tot = 0;
        for (int i = 1; i <= n; ++i) head[i] = 0;
        for (int i = 1; i <= n; ++i) read(w[i]);
        for (int i = 1; i <= n; ++i) read(h[i]);
        for(int i = 1;i<n;++i)
        {
            int a,b;
            read(a),read(b),add(a,b),add(b,a);
        }
        dfs(1,0);
        dfs2(1,0);
        if(flag) puts("No");
        else puts("Yes");
    }
    return 0;
}

D

$i$ 点权值累加至 $b_i$ 点,且保证 $b_{b_i} \ldots$ 不会死循环,也就是说,从 $i$ 向 $b_i$ 连边,一定可以构成一个有向无环图。

然后拓扑排序一下,对于每个点,如果 $a_i \ge 0$ 就累加到 $a_{b_i}$ 上,否则最后处理。

输出方案时,对于 $a_i \ge 0$ 的点,按拓扑序顺序输出,$a_i < 0$ 的点要保证不累加到 $a_{b_i}$ 上,按拓扑序逆序输出即可。

#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;
const int maxm = 4e5 + 100;
int n,b[maxn];
long long a[maxn];
struct node
{
    int to,next;
}E[maxm];
int head[maxn];
inline void add(const int &x,const int &y)
{
    static int tot = 0;
    E[++tot].next = head[x],E[tot].to = y,head[x] = tot;
}
int in[maxn];
int q[maxn],qh,qt;
int out[maxn],cnt,out2[maxn],cnt2;
int main()
{
    read(n);
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1; i <= n; ++i) read(b[i]);
    for (int i = 1; i <= n; ++i) if(b[i] != -1) add(i,b[i]),in[b[i]]++;
    long long ans = 0;
    qh = 1;
    for (int i = 1; i <= n; ++i) if(in[i] == 0) q[++qt] = i;
    while(qt >= qh)
    {
        int u = q[qh++];
        ans += a[u];
        if(a[u] >= 0) out[++cnt] = u;
        else out2[++cnt2] = u;
        for (int p = head[u]; p; p = E[p].next)
        {
            int v = E[p].to;
            if(a[u] >= 0) a[v] += a[u];
            if(--in[v] == 0) q[++qt] = v;
        }
    }
    printf("%lld\n",ans);
    for (int i = 1; i <= cnt; ++i) printf("%d ",out[i]);
    for (int i = cnt2; i; --i) printf("%d ",out2[i]);
    return 0;
}
本文标题:[Codeforces]Round 660 div2题解(A-D)
本文作者:Clouder
本文链接: https://www.codein.icu/cf1388/
转载请标明。
暂无评论

发送评论 编辑评论

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