Atcoder Yahoo Programming Contest 2019 题解

Author Avatar
Sakits 2月 09, 2019

题解

  感觉 atc 的涨分速度很慢啊… 比我 rk 低一位的选手是橙名,涨了 1010 分,我离橙名还差一大截,结果只涨了一点分,这个收敛速度比 CF 慢到不知道哪里去了…
  赛后 1h1h+ 才想出 E 怎么做… 先水个题解压压惊…

D - Ears

  走路题(大雾
  画一画图可以发现到处走路最后的效果其实把序列分成了 55 段。
  第一段没有走到,第二段走了偶数次,第三段走了奇数次,第四段走了偶数次,第五段没有走到。
  分阶段 DP 即可。
  因为一开始对着样例构出了没有 00 时的贪心做法,所以一直往贪心方向想,但是很遗憾这个做法并不能扩展到有 00 时的情况。

D 代码

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn = 500010, inf = 1e9 + 233;
int n;
int a[maxn];
ll f[maxn][5];
 
template<typename T>
inline void read(T &k)
{
    int f = 1; k = 0; char c = getchar();
    while (c < '0' || c > '9') c == '-' && (f = -1), c = getchar();
    while (c <= '9' && c >= '0') k = k * 10 + c - '0', c = getchar();
    k *= f;
}
 
int main()
{
    read(n);
    for (int i = 1; i <= n; i++) read(a[i]);
 
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    for (int i = 1; i <= n; i++)
    {
        f[i][0] = f[i - 1][0] + a[i];
        f[i][1] = min(f[i - 1][0], f[i - 1][1]) + (a[i] == 0 ? 2 : (a[i] & 1));
        f[i][2] = min(min(f[i - 1][0], f[i - 1][1]), f[i - 1][2]) + (!(a[i] & 1));
        f[i][3] = min(min(f[i - 1][0], f[i - 1][1]), min(f[i - 1][2], f[i - 1][3])) + (a[i] == 0 ? 2 : (a[i] & 1));
        f[i][4] = min(min(min(f[i - 1][0], f[i - 1][1]), min(f[i - 1][2], f[i - 1][3])), f[i - 1][4]) + a[i];
    }
 
    printf("%lld\n", min(min(min(f[n][0], f[n][1]), min(f[n][2], f[n][3])), f[n][4]));
}

E - Odd Subrectangles

  一开始一直想的是钦定行之后对答案贡献是 22 的(有奇数个 11 的列个数 - 1)次方,和我之前出过的选奇数个数的方案的题一样… 没想到把偶数的那些忽略了,不然感觉应该还是能做出来的… 想错了之后一直往这个方向想 DP,然后欢声笑语打出 GG…
  考虑钦定一个行的选择方案,发现如果有任意一列包含奇数个 11,那么这种行的选择方案对答案的贡献一定是 2m12^{m - 1},因为另外列不论奇偶性是多少都可以通过这一列来调整得到。那么就是要求有多少方案使得至少有一列包含奇数个 11,这个显然是要补集转化的。
  问题变成求有多少种行的选择方案使得没有一列包含奇数个 11,如果把每行的 0101 状态压成一个数,这就变成了一个经典问题:给一些数,求有多少个子集使得集合内的数异或和为 00
  线性基即可。

E 代码

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define MOD(x) ((x) >= mod ? (x) - mod : (x))
#define ll long long
using namespace std;
const int maxn = 510, inf = 1e9 + 233, mod = 998244353;
int n, m, ans, cnt;
int a[maxn], b[maxn][maxn];
 
template<typename T>
inline void read(T &k)
{
    int f = 1; k = 0; char c = getchar();
    while (c < '0' || c > '9') c == '-' && (f = -1), c = getchar();
    while (c <= '9' && c >= '0') k = k * 10 + c - '0', c = getchar();
    k *= f;
}
 
inline int power(int a, int b)
{
    int ans = 1; 
    for (; b; b >>= 1, a = 1ll * a * a % mod)
        if (b & 1) ans = 1ll * ans * a % mod;
    return ans;
}
 
int main()
{
    read(n); read(m); 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            read(a[j]);
 
        bool flag = 1;
        for (int j = 1; j <= m; j++)
            if (a[j])
            {
                if (b[j][0])
                {
                    for (int k = 1; k <= m; k++)
                        a[k] ^= b[j][k];
                }
                else
                {
                    b[j][0] = 1;
                    for (int k = 1; k <= m; k++)
                        b[j][k] = a[k];
 
                    flag = 0;
                    break;
                }
            }
 
        cnt += flag;
    }
 
    ans = power(2, n) - power(2, cnt) + mod; ans = MOD(ans);
    printf("%lld\n", 1ll * ans * power(2, m - 1) % mod);
}

F - Pass

  这是真走路题了…
  可以发现第 ii 次操作可以使用前 ii 位的所有球,那么设 fi,jf_{i,j} 表示红球用了 ii 个,蓝球用了 jj 个的方案即可。

F 代码

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define MOD(x) ((x) >= mod ? (x) - mod : (x))
#define ll long long
using namespace std;
const int maxn = 4010, inf = 1e9 + 233, mod = 998244353;
int n, ans;
char s[maxn];
int f[maxn][maxn], sumr[maxn], sumb[maxn];
 
template<typename T>
inline void read(T &k)
{
    int f = 1; k = 0; char c = getchar();
    while (c < '0' || c > '9') c == '-' && (f = -1), c = getchar();
    while (c <= '9' && c >= '0') k = k * 10 + c - '0', c = getchar();
    k *= f;
}
 
int main()
{
    scanf("%s", s + 1); n = strlen(s + 1);
    for (int i = 1; i <= n; i++)
    {
        sumr[i] = sumr[i - 1];
        sumb[i] = sumb[i - 1];
 
        if (s[i] == '0') sumr[i] += 2;
        else if (s[i] == '1') sumr[i]++, sumb[i]++;
        else sumb[i] += 2;
    }
    for (int i = n + 1; i <= n * 2; i++) sumr[i] = sumr[i - 1], sumb[i] = sumb[i - 1];
 
    f[0][0] = 1; ans = 0;
    for (int i = 1; i <= n * 2; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            if (sumr[i] - j >= 0 && j) f[j][i - j] = MOD(f[j][i - j] + f[j - 1][i - j]);
            if (sumb[i] - (i - j) >= 0 && i - j) f[j][i - j] = MOD(f[j][i - j] + f[j][i - j - 1]);
            // printf("f[%d][%d]:%d %d %d %d %d\n", j, i - j, f[j][i - j], sumr[i], sumb[i], f[j - 1][i - j], f[j][i - j - 1]);
 
            if (i == 2 * n) ans = MOD(ans + f[j][i - j]);
        }
    }
 
    printf("%d\n", ans);
}