题解
2025-10-19 17:30:12
发布于：浙江
J2-超大序列
让 ( K ) 是所需的答案。
让我们记 ( sumA = \sum_{i=1}^N A_i )。
({B_1, \ldots, B_K}) 是 ( A ) 的若干个（比如 ( p ) 个）副本的连接，后跟 ( A ) 的前几个（比如 ( q ) 个）项。
这里，我们假设 ( p \geq 0, 1 \leq q \leq N )。
现在让我们找到 ( p ) 和 ( q )。
( p ) 可以通过
[p = \lfloor \frac{x}{sumA} \rfloor]
得到。
( q ) 可以通过朴素地求和 ( A_i ) 得到，计算时间为 ( O(N) )。
现在我们得到答案
[K = p \times N + q,]
因此问题已经解决。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
signed main(){
ll n;cin>>n;
vector<ll> a(n);
for(int i=0;i<=n-1;i++)cin>>a[i];
ll x;cin>>x;
ll sum=0;
for(ll val:a)sum+=val;
ll P = x / sum;
ll sumb = P * sum;
ll ans = P * n;
for(ll val:a){
sumb += val;
ans++;
if(sumb > x){
cout<< ans <<endl;
return 0;
}
}
return 0;
}
J2-序列查询
我们称一个整数为好整数，如果它不同于 ( A_1, A_2, \ldots, A_N ) 中的任何一个。
对于每个 ( i )，找到小于或等于 ( A_i ) 的好整数的个数，并将其记录为 ( C_i )。
那么，第K小的好整数可以通过以下方式找到：
- 如果 ( C_N < K )
- 答案总是大于 ( A_N )。由于每个大于 ( A_N ) 的整数都是好整数，所以答案是 ( A_N + (K - C_N) )。
- 如果 ( C_N \geq K )
- 使用二分查找找到最小的 ( i ) 使得 ( C_i \geq K )，那么答案大于 ( A_{i-1} ) 且小于 ( A_i )（这里我们假设 ( A_0 = 0 )）。由于每个大于 ( A_{i-1} ) 且小于 ( A_i ) 的整数都是好整数，所以答案是 ( (A_i - 1) - (C_i - K) )，也就是说，在 ( A_i - 1 ) 之前的 ( C_i - K ) 个元素。
复杂度为 ( O(N + Q \log N) )。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N, Q;
cin >> N >> Q;
vector<long long> A(N);
for (auto& x : A) {
cin >> x;
}
vector<long long> low(N);
for (int i = 0; i < N; ++i) {
low[i] = A[i] - (i + 1);
}
while (Q--) {
long long K;
cin >> K;
const int idx = lower_bound(low.begin(), low.end(), K) - low.begin();
if (idx == N) {
cout << A[N - 1] + (K - low[N - 1]) << '\n';
} else {
cout << A[idx] - (low[idx] - K + 1) << '\n';
}
}
return 0;
}
J2-序列差值
首先，如果简单地比较所有配对，你需要计算所有 ( NM ) 对的差值。在本次约束条件下，这将需要 ( 4 \times 10^{10} ) 次计算，无法在时间限制内完成。
相反，我们首先对两个数组进行排序。通常，如果给定序列或集合的顺序无关紧要，通过排序使其单调有时可以使问题更容易解决。我们几乎总是可以对给定的大序列进行排序，而且如果问题可解，那么排序后数组的问题也应该可解，因此考虑这种情况没有任何缺点。
现在，我们假设数组已排序。即，我们假设 ( A_1 \leq A_2 \cdots \leq A_N ) 和 ( B_1 \leq B_2 \cdots \leq B_M )。然后，对于每个 ( i = 1, 2, \ldots, N )，按此顺序，我们将找到使 ( |A_i - B_j| ) 最小的 ( j )。如果 ( A_i \leq B_j )，那么对于任何 ( j < j' )，有 ( |A_i - B_j| = B_j - A_i \leq B_j - A_i = |A_i - B_j| )，因此我们不需要检查任何大于 ( j ) 的 ( j' )。这看起来或多或少减少了计算量，但如果 ( A_i > B_N )，我们就必须检查每一对，所以这还不够。这里的关键在于反过来也很有用。即，如果 ( B_j \leq A_i < B_{j+1} )，那么对于每个 ( j' \leq j )，有 ( |A_{i+1} - B_j| = A_{i+1} - B_j \geq A_{i+1} - B_j \geq A_i - B_j = |A_i - B_j| )，因此我们不需要检查它。
总体而言，我们可以从 ( A_1 ) 和 ( B_1 ) 开始，重复以下步骤：
- 如果值 ( |A_i - B_j| ) 小于当前最小差值，则更新初步答案。
- 然后，比较 ( A_i ) 和 ( B_j )。
- 如果 ( A_i > B_j )，则将 ( B_j ) 更新为 ( B_{j+1} ) 并继续下一次迭代。
- 如果 ( A_i \leq B_j )，则我们不需要计算任何 ( j' > j ) 的 ( |A_i - B_j| )。此外，对于 ( A_{i+1} )，我们也不需要计算任何 ( j' < j ) 的 ( |A_{i+1} - B_j| )，因此我们继续使用 ( A_{i+1} ) 和 ( B_j ) 进行下一次迭代。
- 如果 ( i > N ) 且 ( j > M )，则终止操作。
现在让我们考虑上述步骤的复杂度。在每一步中，值 ( i + j ) 每次增加 1，因此迭代次数最多为 ( N + M - 1 )。由于每个操作可以在 ( O(1) ) 时间内完成，这部分可以在 ( O(N + M) ) 总时间内完成，因此加上初始排序，原问题可以在 ( O(N \log N + M \log M) ) 总时间内解决。
#include <bits/stdc++.h>
using namespace std;
#define N 200010
#define INF 1010000000
#define rep(i, n) for(int i = 0; i < n; ++i)
int main(void) {
int n, m;
int a[N];
int b[N];
int ans = INF;
cin >> n >> m;
rep(i, n)cin >> a[i];
rep(i, m)cin >> b[i];
sort(a, a + n);
sort(b, b + m);
int x = 0;
int y = 0;
while ((x < n) && (y < m)) {
ans = min(ans, abs(a[x] - b[y]));
if (a[x] > b[y])y++;
else x++;
}
cout << ans << endl;
return 0;
}
J2-子串询问
如果对每个查询都朴素地扫描 ( S_i, S_{i+1}, \ldots, S_n ) 来统计相同字母的出现次数，那么每个查询在最坏情况下需要 (\Theta(N)) 时间，对于 (Q) 个查询，最坏情况下总共需要 (\Theta(QN)) 时间，因此很难在时间限制内完成。
我们考虑一种更快响应每个查询的方法。假设查询给定一个子串 ( S_i, S_{i+1}, \ldots, S_n )，我们来思考如何找到答案。
基于给定的字符串 ( S )，定义一个长度为 ((N-1)) 的序列 ( A = (A_1, A_2, \ldots, A_{N-1}) )，其中：
[
A_i =
\begin{cases}
1 & \text{如果 } S_i = S_{i+1} \
0 & \text{如果 } S_i \neq S_{i+1}
\end{cases}
]
那么答案可以表示为 ( A_i + A_{i+1} + \cdots + A_{n-1} )。此外，我们定义一个序列 ( B = (B_0, B_1, B_2, \ldots, B_{N-1}) )：
[
B_i =
\begin{cases}
0 & \text{如果 } i = 0 \
A_1 + A_2 + \cdots + A_i & \text{如果 } i \geq 1
\end{cases}
]
这里，( B ) 是 ( A ) 的前缀和数组。那么，查询 ( A_i + A_{i+1} + \cdots + A_{n-1} ) 的答案等于：
[
A_i + A_{i+1} + \cdots + A_{n-1} = (A_1 + A_2 + \cdots + A_{n-1}) - (A_1 + A_2 + \cdots + A_{i-1}) = B_{n-1} - B_{i-1}
]
即 ( B ) 中两个元素的差：( B_{n-1} - B_{i-1} )。因此，如果我们预先计算 ( B )，那么每个查询的答案只需计算 ( B_{n-1} - B_{i-1} ) 即可在 ( O(1) ) 时间内得到。
因此，问题可以通过以下步骤在 ( O(N + Q) ) 总时间内解决：
- 首先针对输入的字符串 ( S ) 计算序列 ( A ) 及其前缀和数组 ( B )；
- 然后对于每个查询，以 ( O(1) ) 时间计算答案 ( B_{n-1} - B_{i-1} )。
注意，可以通过递推关系从序列 ( A ) 计算序列 ( B )，总时间为 ( O(N) )：
[
B_i =
\begin{cases}
0 & \text{如果 } i = 0 \
B_{i-1} + A_i & \text{如果 } i \geq 1
\end{cases}
]
#include <iostream>
using namespace std;
int n, q;
char s[300001];
int a[300000], b[300000];
int main(void)
{
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> s[i];
for(int i = 1; i <= n-1; i++) if(s[i] == s[i+1]) a[i] = 1;
for(int i = 1; i <= n-1; i++) b[i] = b[i-1] + a[i];
int l, r;
for(int i = 1; i <= q; i++){
cin >> l >> r;
cout << b[r-1]-b[l-1] << "\n";
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
long long a[100005]; // 存储输入的正整数序列
long long low[100005]; // 存储每个位置之前缺失的数字数量
int main(){
int n, q; // n:序列长度, q:查询次数
cin >> n >> q;
// 读入序列
for(int i = 1 ; i <= n ; i++) {
cin >> a[i];
}
// 对序列进行排序，便于分析缺失数字
sort(a+1, a+1+n);
// 计算low数组：low[i] = a[i] - i
// 表示在a[i]之前缺失的正整数数量
// 例如：a[1]=3, low[1]=3-1=2 (缺失1,2)
for(int i = 1 ; i <= n ; i++){
low[i] = a[i] - i;
}
// 处理每个查询
while(q--){
long long k; // 要查找的第k个缺失数字
cin >> k;
// 二分查找：在low数组中找到第一个大于等于k的位置
// low数组存储的是每个位置之前缺失的数字数量
// 我们要找的是第k个缺失数字，所以需要找到第一个缺失数量>=k的位置
int idk = lower_bound(low + 1, low + 1 + n, k) - low;
// 情况1：如果所有位置的缺失数量都小于k
// 说明第k个缺失数字在序列最大值之后
if(idk == n + 1){
// 在最大值之后的情况
// 因为前n个位置已经被序列中的数字占用
// 所以第k个缺失数字从n+1开始数，就是k+n
// 例如：序列[3,5,6,7]，k=5，缺失数字为[1,2,4,8,9,...]
// 第5个缺失数字是9 = 5 + 4
cout << k + n << endl;
} else {
// 情况2：在序列中间找到位置
// 第k个缺失数字 = k + idk - 1
// 解释：idk表示从第1个到第idk个元素之间缺失的数字数量≥k
// 所以第k个缺失数字就是k加上前面已经占用的位置数(idk-1)
// 例如：序列[3,5,6,7]，k=2，idk=1
// 第2个缺失数字是2 = 2 + 1 - 1
cout << k + idk - 1 << endl;
}
}
return 0;
}
这里空空如也
有帮助，赞一个