牛客练习赛131（dp，dfs，bfs，线段树维护等差数列）

---

整场题意都要靠和出题人心心相印才行，(lll￢ω￢)

F不会，PASS

---

A. 小H学语文

题意：

在 $n$ 个木板中选择 $m$ 个，定义 $V=m^2\ast h_{min}$，输出一个方案，令 $V$ 最大。其中，$m$ 表示木板的个数，$h_{min}$ 表示选择木板的最小值。

思路：

按木板长度排序，每次选前 $i$ 大个木板，作为方案，取最大的 $V$。

code:

#include<bits/stdc++.h>using namespace std;const int maxn = 2e5 + 10;pair<int, int> a[maxn];int main(){int n;cin >> n;int x;for(int i = 1; i <= n; i++){cin >> x;a[i] = {x, i};}sort(a+1, a+1+n);long long mx = 0, pos = 0;for(int i = n; i >= 1; i--){long long tmp = 1ll * (n - i + 1) * (n - i + 1) * a[i].first;if(tmp > mx){mx = tmp;pos = i;}}vector<int> res;for(int i = pos; i <= n; i++) res.push_back(a[i].second);sort(res.begin(), res.end());cout << res.size() << endl;for(auto x : res) cout << x << " ";cout << endl;return 0;
}

B. 小H学数学（dp、偏移值）

题意：

$y+1$个人，每个人的两个手，手指健全。对于每个人，可以用两个手表示一个 $[1,10]$ 的数，也可以用两个手各表示一个 $[1,5]$ 的数。

问：这些人有多少种方案，使得他们表示的数字通过加减计算出 $x$。（任意一个同学左右手表示的数不同或者计算时需要的操作符不同视为不同的方案）

思路：

先考虑一个人，表示 $[1,10]$ 之间的数。令 $V[x]$ 表示一个人有多少种方案可以构成 $x$，直接暴力枚举维护出 $V$ 数组。

再考虑多个人，令 $dp[i][j]$ 表示 $i$ 个人，构成 $j$ 的方案数。 $dp[i][j]={\sum }_{x}dp[i-1][j\pm x]+V[x],x\in V_{key}$。

最后，因为 x 可能出现负数，注意设置偏移值。

code：

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int maxn = 2e3 + 10;
const int M = 1e3;
const ll mod = 1e9 + 7;ll dp[105][maxn];map<int, int> v;int main(){// for(int i = 1; i <= 5; i++){for(int j = 1; j <= 5; j++){int a = i + j;int b = i - j;
//    		printf("(%d,%d) = %d, %d\n", i, j, a, b);v[a]++;v[b]++;}}for(int i = 1; i <= 10; i++) v[i]++;	//	for(auto i : v) cout << i.first << " " << i.second << endl;int x, y;cin >> x >> y;dp[0][M+0] = 1;for(int i = 1; i <= y+1; i++){for(int j = -1000; j <= 1000; j++){for(auto _ : v){ll num = _.first, cnt = _.second;if(j - num >= -1000 && j - num <= 1000){dp[i][M+j] = (dp[i][M+j] + dp[i-1][M+j-num] * cnt % mod) % mod;}if(j + num >= -1000 && j + num <= 1000){dp[i][M+j] = (dp[i][M+j] + dp[i-1][M+j+num] * cnt % mod) % mod;}}}}cout << dp[y+1][x+M] << endl;return 0;
}

C. 小H学生物（DFS、树上两点间路径的距离）

题意:

给一棵树$T$ 和一个序列$A$，树上每条边都有一个二进制边权，序列$A$ 中每个元素对应树上一个节点。

设：

• 在序列$A$中，设点对$(i,j)$的距离为 $|j-i|$。
• 对于点对 $(i,j)$，其 $D$ 值 = 在树$T$上，节点 $A_i$ 到节点 $A_j$ 的边权的异或和。

求：序列$A$ 中，所有满足距离大于 $1$ 的点对的 $D$ 值的异或和。

思路:

对于异或的两个知识点：

• X ^ X = 0
• X ^ 0 = X

对于树上任意两点的简单路径的一个知识点：

• 在树上，$dist(u,v)=deep(u)+deep(v)-deep(LCA(u,v))\ast 2$，其中 $deep(x)$ 表示x的深度，$LCA(u,v)$ 表示 u 和 v的最近公共祖先。（原理自行百度即可）

