P12131 客流量上限#

题目链接：https://www.luogu.com.cn/problem/P12137
大致题意：有一个数组 $A_1,A_2,A_3,A_4,...,A_{2025}$ ，需要满足以下条件：
1. $A_1,A_2,...,A_{2025}$ 是1到2025的一个排列。
2.对于任意的的 $i$ 和 $j$ ( $1 <= i,j <= 2025$ . $i$ 可以等于 $j$ )， $A_i$ 和 $A_j$ 的乘积不得超过 $i \times j + 2025$ 。
求满足条件的分配方案有多少种，输出对 $10^9+7$ 取余之后的结果即可。

代码是很短的，但是思考和推导数学公式的过程还是不容易的。
思路：首先我们可以很容易发现 $A_i = i$ 时一定满足条件。接着我们尝试思考其他可能的解。
我们尝试微扰。只交换相邻两个数的位置，看看是否满足条件。令 $j = i + 1$ ，将原式化简 $i \times (i + 1) <= i \times (i + 1) + 2025$ 。显然也是成立的，但我们需要去考虑更加极端的条件。我们让 $i$ 也等于 $j$ 。那么 $A_i = i + 1$ ，这是最极端的情况。 $A_i^2 = (i + 1)^2 <= i^2 + 2025$ ，从而化简得到 $i <= 1012$ ，也就是说在只交换两个数的情况下已经无法满足所有的数了，那么在更高程度的扰动就更无法满足条件了。
因此，根据结论，所有可能的分配方案有 $2^{1012}$ 种。也就是当 $i <= 1012$ 时，有 $2$ 种选择的可能， $A_{1013}$ 的值取决于前面的数哪个没取。但当 $1014 <= i <= 2025$ 时，只能是原来的数。由于数比较大，直接用 $pow()$ 会超时，所以我们需要用快速幂。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define endl '\n'
6
#define mod 998244353
7
const ll MOD = 1e9 + 7;
8
ll fast_pow(ll a,ll b,ll MOD){
9
    ll ans = 1;
10
    while(b){
11
        if(b & 1) ans = (ans * a) % MOD;
12
        b >>= 1;
13
        a = (a * a) % MOD;
14
    }
15
    return ans;
16
}
17

18
void solved(){
19
    cout << fast_pow(2, 1012, MOD);
20
}
21

22
int main(){
23
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
24
    solved();
25
    return 0;
26
}

P12343 树上寻宝#

题目链接：https://www.luogu.com.cn/problem/P12343
大致题意：我们需要在一个节点数为 $n$ 的树的根节点上不断向外搜索并累计权值。每次可以操作 $k$ 次，每一次都可以走一条边或者两条边。达到 $k$ 次之后就会自动收获当前节点的权值并返回根节点，重新进行搜索，求所有能到达的节点的权值之和。
这种题还是挺模板的，多练练就会了。
思路：这里的每次操作一条边或者两条边其实可以理解为搜索的深度 $x <= 2 k$ 的节点权值都可以搜到。而深度大于 $2 k$ 的权值搜不到不计入总和即可。
我们用邻接表来记录一个父节点的相邻节点以遍历。然后用队列来操作父节点搜索，接着将子节点入队作为新父节点，不断向深搜索。（ $BFS$ ）用 $depth$ 数组记录对应节点的深度。 $depth$ 数组初始化为 $-1$ ，表示还未搜索和记录深度。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define endl '\n'
6
#define mod 1000000007LL
7

8
vector<vector<int>> g;
9
vector<ll> w;
10
queue<int> q;
11
vector<int> depth;
12
int n,k;
13

