[Codeforces]Round 659 div2
本文最后更新于 159 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

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

前言

补题。

A

不难发现,每个满足条件的串,可以直接拷贝上串的前 $a_i$ 个字符,随后取与上串不同的一个字符,再乱取即可。
对于 $s_i$,其长度一定可以为 $\max{a_{i-1},a_{i}}$,而一个字符的差别便可以阻断前缀,保险起见把长度开大点。

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

const int bufSize = 1e6;
#define DEBUG
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;
const int maxl = 310;
int T, n;
char s[maxn][maxl];
int a[maxn], len[maxn];
int main()
{
    read(T);
    while (T--)
    {
        read(n);
        for (int i = 1; i <= n; ++i) { read(a[i]); }
        ++n;
        a[n + 1] = 0;
        for (int i = 1; i <= n; ++i) { len[i] = std::max(a[i - 1], a[i]) + 2; }
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= len[i]; ++j) { s[i][j] = 0; }
        for (int i = 1; i <= len[1]; ++i) { s[1][i] = 'a'; }
        for (int i = 2; i <= n; ++i)
        {
            for (int j = 1; j <= a[i - 1]; ++j) { s[i][j] = s[i - 1][j]; }
            for (char j = 'a'; j <= 'z'; ++j)
                if (j != s[i - 1][a[i - 1] + 1])
                {
                    s[i][a[i - 1] + 1] = j;
                    break;
                }
            for (int j = a[i - 1] + 2; j <= len[i]; ++j) { s[i][j] = 'a'; }
            s[i][len[i] + 1] = '\0';
        }
        for (int i = 1; i <= n; ++i) { printf("%s\n", (s[i] + 1)); }
    }
    return 0;
}

B

每 $2 \times k$ 秒一个循环,前 $k$ 秒,深度每秒 $+1$,而后每秒 $-1$,每秒游一个单位,限定到达区域深度不超过 $l$,求能否到达对岸。

首先,如果某点 $d_i + k \leq l$,那么在该点可以随意决定出发时间,记为中转点。在中转点无淹死之忧。

而出发后,要么达到终点,要么达到下一个中转点,否则一定会半途被淹死。

考虑在某点出发,到下一个中转点或终点的过程中,每个位置都不能淹死。
假定不停留,对出发时间分类为涨潮阶段与降潮阶段。

假如在涨潮时出发,那么途中一定不会停留,一路走到下一个中转点,要求每个位置都不淹死。

假如在降潮时出发,贪心地游泳,如果某个点当前可通过,就一定通过,否则等待能通过便通过。
如果走到了涨潮阶段,便又是不停留向前。

发现涨潮时出发,一定可以看做降潮时在起点等到至涨潮时再出发。因此直接模拟降潮时出发即可。

细节恶心,实现困难的模拟题,吞了我快1h的时间。

#include <algorithm>
#include <cstdio>
#include <ctype.h>
const int bufSize = 1e6;
#define DEBUG
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++;
}
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 = 4e5 + 100;
int T, n, k, l;
int d[maxn];
int s[maxn], num;
inline int getx(int x)
{
    if (x <= k) return x;
    else return 2 * k - x;
}
inline int getok(int x)
{
    return l - x;  //getx(t) <= l - x is ok.
}
int main()
{
    read(T);
    while (T--)
    {
        read(n), read(k), read(l);
        for (int i = 1; i <= n; ++i) read(d[i]);
        num = 0;
        s[++num] = 0;
        int pos = 0, t = 0;
        for (int i = 1; i <= n; ++i) if (d[i] + k <= l) s[++num] = i;
        for (int i = 1; i <= n; ++i) if (d[i] > l) goto fail;
        if (s[num] != n) s[++num] = n;  //no matter when we get to the n,we can straightly swim to the island.
        for (int i = 1; i < num; ++i)
        {
            pos = s[i] + 1, t = 2 * k - getok(d[s[i] + 1]);
            while (pos < s[i + 1])
            {
                t %= 2 * k;
                int ok = getok(d[pos + 1]);
                if (t < k)
                {
                    if (ok >= getx(t + 1)) ++t, ++pos;
                    else goto fail;
                }
                else
                {
                    if (ok >= getx(t + 1)) ++t, ++pos;
                    else t = 2 * k - ok, ++pos;
                }
            }
        }
        puts("Yes");
        continue;
    fail:
        puts("No");
    }
    return 0;
}