类比上述知识点，推理得到：任意两点之间的边权异或和 $d_{u,v}=d_{1,u}⨁d_{1,v}$，其中 $d_{u,v}$ 表示 u 到 v 的简单路径异或和，一遍DFS即可维护出全部的$d_{1,x}$。

---

设序列 A = {5, 4, 3, 6}，则 $res=d_{5,3}⨁d_{5,6}⨁d_{4,6}=(d_{1,5}⨁d_{1,3})⨁(d_{1,5}⨁d_{1,6})⨁(d_{1,4}⨁d_{1,6})$

观察上述，式子，可以发现，每个元素对 res 的贡献，对它所在学列A中的位置有关。

手搓两个样例，对 |A| 是奇偶的情况分类讨论即可总结出。

code:

#include<bits/stdc++.h>using namespace std;const int maxn = 1e5 + 5;int a[maxn], in[maxn];
vector<pair<int, bitset<100>>> mp[maxn];bitset<100> d[maxn]; // d[i] = i 到 root 的异或值 void dfs(int u){for(auto item : mp[u]){d[item.first] = d[u] ^ item.second;dfs(item.first);}
}int main(){int n, m, l;cin >> n >> m >> l;int u, v; char c;    for(int i = 2; i <= n; i++){cin >> u >> v;	bitset<100> tmp;for(int j = 0; j < l; j++){cin >> c;tmp[j] = (c == '1' ? 1 : 0);}mp[u].push_back({v, tmp});in[v]++;}for(int i = 1; i <= m; i++) cin >> a[i];int root = 1;for(int i = 1; i <= n; i++) if(in[i] == 0) root = i;dfs(root);bitset<100> res;if(m&1) res = d[a[1]] ^ d[a[m]];else{for(int i = 2; i < m; i++){res = res ^ d[a[i]];}}for(int i = 0 ; i < l; i++) cout << res[i];cout << endl;return 0;
}

D. 小H学历史(BFS)

题意：

有一棵树，每个节点的点有一个标记值，A 、B 或者 Z。A 和 B 的节点可以攻击 Z 的结点，把Z变为和自己一样的标记。并且，树中度为一的结点一定为 A 或 B。

若干次进攻后，树上没有标记为 Z的结点，求||A| - |B|| 的最小值。（标记为 A 的节点数 - 标记为 b 的节点数的绝对值的最小值）

思路：

先分别求，标记为 A 的结点的最大值MX_A 和标记为 B 的结点的最大值MX_B。(从标记为 A 的结点开始BFS，遍历所有的结点，即可求出MX_A，MX_B同理)

再求，标记为 A 的结点的最小值MN_A = n - MX_B 和标记为 B 的结点的最小值MN_B = n - MX_A。

现考虑所有情况，设 MN_A <= MN_B：

1. MN_A = 0，则 res = n
2. MN_A != 0 ，因为 MN_A <= MN_B，所以 MN_A <= n /2,
   1. 如果这时 MX_A >= n / 2，A 的数量一定可以等于 n/2，res = n % 2
   2. 如果这时 MX_A < n / 2，A 的数量一定小于 n/2，res = MN_B - MX_A，即所有可变为A 的 Z 都变为A。

补充两个帮助例子，用作解释为什么求 MX_A 和 MN_A：

• 自由的 Z，如下图所示，这时的 Z 可为 A 也可以为 B。
  

• 不自由的 Z，这时 Z 只能为 A。
  

code:

#include<bits/stdc++.h>using namespace std;const int maxn = 1e5 + 5;vector<int> mp[maxn];
char c[maxn];
int vis[maxn];int bfs(int n, char flag){queue<int> qu;for(int i = 1; i <= n; i++){if(c[i] == flag){qu.push(i);vis[i] = 1;} else vis[i] = 0;}int mx = 0;while(!qu.empty()){int u = qu.front();qu.pop();mx++;for(auto v : mp[u]){if(vis[v] == 1) continue;if(c[v] == flag || c[v] == 'Z'){qu.push(v);vis[v] = 1;}}}return mx;
}int main(){int n;cin >> n;for(int i = 1; i <= n; i++) cin >> c[i];int x, y;for(int i = 2; i <= n; i++){cin >> x >> y;mp[x].push_back(y);mp[y].push_back(x);}int mx_A = bfs(n, 'A'), mx_B = bfs(n, 'B');int mn_A = n - mx_B, mn_B = n - mx_A;if(mn_A > mn_B) swap(mn_A, mn_B), swap(mx_A, mx_B);if(mn_A == 0) cout << n << endl;else if(mx_A >= n / 2) cout << n % 2 << endl;else cout << n - mx_A - mx_A << endl;return 0;
}

