1月6日 Educational DP Contest
题目链接:https://atcoder.jp/contests/dp

大部分水题就不讲了,记录几道有趣的题目。

J – Sushi

思路:
期望要倒着推!!!

设 $f_{i,j,k}$ 为有 $i$ 个 $3$ 个的寿司碟子,有 $j$ 个 $2$ 个的寿司碟子,有 $k$ 个 $1$ 个的寿司碟子的期望,那么就有 $n-i-j-k$ 个空着的碟子。然后倒着推期望!!!!

$$ f_{i,j,k}=\frac{i}{n}f_{i-1,j+1,k}+\frac{j}{n}f_{i,j-1,k+1}+\frac{v}{n}f_{i,j,k-1}+\frac{n-i-j-k}{n}f_{i,j,k}+1 $$

$$f_{i,j,k}=\frac{i * f_{i-1,j+1,k}+j * f_{i,j-1,k+1}+v*f_{i,j,k-1}+n}{i+j+k} $$

这样我们就得到了递推的关系。因为转移的顺序问题,我们不能简单地按照 $i, j, k$ 的顺序 DP。但发现转移是从寿司总数少的状态到寿司总数多到状态,因此我们要按照寿司的总数进行 DP。总时间复杂度 $O(n^3)$。

代码:

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

int n, sum, a[MAXN], num[4];
LD f[MAXN][MAXN][MAXN];

int main()
{
    scanf("%d", &n);
    for(rint i=1; i<=n; ++i)
    {
        scanf("%d", &a[i]);
        num[a[i]]++; sum+=a[i];
    }
    for(rint x=1; x<=sum; ++x)
    {
        for(rint i=0; i<=x/3; ++i)
        {
            for(rint j=0; j<=(x-i*3)/2; ++j)
            {
                int k=x-i*3-j*2;
                if(i+j+k>n) continue;
                //printf("%d %d %d!!!\n", i, j, k);
                f[i][j][k]=n;
                if(i>0) f[i][j][k]+=i*f[i-1][j+1][k];
                if(j>0) f[i][j][k]+=j*f[i][j-1][k+1];
                if(k>0) f[i][j][k]+=k*f[i][j][k-1];
                f[i][j][k]/=(i+j+k);
                //printf("%d %d %d %Lf!!!\n", i, j, k, f[i][j][k]);
            }
        }
    }
    printf("%.10Lf\n", f[num[3]][num[2]][num[1]]);
    return 0;
}

O – Matching

思路:
一个简单的容斥计数,感觉和 DP 关系不大。

枚举女生集合 $S$,计算所有男生和集合中女生配对的方案数,记为 $f[S]$。既然题目要求一一配对的方案,那么如果 $n-|S|$ 为奇数,那么答案就应该减去 $f[S]$,否则就加上 $f[S]$。

代码:

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

int n, ans, s[MAXN];

int main()
{
    scanf("%d", &n);
    for(rint i=0; i<n; ++i)
        for(rint j=0, x; j<n; ++j)
        {
            scanf("%d", &x);
            s[i]|=(x<<j);
        }
    for(rint sta=0; sta<(1<<n); ++sta)
    {
        int siz=0, val=1;
        for(rint i=0; i<n; ++i)
            siz+=((sta>>i)&1);
        for(rint i=0; i<n; ++i)
        {
            int temp=s[i]&sta, num=0;
            for(rint j=0; j<n; ++j)
                num+=((temp>>j)&1);
            val=1LL*val*num%p;
        }
        if((n-siz)&1) ans=(ans+p-val)%p;
        else ans=(ans+val)%p; 
    }
    printf("%d\n", ans);
    return 0;
}

U – Grouping

思路:
一个简单的子集 DP。

枚举所有集合 $S$,记 $f[S]$ 为选取 $S$ 集合的最大答案。先算出把 $S$ 集合作为一整组的分数作为 $f[S]$ 的初值,然后枚举 $S$ 的子集 $T$,得到转移方程 $f[S]=max(f[S], f[T]+f[S xor T])$,直接转移就行。总复杂度 $O(3^nn^2)$
代码:

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

int n, mp[MAXN][MAXN];
LL f[1 << 17];

int main()
{
    scanf("%d", &n);
    for(rint i = 0; i < n; ++i)
        for(rint j = 0; j < n; ++j)
            scanf("%d", &mp[i][j]);

    for(rint sta = 0; sta < (1 << n); ++sta)
    {
        for(rint i = 0; i < n; ++i)
            if((sta >> i) & 1)
                for(rint j = i + 1; j < n; ++j)
                    if((sta >> j)&1) f[sta] += mp[i][j];
        for(rint i = sta; i; i = (i-1) & sta)
        {
            int j = sta ^ i;
            f[sta] = max(f[sta], f[i] + f[j]);
            //printf("%d %d %d %lld %lld!!\n", sta, i, j, f[i], f[j]);
        }
    }
    printf("%lld\n", f[(1 << n) - 1]);
}