14
void solved(){
15
    cin >> n >> k;
16
    w.resize(n);
17
    g.resize(n);
18
    depth.resize(n, -1);
19
    for(auto &it:w){
20
        cin >> it;
21
    }
22
    for (int i = 1; i < n;i++){
23
        int u, v;
24
        cin >> u >> v;
25
        u--, v--;
26
        g[u].push_back(v), g[v].push_back(u);
27
    }
28
    depth[0] = 0;
29
    q.push(0);
30
    while(!q.empty()){
31
        int u = q.front(); q.pop();
32
        for(auto v : g[u]){
33
            if(depth[v] == -1){
34
                depth[v] = depth[u] + 1;
35
                q.push(v);
36
            }
37
        }
38
    }
39
    ll ans = 0;
40
    int limit = k * 2;
41
    for (int i = 0; i < n;i++){
42
        if(depth[i] <= limit){
43
            ans += w[i];
44
        }
45
    }
46
    cout << ans;
47
}
48

49
int main(){
50
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
51
    solved();
52
    return 0;
53
}

P12136 生产车间#

题目链接：https://www.luogu.com.cn/problem/P12136
题意：一个有 $n$ 个节点的树，节点 $i$ 的权值为 $w_i$ 。叶节点的权值代表着会传递 $w_i$ 个产品给父节点，而其他非根节点会向其父节点传递最多 $w_i$ 个产品(也就是说传递的产品数由所有子节点传递的产品数之和决定)，现在我们要删去部分节点使得其对应的父节点的权值大于等于所有子节点权值之和，问使得最终传递到根节点的产品数最多是多少。

这题是比较困难的树上 $dp$ ，同时还使用了 $bitset$ 压缩状态，蒟蒻博主也是去反复看题解和询问 $AI$ 才最终搞懂。大部分解释都写在注释里了，这里的思路可能主要是补充。顺带一提，注释是自己写的，不是 $AI$ （）。
思路： $bitset$ ：这里的 $bitsset$ 可能比较抽象。它其实指的是用位方式权值表示所有可以取到的值。举个例子： $010011001$ ，从右往左看，第 $0$ 位为1，表示的是 $i$ 节点的权值 $w[i]$ 可以取到 $0$ （也就是不取）。同样地，对应第 $3$ 位，第 $4$ 位,第 $7$ 位表示的是权值 $w[i]$ 可以取到 $3,4,7$ 。所以我们后续的状态继承也是通过位运算的方式进行。
掩码：掩码设置为不超过权值 $w[u]$ 的全 $1$ 码，这是为了保证继承状态中 $bitset$ 的最大位不会超过当前父节点最大权值 $w[u]$ 。（超出最大权值的部分会被按位取合操作清零）。
$cur.\_Find\_first()$ 和 $cur.\_Find\_next()$ ：前者为从低位开始找，找到第一个为 $1$ 的位，输出对应的位置。后者为找到从 $x$ 位开始找第一个为 $1$ 的位，然后输出位置。
大佬（不是博主）的AC代码：

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define endl '\n'
6
#define mod 998244353
7

8
const int N = 1e3 + 10;
9
int n,ans;
10
vector<int> w(N);                 //权值
11
vector<vector<int>> g(N);         //邻接表
12
vector<bitset<N>> dp(N);          //1,父节点 2,对应的bitset权值
13

14
void dfs(int u,int p){
15
    if(g[u].size() == 1 && p != -1){  // 判断是叶节点就返回
16
        dp[u][0] = 1;                 // 把0位设置为1，表示权值可为0
17
        dp[u][w[u]] = 1;              //对应位的设置为1
18
        return;
19
    }
20
    bitset<N> cur,mask;           //设置当前的操作权值cur和掩码mask
21
    cur[0] = 1;
22
    for (int i = 0; i <= w[u];i++){       //掩码设置为全1，不超过w[u]
23
        mask.set(i);
24
    }
25
    for(auto v:g[u]){                   //遍历对应的邻接表
26
        if(v != p){                     //不为父节点继续搜索
27
            dfs(v, u);                  //搜索到叶节点后开始计算
28
            bitset<N> next;
29
            next[0] = 1;
30
            for (int i = cur._Find_first(); i <= w[u]; i = cur._Find_next(i)){
31
                next |= (dp[v] << i);
32
            }
33
            next &= mask;               //掩码保证不超过w[u]
34
            cur = next;                 //更新cur
35
        }
36
    }
37
    dp[u] = cur;                       //更新dp[u]
38
}
39