E. 小H学物理 (线段树±区间等差数列)

思路:

维护λ颗线段树，每次修改操作，维护两个值。一个是区间整体±的值value，另一个为区间被操作的次数cnt。

更具体的，如下图所示。如果对区间 [1, 6] 进行一次操作，划分为两个子区间 [1, 3] 和 [4, 6]。

在子区间 [1, 3] 上，等价于区间整体 + x，再减去一个递减序列（0， 1，2）。

在子区间 [4, 6] 上，等价于区间整体 + y，再减去一个递减序列（0， 1，2）。

类比到线段树上，一个结点的两个孩子结点的大小是一定的，对一个结点的操作可以等价为上述的分裂操作。

其中，比较重要的是，计算出 h 的值，左孩子区间长度 * 公差 d，即可求出右孩子的 y。

code：

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int maxn = 1e5 + 5;typedef struct Node{ll value;ll lazy;ll cnt;
} node;node tree[10][maxn * 4];void pushdown(int tno, int root, int l, int r){if(tree[tno][root].lazy || tree[tno][root].cnt){ll mid = l + r >> 1, len_l = mid - l + 1, len_r = r - mid;tree[tno][root<<1].value += tree[tno][root].lazy * len_l - tree[tno][root].cnt * len_l * (len_l - 1) / 2;tree[tno][root<<1].lazy += tree[tno][root].lazy;tree[tno][root<<1].cnt += tree[tno][root].cnt;ll new_lazy = tree[tno][root].lazy - len_l * tree[tno][root].cnt;tree[tno][root<<1|1].value += new_lazy * len_r - tree[tno][root].cnt * len_r * (len_r - 1) / 2;tree[tno][root<<1|1].lazy += new_lazy;tree[tno][root<<1|1].cnt += tree[tno][root].cnt;tree[tno][root].lazy = tree[tno][root].cnt = 0;}
}void update(int tno, int root, int l, int r, int L, int R, ll value){if(L <= l && r <= R){ll op = (value > 0 ? -1 : 1);tree[tno][root].value += 1ll * (value + op *  (l - L)) * (r - l + 1) + op *  (r - l + 1) * (r - l) / 2;tree[tno][root].lazy += (value + op * (l - L));tree[tno][root].cnt += (value > 0 ? 1 : -1); // cnt 表示 sum(0 -1 -2 -3 ...)，value + 则要 +1次 return;}pushdown(tno, root, l, r);int mid = l + r >> 1;if(L <= mid) update(tno, root<<1, l, mid, L, R, value);if(R > mid) update(tno, root<<1|1, mid+1, r, L, R, value);tree[tno][root].value = tree[tno][root<<1].value + tree[tno][root<<1|1].value;
}long long query(int tno, int root, int l, int r, int L, int R){if(L <= l && r <= R) return tree[tno][root].value;pushdown(tno, root, l, r);long long res = 0, mid = l + r >> 1;if(L <= mid) res += query(tno, root<<1, l, mid, L, R);if(R > mid) res += query(tno, root<<1|1, mid+1, r, L, R);tree[tno][root].value = tree[tno][root<<1].value + tree[tno][root<<1|1].value;return res;
}int main(){int n, q, l;cin >> q >> n >> l;int nn = n;n = n / l + 1;while(q--){int op, x, y;cin >> op >> x >> y;if(op == 0) {int tno = x % l, L = x / l + 1;update(tno, 1, 1, n, L, min(L + abs(y) - 1, n), y);
// 			for(int i = 1; i <= nn; i++) 
// 				cout << query(i%l, 1, 1, n, i / l + 1, i / l + 1) << " ";
// 			cout << endl;			}else{long long res = 0;if(y - x < 5 * l){for(int i = x; i <= y; i++){res += query(i % l, 1, 1, n, i / l + 1, i / l + 1);}}else{while(x % l != 0){res += query(x % l, 1, 1, n, x / l + 1, x / l + 1);x++;}while(1){res += query(y % l, 1, 1, n, y / l + 1, y / l + 1);if(y % l == 0) break;else y--;}int s = x / l + 1, e = y / l + 1 - 1; // y 所在的块已经算过了，所以-1 for(int i = 0; i < l; i++){res += query(i, 1, 1, n, s, e);}}cout << res << endl;}}return 0;
}