目录
写在前面
比赛地址：https://codeforces.com/contest/1935。
被精心构造的 C 的样例鲨了的一集。
妈的天使骚骚☆REBOOT完全就是他妈拔作啊我草，要是被人知道我他妈推了全线要被笑话一辈子吧、、、
A
签到。
操作偶数次，则答案仅可能为 s 或 reverse(s) + s，更长的字符串的前缀一定为二者之一，则选择这两者是最优的。
则仅需比较 s 与 reverse(s) 的字典序即可。
//
/*
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; std::cin >> n;
std::string s; std::cin >> s;
std::string t = s; std::reverse(t.begin(), t.end());
if (s <= t) std::cout << s << "\n";
else std::cout << t + s << "\n";
}
return 0;
}
B
枚举。
显然答案仅可能为 \(\operatorname{mex}_{i=1}^{n} a_i\) 或无解。
于是检查 \(\operatorname{mex}_{i=1}^{n} a_i\) 是否可以成为答案。发现若可以分成多段，则一定可以分成两段，于是仅需枚举两段互补的前缀后缀并检查它们的 \(\operatorname{mex}\) 是否为 \(\operatorname{mex}_{i=1}^{n} a_i\) 即可。
赛时写的比较傻比，先找到了最短的满足 \(\operatorname{mex} = \operatorname{mex}_{i=1}^{n} a_i\) 的前缀，然后再检查剩下的后缀是否也满足条件。
//枚举
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n, ans, a[kN];
bool yes[kN];
std::vector <std::pair <int, int> > sol;
int cntnum, nowtime, cnt[kN], tim[kN];
//=============================================================
void add(int x_) {
if (tim[x_] != nowtime) cnt[x_] = 0, tim[x_] = nowtime;
if (!cnt[x_]) ++ cntnum;
++ cnt[x_];
}
void clear() {
cntnum = 0;
++ nowtime;
}
void check(int mex_) {
int sum = 0, last = 1;
sol.clear();
for (int i = 1; i <= n; ++ i) {
if (a[i] < mex_) add(a[i]);
if (cntnum == mex_) {
++ sum;
clear();
if (sol.empty()) sol.push_back(std::make_pair(last, i)), last = i + 1;
}
}
sol.push_back(std::make_pair(last, n));
if (sum >= 2) ans = mex_;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
ans = -1;
sol.clear();
clear();
std::cin >> n;
for (int i = 0; i <= n; ++ i) yes[i] = 0;
for (int i = 1; i <= n; ++ i) {
std::cin >> a[i];
yes[a[i]] = 1;
}
for (int i = 0; i <= n; ++ i) {
if (!yes[i]) {
check(i);
break;
}
}
if (ans == -1) {
std::cout << -1 << "\n";
continue;
}
std::cout << sol.size() << "\n";
for (auto x: sol)
std::cout << x.first << " " << x.second << "\n";
}
return 0;
}
C
枚举，排序，线段树
被精心构造的 C 的样例鲨了的一集。
这个贡献的形式显然是典中典，考虑将所有元素按 \(b\) 排序然后枚举区间 \([l, r]\) 表示钦定选择了元素 \(l, r\)，使选择的元素满足后半部分贡献为 \(b_{r} - b_{l}\)，之后应在 \((l, r)\) 中再选择尽可能多的元素使总贡献不超过 \(T\)，此时仅需考虑 \(a\) 的贡献即可。
显然应当按照 \(a\) 升序选择元素，一个显然的想法是用线段树维护 \((l, r)\) 中元素的属性 \(a\)，以 \(a\) 的值为下标维护区间元素个数与区间贡献之和，然后在线段树上以上限 \(T - (b_r - b_l) - (a_r + a_l)\) 二分即可得到至多能选择元素的数量。
在枚举区间的同时维护线段树即可。注意对 \(a\) 先离散化，总时间复杂度 \(O(\sum n^2\log n)\) 级别。
有复杂度同阶的 DP 解法。
为什么想到这个？因为前天刚写了一个线段树上二分的题，直接复制过来用了哈哈
//枚举，排序，线段树
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define pii std::pair<int,int>
#define mp std::make_pair
const int kN = 2010;
//=============================================================
int n, datanum, b[kN];
pii a[kN];
LL ans, l;
//=============================================================
namespace Seg {
#define ls (now_<<1)
#define rs (now_<<1|1)
#define mid ((L_+R_)>>1)
const int kNode = kN << 2;
LL sum[kNode], cnt[kNode];
void Pushup(int now_) {
sum[now_] = sum[ls] + sum[rs];
cnt[now_] = cnt[ls] + cnt[rs];
}
void Insert(int now_, int L_, int R_, int pos_, LL sum_, LL cnt_) {
if (L_ == R_) {
sum[now_] += sum_;
cnt[now_] += cnt_;
return ;
}
if (pos_ <= mid) Insert(ls, L_, mid, pos_, sum_, cnt_);
else Insert(rs, mid + 1, R_, pos_, sum_, cnt_);
Pushup(now_);
}
LL Query(int now_, int L_, int R_, LL lim_) {
if (L_ == R_) {
return std::min(cnt[now_], lim_ / b[L_]);
}
LL sl = sum[ls], cl = cnt[ls];
if (lim_ <= sl) return Query(ls, L_, mid, lim_);
return cl + Query(rs, mid + 1, R_, lim_ - sl);
}
#undef ls
#undef rs
#undef mid
}
void Solve() {
ans = 0;
for (int i = 1; i <= n; ++ i) {
for (int j = i; j <= n; ++ j) {
LL cost = 1ll * b[a[i].second] + 1ll * (j > i) * b[a[j].second] + a[j].first - a[i].first;
if (l >= cost) {
LL c = 1 + (j > i) + Seg::Query(1, 1, datanum, l - cost);
ans = std::max(ans, c);
}
if (j > i) Seg::Insert(1, 1, datanum, a[j].second, b[a[j].second], 1);
}
for (int j = i; j <= n; ++ j) {
if (j > i) Seg::Insert(1, 1, datanum, a[j].second, -b[a[j].second], -1);
}
}
}
void Init() {
ans = 0;
std::cin >> n >> l;
for (int i = 1; i <= n; ++ i) {
int x, y; std::cin >> x >> y;
a[i] = mp(y, x);
}
std::sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++ i) b[i] = a[i].second;
std::sort(b + 1, b + n + 1);
datanum = std::unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; ++ i) {
a[i].second = std::lower_bound(b + 1, b + datanum + 1, a[i].second) - b;
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
Init();
Solve();
std::cout << ans << "\n";
}
return 0;
}
/*
1
5 100
1 1
1000 2
1000 3
1000 4
1 98
*/
D
数学，容斥
一眼题。C 实在调不出来看了一眼就会的呃呃题，五分钟过了之后继续调 C 呃呃
考虑求补集，即求多少二元组 \((x, y)(x\le y)\) 满足 \((x + y\in \{s_i\})\lor (y - x\in \{s_i\})\)。保证了 \(s_i\) 两两不同，则简单容斥下即求下列三部分二元组的数量：
- \(f_1: (x + y \in \{s_i\})\)，数量为 \(\sum_i \left\lfloor\frac{s_i}{2}\right\rfloor + 1\)。
- \(f_2: (y - x\in \{s_i\})\)，数量为 \(\sum_i c - s_i + 1\)。
- \(f_3: (x + y\in \{s_i\}) \land (y - x\in \{s_j\})\)，若二元组满足该条件，则有 \(i\not= j\) 且 \(s_i \equiv s_j \pmod 2\)，则记 \(s_i\bmod 2 = 0/1\) 的数量分别为 \(k_0, k_1\)，二元组数量为 \(\frac{k_0(k_0 + 1)}{2} + \frac{k_1(k_1 + 1)}{2}\)。
答案即为 \(\frac{c(c + 1)}{2} - f_0 - f_1 + f_2\)，复杂度 \(O\left(\sum n\right)\) 级别。
//数学，容斥
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 3e5 + 10;
//=============================================================
int n, c, s[kN];
LL ans;
//=============================================================
void Solve() {
ans = 1ll * (c + 1) * (c + 2) / 2ll;
int cnt[2] = {0, 0};
for (int i = 1; i <= n; ++ i) {
ans -= s[i] / 2ll + 1;
ans -= c - s[i] + 1;
++ cnt[s[i] % 2];
}
ans += 1ll * cnt[0] * (cnt[0] + 1ll) / 2ll;
ans += 1ll * cnt[1] * (cnt[1] + 1ll) / 2ll;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
std::cin >> n >> c;
for (int i = 1; i <= n; ++ i) std::cin >> s[i];
Solve();
std::cout << ans << "\n";
}
return 0;
}
E
位运算，贪心，线段树
好玩的按位或。
先考虑 \(\forall 1\le i\le n,\ x_i = 0\) 的情况，考虑按位贪心。设当前降序枚举到 \(i(0\le i\le 29)\) 位，记 \(c_i\) 表示 \([l, r]\) 内有多少元素的 \(y\) 此位为 1：
- \(c_i = 0\)：则此位无贡献。
- \(c_i = 1\)：贡献为 \(2^{i}\)，来自唯一的此位为 1 的数。
- \(c_i\ge 2\)：贡献为 \(2^{i} + (2^{i} - 1)\)，令 \(y\) 此位为 1 的两个元素一个取 \(y\)，一个取 \((y - 2^i) \operatorname{or} (2^{i} - 1)\) 即可，则之后所有位均有贡献，直接停止枚举即可。
当 \(x\not= 0\) 时类似，同样考虑按位贪心并考虑每位为 1 的有多少个数。\(c_i=0/1\) 的情况不受影响，然而对于 \(c_i\) 可能有 \(2^{i}-1< x\)，使对应元素无法取到 \(2^i - 1\) 影响 \(c_i\ge 2\) 的贡献。但想法还是相同的：对于 \(c_i\ge 2\) 的位，仅取其中一个保留第 \(i\) 位贡献，其他数向下调整使得某位 \(j\) 之后的所有位均有贡献。
手玩下发现满足条件的最大的 \(j\) 即为 \(x, y\) 中按照降序第一位不同的，由于 \(y>x\) 则一定有 \(y\) 第 \(j\) 位为 1，\(x\) 第 \(j\) 位为 0，则此时该元素可取到 \((y - 2^j) \operatorname{or} (2^j - 1) \ge x\)，使 \(j\) 位之后的贡献均为 1——感觉和特殊情况很类似？
于是考虑先预处理出每个元素的 \(x, y\) 中按照降序第一位不同的位 \(j\)，发现每个元素 \(j\) 位之前的部分一定可以贡献到答案中，于是先将这部分提取出来线段树维护区间按位或；对于 \(j\) 位及之后的部分 \(y\operatorname{and} (2^{j+1} - 1)\)，此时相当于 \(x'=0, y' = y\operatorname{and} (2^{j+1} - 1)\) 的对 \(x'\) 无限制的情况，可以套用一开始的特殊情况。
总时间复杂度 \(O\left((n + m)\left(\log n + \log v\right)\right)\) 级别。
//位运算，贪心，线段树
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, m, must[kN], cnt[31][kN];
//=============================================================
namespace Seg {
#define ls (now_<<1)
#define rs (now_<<1|1)
#define mid ((L_+R_)>>1)
const int kNode = kN << 2;
int t[kNode];
void Pushup(int now_) {
t[now_] = t[ls] | t[rs];
}
void Build(int now_, int L_, int R_) {
if (L_ == R_) {
t[now_] = must[L_];
return ;
}
Build(ls, L_, mid), Build(rs, mid + 1, R_);
Pushup(now_);
}
int Query(int now_, int L_, int R_, int l_, int r_) {
if (l_ <= L_ && R_ <= r_) return t[now_];
int ret = 0;
if (l_ <= mid) ret |= Query(ls, L_, mid, l_, r_);
if (r_ > mid) ret |= Query(rs, mid + 1, R_, l_, r_);
return ret;
}
#undef ls
#undef rs
#undef mid
}
void Init() {
std::cin >> n;
for (int i = 1; i <= n; ++ i) {
int x, y; std::cin >> x >> y;
for (int j = 29; j >= 0; -- j) {
cnt[j][i] = cnt[j][i - 1];
}
if (x == y) {
must[i] = x;
} else {
int val = (1 << ((int) log2(x ^ y) + 1)) - 1;
must[i] = y - (y & val);
val = y & val;
for (int j = 29; j >= 0; -- j) {
cnt[j][i] += ((val >> j & 1) > 0);
}
}
}
Seg::Build(1, 1, n);
}
int Query(int l_, int r_) {
int ans = Seg::Query(1, 1, n, l_, r_);
for (int i = 29; i >= 0; -- i) {
int c = cnt[i][r_] - cnt[i][l_ - 1] + (ans >> i & 1);
if (c > 1) {
ans |= (1 << (i + 1)) - 1;
} else if (c == 1) {
ans |= (1 << i);
}
}
return ans;
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
Init();
for (int i = 1; i <= n; ++ i) std::cout << must[i] << "\n";
std::cin >> m;
while (m --) {
int l_, r_; std::cin >> l_ >> r_;
std::cout << Query(l_, r_) << " ";
}
std::cout << "\n";
}
return 0;
}
/*
1
1
2 2
1
1 1
*/
写在最后
学到了什么：
- B：区间 $\operatorname{mex}\le $ 全局 \(\operatorname{mex}\)。
- E：提取贡献，转化为特殊情况。