挑战赛 #15 题解
2025-02-24 08:59:17
发布于：浙江
T1
这是一道简单的字符串题目，任务是判断字符串中指定位置的字符，是否为给定的特定字符 。
int n;
string x;
cin >> n >> x;
if (x[n] == 'x')cout << "No" << endl;
else cout << "Yes" << endl;
T2
判断两个字符串的字符集是否一样
在处理字符串问题时，我们常常需要判断两个字符串的字符集是否相同。有一种可行的方法是，分别统计这两个字符串中每个字符的出现情况，就像把它们各自的字符放入两个 “桶” 中一样。这里的 “桶” 可以理解为一种数据结构，用于记录每个字符的存在与否或者出现次数。最后，通过比较这两个 “桶” 里的数据，来确定这两个字符串的字符集是否一致。
string x1, x2;
cin >> x1 >> x2;
map<char, int> mp1, mp2;
for (auto i: x1) {
mp1[i]++;
}
for (auto i: x2) {
mp2[i]++;
}
for (auto [i,j]: mp1) {
if (mp2[i] != j) {
cout << "No" << endl;
return;
}
}
for (auto [i,j]: mp2) {
if (mp1[i] != j) {
cout << "No" << endl;
return;
}
}
cout << "Yes" << endl;
T3
针对这道题目，我们可以先进行一个关键的分析：鼹鼠的能力值越高，其能够放置的位置选择也就越多，适用范围越广。基于此特性，在处理时，我们可以采用贪心策略，即从前往后遍历每一个位置，在每个位置都尝试放置当前可放置的鼹鼠中能力值最小的那一只。
具体实现上，我们可以通过简单的搜索来完成。使用一个二维搜索方式，第一维用于标记我们想要到达的位置 i，第二维则是在尚未使用过的鼹鼠中寻找能力值最小的那一只。若能找到符合条件的鼹鼠，就表明我们可以顺利到达 i 位置；反之，若找不到，那就说明无法到达该位置。
需要特别注意的是，在使用完某只鼹鼠后，一定要给它打上已使用的标记，避免重复使用。
这种解题方法采用了贪心算法和顺序处理的思路，时间复杂度为 。
int n;
cin >> n;
vector<int> arr(n + 1);
for (int i = 1; i <= n; i++) cin >> arr[i];
vector<int> op(n + 1);
for (int i = 1; i <= n; i++) cin >> op[i];
vector<int> vis(n + 1);
int now = 2;
for (int i = 2; i <= n; i++) {
int dis = arr[i] - arr[i - 1];
int mins = 1e9 + 7;
int len = 0;
for (int j = 1; j <= n; j++) {
//没用过 可用 更小花费
if (!vis[j] && op[j] >= dis && mins > op[j]) {
len = j;
mins = op[j];
}
}
if (len == 0) {
cout << "NO" << endl;
cout << i - 1 << endl;
return;
}
vis[len] = 1;
}
cout << "YES" << endl;
接下来，我为大家介绍另一种解题方法。对于每个位置，我们的目标是找出所有鼹鼠中能够适用且能力值最小的那一只。为了高效地实现这一目标，我们只需维护一个特定的数据结构，该结构要具备快速查找所需数据的能力。
在具体的数据结构选择上，有两种不错的方案。其一，我们可以采用动态开点的权值线段树，并在其上进行二分查找操作；其二，也可以使用 set 容器，利用其内部自带的二分查找功能。
这种方法运用了二分查找的思想，时间复杂度为 ，相较于某些传统方法在效率上有显著提升。
int n;
cin >> n;
vector<int> arr(n + 1);
for (int i = 1; i <= n; i++) cin >> arr[i];
set<pair<int, int> > s;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
s.emplace(x, i);
}
for (int i = 2; i <= n; i++) {
int dis = arr[i] - arr[i - 1];
auto it = s.upper_bound({dis, 0});
if (it == s.end()) {
cout << "NO" << endl;
cout << i - 1 << endl;
return;
}
s.erase(it);
}
cout << "YES" << endl;
T4
让我们来思考这样一个问题：给定 n 个数（其中 n 小于等于 20），对于每个数都有两种选择，即选或者不选。那么，总共会有多少种不同的选择情况呢？答案是 2 的 n 次方种，当 n 为 20 时，大约是 10 的 6 次方种情况，这个数量似乎还在可接受范围内。
然而，当 n 增加到 35 时，情况就截然不同了。此时，2 的 35 次方远大于 10 的 10 次方，这样的时间复杂度显然会导致程序运行效率极低，甚至可能超时。那么，我们该如何对这个问题进行时间复杂度上的优化呢？这里就要用到一个相对冷门但非常有效的知识点——折半搜索。
具体操作如下：首先，我们将这 n 个数分成前后两部分。对前半部分的所有数，穷举它们的所有选择情况，由于前半部分的数大约是 n/2 个，其组合情况数不到 10 的 6 次方种；后半部分也采用同样的方法进行处理。
现在问题来了，我们已经分别得到了前后两部分的所有组合情况，该如何将它们进行有效的组合呢？我们的目标是找出这些组合中对 x 取模结果最大的数。根据取模运算的性质，即 (x + y) % z 等于 (x % z + y % z) % z，我们可以先分别对前后两部分组合得到的数进行取模运算，然后再进行后续的计算，这样做并不会影响最终的结果。
同时，我们注意到一个重要的特性：对于前半部分集合中的任意元素 a，都有 a 小于 x；对于后半部分集合中的任意元素 b，也有 b 小于 x。由此可知，a + b 的值小于 2 * x。所以，我们只需要考虑两种情况：一是 a + b 小于 x 的情况，二是 x 小于等于 a + b 且 a + b 小于 2 * x 的情况。
针对这两种情况的处理，我们可以使用简单的双指针算法来高效实现。通过这种方式，我们可以在保证结果正确性的前提下，有效降低时间复杂度，避免因情况数过多而导致的效率问题。
i64 n, x;
cin >> n >> x;
if (n == 1) {
int t;
cin >> t;
cout << t % x << endl;
return;
}
i64 l = n / 2;
i64 r = n - l;
vector<i64> vl(l);
vector<i64> vr(r);
for (auto &i: vl)cin >> i;
for (auto &i: vr) cin >> i;
auto get = [&](vector<i64> &vv, int nn) {
set<i64> now;
for (int i = 0; i < nn; i++) {
set<i64> tmp;
for (auto j: now) {
tmp.emplace(j);
tmp.emplace((j + vv[i]) % x);
}
tmp.emplace(vv[i] % x);
now = tmp;
}
vector<i64> ans(now.begin(), now.end());
return ans;
};
auto ll = get(vl, l);
auto rr = get(vr, r);
int mid1 = rr.size();
mid1--;
int last = mid1;
i64 maxs = 0;
for (long long i: ll) {
while (mid1 > 0 && rr[mid1] + i >= x)mid1--;
maxs = max({
maxs,
(i + rr[mid1]) % x,
(i + rr[last]) % x,
i
});
}
cout << maxs << endl;
T5
我们留意到题目要求中必定存在一条从节点 i 到节点 i + 1 的路线。由此我们不禁思考，对于任意一条从节点 i 到节点 i + x（x > 1）的边，是否都属于无效边呢？是不是只需关注那些向前走的边就足够了？此外，如果我们已经到达了某个节点 i，那么是否意味着 i 之后的所有节点都能够到达呢？
如此一来，问题就转化为：在可以对边进行添加或删除操作的情况下，我们最终能够到达的最靠前的节点是哪一个？
针对这个问题，我们来分析有效边 (x, y) 所具备的性质。首先，显然需要满足 x > y，那么除此之外还有其他特性吗？仅观察一条边，似乎难以发现更多性质。那我们增加边的数量，假设有两条边 (r1, l1) 和 (r2, l2)，我们可以将它们看作两条线段，端点分别为 l1、r1 和 l2、r2。
经过分析我们发现，若 l1 ≤ l2 ≤ r2 ≤ r1，那么线段 l2 r2 实际上是无用的；若 l1 < r1 < l2 < r2，这两条线段之间似乎没有明显的关联。然而，当出现 l1 ≤ l2 ≤ r1 ≤ r2 的情况时，对于处于区间 [l1, r2] 内的任意点 x，它可以先到达 r2，接着到 l2，再到 r1，最后到达 l1，这一过程似乎等价于存在一条从 (r2, l1) 的边。
换一种思路来理解，对于每一条区间为 [r, l] 的边，我们可以将其拆解为 r - l + 1 条长度为 1 的边。具体来说，这些边依次为 [r, r - 1]、[r - 1, r - 2]、……、[l + 1, l] 。通过这样的拆解方式，大家能更加直观、便捷地理解区间合并的相关知识 。
至此，这道题就变得清晰明了了。该问题可以转化为：给定一条线段，其上分布着若干子线段，并且允许对这些子线段进行添加或删除操作。现在有一些询问点 x，需要找出在区间 [1, x] 中最后一个没有被任何子线段覆盖的点。很明显，这是一个典型的扫描线问题。
这里给出一种使用支持区间加和线段树二分的解法。需要注意的是，这里采用的是线段树二分，而非二分线段树，因为二者的单次操作复杂度有所不同，前者为 ，而后者为 。
线段树模版大家可以自行学习，这里只给主函数代码
解法
int n, q;
cin >> n >> q;
STG stg(n);
for (int i = 1; i <= q; i++) {
int op, x, y;
cin >> op >> x;
if (op == 1) {
cin >> y;
if (x > y) {
stg.add(1, 1, n, y, x, 1);
}
} else if (op == 2) {
cin >> y;
if (x > y) {
stg.add(1, 1, n, y, x, -1);
}
} else {
int t = stg.biny_search(1, 1, n, 1, x);
if (t == x) t--;
cout << n - t << endl;
}
}
T6
题目要求十分清晰，给定两个字符串 和 ，需要找出字符串 的最长前缀 ，使得该前缀在字符串 中至少出现 次，判断这样的前缀是否存在，若存在则将其输出。
那么，该如何解决这个问题呢？下面为大家提供两种解法。
第一种解法，运用哈希字符串结合二分查找的方法。
哈希函数这个大家可以进行相关搜索，这里只给主函数
string a, b;
cin >> a >> b;
int t;
cin >> t;
int now = 0;
strhash::StringHash sh1(a), sh2(b);
int n1 = a.length(), n2 = b.length();
for (int i = 20; i >= 0; i--) {
if (now + (1 << i) > n2 || now + (1 << i) > n1) continue;
int tt = 0;
int ll = now + (1 << i);
for (int j = 0; j + ll <= n1; j++) {
if (sh2.get(0, ll ) == sh1.get(j, j + ll )) {
tt++;
}
}
if (tt >= t) {
now = ll;
}
}
第二种方法是利用 KMP 算法。在使用 KMP 算法进行字符串匹配时，模式串每移动一次都会产生一定的相对位移。此时，我们可以记录下模式串每次移动后的当前位置，并把这些位置信息存储到一个数据结构（可形象地将其视为“桶”）当中。
同样的模版大家自己学习去啦
string a, b;
cin >> a >> b;
//计算a中每一个点匹配到b的哪个位置
auto t = find_occurrences(a, b);
//next函数
auto z = prefix_function(b);
// debug(z);
int nn = b.size();
vector<int> bn(nn + 1);
for (auto i: t)bn[i]++;
for (int i = nn; i; i--) {
// debug(z[i- 1], i);
bn[z[i - 1]] += bn[i];
}
int k;
cin >> k;
for (int i = nn; i; i--) {
if (bn[i] > k) {
cout << b.substr(0, i) <<endl;;
return;
}
}
cout << "IMPOSSIBLE" << endl;
有帮助，赞一个