V – Subtree

思路:
一个简单的树形 DP 加换根操作,但是有一个很有趣的细节。

设 $f_i$ 为以 $i$ 为根的子树的方案数,那么就有 DP 方程:$f_i=\prod (f_{to}+1)$。考虑换根操作,设 $val_i$ 为节点 $i$ 的父亲所在子树的贡献,那么节点 $i$ 的答案就是 $(val_i+1)*f[i]$。$val$ 的求法一般有两种,第一种是通过式子:$val_{to}=(val_x+1)*f_x/f_{to}$ 得到。这种方法看似很简单,但是其中有除法,对于模意义下的除法表面上看可以用扩展欧几里得求逆元实现。但是,有一些数是没有逆元的,也就是说对于任意除数的除法我们不能够简单地实现。

这时候我们就要考虑第二种求 $val$ 的方法,那就是给子树一个固定的顺序,然后求出子树的前缀和后缀贡献,从而推出 $val_{to}$,虽然这种方法更为复杂,但可以很好地避免除法。

代码:

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

int n, m, cnt, head[MAXN], f[MAXN], ans[MAXN];
vector<int> vec[MAXN], l[MAXN], r[MAXN];

void dfs1(int x, int fa)
{
    f[x] = 1;
    for(rint i = 0; i < vec[x].size(); ++i)
    {
        int to = vec[x][i];
        if(to == fa) continue;
        dfs1(to, x);
        f[x]= 1LL * f[x] * (f[to]+1) % m;
    }
}

void dfs2(int x, int fa, int val)
{
    ans[x] = 1LL * f[x] * (val + 1) % m;
    l[x].resize(vec[x].size());
    r[x].resize(vec[x].size());
    for(rint i = 0; i < vec[x].size(); ++i)
    {
        if(i == 0) l[x][i] = 1;
        else
        {
            if(vec[x][i - 1] == fa) l[x][i] = l[x][i - 1];
            else l[x][i] = 1LL * l[x][i - 1] * (f[vec[x][i - 1]] + 1) % m;
        }
    }
    for(rint i=vec[x].size()-1; i >= 0; --i)
    {
        if(i == vec[x].size() - 1) r[x][i] = 1;
        else
        {
            if(vec[x][i + 1] == fa) r[x][i] = r[x][i + 1];
            else r[x][i] = 1LL * r[x][i + 1] * (f[vec[x][i + 1]] + 1) % m;
        }
    }
    //printf("%d %d %d!!\n", x, fa, val);
    for(rint i = 0; i < vec[x].size(); ++i)
    {
        int to = vec[x][i];
        if(to == fa) continue;
        //printf("%d %d %d!!!\n", to, l[x][i], r[x][i]);
        dfs2(to, x, 1LL * (val + 1) * l[x][i] % m * r[x][i] % m);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(rint i = 1, x, y; i < n; ++i)
    {
        scanf("%d%d", &x, &y);
        vec[x].push_back(y);
        vec[y].push_back(x);
    }
    dfs1(1, 0);
    dfs2(1, 0, 0);
    for(rint i = 1; i <= n; ++i) printf("%d\n", ans[i]);
    return 0;
}

W – Intervals

思路:

代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 200005
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
#define pii pair<int, int>
#define ls (root<<1)
#define rs (root<<1|1)
#define mid ((l+r)>>1)
using namespace std;

int n, m;
LL t[MAXN*4], tag[MAXN*4];
vector<pii> vec[MAXN];

void up(int root)
{
    t[root]=max(t[ls], t[rs])+tag[root];
}

void update(int root, int l, int r, int x, int y, LL k)
{
    //printf("%d %d %d %d!!!\n", root, l, r, k);
    if(l>y || r<x) return;
    if(l>=x && r<=y)
    {
        t[root]+=k, tag[root]+=k;
        return ;
    }
    update(ls, l, mid, x, y, k);
    update(rs, mid+1, r, x, y, k);
    up(root);
}

int main()
{
    scanf("%d%d", &n, &m);
    for(rint i=1; i<=m; ++i)
    {
        int l, r, a;
        scanf("%d%d%d", &l, &r, &a);
        vec[r].push_back(make_pair(l, a));
    }
    for(rint i=1; i<=n; ++i)
    {
        update(1, 1, n, i, i, t[1]);
        for(rint j=0; j<vec[i].size(); ++j)
        {
            pii temp=vec[i][j];
            update(1, 1, n, temp.first, i, temp.second);
        }
    }
    printf("%lld\n", max(0LL, t[1]));
}

1 对 “Educational DP Contest”的想法;

发表评论

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