2月10日 Yahoo Programming Contest 2019
题目链接:https://atcoder.jp/contests/yahoo-procon2019-qual

D – Ears

思路:
我们可以将 Snuke 走过的路抽象成这五个部分:

无论 Snuke 怎么走都会符合这个模型,只是可能有一些部分不会出现。如果发现了这个,后面只要直接 DP 就可以了。设 $f[i][j]$ 为第 $i$ 个位置属于第 $j$ 个部分的代价,转移时加上每个部分相应的代价即可。

代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 200005
#define P 
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, a[MAXN];
LL ans=1e18, f[MAXN][5];

LL cost(int x, int op)
{
    if(op==0 || op==4) return x;
    if(op==1 || op==3)
    {
        if(!x) return 2;
        else return x&1;
    }
    if(op==2)
    {
        if(!x) return 1;
        else return !(x&1);
    }
}

int main()
{
    scanf("%d", &n);
    for(rint i=1; i<=n; ++i) scanf("%d", &a[i]);
    memset(f, 0x3f, sizeof(f));
    for(rint i=0; i<=4; ++i) f[0][i]=0;
    for(rint i=1; i<=n; ++i)
        for(rint j=0; j<=4; ++j)
        {
            if(j) f[i][j]=min(f[i][j], f[i][j-1]);
            f[i][j]=min(f[i][j], f[i-1][j]+cost(a[i], j));
        }
    for(rint i=0; i<=4; ++i) ans=min(ans, f[n][i]);
    printf("%lld\n", ans);
}

E – Odd Subrectangles

思路:
如果行的集合已知,有一个很巧妙的性质:如果这些行的 $m$ 位的异或和不全为 $0$,那么有 $2^{m-1}$ 个列的集合满足题目要求;否则不会有列的集合满足要求。

因此答案就变成了有多少个行的集合它们 $m$ 位的异或和不全为 $0$,这个东西和线性基的大小有关。设线性基的大小为 $siz$,那么不在线性基中 $n-r$ 个行构成的集合中的所有子集,线性基中都有唯一的集合和该子集异或和全为 $0$,因此答案就是 $2^{m-1}*(2^n-2^{n-siz})$。

代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 305
#define P 998244353
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, m, siz, a[MAXN][MAXN], bas[MAXN][MAXN], temp[MAXN], vis[MAXN];

int ksm(int x, int y)
{
    int ans=1;
    while(y)
    {
        if(y&1) ans=1LL*ans*x%P;
        x=1LL*x*x%P; y>>=1;
    }
    return ans;
}

void insert(int a[])
{
    memcpy(temp, a, sizeof(temp));
    for(rint i=1; i<=m; ++i)
        if(temp[i])
        {
            if(!vis[i])
            {
                for(rint j=1; j<=m; ++j) bas[i][j]=temp[j];
                vis[i]=1;
                siz++;
                break;
            }
            for(rint j=1; j<=m; ++j) temp[j]^=bas[i][j];
        }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(rint i=1; i<=n; ++i)
        for(rint j=1; j<=m; ++j) scanf("%d", &a[i][j]);
    for(rint i=1; i<=n; ++i) insert(a[i]);
    printf("%d\n", 1LL*(ksm(2, n)-ksm(2, n-siz)+P)*ksm(2, m-1)%P);
}

F – Pass

思路:
有一个性质是第 $i$ 个球一个是从 $1~i$ 中的一个人手上来的。因此对于序列唯一的限制就是序列中前 $i$ 个中红球数量不能超过前 $i$ 个人手中的红球数量,对于黑球也同理,且序列中后 $n$ 球没有任何限制。然后就可以根据这个性质简单 DP 即可。

代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 2005
#define P 998244353
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, ans, r[MAXN], b[MAXN], c[MAXN*2][MAXN*2], f[MAXN][MAXN];
char s[MAXN];

int main()
{
    scanf("%s", s+1);
    n=strlen(s+1);
    c[0][0]=1;
    for(rint i=1; i<=n*2; ++i)
        for(rint j=0; j<=i*2; ++j) c[i][j]=(c[i-1][j-1]+c[i-1][j])%P;
    for(rint i=1; i<=n; ++i)
    {
        if(s[i]=='0') r[i]=2;
        if(s[i]=='1') r[i]=b[i]=1;
        if(s[i]=='2') b[i]=2;
        r[i]+=r[i-1], b[i]+=b[i-1];
    }
    f[0][0]=1;
    for(rint i=1; i<=n; ++i)
        for(rint j=max(0, i-b[i]); j<=min(i, r[i]); ++j)
        {
            f[i][j]=(f[i][j]+f[i-1][j])%P;
            if(j) f[i][j]=(f[i][j]+f[i-1][j-1])%P;
        }
    for(rint i=max(0, n-b[n]); i<=min(i, r[n]); ++i) ans=(ans+1LL*c[n][r[n]-i]*f[n][i]%P)%P;
    printf("%d\n", ans);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注