2022/07/04学习记录

简单的异或问题（构造 + 异或）

Description:

​ 有一组整数 {0,1,2,…,2^m−1}, 请从中选出 k 个数，使得这 k 个数的异或和为 n, 请输出最大的满足条件的 k。

Solution:

​ 既然要选择最多的k 那么我们可以想到0和x异或为x 我们让尽量多的数字异或和为0 最后找一个x
$$\begin{gathered} 对于任何[0,2^m-1]中，举例0\oplus 7=1\oplus 6=2\oplus 5=3\oplus 4=0 \\ 那么总异或和就为0 \\ 所以如果我们需要一个数n的话，我们就会将带有n的数对拆掉，且去掉n的另一个，这是一般情况 \\ 特殊情况就是当n和m特别小的时候我们需要分类讨论一下边界情况 \\ 当n==0且m!=1的时候，我们可以一个都不去掉，k=2^m \\ 当n==1且m==1的时候，k=2 \\ 其余情况，皆为正常情况,有k=2^m-1 \end{gathered}$$
Code:

int main()
{
    cin >> n >> m;
    LL res = (1LL << m);
    if(n == 0 && m != 1)
        cout << res << '\n';
    else if(n == 1 && m == 1)
        cout << 2 << '\n';
    else 
        cout << res - 1LL << '\n';
}
1
2
3
4
5
6
7
8
9
10
11

完美数（构造 + 排列组合）

Description:

​ 对于给定的数字 a , b ,当整数 n 在十进制下的所有数位都为 a 或 b 时，我们称 n 是“好数”

​ 对于好数 n ，当 n 在十进制下每一位的数字之和也为“好数”时，我们称 n 是一个“完美数”

​ 请你求出有多少 m 位数是“完美数”

​ (1≤m≤1e6,1≤a,b≤9)。

Solution:

​ 由于m很大 你心想的dfs暴力行不通 O(2^m) 想来也是岂会那么简单

​ 为什么dfs如此缓慢呢 因为对于每一位我都确认了他是a还是b 如果我避免这一点就可以节省大量时间

​ 所以我们想到枚举a和b分别的数量 但是不考虑其摆放 花费时间O(n)

​ 我们在枚举的同时 验证方案是否可行 大概是常数级别的时间

​ 当方案可行的时候 我们要更新答案 如何更新呢 假设有x个a n-x个b 这是一种合法的方案

​ 由于方案跟摆放顺序无关 于是这x个a可以放置在任意数位上 此时一个排列组合的做法就想到了

Code:

const int N = 1e6 + 5, mod = 1e9 + 7;
int a, b;
LL m;
LL fac[N], inv[N];

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

void init()
{
    inv[0] = fac[0] = 1;
    rep(i, 1, N)
        fac[i] = i * fac[i - 1] % mod;
    
    inv[N - 1] = qmi(fac[N - 1], mod - 2);
    for(int i = N - 2; i; i --)
        inv[i] = inv[i + 1] * (i + 1) % mod;
}

LL C(int a, int b)
{
    return (fac[a] * inv[b] % mod * inv[a - b] % mod) % mod;
}
//组合数学板子

int main()
{
    cin >> a >> b >> m;
    init();

    LL res = 0;
    rep(i, 0, m + 1) //选i个b m-i个a 组合
    { 
        LL last = m - i;
        LL num = last * a + i * b;
        bool flag = 1;
        while(num)
        {
            if(num % 10 != a && num % 10 != b)
            {
                flag = false;
                break;
            }
            num /= 10;
        }
        if(flag)
            res = (res + C(m, i)) % mod;
    }
    cout << res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

数字组合（01背包求方案数）

Description:

​ 给定 N 个正整数 A_1,A_2,…,A_N，从中选出若干个数，使它们的和为 M，求有多少种选择方案。

​ N < 100, M < 10000, A_i < 1000

Solution:

​ 我们可以定义一个数组dp[ j ]，表示和为j的方案数有多少种

​ 显然dp[0] = 1

​ 转移方程为dp[j] += dp[j - a[i]]

Code:

int main()
{
    cin >> n >> m;
    rep(i, 1, n + 1)
        cin >> a[i];
    
    dp[0] = 1;
    rep(i, 1, n + 1)
    for(int j = m; j >= a[i]; j --)
        dp[j] += dp[j - a[i]];
    
    cout << dp[m];
}
1
2
3
4
5
6
7
8
9
10
11
12
13

自然数拆分（完全背包求方案数）

Description:

​ 给定一个自然数 N，要求把 N 拆分成若干个正整数相加的形式，参与加法运算的数可以重复。

• 拆分方案不考虑顺序；
• 至少拆分成 2 个数的和。

Solution:

​ 这题还是求和的方案数，但是跟上一题的差别就在于上一题是每个数只能选一次 然而这一题每个数可以选任意次，所以这就是01背包和完全背包的区别了

​ 定义数组dp[ j ] 表示和为j的方案数

​ dp[0] = 1

​ 转移方程为dp[j] += dp[j - a[i]]

Code:

int main()
{
    cin >> n;
    dp[0] = 1;
    for(int i = 1; i < n; i ++) //[1, n - 1]
        for(int j = i; j <= n; j ++)
            dp[j] = (dp[j] + dp[j - i]) % mod;
    
    cout << dp[n];
}
1
2
3
4
5
6
7
8
9
10

记录一下区间DP板子题：合并石子

每次合并相邻两堆石子，合并代价为两堆石子的质量和，由于合并的顺序不同，因此付出的代价也就不同，请问合并长度为n的石子需要的最小代价是多少

N = 300

我们来了解一下区间DP的概念

​ 区间DP是为了解决线性DP中分阶段划分问题时，与顺序相关和合并相关的问题而产生的

​ 其主要的特点分为以下三点

• 合并：将两个或者多个部分进行整合，或者拆分
• 特征：将问题分解为两两合并的形式
• 求解：对整个问题设置最优值，枚举合并点，将问题分解为左右两个部分，最后通过合并两个部分的最优值来得到整个问题的最优值

对于本题而言 我们需要设置dp[ i ] [ j ]来表示和并[i, j]的最小代价

通过区间DP的特点 我们不难写出转移方程dp[ i ] [ j ] = min(dp[i] [k] + dp[k + 1] [j] + 合并需要付出的代价)

因为区间dp的性质 是将一个问题分为左右两个部分 于是我们必须先知道小的部分 才能向大的部分递推求解 这就决定了区间DP中的遍历顺序 也就是说我们必须先得到长度更小的区间的最优值 再向长度更大的区间递推而得最优值

//本题核心代码
	memset(dp, 0x3f, sizeof dp);    
    for(int len = 1; len <= n; len ++)
    {
        for(int i = 1; i + len - 1 <= n; i ++)
        {
            int j = i + len - 1;
            if(len == 1) //初始化为0
                dp[i][j] = 0;
            else //若len不为1 开始递推
            {
                for(int k = i; k < j; k ++)
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + s[j] - s[i - 1]); //s代表前缀和数组
            } 
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

//练习一下记忆化搜索写法
int dfs(int s, int e)
{
    if(s == e)  return 0;
    int &v = dp[s][e];

    if(v != -1) return v;
    
    v = 1e9;
    for(int k = s; k < e; k ++) 
        v = min(v, dfs(s, k) + dfs(k + 1, e) + pre_[e] - pre_[s - 1]);
    return v;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

明天一套CF 刷区间DP题目