C

看起来挺友善的题目,每次移动选择字符 $a,b$ 且有 $a < b$,将部分 $=a$ 的字符替换为 $b$,问最少移动次数使得两串相等。

记 $cnt(a,b)$ 为 $A$ 串中字符 $a$ 对应 $B$ 串中位置字符为 $b$ 的个数,特别地,$cnt(b,b) = 0$ 方便处理。
$cnt(a,b)$ 的意义亦为,需要将 $cnt(a,b)$ 个字符 $a$ 转化为字符 $b$。
枚举 $a$,枚举 $b > a$,贪心地将所有处 $A_i = B_i = a$ 的字符 $a$ 转化为 $b$,即对于 $k \in [b + 1,20]$,$cnt(a,k) := cnt(b,k)$,再将 $cnt(a,k)$ 赋值为零。
这样一定不会更劣:
对某位置 $i$,$B_i \neq a$ 且 $B_i \neq b$,本次操作无影响,因为 $B_i > a$ 且需要从 $a$ 转移,操作后 $B_i > b$ 且需要从 $b$ 转移,前者必须操作一次,后者至多操作一次。

当然,官方的图论题解更好理解。对于每个 $A_i < B_i$,从 $A_i$ 向 $B_i$ 连有向边,代表需要从 $A_i$ 转化到 $B_i$,由于 $A_i < B_i$,最后图会被拆分为若干棵树,而对于每棵树,贡献即为树的边数。
似乎无需显式建图,用并查集维护集合及其大小即可,最后答案即为所有集合大小减一的和。

Solution1

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

using namespace std;
const int bufSize = 1e6;
#define DEBUG
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 = 1e5 + 100;
int T, n;
char A[maxn], B[maxn];
int cnt[30][30];
int main()
{
    read(T);
    while (T--)
    {
        read(n);
        read(A + 1), read(B + 1);
        int times = 0;
        for (int i = 1; i <= n; ++i) if (A[i] > B[i]) goto fail;
        for (int i = 1; i <= 20; ++i) for (int j = 1; j <= 20; ++j) cnt[i][j] = 0;
        for (int i = 1; i <= n; ++i) if (A[i] != B[i]) cnt[A[i] - 'a' + 1][B[i] - 'a' + 1]++;
        for (int i = 1; i <= 20; ++i)
        {
            for (int j = i + 1; j <= 20; ++j)
            {
                if (!cnt[i][j]) continue;
                ++times;
                for (int k = j + 1; k <= 20; ++k) cnt[j][k] += cnt[i][k], cnt[i][k] = 0;
            }
        }
        printf("%d\n", times);
        continue;
    fail:
        puts("-1");
    }
    return 0;
}

Solution2

