1.23 补题 寒假训练营
E 一起走很长的路！
输入描述
第一行输入两个整数 n,q（1≤n,q≤2×10^5），代表多米诺骨牌的个数和询问次数。
第二行输入 n 个整数 a1,a2,…,an（1≤ai≤10^9），表示多米诺骨牌的重量。
此后输入 q 行，每行输入两个整数 l,r（1≤l≤r≤n），代表一次询问。
输出描述
对于每一次询问，新起一行。输出一个整数，代表牛可乐最少需要调整的次数。每一次询问相互独立。
示例
输入：
4 2 2 1 2 7 2 3 1 4
输出：
1 2
说明：
-
对于第一次询问，其中一种最优的调整方案是：将第 3 张多米诺骨牌的重量减少 1。
-
对于第二次询问，其中一种最优的调整方案是：将第 3 张多米诺骨牌的重量增加 1、将第 4 张多米诺骨牌的重量减少 1，此时，各张多米诺骨牌的重量分别为 2, 1, 3, 6，符合题意，游戏完美。
思路
-
前缀和计算：首先计算数组
a的前缀和s，即s[i] = s[i-1] + a[i]。前缀和的作用是快速计算任意区间的和。 -
构建线段树：我们需要构建一个线段树来维护区间内的最大值。线段树的每个节点维护以下信息：
-
l和r：表示当前节点所代表的区间范围。 -
maxv：表示当前区间内的最大值。 -
add：表示当前区间内的延迟标记（用于区间更新）。
-
-
初始化线段树：在构建线段树时，我们初始化每个叶子节点的值为
w[i] = a[i] - s[i-1]。这是因为我们需要维护的表达式是a[i] - s[i-1]。 -
查询处理：对于每个查询
[l, r]，我们需要计算区间[l+1, r]内的最大值。具体步骤如下：-
首先，我们计算
tmp = s[l-1]，即区间[1, l-1]的和。 -
然后，我们对区间
[l+1, r]进行区间更新，将每个元素的值增加tmp。这是因为我们需要计算的是a[i] - s[i-1] + s[l-1]，即a[i] - (s[i-1] - s[l-1])。 -
接着，我们查询区间
[l+1, r]的最大值，并将其与0取最大值（因为题目要求输出非负数）。 -
最后，我们将区间
[l+1, r]的值恢复原状，即减去tmp。
-
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, q;
int a[200005], s[200005], w[200005];
#define lc (p << 1)
#define rc (p << 1 | 1)
struct Node {
int l, r;
int maxv;
int add;
} tr[800005];
void pushup(int p) {
tr[p].maxv = max(tr[lc].maxv, tr[rc].maxv);
}
void pushdown(int p) {
if (tr[p].add != 0) {
tr[lc].maxv += tr[p].add;
tr[rc].maxv += tr[p].add;
tr[lc].add += tr[p].add;
tr[rc].add += tr[p].add;
tr[p].add = 0;
}
}
void build(int p, int l, int r) {
tr[p] = {l, r, w[l], 0};
if (l == r) return;
int m = (l + r) >> 1;
build(lc, l, m);
build(rc, m + 1, r);
pushup(p);
}
//区间更新
void modify(int p, int x, int y, int k) {
if (x <= tr[p].l && tr[p].r <= y) {
tr[p].maxv += k;
tr[p].add += k;
return;
}
pushdown(p);
int m = (tr[p].l + tr[p].r) >> 1;
if (x <= m) modify(lc, x, y, k);
if (y > m) modify(rc, x, y, k);
pushup(p);
}
int query(int p, int x, int y) {
if (x <= tr[p].l && tr[p].r <= y) {
return tr[p].maxv;
}
pushdown(p);
int m = (tr[p].l + tr[p].r) >> 1;
int res = -1e9;
if (x <= m) res = max(res, query(lc, x, y));
if (y > m) res = max(res, query(rc, x, y));
return res;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
s[i] = s[i - 1] + a[i];
}
for (int i = 1; i <= n; i++) {
w[i] = a[i] - s[i - 1];
}
build(1, 1, n);
while (q--) {
int l, r;
cin >> l >> r;
if (l == r) {
cout << 0 << '\n';
continue;
}
int tmp = s[l - 1];
modify(1, l + 1, r, tmp);
int ans = max(0LL, query(1, l + 1, r));
cout << ans << '\n';
modify(1, l + 1, r, -tmp);
}
return 0;
}C 字符串外串
题目描述
牛可乐定义字符串 ss 的可爱度为最大的整数 k，满足存在一个长度为 k 的连续子串 a，和一个长度为 k 的不连续子序列 b，满足 a=b。
现在，牛可乐给定你两个整数 n,m，并且询问你是否存在长度为 n、仅由小写字母构成的字符串 t，使得 t 的可爱度恰好等于 m。如果存在，输出任意一个符合条件的字符串 t。
定义：
-
连续子串：从原字符串中连续选择一段字符（可以全选、可以不选）得到的新字符串。
-
不连续子序列：至少由两段不相邻的非空子串构成。
输入描述：
每个测试文件均包含多组测试数据。第一行输入一个整数 T（1≤T≤10^4）代表数据组数，每组测试数据描述如下：
在一行上输入两个整数 n,m（3≤m≤n≤2×10^5）代表限制。
除此之外，保证单个测试文件的 n 之和不超过 2×10^5。
输出描述：
如果答案不存在，直接输出 NO；否则，在第一行输出 YES，在第二行输出一个仅由小写字母构成的字符串 ss，代表构造出的字符串。
示例
输入：
2 4 3 3 3
输出：
YES abcc NO
解释：
1.对于第一组测试数据：
字符串 abcc 的连续子串 abc 和不连续子序列 abc 满足条件。
因此，可爱度为 3，符合要求。
2.对于第二组测试数据：
无法构造满足条件的字符串，输出 NO。
数据范围
-
1≤T≤10^4
-
3≤m≤n≤2×10^5
-
单个测试文件的 n 之和不超过 2×10^5
思路
如果 n==m，则无法构造满足条件的字符串，因为不连续子序列至少需要两段不相邻的子串，而连续子串的长度为 n，无法满足条件。
如果 n−m>26，则无法构造满足条件的字符串，因为字母种类有限，无法保证不连续子序列的构造。
否则，可以通过构造一个字符串，使得其连续子串和不连续子序列的长度为 m。
构造方法：
使用循环字母表构造字符串，使得字符串的前 n−m 个字符是唯一的，后面的字符重复前面的字符。
这样可以保证存在一个长度为 m 的连续子串和一个长度为 m 的不连续子序列。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
int t;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
if (n == m || n - m > 26)
{
cout << "NO" << "\n";
continue;
}
cout << "YES" << "\n";
for (int i = 0; i < n; i++)
{
cout << (char)('a' + i % (n - m));
}
cout << "\n";
}
}
M 那是我们的影子
示例
输入：
4 6 1???56 456789 7891?? 3 ??? ??? ?11 3 123 456 789 3 723 18? ?9?
输出：
2 0 1 6
解释：
-
对于第一组测试数据，合法的情况有两种：
-
第一种：
1 2 3 4 5 6 4 5 6 7 8 9 7 8 9 1 2 3
-
第二种：
1 3 2 4 5 6 4 5 6 7 8 9 7 8 9 1 3 2
-
-
对于第二组测试数据，由于初始的矩阵中存在两个
1，所以无论如何构造都不合法。 -
对于第三组测试数据，不需要填入任何数字，所以只有唯一一种合法解。
-
对于第四组测试数据，有 6 种合法的填法。
数据范围
-
1≤T≤100
-
3≤n≤10^5
-
单个测试文件的 n 之和不超过 3×10^5
思路
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<string> s(3);
for (auto &i : s) cin >> i;
int flag = 1;
vector<set<int>> st(3);
vector<int> a(n);
for (int j = 0; j < n; j++) {
set<int> t;
for (int i = 0; i < 3; i++) {
if (s[i][j] == '?') {
a[j]++;
continue;
}
s[i][j] -= '0';
if (t.count(s[i][j])) flag = 0;
t.insert(s[i][j]);
}
st[j % 3].merge(t);
}
vector<int> sst;
for (auto &i : st) {
if (i.size() > 3) flag = 0;
int x = 0;
for (auto &j : i) x ^= 1 << j;
sst.push_back(x);
}
if (!flag) {
cout << 0 << endl;
continue;
}
int S = 1;
for (int i = 3; i < n; i++) {
if (a[i] == 2) S = S * 2 % MOD;
if (a[i] == 3) S = S * 6 % MOD;
}
vector<int> v(9);
iota(v.begin(), v.end(), 1);
int sum = 0;
do {
int flag = 1;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (s[i][j] == '?') continue;
int x = i + j * 3;
if (s[i][j] != v[x]) flag = 0;
}
}
int x;
x = (1 << v[0]) + (1 << v[1]) + (1 << v[2]);
if (x != (x | sst[0])) flag = 0;
x = (1 << v[3]) + (1 << v[4]) + (1 << v[5]);
if (x != (x | sst[1])) flag = 0;
x = (1 << v[6]) + (1 << v[7]) + (1 << v[8]);
if (x != (x | sst[2])) flag = 0;
if (!flag) continue;
sum = (sum + S) % MOD;
} while (next_permutation(v.begin(), v.end()));
cout << sum << '\n';
}
return 0;
}
I 一起看很美的日落！
题目描述
牛可乐有一棵由 n 个结点构成的树，第 i 个节点的权值为 ai。
我们定义一个连通块 V 的权值为：
-
当前连通块中两两结点的权值异或和，即 ∑i,j∈V(ai⊕aj)。
你需要计算全部连通块的权值之和。由于答案可能很大，请将答案对 10^9+7 取模后输出。
此题中的连通块定义为：对于树上的任意一个点集 S，如果 S 中的任意两点 u,v 之间存在一条路径，且路径上的所有点都在 S 中，则称 S 是一个连通块。
输入描述
第一行输入一个整数 n（1≤n≤105），代表树上的节点数量。
第二行输入 n 个整数 a1,a2,…,an（1≤ai≤109），代表每个节点的权值。
此后 n−1 行，第 i 行输入两个整数 ui,vi（1≤ui,vi≤n,ui≠vi），代表树上第 i 条边连接节点 ui 和 vi。
输出描述
输出一个整数，代表全部连通块的权值和。答案可能很大，请将答案对 10^9+7 取模后输出。
示例 1
输入
3 5 2 1 1 2 1 3
输出
50
解释
在这个样例中，一共有 6 个连通块，每一个连通块的权值依次为：
-
{1}，记为 V1，权值为 a1⊕a1=0；
-
{1,2}，记为 V2，权值为 (a1⊕a1)+(a1⊕a2)+(a2⊕a1)+(a2⊕a2)=14；
-
{1,3}，记为 V3，权值为 (a1⊕a1)+(a1⊕a3)+(a3⊕a1)+(a3⊕a3)=8；
-
{1,2,3}，记为 V4，权值为 28；
-
{2}，记为 V5，权值为 a2⊕a2=0；
-
{3}，记为 V6，权值为 a3⊕a3=0。
所以，全部连通块的权值和为 0+14+8+28+0+0=50。
示例 2
输入
4 5 6 3 1 1 2 1 3 2 4
输出
142
思路
每个连通块的权值是所有点对的异或和。
直接枚举所有连通块并计算权值会超时，因为连通块的数量是指数级的。
需要利用树的性质和动态规划来优化计算。
动态规划：
定义 dp[u]dp[u] 表示以 u 为根的子树中所有连通块的权值和。
定义 cnt[b][w][u] 表示以 u 为根的子树中，第 w 位为 b 的节点数。
定义 sz[u] 表示以 u 为根的子树中节点数。
DFS 遍历：
在 DFS 过程中，更新 dp[u]、cnt[b][w][u] 和 sz[u]。
对于每个子节点 v，计算其对 dp[u] 的贡献，并更新 cnt[b][w][u] 和 sz[u]。
最终答案：
所有连通块的权值和为 ans×2mod (10^9+7)
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e5 + 1;
int dp[N];
int cnt[2][30][N];
int sz[N];
int ans = 0;
void dfs(int u, int fa, const vector<vector<int>>& adj, const vector<int>& a) {
sz[u] = 1;
for (int w = 0; w < 30; w++) {
if ((a[u] >> w) & 1) {
cnt[1][w][u] = 1;
} else {
cnt[0][w][u] = 1;
}
}
for (int v : adj[u]) {
if (v == fa) continue;
dfs(v, u, adj, a);
dp[u] = (dp[u] + 1LL * dp[v] * sz[u] % mod + 1LL * dp[u] * sz[v] % mod) % mod;
for (int w = 0; w < 30; w++) {
int t = (1 << w) % mod;
dp[u] = (dp[u] + 1LL * t * cnt[0][w][u] % mod * cnt[1][w][v] % mod) % mod;
dp[u] = (dp[u] + 1LL * t * cnt[1][w][u] % mod * cnt[0][w][v] % mod) % mod;
cnt[0][w][u] = (cnt[0][w][u] + 1LL * cnt[0][w][u] * sz[v] % mod + 1LL * cnt[0][w][v] * sz[u] % mod) % mod;
cnt[1][w][u] = (cnt[1][w][u] + 1LL * cnt[1][w][u] * sz[v] % mod + 1LL * cnt[1][w][v] * sz[u] % mod) % mod;
}
sz[u] = (sz[u] + 1LL * sz[v] * sz[u] % mod) % mod;
}
ans = (ans + dp[u]) % mod;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> a(n + 1);
vector<vector<int>> adj(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
assert(a[i] >= 1 && a[i] <= 1e9);
}
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
memset(dp, 0, sizeof(dp));
memset(cnt, 0, sizeof(cnt));
memset(sz, 0, sizeof(sz));
ans = 0;
dfs(1, 0, adj, a);
cout << ans * 2 % mod << '\n';
return 0;
}