写在前面
比赛地址：https://codeforces.com/contest/1884
oonp 这场 div2 怎么才 2k5 人打啊我草
里面还不知道多少大神的小号，呃呃
打了 1k3 掉了 75 分也是牛逼
A
考虑如何拼出一个长度为 \(n-k\) 的回文串，先一对一对地拼，再看需不需要再顶上去一个单的即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, k, cnt[30];
char s[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read(), k = read();
scanf("%s", s + 1);
int r = n - k;
for (int i = 0; i < 26; ++ i) cnt[i] = 0;
for (int i = 1; i <= n; ++ i) cnt[s[i] - 'a'] ++;
for (int i = 0; i < 26; ++ i) {
while (r >= 2 && cnt[i] >= 2) r -= 2, cnt[i] -= 2;
}
for (int i = 0; i < 26; ++ i) {
if (r == 1 && cnt[i] >= 1) -- r;
}
printf("%s\n", r ? "NO" : "YES");
}
return 0;
}
B
发现 \(2\le k\le 5\)，懒得多想了，于是直接无脑大力特判。
见代码吧。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, k, a[kN];
int cnt[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Solve2() {
int r = 1;
for (int i = 1; i <= n; ++ i) {
a[i] = read();
r = r * a[i] % 2;
}
printf("%d\n", (r == 1));
}
void Solve3() {
for (int i = 1; i <= n; ++ i) {
a[i] = read();
cnt[a[i] % 3] ++;
}
if (cnt[0]) printf("0\n");
else if (cnt[2]) printf("1\n");
else if (cnt[1]) printf("2\n");
}
void Solve4() {
for (int i = 1; i <= n; ++ i) {
a[i] = read();
cnt[a[i] % 4] ++;
}
if (cnt[0] || cnt[2] >= 2) printf("0\n");
else if (cnt[3]) printf("1\n");
else if (n >= 2 && cnt[2] >= 1) printf("1\n");
else if (n == 1 && cnt[2] == 1) printf("2\n");
else if (n == 1 && cnt[1] == 1) printf("3\n");
else printf("2\n");
}
void Solve5() {
for (int i = 1; i <= n; ++ i) {
a[i] = read();
cnt[a[i] % 5] ++;
}
if (cnt[0]) printf("0\n");
else if (cnt[4]) printf("1\n");
else if (cnt[3]) printf("2\n");
else if (cnt[2]) printf("3\n");
else if (cnt[1]) printf("4\n");
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read(), k = read();
for (int i = 0; i <= 10; ++ i) cnt[i] = 0;
// printf("-------");
if (k == 2) Solve2();
if (k == 3) Solve3();
if (k == 4) Solve4();
if (k == 5) Solve5();
}
return 0;
}
C
我的想法可能比较奇怪呃呃
首先考虑求补集，求不合法区间数量。记权值 \(i\) 的出现位置为 \(p_i = \{ p_{i, 1}, p_{i, 2}, \dots, p_{i, k} \}\) 手玩之后发现以 \(p_{i, 1}\sim p_{i, k-1}\) 为右端点的区间一定不合法，以 \(p_{i, 2}\sim p_{i, k}\) 为左端点的区间一定不合法。又发现考虑上述区间一定可以覆盖所有不合法区间，于是仅需考虑减去左右端点均为上述位置，即 \([p_{j, \dots}, p_{k, \dots}]\) 型的区间的贡献。
考虑枚举权值的同时维护两个树状数组，维护某个位置是否作为左端点/右端点被统计了贡献，然后在枚举每种权值的上述两种出现位置的同时使用树状数组求对应的端点数量即可。
总时间复杂度 \(O(n\log n)\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n, idnum, a[kN];
std::map <int, int> id;
std::vector <int> pos[kN], val;
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
namespace BIT1 {
#define lowbit(x) ((x)&(-x))
const int kL = kN;
int t, lim, time[kN];
LL f[kN];
void Init(int n_) {
++ t;
lim = n_;
}
void Insert(int pos_, int val_) {
for (int i = pos_; i <= lim; i += lowbit(i)) {
if (time[i] != t) time[i] = t, f[i] = 0;
f[i] += val_;
}
}
LL Sum(int pos_) {
LL ret = 0;
for (int i = pos_; i; i -= lowbit(i)) {
if (time[i] != t) time[i] = t, f[i] = 0;
ret += f[i];
}
return ret;
}
LL Query(int l_, int r_) {
return Sum(r_) - Sum(l_ - 1);
}
#undef lowbit
}
namespace BIT2 {
#define lowbit(x) ((x)&(-x))
const int kL = kN;
int t, lim, time[kN];
LL f[kN];
void Init(int n_) {
++ t;
lim = n_;
}
void Insert(int pos_, int val_) {
for (int i = pos_; i <= lim; i += lowbit(i)) {
if (time[i] != t) time[i] = t, f[i] = 0;
f[i] += val_;
}
}
LL Sum(int pos_) {
LL ret = 0;
for (int i = pos_; i; i -= lowbit(i)) {
if (time[i] != t) time[i] = t, f[i] = 0;
ret += f[i];
}
return ret;
}
LL Query(int l_, int r_) {
return Sum(r_) - Sum(l_ - 1);
}
#undef lowbit
}
void Init() {
n = read();
BIT1::Init(n), BIT2::Init(n);
for (int i = 1; i <= n; ++ i) pos[i].clear();
val.clear();
id.clear();
idnum = 0;
for (int i = 1; i <= n; ++ i) {
a[i] = read();
if (!id.count(a[i])) id[a[i]] = ++ idnum, val.push_back(a[i]);
pos[id[a[i]]].push_back(i);
}
}
void Solve() {
LL ans = 1ll * n * (n + 1) / 2ll;
for (auto x: val) {
if (pos[id[x]].size() == 1) continue;
for (int i = 0, sz = pos[id[x]].size(); i < sz - 1; ++ i) {
int p = pos[id[x]][i];
ans -= p - BIT1::Query(1, p);
BIT2::Insert(p, 1);
}
for (int i = pos[id[x]].size() - 1; i >= 1; -- i) {
int p = pos[id[x]][i];
ans -= (n - p + 1) - BIT2::Query(p, n);
BIT1::Insert(p, 1);
}
// ans -= s - BIT2::Query(s, n);
}
printf("%lld\n", ans);
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
Init();
Solve();
}
return 0;
}
D1/D2
先手玩下这个游戏。当 \(a, b\) 确定时，发现最优的策略是先分别对 \(a, b\) 排序，每轮删掉 \(a\) 中最大的和 \(b\) 中最小的。对于排序后的两个数组，记 \(p_i = \min_{b_j >a_i} j\)，特别地若这样的 \(j\) 不存在则 \(p_i=n+1\)，手玩下可以发现某轮游戏的答案即 \(\max p_i\)。
于是 D1 就是傻逼题了，排序后再 \(O(n)\) 地模拟上述过程即可。
再考虑 \(m\not= 1\) 的情况。记 \(f(k)\) 表示当 \(a_1 = k\) 时某轮游戏的答案。手玩下发现当 \(k\) 很大时仅有 \(f(k) = f(1) + 1\)，考虑实际意义即插入了一个很大的数使得原来的 \(\max p_i\) 对应的位置 \(i\) 左移了一位从而使 \(\max p_i\) 增大了 1。于是猜测不同游戏的答案仅与是否影响了这个位置有关，且 \(k\) 越大越有可能影响，于是猜测存在一个阈值 \(K\) 使得：
\[\begin{cases}
f(k) = f(1) &k \le K\\
f(k) = f(1) + 1 &k > K
\end{cases}\]
可以通过二分+重复 D1 中的模拟来求得 \(K\)，答案即 \(K\times f(1) + (m - K)\times (f(1) + 1)\)。
总时间复杂度 \(O(n\log n\log m)\) 级别。
有更牛逼的找阈值的不用二分的做法但是懒了，就这样吧。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n, m, oria[kN], orib[kN], a[kN], b[kN];
int maxp;
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Init() {
n = read(), m = read();
for (int i = 2; i <= n; ++ i) oria[i] = read();
for (int i = 1; i <= n; ++ i) b[i] = read();
std::sort(b + 1, b + n + 1);
}
int Solve(int val_) {
a[1] = val_;
for (int i = 2; i <= n; ++ i) a[i] = oria[i];
std::sort(a + 1, a + n + 1);
maxp = 0;
for (int p = 1, q = 1; p <= n; ++ p) {
while (a[p] >= b[q] && q <= n) ++ q;
maxp = std::max(maxp, q - p);
}
return maxp;
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
Init();
int f = Solve(1), pos = m;
for (int l = 1, r = m; l <= r; ) {
int mid = (l + r) >> 1;
if (Solve(mid) == f) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
printf("%lld\n", 1ll * pos * f + 1ll * (m - pos) * (f + 1));
}
return 0;
}
E
写在最后
学到了什么：
- D：阈值