乐趣区

关于c++:ACM算法竞赛日常训练DAY4题解与分析树子序列-组合数学-动态规划

DAY4 共 2 题:

  • 树(组合数学)
  • 子序列(dp,数学)

🎈 作者:Eriktse
🎈 简介:19 岁,211 计算机在读,现役 ACM 银牌选手🏆力争以通俗易懂的形式解说算法!❤️欢送关注我,一起交换 C ++/Python 算法。(优质好文继续更新中……)🚀
🎈 原文链接(浏览原文取得更好浏览体验):https://www.eriktse.com/algorithm/1095.html

题目传送门:https://ac.nowcoder.com/acm/problem/13611

通过观察条件“一个染色计划是非法的,当且仅当对于所有雷同色彩的点对 (x,y),x 到 y 的门路上的所有点的色彩都要与 x 和 y 雷同。”咱们能够发现,当且仅当 染色的点能够全副连通 时能够满足条件。

所以当初问题是如何将 n 个点划分为 k 块。

咱们能够发现在树上,任意删除一条边都会使得联通块个数 + 1

其实块数只有 <= k 即可,因为咱们能够有一些色彩不应用。所以要划分为 i 块,只须要从 n - 1 条边中任选 i - 1 条进行删除即可,计划数是C(n - 1, i - 1)

假如当初咱们失去了 i (i <= k) 个联通块,须要将 i 种颜色染上去,首先须要 C(k, i) 种办法取出色彩,而后 A(i, i) 一个全排列将色彩染上去。

所以答案公式如下:

$$ans=\sum_{i=1}^{k}C(n – 1, i – 1)C(k, i)i!$$

可能波及一些 疾速幂 乘法逆元 的常识,须要自行学习。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 350, p = 1e9 + 7;

int fac[maxn];

int qmi(int a, int b)
{
    int res = 1;
    while(b)
    {if(b & 1)res = res * a % p;
        a = a * a % p, b >>= 1;
    }
    return res;
}

int inv(int x){return qmi(x, p - 2);}

int C(int n, int m)
{if(n < m || n < 0 || m < 0)return 0;
    return fac[n] * inv(fac[n - m] * fac[m] % p) % p;
}

signed main()
{int n, k;scanf("%lld %lld", &n, &k);
    fac[0] = 1;
    for(int i = 1;i <= n; ++ i)fac[i] = fac[i - 1] * i % p;
    
    int ans = 0;
    for(int i = 1;i <= n; ++ i)// 分为 i 块
    {int tmp = C(n - 1, i - 1) * C(k, i) % p * fac[i] % p;
        ans = (ans + tmp) % p;
    }
    printf("%lld\n", ans);
    return 0;
}

子序列

题目传送门:https://ac.nowcoder.com/acm/problem/17065

小技巧:察看数据范畴,比拟小,应该能够包容 O(n^3)的复杂度,所以能够大胆思考 dp。

首先定义状态 dp[i][j] 示意 以第 i 个元素结尾,且长度为 j 的序列的个数

再考虑一下转移,题目中的条件能够进行一些转换:

$${a_{p_i}}^{p_j} < {a_{p_j}}^{p_i}$$

等价于:

$$ \frac{log(a_{p_i})}{p_i} < \frac{log(a_{p_j})}{p_j} $$

咱们能够记:

$$ b_i = \frac{log(a_{p_i})}{p_i} $$

也就是说 对于选出的子序列中的每一个元素 ,他们满足一个偏序关系,只有我的b[j] > b[i],那么b[j] 将会大于所有的b[k] (k < i)

所以咱们能够思考以下的转移:

$$dp_{i, j} = \sum_{k=1}^{i – 1}[b_i > b_k] \times dp_{k, j – 1}$$

思考初始化,当最初一个元素确定,序列长度为 1 (j = 1)时,计划仅有 1 种。

最初的答案是将所有状况加起来(留神取模,不过这道题数据较弱,不取模也能够过)。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 109, p = 1e9 + 7;

//dp[i][j]示意以第 i 个元素结尾,长度为 j 的计划数
int a[maxn], dp[maxn][maxn];


signed main()
{int n;scanf("%lld", &n);
    for(int i = 1;i <= n; ++ i)scanf("%lld", a + i);
    
    for(int i = 1;i <= n; ++ i)
    {dp[i][1] = 1;
        for(int j = 1;j <= i; ++ j)
        {for(int k = 1; k < i; ++ k)
            {if(log(a[k]) / k < log(a[i]) / i)
                {dp[i][j] += dp[k][j - 1];
                    dp[i][j] %= p;
                }
            }
        }
    }

    int ans = 0;
    for(int i = 1;i <= n; ++ i)
        for(int j = 1;j <= i; ++ j)
        {ans = (ans + dp[i][j]) % p;
        }
    printf("%lld\n", ans);
    return 0;
}

🎈 本文由 eriktse 原创,创作不易,如果对您有帮忙,欢送小伙伴们点赞👍、珍藏⭐、留言💬

退出移动版