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

Before the Beginning

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

前言

补题。

C

对于每个 $i$,向它前面第一个 $j (p_j > p_i)$ 连边,向后面第一个 $j (p_j > p_i)$ 连边。
问对于长度为 $n$ 的排列,有多少种图中带环。
思考什么时候会出现环。发现只要存在 $i < j < k$,使得 $\min(a_i,a_k) > a_j$,即两数之间出现比两数最小值小的数,就会有环。
假设 $a_i < a_k$,如果有 $a_j < a_i$ 就有环,无环的条件就是 $a_j > a_i$,但如果 $a_j > a_i$ 那么 $k = j$,另一边同理。这说明无环时,每个数都只会与相邻的数连边。
这个限制相当强力,因此可以考虑计算无环的个数,用减法计算出有环的个数。
手玩一下,可以发现无环的情况总是单峰的,即一段单增一段单减。否则就会出现谷底,而导致谷底处小于两边最小值成环。
那么定义 $f(i)$ 为长度为 $i$ 时的无环方案数,$f(i) = f(i-1) \times 2$,具体推导:
对于长度为 $i$ 的某个无环排列,整体加一后,在两侧添加 $1$ 都能构成新的合法排列。例如 $1,2,3$ 变为 $2,3,4$ 后在两侧加 $1$,因为 $1$ 总是最小的,不会影响单峰性。
如果对整体平移的证明感到不够严谨的话,可以用添加 $i + 1$ 的证明方法。要维护单峰,$i + 1$ 只能添加在数值 $i$ 的前面或后面,放在前面则将 $i$ 作为下降的第一个数,放在后面则将 $i$ 作为上升的倒数第二个数。即两种方案。
最后答案就是 $n! – 2^{n-1}$。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
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 = 1e6 + 100;
const int mod = 1e9 + 7;
int n;
long long f[maxn],g;
int main()
{
    read(n);
    g = f[1] = 1;
    for (int i = 2; i <= n; ++i) f[i] = (f[i-1] * 2) % mod,g = (g * i) % mod;
    printf("%lld\n",(((g - f[n]) % mod) + mod) % mod);
    return 0;
}

B

每个点右方向,通向右方或下方的点,要求改变若干个点的方向,使得每点都能到达 $(n,m)$,求最少次数。
不妨从终点开始考虑,对于 $(n-1,m)$ 和 $(n,m-1)$ 来说,方向是唯一固定的,检查是否要更改即可,而对于 $(n-1,m-1)$,任意方向都是可行的。
同理,对于所有的 $(i,m)$ 与 $(n,j)$,都有唯一固定的方向。而其他的所有点,无论方向如何,最后都会走到边界上,因此无需考虑。

#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 T,n,m;
char s[maxn][maxn];
int main()
{
    read(T);
    while(T--)
    {
        read(n),read(m);
        for (int i = 1; i <= n; ++i) read(s[i] + 1);
        int ans = 0;
        for(int i = 1;i<m;++i) if(s[n][i] != 'R') ++ans;
        for(int i = 1;i<n;++i) if(s[i][m] != 'D') ++ans;
        printf("%d\n",ans);
    }
    return 0;
}

A

有一个性质: $p_j OR p_i > \max(p_j,p_i)$,所以直接 $1,2,3,4,\ldots,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;
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        for (int i = 1; i <= n; ++i) printf("%d ",i);
        putchar('\n');
    }
    return 0;
}

D

一旦包含 $4 \times 4$ 的子矩阵,就一定无解。因为 $4 \times 4$ 的矩阵可拆分成四个 $2 \times 2$ 的矩阵,而四个奇数相加一定为偶数。
也就是说 $\min(n,m) < 4$,而且只需要考虑 $2 \times 2$ 的矩阵,因此可以动态规划。
若 $n < m$ 则交换 $n,m$,定义 $f(i,j)$ 为前 $i$ 行满足条件,最后一行状态为 $j$ 的最小花费,枚举当前状态转移即可。
复杂度大概是 $n \times 2^m \times 2^m$。

#include <cstdio>
#include <algorithm>
#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 (; c != '0' && c != '1'; c = nc());
    for (; c == '0' || c == '1'; 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 = 1e6 + 100;
int n,m;
char s[maxn];
int a[maxn];
int f[maxn][10],ok[10][10],num[10];
int main()
{
    read(n),read(m);
    if(std::min(n,m) > 3) 
    {
        puts("-1");
        return 0;
    }
    else if(std::min(n,m) == 1) 
    {
        puts("0");
        return 0;
    }
    if(n >= m)
    {
        for (int i = 1; i <= n; ++i)
        {
            read(s + 1);
            for (int j = 1; j <= m; ++j) a[i] = (a[i] << 1) + s[j] - '0';
        }
    }
    else
    {
        for (int i = 1; i <= n; ++i) 
        {
            read(s + 1);
            for (int j = 1; j <= m; ++j) a[j] = (a[j] << 1) + s[j] - '0';
        }
    }
    if(n < m) std::swap(n,m);
    int maxx = 1 << m;
    num[1] = 1;
    for (int i = 2; i < maxx; ++i) num[i] = num[i >> 1] + (i & 1);
    if(m == 3)
    {
        for (int i = 0; i < maxx; ++i)
            for (int j = 0; j < maxx; ++j)
            {
                int num1 = num[(i & 3)] + num[(j & 3)];
                int num2 = num[(i & 6)] + num[(j & 6)];
                if ((num1 & 1) && (num2 & 1)) ok[i][j] = 1;
            }
    }
    else if(m == 2)
    {
        for (int i = 0; i < maxx; ++i)
            for (int j = 0; j < maxx; ++j)
                if ((num[i] + num[j]) & 1) ok[i][j] = 1;
    }
    for (int i = 0; i < maxx; ++i) f[1][i] = num[i ^ a[1]];
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 0; j < maxx; ++j) f[i][j] = 1 << 30;
        for (int j = 0; j < maxx; ++j)
        {
            for (int k = 0; k < maxx; ++k)
            {
                if (!ok[j][k]) continue;
                int x = num[k ^ a[i]];
                f[i][k] = std::min(f[i][k], f[i - 1][j] + x);
            }
        }
    }
    int ans = 1 << 30;
    for (int i = 0; i < maxx; ++i) ans = std::min(ans, f[n][i]);
    printf("%d\n", ans);
    return 0;
}
本文标题:[Codeforces]Round 663 div2题解(A-D)
本文作者:Clouder
本文链接: https://www.codein.icu/1391-2/
转载请标明。
暂无评论

发送评论 编辑评论

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