#include <algorithm>
#include <cstdio>
#include <ctype.h>
#include <queue>
using namespace std;
const int bufSize = 1e6;
#define DEBUG
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 = 1e5 + 100;
int T, n;
char A[maxn], B[maxn];
int fa[40], siz[40];
int find(const int& x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
inline void merge(int x, int y)
{
    x = find(x), y = find(y);
    if (x == y) return;
    fa[y] = x, siz[x] += siz[y];
}
int main()
{
    read(T);
    while (T--)
    {
        read(n);
        read(A + 1), read(B + 1);
        int times = 0;
        for (int i = 1; i <= n; ++i) if (A[i] > B[i]) goto fail;
        for (int i = 1; i <= 20; ++i) fa[i] = i, siz[i] = 1;
        for (int i = 1; i <= n; ++i) if (A[i] < B[i]) merge(A[i] - 'a' + 1, B[i] - 'a' + 1);
        for (int i = 1; i <= 20; ++i) if (find(i) == i) times += siz[i] - 1;
        printf("%d\n", times);
        continue;
    fail:
        puts("-1");
    }
    return 0;
}

E

请直接看这位大佬的博客

以下内容全文转载于该大佬博客:


题目传送门

传送门

我怎么菜到这种比赛也能下分。

感觉除了 C,这场比赛剩下的题目都有点愚蠢,就懒得写题解了。注意 D 是要求的是集合相同不是数组相同。

考虑如果 $s_i \neq t_i$ 那么在 $G$ 中连一条 $s_i \rightarrow t_i$ 的有向边。题目相当于要求在另一个初始没有边的新图 $G’$ 中添加若干边,满足每个点经过时间递增的边能够到达旧图中与它直接相连的点。

显然每个弱连通块独立。所以假设 $G’$ 弱连通,设图 $G’$ 的点数为 $n$,其中最大的点导出 DAG 的大小为 $m$,那么答案为 $2n – 1 – m$。

先证明这个是上界,假设不在 DAG 中为 $m + 1, \cdots, n$,那么依次操作 $(m + 1, m + 2), (m + 2, m + 3), \cdots, (n – 1, n), (n, m + 1), \cdots, (m + 1, m + 2), \cdots, (n – 2,n – 1)$,显然此时每个点经过时间递增的边能够到达这中间的所有点,假设 DAG 的拓扑序为 $1, \cdots, m$,那么依次操作 $(n – 1, 1), (1, 2), \cdots, (m – 1 ,m)$。

然后证明这是下界,考虑依次进行每个操作,考虑每个弱连通块维护它的最大点导出 DAG。显然这个 DAG 中的点在图 $G$ 中也是一个点导出 DAG。考虑如果操作了 $(u, v)$

  • 如果 $u, v$ 在同一弱连通块内,考虑如果 $v$ 在 DAG 中,那么删掉 $v$,因此点导出的 DAG 之和至多减少 1。
  • 如果在不同弱连通块,那么连接它们的 DAG。

假设操作了 $k$ 次,那么第二种情况会恰好发生 $n – 1$ 次,情况一至多发生 $k – n + 1$ 次,所以有 $|DAG| \geqslant 2n – k – 1$,即 $k \geqslant 2n – |DAG| – 1$。当 $|DAG|$ 取到最大值时,即为 $k$ 的下界。

剩下是一个普及组 dp,相信大家都会。


贴一下本人代码……

具体地,用并查集求弱联通分量,然后进行所谓的“普及组 dp”求最大点导出DAG。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <ctype.h>
#include <vector>
const int bufSize = 1e6;
#define DEBUG
using namespace std;
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 = 1e5 + 100;
const int maxm = 22;
int T, n;
char A[maxn], B[maxn];
int G[maxm][maxm];
int G2[maxm];
vector<int> s[maxm];
int fa[maxm];
int find(const int& x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
inline void merge(int x, int y)
{
    x = find(x), y = find(y);
    if (x == y) return;
    if (s[x].size() < s[y].size()) swap(x, y);
    fa[y] = x;
    for (vector<int>::iterator it = s[y].begin(); it != s[y].end(); ++it) s[x].push_back(*it);
    s[y].clear();
}
int f[1 << 21], num[1 << 21];
inline void init()
{
    for (int i = 1; i <= 20; ++i) fa[i] = i, s[i].clear(), s[i].push_back(i);
    for (int i = 1; i <= 20; ++i)
        for (int j = 1; j <= 20; ++j) G[i][j] = 0;
}
int main()
{
    for (int i = 0; i < (1 << 20); ++i)
        for (int x = i; x; x >>= 1) num[i] += (x & 1);
    read(T);
    while (T--)
    {
        read(n);
        read(A + 1), read(B + 1);
        init();
        for (int i = 1; i <= n; ++i)
        {
            if (A[i] == B[i]) continue;
            G[A[i] - 'a' + 1][B[i] - 'a' + 1] = 1;
            merge(A[i] - 'a' + 1, B[i] - 'a' + 1);
        }
        int ans = 0;
        for (int i = 1; i <= 20; ++i)
        {
            if (find(i) != i) continue;
            for (unsigned int j = 0; j < s[i].size(); ++j) G2[j] = 0;
            for (unsigned int j = 0; j < s[i].size(); ++j)
                for (unsigned int k = 0; k < s[i].size(); ++k)
                    if (G[s[i][j]][s[i][k]]) G2[j] |= (1 << k);
            int maxx = (1 << (int)s[i].size());
            for (int status = 0; status < maxx; ++status) f[status] = 0;
            f[0] = 1;
            int res = 0;
            for (int status = 0; status < maxx; ++status)
            {
                if (!f[status]) continue;
                res = max(res, num[status]);
                for (unsigned int j = 0; j < s[i].size(); ++j) 
                    if (!(status & (1 << j)) && !(G2[j] & status)) f[status | (1 << j)] = 1;
            }
            ans += 2 * s[i].size() - res - 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}

D

玩家依次拿走数组中某个数,与其手上的数异或,取完数组后问先手能否赢得游戏。

看到异或,自然地从高位开始贪心考虑。

记 $one(i)$ 为从低到高第 $i$ 位为 $1$ 的数字数量,$zero(i)$ 为第 $i$ 位为 $0$ 的数字数量。

轮流取数,先讨论 $one(i)$ 的奇偶性。

若 $one(i)$ 为偶数,则先后手任意取数,最后二人在该位结果都是相同的。例如先手取走 $x$ 个 $1$,若 $x$ 为奇数,则后手也取走了奇数个 $1$,若 $x$ 为偶数,则后手也取走偶数个 $1$。

若 $one(i)$ 为奇数,我们相信此时可以分出胜负。

胜者需要取出奇数个 $1$,二人依次取走两个 $1$,即一共取走 $4$ 个 $1$ 为一个循环,答案不变,因此可以考虑对 $one(i) \bmod 4$ 进行分析。

当 $one(i) \bmod 4 = 1$ 时,先手取走第一个 $1$,随后跟着后手操作,此时 $one(i)$ 被取为偶数,无论后手如何操作,都只能与先手平分剩余的 $1$,先手必胜。

当 $one(i) \bmod 4 = 3$ 时,需要讨论 $zero(i)$ 的奇偶性。

若 $zero(i)$ 为偶数,那么无论先手取什么数,后手跟着取,最终先手被迫取走最后一个 $1$,后手取得奇数个 $1$,必胜。

若 $zero(i)$ 为奇数,那么先手取走一个 $0$ 后,即为上面的情况,先手必胜。

因此:对于 $one(i) \bmod 2 \neq 0$,$one(i) \bmod 4 = 3$ 且 $zero(i) \bmod 2 = 0$ 时后手必胜,否则先手必胜。

若 $one(i) \bmod 2 = 0$ 恒成立,则平手。

虽然看着官方题解能想明白,但思考路径我并不很清楚。

也许大佬们都是手玩看出来的吧orz

#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++;
}
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 = 1e5 + 100;
int T,n,a[maxn];
int one[40],zero[40];
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        for(int i = 1;i<=n;++i) read(a[i]);
        for(int i = 0;i<=30;++i) one[i] = zero[i] = 0;
        for(int j = 0;j<=30;++j) for(int i = 1;i<=n;++i) if(a[i] & (1<<j)) one[j]++; else zero[j]++;
        for(int i = 30;i >= 0;--i) 
        {
            if((one[i] % 2) == 0) continue;
            if((one[i] % 4) == 3 && (zero[i] % 2) == 0)  puts("LOSE");
            else puts("WIN");
            goto end;
        }
        puts("DRAW");
        end:;
    }
    return 0;
}
本文标题:[Codeforces]Round 659 div2
本文作者:Clouder
本文链接: https://www.codein.icu/cf1384/
转载请标明。
暂无评论

发送评论 编辑评论

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