40
void solved(){
41
    cin >> n;
42
    for (int i = 1; i <= n;i++){
43
        cin >> w[i];
44
    }
45
    for (int i = 1; i < n;i++){
46
        int u, v;
47
        cin >> u >> v;
48
        g[u].push_back(v), g[v].push_back(u);   //加入邻接图
49
    }
50

51
    dfs(1, -1);     //父节点p设为-1
52

53
    for (int i = w[1]; i >= 0;i--){           //从高位找到第一位为1的权值即为答案
54
        if(dp[1][i]){
55
            ans = i;
56
            break;
57
        }
58
    }
59
    cout << ans;
60
}
61

62
int main() {
63
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
64
    solved();
65
    return 0;
66
}

P12137 装修报价#

题目链接：https://www.luogu.com.cn/problem/P12137
题意： $N$ 个数构成的数组 $A_1,A_2,...,A_N$ ，在每对相邻的数字中间随意插入 $+、-、\bigoplus$ 三者其中一个(其中在这题中异或的运算优先级最高)，计算所有可能的结果的总和并对 $10^9 + 7$ 取余。
这题其实是找数学规律，找到之后用代码实现一下即可。
思路：像这种全排列的求和运算，我们很容易就想到会有一部分的项数会相互抵消掉而不影响最终结果。我们可以看到题目给的对应的例子：只有前三项没有相互抵消掉，而后 $6$ 项总会出现相同的项数加了又减，前后加减异或的情况。由此我们可以大胆猜想只有前缀异或才会对总和有贡献：每当前 $k$ 项全为 $\bigoplus$ 时， $k+1$ 位的项可以取 $+$ , $-$ 。而 $k + 2$ 以及后面所有的项可以任意填 $+$ 或 $-$ 或 $\bigoplus$ ，并且这些情况是不会被抵消掉的，需要计入总和。因此我们可以得到每个前缀长度为 $i$ 的可能结果有 $2 \times 3^{n - i - 1}$ 种。对应能产出的贡献为 $pre\_xor \times 2 \times 3^{n-i-1}$ 。（这是因为除了前缀的异或块外后面的项同样会相互抵消，最终真正贡献的是前缀异或的代码块累加了多少次，也就是有多少种）。
这里代码实现前缀异或没有专门开数组计算前缀和，而是用 $temp$ 在每一次循环都计算了该次前缀异或所有的结果并计入总和。对应的情况由于 $n$ 最大可以取到 $10^5$ ，我们需要使用快速幂。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define endl '\n'
6
#define mod 1000000007LL
7

8
ll fast_pow(ll a,ll b,ll MOD){
9
    ll ans = 1;
10
    while(b){
11
        if(b & 1) ans = (ans * a) % MOD;
12
        b >>= 1;
13
        a = (a * a) % MOD;
14
    }
15
    return ans;
16
}
17

18
void solved(){
19
    ll n;
20
    cin >> n;
21
    vector<ll> a(n + 1);
22
    ll ans = 0;
23
    ll temp = 0;
24
    for (int i = 1; i <= n;i++){
25
        cin >> a[i];
26
    }
27
    for (int i = 1; i <= n;i++){
28
        temp ^= a[i];
29
        if(i < n){
30
        ans += (temp * (2 * fast_pow(3, n - i - 1, mod)) % mod) % mod;
31
        }
32
        else{
33
            ans = (ans + temp) % mod;
34
        }
35
        ans %= mod;
36
    }
37
    cout << ans;
38
}
39

40
int main(){
41
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
42
    solved();
43
    return 0;
44
}