A.Longest k-Good Segment
核心思路
采用滑动窗口（双指针）维护一个合法区间，保证区间内不同元素个数不超过 k。枚举右端点，若加入新元素后不同元素个数超过 k，则移动左指针缩小区间，直到合法。在每次合法时更新最长区间的左右端点。
具体步骤
-
读入 n,k 和数组 a（下标从 0 开始）。
-
初始化左指针
left = 0，不同元素计数distinct = 0，计数数组cnt（记录窗口内各数值出现次数）。 -
初始化最优长度
len = 0，最优左右端点ansL = 0, ansR = -1。 -
枚举右端点
right从 0 到 n−1：-
将
a[right]加入窗口：若cnt[a[right]] == 0，则distinct++；然后cnt[a[right]]++。 -
若
distinct > k，循环移动左指针：- 将
a[left]移出窗口：cnt[a[left]]--；若cnt[a[left]] == 0，则distinct--；left++。
- 将
-
当前合法区间长度为
right - left + 1，若大于len，则更新len、ansL = left、ansR = right。
-
-
输出
ansL + 1和ansR + 1（题目下标从 1 开始）。
题解
#include <bits/stdc++.h>
using namespace std;
const int N = 1000000;
int main()
{
int n, k;
scanf("%d%d", &n, &k);
vector<int> a(n);
for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
vector<int> cnt(N + 1, 0);
int left = 0, d = 0;
int len = 0, l = 0, r = -1;
for (int right = 0; right < n; right ++)
{
int x = a[right];
if (cnt[x] == 0) d ++;
cnt[x] ++;
while (d > k)
{
int y = a[left];
cnt[y] --;
if (cnt[y] == 0) d--;
left ++;
}
int curLen = right - left + 1;
if (curLen > len)
{
len = curLen;
l = left;
r = right;
}
}
printf("%d %d", l + 1, r + 1);
return 0;
}
B.Range Update Point Query
核心思路
只有数值 ≥10 的位置才会在“数位和”操作中发生变化，且每次操作后数值严格减小，最终变为一位数。用有序集合 set 维护所有当前值 ≥10 的位置。操作 1 时，只需在区间内处理这些位置，计算数位和并更新，若结果 <10 则从集合中删除；否则保留，等待后续再次变化。每个位置至多被处理有限次（约 3~4 次），总时间复杂度 O((n+q) log n)。
具体步骤
-
读入测试组数
t。 -
对每组数据：
-
读入
n, q和数组a[1..n]。 -
初始化空集合
st，将所有a[i] ≥ 10的下标i插入。 -
循环处理
q个操作：-
若操作为
1 l r：-
用
st.lower_bound(l)找到区间内第一个可能变化的位置。 -
当迭代器指向的位置 ≤ r 时：
- 计算该位置的数位和
val，更新a[pos] = val。 - 若
val < 10，则从集合中删除该位置（it = st.erase(it)）；否则++it。
- 计算该位置的数位和
-
-
若操作为
2 x：直接输出a[x]。
-
-
-
每组数据结束后换行（如有多个输出）。
题解
#include <bits/stdc++.h>
using namespace std;
int workOut(int x)
{
int sum = 0;
while (x)
{
sum += x % 10;
x /= 10;
}
return sum;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--)
{
int n, q;
cin >> n >> q;
vector<int> a(n + 1);
set<int> st;
for (int i = 1; i <= n; i ++)
{
cin >> a[i];
if (a[i] >= 10) st.insert(i);
}
while (q--)
{
int op;
cin >> op;
if (op == 1)
{
int l, r;
cin >> l >> r;
auto it = st.lower_bound(l);
while (it != st.end() && *it <= r)
{
int pos = *it;
int val = workOut(a[pos]);
a[pos] = val;
if (val < 10) it = st.erase(it);
else it ++;
}
}
else
{
int x;
cin >> x;
cout << a[x] << '\n';
}
}
}
return 0;
}
C.Tracking Segments
核心思路
利用单调性：若前 mid 次修改后存在美丽区间，则修改次数更多时该区间仍然美丽，因此可二分最早修改次数。检查时，用前缀和快速统计前 mid 个被修改位置上 1 的个数，然后遍历所有给定区间，判断是否存在满足 2 * ones > len 的区间。
具体步骤
-
读入测试组数
t。 -
对每组数据：
-
读入
n, m，存储m个区间(l, r)。 -
读入
q和q个修改位置（存入数组c，下标从 0 开始）。 -
先调用
check(q)检查所有修改完成后是否已有美丽区间；若无，输出-1并继续下一组。 -
否则二分答案：左边界
l = 1，右边界r = q，维护ans = q。- 计算
mid = (l + r) / 2，若check(mid)为真，则更新ans = mid，r = mid - 1；否则l = mid + 1。
- 计算
-
输出
ans。
-
-
check(mid)实现：- 创建长度为
n+1的前缀和数组pre，初始化为 0。 - 将前
mid个修改位置c[0..mid-1]在pre中标记为 1。 - 计算前缀和
pre[i] += pre[i-1]。 - 遍历所有区间，若存在
2 * (pre[r] - pre[l-1]) > (r - l + 1)，返回true，否则返回false。
- 创建长度为
题解
#include <bits/stdc++.h>
using namespace std;
int n, m, q;
vector<pair<int, int>> a;
vector<int> c;
bool check(int mid)
{
vector<int> pre(n + 1, 0);
for (int i = 0; i < mid; i ++)
{
pre[c[i]] = 1;
}
for (int i = 1; i <= n; i ++)
{
pre[i] += pre[i - 1];
}
for (auto &seg : a)
{
int l = seg.first, r = seg.second;
int len = r - l + 1;
int ones = pre[r] - pre[l - 1];
if (2 * ones > len) return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t --)
{
cin >> n >> m;
a = vector<pair<int,int>>(m);
for (int i = 0; i < m; i ++)
{
cin >> a[i].first >> a[i].second;
}
cin >> q;
c = vector<int>(q);
for (int i = 0; i < q; i ++) cin >> c[i];
if (!check(q))
{
cout << -1 << '\n';
continue;
}
int l = 1, r = q, ans = q;
while (l <= r)
{
int mid = (l + r) / 2;
if (check(mid))
{
ans = mid;
r = mid - 1;
}
else
{
l = mid + 1;
}
}
cout << ans << '\n';
}
return 0;
}
D.Fountains
核心思路
分三类情况计算最大美丽值：①用金币买一座、钻石买一座；②用金币买两座；③用钻石买两座。分别求最大值，取三者最大。
对于单一货币买两座，先将所有价格 ≤ 预算的喷泉按价格排序，用前缀最大值记录价格不超过当前位置的最大美丽值，再枚举较贵的喷泉，二分查找价格不超过剩余预算的最便宜喷泉位置，更新答案。
具体步骤
-
读入
n, c, d，按货币类型将喷泉分别存入coin（金币）和dia（钻石）列表。 -
计算混合购买：
- 遍历
coin，找出价格 ≤c的最大美丽值bestC；遍历dia，找出价格 ≤d的最大美丽值bestD。 - 若两者都存在，则用
bestC + bestD更新答案。
- 遍历
-
计算同币种购买：
- 对
coin和dia分别调用getTwo(items, budget)，得到该货币下买两座喷泉的最大美丽值（若不足两座则返回 -1），更新答案。
- 对
-
getTwo实现：-
过滤出价格 ≤
budget的喷泉，存入v。 -
若
v.size() < 2返回 -1。 -
将
v按价格升序排序。 -
构建前缀最大值数组
pre，pre[i]表示前i个喷泉（按价格排序）中的最大美丽值。 -
枚举
i从 1 到m-1（将v[i]作为较贵的那座）：- 计算剩余预算
remain = budget - v[i].second。 - 在
v[0..i-1]中二分查找价格 ≤remain的最大下标pos。 - 若存在，用
pre[pos] + v[i].first更新答案。
- 计算剩余预算
-
-
输出最终答案
ans（初始为 0）。
题解
#include <bits/stdc++.h>
using namespace std;
bool cmp(pair<int, int> x, pair<int, int> y)
{
return x.second < y.second;
}
int getTwo(vector<pair<int, int>> items, int budget)
{
vector<pair<int, int>> v;
for (auto p : items)
{
if (p.second <= budget) v.push_back(p);
}
if (v.size() < 2) return -1;
sort(v.begin(), v.end(), cmp);
int m = v.size();
vector<int> pre(m);
pre[0] = v[0].first;
for (int i = 1; i < m; i ++)
{
pre[i] = max(pre[i - 1], v[i].first);
}
int ans = -1;
for (int i = 1; i < m; i ++)
{
int remain = budget - v[i].second;
if (remain <= 0) continue;
int l = 0, r = i - 1, pos = -1;
while (l <= r)
{
int mid = (l + r) / 2;
if (v[mid].second <= remain)
{
pos = mid;
l = mid + 1;
}
else
{
r = mid - 1;
}
}
if (pos != -1)
{
ans = max(ans, pre[pos] + v[i].first);
}
}
return ans;
}
int main()
{
int n, c, d;
cin >> n >> c >> d;
vector<pair<int, int>> coin, dia;
for (int i = 0; i < n; i ++)
{
int b, p; char type;
cin >> b >> p >> type;
if (type == 'C') coin.push_back({b, p});
else dia.push_back({b, p});
}
int ans = 0;
int bestC = -1, bestD = -1;
for (auto it : coin)
{
if (it.second <= c)
{
bestC = max(bestC, it.first);
}
}
for (auto it : dia)
{
if (it.second <= d)
{
bestD = max(bestD, it.first);
}
}
if (bestC != -1 && bestD != -1) ans = max(ans, bestC + bestD);
int twoC = getTwo(coin, c);
if (twoC != -1) ans = max(ans, twoC);
int twoD = getTwo(dia, d);
if (twoD != -1) ans = max(ans, twoD);
cout << ans;
return 0;
}
评论
0