选择性子数组求和问题
问题 A: 选择性子数组求和
给定一个包含 n 个整数的数组以及一个整数 x。目标是找到一个最大的子数组，其元素的总和不能被 x 整除。
解题思路:
首先，计算整个数组的总和。如果整个数组的总和不能被 x 整除，那么整个数组就是符合条件的最大的子数组，此时的最大长度即为 n。
如果整个数组的总和可以被 x 整除，我们需要从数组的两端找到第一个不能被 x 整除的元素。具体操作如下：
- 从数组的左侧开始，找到第一个元素
a[i]，使得a[i] % x != 0。记下这个索引i。 - 从数组的右侧开始，找到第一个元素
a[j]，使得a[j] % x != 0。记下这个索引j。
此时，我们可以移除从左侧找到的第一个不被 x 整除的元素到数组末尾的子数组，或者移除从右侧找到的第一个不被 x 整除的元素到数组开头的子数组。这两种情况分别对应着移除 i 个元素或移除 n-j+1 个元素。因此，我们需要选择移除元素数量较少的那一部分，即比较 i 和 n-j+1 的大小。最终的最大子数组长度为 n - min(i, n - j + 1)。如果计算出的最大长度为 0（即所有元素都可被 x 整除），则返回 -1。
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int T;
std::cin >> T;
while (T--) {
int n;
long long x;
std::cin >> n >> x;
std::vector<long long> a(n);
long long total_sum = 0;
for (int i = 0; i < n; ++i) {
std::cin >> a[i];
total_sum += a[i];
}
if (total_sum % x != 0) {
std::cout << n << "\n";
continue;
}
int first_uneven_left = -1;
for (int i = 0; i < n; ++i) {
if (a[i] % x != 0) {
first_uneven_left = i;
break;
}
}
int first_uneven_right = -1;
for (int i = n - 1; i >= 0; --i) {
if (a[i] % x != 0) {
first_uneven_right = i;
break;
}
}
if (first_uneven_left == -1) { // All elements are divisible by x
std::cout << -1 << "\n";
} else {
// Length of subarray if we remove from left: n - (first_uneven_left + 1)
// Length of subarray if we remove from right: first_uneven_right
int max_len = std::max(n - (first_uneven_left + 1), first_uneven_right);
std::cout << max_len << "\n";
}
}
return 0;
}
问题 B: 陷阱游戏
有 n 个地点，m 个士兵，k 个陷阱。每个士兵具有敏捷值 a[i]。第 i 个陷阱位于地点 l[i]，危险值为 d[i]。如果士兵的敏捷值 a[i] >= d[i]，则士兵不会阵亡。如果提前到达陷阱的解除点 r[i] (r[i] > l[i])，则可以解除该陷阱。队长需要带领队伍，且队伍不能进入未解除的陷阱。给定总时间限制 T，每移动一个单位消耗一个时间。目标是求最多能带多少士兵到达地点 n+1。
解题思路:
这个问题可以建模为：队长需要先去解除陷阱，然后大部队跟随。如果队伍能够一起行动，可以节省时间。当遇到陷阱时，队长需要单独前往解除点 r[i]，然后再返回与大部队汇合。多次单独行动会消耗大量时间，因此一次性解除多个陷阱是更优的选择。然而，如果队长跑得太远，返回的时间也会增加，这会造成时间上的浪费。因此，需要找到一个最优的"分界点"。
可以将陷阱的出现地点 l[i] 和解除点 r[i] 看作线段。重叠的线段可以被一同处理，而非重叠的线段则会造成行程的浪费。这个问题可以通过差分数组来处理。
在所有士兵和陷阱被处理完后，可以考虑抛弃敏捷值较低的士兵。这是一个可以二分查找的优化过程。通过二分查找，我们可以确定在给定时间内，最多能够带多少士兵（即敏捷值最高的士兵）通过所有必要的陷阱。
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
struct Trap {
int l, r, d;
bool operator<(const Trap& other) const {
return l < other.l;
}
};
bool can_pass(int num_soldiers, int n, int m, int k, int T, const std::vector<int>& soldier_agility, const std::vector<Trap>& traps) {
if (num_soldiers == 0) return true;
int required_agility = soldier_agility[num_soldiers - 1]; // The agility of the least agile soldier in the group
std::vector<int> trap_effect(n + 2, 0);
for (const auto& trap : traps) {
if (trap.d > required_agility) {
trap_effect[trap.l]++;
trap_effect[trap.r + 1]--;
}
}
int current_traps = 0;
long long time_cost = 0;
for (int i = 1; i <= n; ++i) {
current_traps += trap_effect[i];
if (current_traps > 0) {
time_cost += 2; // Travel to trap and return
}
time_cost += 1; // Travel to next location
}
time_cost += 1; // Final travel to n+1
return time_cost <= T;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int m, n, k, T;
std::cin >> m >> n >> k >> T;
std::vector<int> soldier_agility(m);
for (int i = 0; i < m; ++i) {
std::cin >> soldier_agility[i];
}
std::sort(soldier_agility.begin(), soldier_agility.end());
std::vector<Trap> traps(k);
for (int i = 0; i < k; ++i) {
std::cin >> traps[i].l >> traps[i].r >> traps[i].d;
}
std::sort(traps.begin(), traps.end());
int low = 0, high = m, max_soldiers = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
if (can_pass(mid, n, m, k, T, soldier_agility, traps)) {
max_soldiers = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
std::cout << max_soldiers << "\n";
return 0;
}
问题 E: 压缩单词
给出 n 个字符串，需要将它们进行合并。如果当前处理的字符串的前缀与之前合并结果的后缀相同，则可以省略这部分相同的前缀。求最终合并后的字符串。
解题思路:
由于字符串的总长度可能达到 106，暴力匹配前缀和后缀会导致超时。可以使用字符串哈希（Rolling Hash）来优化匹配过程。对于每个新的字符串 s，计算其所有前缀的哈希值，并计算已合并结果（当前答案字符串 ans）的后缀哈希值。通过比较哈希值来判断是否存在可合并的前缀。
需要注意的是，匹配是从前往后（计算 s 的前缀哈希）和从后往前（计算 ans 的后缀哈希）进行的，这两种哈希计算方式略有不同。
在比较过程中，如果找到最长的可合并前缀，则将该前缀之后的部分添加到 ans 字符串中。
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
long long power(long long base, long long exp, long long mod) {
long long res = 1;
base %= mod;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % mod;
base = (base * base) % mod;
exp /= 2;
}
return res;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n;
std::cin >> n;
std::string final_ans;
std::cin >> final_ans;
long long base = 233;
long long mod = 1e9 + 7;
for (int i = 1; i < n; ++i) {
std::string current_s;
std::cin >> current_s;
int max_overlap = 0;
long long current_prefix_hash = 0;
long long current_suffix_hash = 0;
long long p_pow = 1;
int s_len = current_s.length();
int ans_len = final_ans.length();
for (int j = 0; j < std::min(s_len, ans_len); ++j) {
current_prefix_hash = (current_prefix_hash * base + current_s[j]) % mod;
current_suffix_hash = (current_suffix_hash + final_ans[ans_len - 1 - j] * p_pow) % mod;
p_pow = (p_pow * base) % mod;
if (current_prefix_hash == current_suffix_hash) {
// Verify actual string match to avoid hash collisions
bool match = true;
for(int k=0; k <= j; ++k) {
if (current_s[k] != final_ans[ans_len - 1 - j + k]) {
match = false;
break;
}
}
if(match) {
max_overlap = j + 1;
}
}
}
final_ans += current_s.substr(max_overlap);
}
std::cout << final_ans << "\n";
return 0;
}
问题 F: 数组稳定化 (GCD 版本)
给定一个数组 a，每次操作生成一个新数组 b，其中 b[i] = gcd(a[i], a[(i+1) % (n+1)])。问至少需要多少次操作才能使数组中的所有元素都相同。
解题思路:
最终数组中的所有元素都将等于原始数组中所有元素的最大公约数 (GCD)。
考虑第 k 次操作后，b[i] 的值将是原始数组中从 a[i] 到 a[i+k]（在环上）的 GCD。最多需要进行 n-1 次操作，因为在第 n-1 次操作后，数组中的每个元素都将是整个原始数组的 GCD。
这个问题具有单调性：如果第 k 次操作后数组稳定，那么第 k+1 次操作后数组也必然稳定。因此，可以使用二分查找来寻找最小的操作次数。
为了处理环形数组的 GCD 计算，可以将数组复制一份，形成一个长度为 2*n 的数组。这样，任意长度为 n 的子数组的 GCD 都可以通过在倍长数组上进行区间查询来获得。
可以使用线段树来高效地计算区间 GCD。线段树的每个节点存储对应区间的 GCD 值。
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
int gcd(int a, int b) {
while (b) {
a %= b;
std::swap(a, b);
}
return a;
}
std::vector<int> segment_tree;
std::vector<int> arr;
int n_double;
void build_segment_tree(int node, int start, int end) {
if (start == end) {
segment_tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
build_segment_tree(2 * node, start, mid);
build_segment_tree(2 * node + 1, mid + 1, end);
segment_tree[node] = gcd(segment_tree[2 * node], segment_tree[2 * node + 1]);
}
}
int query_segment_tree(int node, int start, int end, int l, int r) {
if (r < start || end < l) {
return 0; // Identity element for GCD is 0, as gcd(x, 0) = x
}
if (l <= start && end <= r) {
return segment_tree[node];
}
int mid = (start + end) / 2;
int p1 = query_segment_tree(2 * node, start, mid, l, r);
int p2 = query_segment_tree(2 * node + 1, mid + 1, end, l, r);
return gcd(p1, p2);
}
bool check(int k, int n) {
for (int i = 0; i < n; ++i) {
int gcd1 = query_segment_tree(1, 0, n_double - 1, i, i + k);
int gcd2 = query_segment_tree(1, 0, n_double - 1, (i + 1) % n_double, (i + 1) % n_double + k);
if ((i + 1) % n_double + k >= n_double) { // Handle wrap around carefully for range
// This case requires more careful segment tree query logic for ranges that span the wrap-around point.
// A simpler approach for this problem might be to just ensure k is small enough such that i+k is always within bounds,
// or to use a segment tree that handles the circularity directly.
// For simplicity in this explanation, assuming k < n allows i+k to be within the 2n array bounds for most i.
// A more robust implementation would query two segments if the range wraps.
// For now, let's assume a simplified check.
// A correct wrap-around query:
int effective_end_2 = (i + 1) % n_double + k;
int gcd_part1 = query_segment_tree(1, 0, n_double - 1, (i + 1) % n_double, n_double - 1);
int gcd_part2 = query_segment_tree(1, 0, n_double - 1, 0, effective_end_2 % n_double);
gcd2 = gcd(gcd_part1, gcd_part2);
} else {
gcd2 = query_segment_tree(1, 0, n_double - 1, i + 1, i + 1 + k);
}
if (gcd1 != gcd2) {
return false;
}
}
return true;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int T;
std::cin >> T;
while (T--) {
int n;
std::cin >> n;
arr.assign(n, 0);
bool all_same = true;
std::cin >> arr[0];
for (int i = 1; i < n; ++i) {
std::cin >> arr[i];
if (arr[i] != arr[0]) {
all_same = false;
}
}
if (all_same) {
std::cout << "0\n";
continue;
}
n_double = 2 * n;
arr.resize(n_double);
for (int i = 0; i < n; ++i) {
arr[i + n] = arr[i];
}
segment_tree.assign(4 * n_double, 0);
build_segment_tree(1, 0, n_double - 1);
int ans = n - 1;
int low = 0, high = n - 1; // k is the number of operations, range is 0 to n-1
while (low <= high) {
int mid_k = low + (high - low) / 2; // mid_k represents the number of operations
if (check(mid_k, n)) {
ans = mid_k;
high = mid_k - 1;
} else {
low = mid_k + 1;
}
}
std::cout << ans << "\n";
}
return 0;
}
问题 G: Orac and Models
给定一个数组，需要从中挑选一个上升子序列。该子序列的特点是：子序列中的每个元素在原数组中的下标必须是其前一个元素下标的倍数。求满足条件的最长上升子序列的长度。
解题思路:
这是一个典型的动态规划问题。我们可以定义 dp[i] 为以原数组中下标为 i 的元素结尾的最长满足条件的子序列的长度。
状态转移方程如下：
dp[i] = 1 + max(dp[j])，其中 j < i，a[i] > a[j]，且 i 是 j 的倍数（即 i % j == 0）。
初始条件为 dp[i] = 1，表示每个元素本身可以构成一个长度为 1 的子序列。
为了优化计算 max(dp[j]) 的过程，我们可以只考虑 j 是 i 的约数的情况。具体来说，对于每个 i，我们遍历其所有约数 j。如果 a[i] > a[j]，则更新 dp[i]。
最终答案是所有 dp[i] 中的最大值。
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int T;
std::cin >> T;
while (T--) {
int n;
std::cin >> n;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
}
std::vector<int> dp(n + 1, 0);
int max_len = 0;
for (int i = 1; i <= n; ++i) {
dp[i] = 1; // Each element itself is a subsequence of length 1
// Iterate through all divisors j of i
for (int j = 1; j * j <= i; ++j) {
if (i % j == 0) {
// Check divisor j
if (a[i] > a[j]) {
dp[i] = std::max(dp[i], dp[j] + 1);
}
// Check divisor i/j (if different from j)
if (j * j != i) {
int divisor_pair = i / j;
if (a[i] > a[divisor_pair]) {
dp[i] = std::max(dp[i], dp[divisor_pair] + 1);
}
}
}
}
max_len = std::max(max_len, dp[i]);
}
std::cout << max_len << "\n";
}
return 0;
}
