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

Before the Beginning

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

前言

今晚似乎题分差不大,感觉是手速场,慢手速可怜人又要掉分了。
开题顺序:C->A->B->D
然后D题fst了,rk200->rk600,唉。

C

给每个 $a_i$ 选择任意一个 $b_j$,要求 $a_i \& b_j$ 的异或和最小。
看到位数较小,考虑直接枚举出答案。枚举出答案后,检查该答案是否合法。
时间复杂度 $O(2^9 \times n^2)$,检查答案合法的方案如下:
对于每个 $a_i$,一定要存在 $a_i \& b_j$ 是答案的子集,即 $a_i \& b_j$ 中的每个 $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;
}
const int maxn = 210;
int n,m;
int a[maxn],b[maxn];
int ans[10],tans;
void dfs(int x)
{
    if(x == 9)
    {
        bool can = 1;
        int t = 0;
        for(int i = 0;i<9;++i) t |= ans[i]<<i;
        for(int i = 1;i<=n;++i) 
        {
            bool flag = 0;
            for(int j = 1;j<=m;++j)
            {
                int now = a[i] & b[j];
                if(now & (~t)) continue;
                flag = 1;
            }
            if(!flag) {return;}
        }
        if(can) tans = std::min(t,tans);
        return;
    }
    ans[x] = 0;
    dfs(x + 1);
    ans[x] = 1;
    dfs(x + 1);
}
int main()
{
    tans = 1<<30;
    read(n),read(m);
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1; i <= m; ++i) read(b[i]);
    dfs(0);
    printf("%d\n",tans);
    return 0;
}

A

要求可以构成回文串,说明最后四个数中至多有一个奇数。
每次操作,相当于前三个数减一,最后一个数加三,发现要么不操作,要么操作一次。如果操作两次,奇偶性与不操作相同,三次与一次相同,其他同理。
因此不操作检查,操作一次后再检查,有一个合法则合法。

#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;
long long a[10];
bool check()
{
    int num = 0;
    for(int i = 1;i<=4;++i) if(a[i] & 1) ++num;
    return num <= 1;
}
int main()
{
    read(T);
    while(T--)
    {
        for(int i = 1;i<=4;++i) read(a[i]);
        if(check()) goto suc;
        for (int i = 1; i <= 3; ++i) a[i]--;
        a[4] += 3;
        for (int i = 1; i <= 4; ++i) if (a[i] < 0) goto fail;
        if (check()) goto suc;
        else goto fail;
        suc:
        puts("Yes");
        continue;
        fail: puts("No");
    }
    return 0;
}

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 = 110;
int n,m,sx,sy;
int vis[maxn][maxn];
void dfs(int x,int y)
{
    if(x > n || y > m) return;
    vis[x][y] = 1;
    printf("%d %d\n",x,y);
    for(int i = 1;i<=m;++i) if(!vis[x][i] && vis[x+1][i]) dfs(x,i);
    for(int i = 1;i<=m;++i) if(!vis[x][i]) dfs(x,i);
    if(!vis[x+1][y]) dfs(x + 1,y);
}
int main()
{
    read(n),read(m),read(sx),read(sy);
    vis[sx][sy] = 1;
    printf("%d %d\n",sx,sy);
    dfs(1,sy);
    return 0;
}

D

枚举禁言次数,假定为 $i$,那么就会占用 $(i-1) \times (d+1) +1$ 天(包括说话的那一天和被禁言的 $d$ 天),那么理想状况下就可以取 $n – (i-1) \times (d + 1) – 1$ 个 $a \leq m$,但如果最大占用天数小于 $a > m$ 的个数,说明一定会有 $a > m$ 无法被禁言覆盖,而导致禁言次数无法取到 $i$ 次,而更多。

对于禁言次数为 $i$ 次的情况,占用天数取值范围为 $[(i-1) \times (d + 1) + d,i \times (d + 1)]$,即最后一天后面可以占用 $[0,d]$ 个数。若占用天数上界仍小于 $a > m$ 的个数,说明该 $i$ 值不合法。

在合法的情况下,取最大的 $i$ 个 $a > m$ 与最大的 $n – (i-1) \times (d + 1) – 1$ 个 $a \leq m$ 即可。

#include <algorithm>
#include <cstdio>
#include <ctype.h>

const int bufSize = 1e6;
inline char nc()
{
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
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 n, m, anum, bnum;
long long d;
int a[maxn], b[maxn];
long long asum[maxn], bsum[maxn];
bool cmp(const int& a, const int& b) { return a > b; }
int main()
{
    read(n), read(d), read(m);
    for (int i = 1; i <= n; ++i)
    {
        int x;
        read(x);
        if (x <= m) a[++anum] = x;
        else b[++bnum] = x;
    }
    std::sort(a + 1, a + 1 + anum, cmp);
    std::sort(b + 1, b + 1 + bnum, cmp);
    for (int i = 1; i <= n; ++i) asum[i] = asum[i - 1] + a[i];
    for (int i = 1; i <= bnum; ++i) bsum[i] = bsum[i - 1] + b[i];
    long long ans = 0;
    if (bnum == 0) ans = asum[anum];
    for (int i = 1; i <= bnum; ++i)
    {
        long long need = (i - 1) * (d + 1) + 1;
        if (bnum > need + d) continue;
        if (need > n) break;
        ans = std::max(ans, bsum[i] + asum[n - need]);
    }
    printf("%lld\n", ans);
    return 0;
}
本文标题:[Codeforces]Round 664 div2 题解(A-D)
本文作者:Clouder
本文链接: https://www.codein.icu/cf1389/
转载请标明。

评论

  1. 5月前
    2020-8-13 8:12:43

    您太强了 一场上绿

    • Clouder 博主
      5月前
      2020-8-13 13:59:03

      您一场都上紫了/kel

发送评论 编辑评论

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