目录
写在前面
比赛地址：https://codeforces.com/contest/1925。
在床上躺了两天终于复活了妈的。
A
发现字符串 \(s\) 合法当且仅当 \(s\) 可以被分为至少 \(n\) 段，其中每段都包含 \(k\) 种字符至少 1 次。
正确性可以归纳证明，这里懒得写了感性理解下。
于是只需构造：abc...abc...abc......。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
int n, k; std::cin >> n >> k;
for (int i = 1; i <= n; ++ i) {
for (int j = 0; j < k; ++ j) {
printf("%c", (char) 'a' + j);
}
}
printf("\n");
}
return 0;
}
/*
abc cba abc
*/
B
典中典之枚举 \(\operatorname{gcd}\)。
考虑枚举 \(x\) 的因数 \(d\)，检查答案是否可以为 \(d\)，即检查是否存在 \(\frac{x}{d}\ge n\)（可以被分为大于 \(n\) 份）即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
int x, n, ans = 1; std::cin >> x >> n;
for (int i = 1; i * i <= x; ++ i) {
if (x % i != 0) continue;
if (x / i >= n) ans = std::max(ans, i);
if (x / (x / i) >= n) ans = std::max(ans, x / i);
}
std::cout << ans << "\n";
}
return 0;
}
C
A 题，何时又来了？
唏，可以和解吗？
套用 A 的结论：字符串 \(s\) 合法当且仅当 \(s\) 可以被分为至少 \(n\) 段，其中每段都包含 \(k\) 种字符至少 1 次，在顺序枚举字符的同时检查当前一段中是否已经有了 \(k\) 种字符，若满足则分一段，最后检查是否分了不少于 \(n\) 段来判断字符串合法。
然后考虑如何找到在不合法的字符串里的一个未出现过的子序列。考虑在上述过程中某不合法字符串被分为了 \(m(m<n)\) 段出现了 \(k\) 种字符的以及最后一段未出现 \(k\) 种字符的，设这 \(m\) 段中最晚出现的字符为 \(c_i(1\le i\le m)\)，最后一段中 \(c_{j}\) 没有出现，则可证明：\(t = c_1c_2\cdots c_m c_j (|t| \le n)\) 没有出现。
其正确性可以考虑反证+归纳：
- 若 \(m=0\)，则 \(c_j\) 未在 \(s\) 中出现过，显然上述结论正确。
- 否则若 \(t\) 在 \(s\) 中出现过，说明结尾的 \(c_j\) 一定来自于第 \(m\) 段，且该位置一定在第 \(m\) 段的 \(c_m\) 之前，而该位置之前的部分只能被分为 \(m-1\) 段出现了 \(k\) 种字符的以及最后一段未出现 \(c_m\) 的，归纳可知无法表示出 \(t\) 的前缀 \(c_1c_2\cdots c_m\)，反证上述结论正确。
要求输出长度为 \(n\) 的，则在 \(t\) 后面随便补什么东西就行。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
int n, k, m; std::cin >> n >> k >> m;
std::string s, t; std::cin >> s;
int cnt = 0, cnt1 = 0, cnt2[30] = {0};
for (int i = 0; i < m; ++ i) {
++ cnt2[s[i] - 'a'];
if (cnt2[s[i] - 'a'] == 1) ++ cnt1;
if (cnt1 == k) {
t.push_back(s[i]);
++ cnt;
cnt1 = 0;
for (int j = 0; j < 26; ++ j) cnt2[j] = 0;
}
}
if (cnt >= n) {
std::cout << "YES\n";
} else {
std::cout << "NO\n";
for (int i = 0; i < k; ++ i) {
if (!cnt2[i]) {
if (t.size() < n) t.push_back((char) (i + 'a'));
while (t.size() < n) t.push_back('a');
std::cout << t << "\n";
break;
}
}
}
}
return 0;
}
/*
aabbcccc
cab
ab
cccaabb
ccbba
*/
D
期望，懒了。
E
呃呃数据结构。
发现这若干个太空港实际上将 \(1\sim n\) 划分成了若干个区间，每个区间内部的贡献都是一个公差为左侧太空港的价值，项数为与右侧太空港距离的等差数列的形式。
这东西长得太分块了哈哈，考虑将询问拆成中间的完整区间与两端点所在的不完整区间的形式。端点位于的区间可以使用 set 求前驱后继得到，等差数列求和即得不完整区间贡献；中间的完整区间考虑预处理出其贡献并存到其左端点上，再用树状数组维护区间和即可。
修改操作相当于将一个完整区间拆成两个区间，发现被影响的位置仅有原来区间的左端点与当前新加入的位置，树状数组单点修改即可。
修改和查询均为 \(O(\log n)\) 级别，总时间复杂度 \(O((m+q)\log n)\) 级别。
代码中为了方便查询操作求不完整区间（主要是两端点在同一区间内的情况）的贡献，钦定了查询的端点位置上不能有太空港，若有则找到区间内最近的非太空港位置再查询，同样使用了 set 维护。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define pii std::pair<int,int>
#define mp std::make_pair
const int kN = 3e5 + 10;
//=============================================================
int n, m, q, num;
int p[kN], v[kN], id[kN];
std::set <pii> h;
std::set <int> noth;
//=============================================================
namespace BIT {
#define lowbit(x) ((x)&(-x))
int lim;
LL s[kN];
void Init(int lim_) {
lim = lim_;
}
void Insert(int pos_, LL val_) {
for (int i = pos_; i <= lim; i += lowbit(i)) {
s[i] += val_;
}
}
LL Sum(int pos_) {
LL ret = 0;
for (int i = pos_; i; i -= lowbit(i)) {
ret += s[i];
}
return ret;
}
LL Query(int L_, int R_) {
if (L_ > R_) return 0;
return Sum(R_) - Sum(L_ - 1);
}
#undef lowbit
}
LL Calc(LL val_, LL dis_) {
return 1ll * (dis_ + 1ll) * dis_ / 2ll * val_;
}
void Init() {
std::cin >> n >> m >> q;
BIT::Init(n);
for (int i = 0; i <= n + 1; ++ i) noth.insert(i);
for (int i = 1; i <= m; ++ i) {
std::cin >> p[++ num];
id[p[i]] = i;
h.insert(mp(p[i], i)), noth.erase(p[i]);
}
for (int i = 1; i <= m; ++ i) std::cin >> v[i];
for (int i = 1; i <= m; ++ i) {
std::set <pii>::iterator it = h.lower_bound(mp(p[i], i));
int pre = (-- it)->second;
if (p[i] > 1) BIT::Insert(p[pre], Calc(v[pre], p[i] - p[pre] - 1));
}
}
void Modify(int p_, int v_) {
std::set <pii>::iterator it = h.lower_bound(mp(p_, num));
int suf = it->second, pre = (-- it)->second;
BIT::Insert(p[pre], Calc(v[pre], p_ - p[pre] - 1) - BIT::Query(p[pre], p[pre]));
BIT::Insert(p_, Calc(v_, p[suf] - p_ - 1));
p[++ num] = p_, v[num] = v_, id[p_] = num;
h.insert(mp(p_, num)), noth.erase(p_);
}
LL Query(int l_, int r_) {
if (id[l_]) l_ = *noth.lower_bound(l_);
if (id[r_]) {
std::set <int>::iterator it = noth.lower_bound(r_);
r_ = *(-- it);
}
if (l_ > r_) return 0ll;
int prel, prer, sufl, sufr;
std::set <pii>::iterator it = h.lower_bound(mp(l_, num));
sufl = it->second, prel = (-- it)->second;
it = h.lower_bound(mp(r_, num));
sufr = it->second, prer = (-- it)->second;
if (prel == prer) {
return Calc(v[prel], p[sufl] - l_) - Calc(v[prer], p[sufr] - (r_ + 1));
}
LL ret = BIT::Query(p[sufl], p[prer] - 1);
ret += Calc(v[prel], p[sufl] - l_);
ret += Calc(v[prer], p[sufr] - p[prer] - 1) - Calc(v[prer], p[sufr] - (r_ + 1));
return ret;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
Init();
while (q --) {
int op, x, y; std::cin >> op >> x >> y;
if (op == 1) Modify(x, y);
else std::cout << Query(x, y) << "\n";
}
return 0;
}
写在最后
学到了什么：
- E：贡献为不相交区间形式，且修改等价于将某区间一分为二，考虑整区间与散区间的贡献。