从这里开始
小结
这场比赛和同学一起打。本来应该是很开心的事情，结果留下好多遗憾。
第一个遗憾是没能在20分钟内消灭A、B题。然后分数就不是很可观。
我第一次交B题都20多分钟了。然后朋友们说我的贪心有锅，然后我就真信了。
于是我就重新写了个贪心交一发。好玩的是，考完我重新交了下B题之前的程序A了。
C、D题做得比较快，因为比较简单。（想吐槽一句。为什么cf div 2前4题只有普及组难度了？）
E题是最好玩的。读完题，写出了dp式子，我觉得会和按$c$分段有关，然后ZJC表示我在搞笑，我怎么又信了？
然后思路就被带偏了。然后写暴力dp打表找决策单调性，然而写挂了，样例都挂，然后就弃疗了。
比赛最后10分钟，红太阳QJX表示她A掉了E题，转移不是长度为1就是$c$。剩下的人全部在试图hack这个做法。（为什这个时候我就不信了qwq）
看到Doggu的一个朋友1小时A掉5道题，最后一题直接弃坑。我的内心是崩溃的。
主要还是A、B题做得太慢了吧。真正有意思的题目到后面都没时间思考。
综上所述，还是我太菜了。
-->
Codeforces 940A Points on the line
题目大意
定义一个可重集的距离是它中间最大的两个数之间的差，特殊地，只有一个元素的可重集的距离为0。
给定一个可重集，问最少删掉多少个数使得它的距离小于等于d。
排序后单调指针扫，或者直接开桶计数。
Code
/**
* Codeforces
* Problem#940A
* Accepted
* Time: 15ms
* Memory: 2000k
*/
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean; int n, d;
int res;
int* ar; inline void init() {
scanf("%d%d", &n, &d);
ar = new int[(n + )];
for (int i = ; i <= n; i++)
scanf("%d", ar + i);
} inline void solve() {
sort (ar + , ar + n + );
int r = ;
res = n - ;
for (int i = ; i <= n; i++) {
while (r < n && ar[r + ] - ar[i] <= d) r++;
res = min(res, i + (n - r) - );
}
printf("%d", res);
} int main() {
init();
solve();
return ;
}
Problem A
Codeforces 940B Our Tanya is Crying Out Loud
题目大意
给定一个数$n$和$k$。你有两个操作可以进行
- 将$n$减去1，花费$a$。
- 当$n$是$k$的倍数的时候，将$n$除以$k$，花费$b$。
问将$n$变为1的最小花费
当 $k = 1$ 的时候特判。
当$n$为$k$的倍数的时候，比较直接除和直接减到$\frac{n}{k}$的花费，如果前者更优就除，否则直接减到1。
当$n$不为$k$的倍数的时候，直接减到$\left \lfloor\frac{n}{k} \right \rfloor k$。
考虑如果在 $ik$ 的决策不是减到 $i$ 或者直接除 $k$ 得到 $i$，那么考虑一定是做了若干次减法操作得到 $p$ 然后再除以 $k$ 得到 $x$。不难证明先除以 $k$ 得到 $l$，再做若干次减法操作得到 $x$ 不会更劣。
考虑这么做的正确性，唯一这么做的问题是会不会存在多减几次使答案更优的情况。
答案是不会的，因为先除可以避免使用多次的减法（除更优的情况下）。
举个例子来说明，将$k^{2} + k$变为1。
方案1：$k ^ {2} + k \rightarrow k + 1 \rightarrow k \rightarrow 1$
方案2：$k ^ {2} + k \rightarrow k^{2} \rightarrow k \rightarrow 1$
方案1使用了1次加法和2次除法，而方案二使用了$k$次加法和2次除法。
-->
Code
/**
* Codeforces
* Problem#940B
* Accepted
* Time: 30ms
* Memory: 2000k
*/
#include <bits/stdc++.h>
#ifndef WIN32
#define Auto "%lld"
#else
#define Auto "%I64d"
#endif
using namespace std; #define ll long long ll n, k, a, b, res = ; inline void init() {
scanf(Auto""Auto""Auto""Auto, &n, &k, &a, &b);
} inline void solve() {
if (k == ) {
res = (n - ) * a;
} else {
while (n != ) {
if (n < k) {
res += (n - ) * a;
break;
} else {
res += min((n % k) * a + b, (n - n / k) * a);
n /= k;
}
}
}
printf(Auto"\n", res);
} int main() {
init();
solve();
return ;
}
Problem B
Codeforces 940C Phone Numbers
题目大意
给定一个由小写字母组成且长度为$n$的字符串$s$，要求输出一个字符串$t$，满足：
- $t$中出现的字符在$s$中也出现过
- 它的长度为$k$
- $t$的字典序大于$s$
- 在满足上述条件的所有串中，是字典序最小的一个
题目保证存在解。
当$k > n$时，直接输出字符串$s$，再补上$s$中最小的字符。
否则找到$s$中从第$k$个字符往前找第一个不是最大的字符，把它变为略比它的字符。
然后后面的补最小的字符。
Code
/**
* Codeforces
* Problem#940C
* Accepted
* Time: 31ms
* Memory: 2100k
*/
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean; int n, k;
int mi = , ma = ;
boolean exist[];
char str[]; inline void init() {
scanf("%d%d", &n, &k);
memset(exist, false, sizeof(exist));
scanf("%s", str + );
} inline void solve() {
for (int i = ; i <= n; i++)
exist[str[i] - 'a'] = true;
for (mi = ; !exist[mi]; mi++);
for (ma = ; !exist[ma]; ma--);
if (n < k) {
printf("%s", str + );
for (int i = n + ; i <= k; i++)
putchar(mi + 'a');
return;
}
int p;
for (p = k; p && str[p] == ma + 'a'; p--);
str[p]++;
while (!exist[str[p] - 'a'])
str[p]++;
for (p = p + ; p <= k; p++)
str[p] = mi + 'a';
str[k + ] = ;
puts(str + );
} int main() {
init();
solve();
return ;
}
Problem C
Codeforces 940D Alena And The Heater
题目大意
给定一个数组$a$，和一个01串$b$，$b$按照如下方式生成（请自行阅读英文）
请你找出一组合法的$l, r$，保证输入存在解。
发现生成方式比较特殊。
于是根据生成方式更新$l, r$即可。
Code
/**
* Codeforces
* Problem#940D
* Accepted
* Time: 31ms
* Memory: 2500k
*/
#include <bits/stdc++.h>
using namespace std; int n;
int a[];
char b[]; inline void init() {
scanf("%d", &n);
for (int i = ; i <= n; i++)
scanf("%d", a + i);
scanf("%s", b + );
} char sameNumber(int p) {
char x = b[p - ];
for (int i = ; i <= ; i++)
if (b[p - i] != x)
return '';
return x;
} int l = -1e9, r = 1e9; inline void solve() {
for (int i = ; i <= n; i++) {
char c = sameNumber(i);
if (c == '') continue;
if (c == b[i]) continue;
if (c == '') {
for (int j = ; j <= ; j++)
r = min(r, a[i - j] - );
} else {
for (int j = ; j <= ; j++)
l = max(l, a[i - j] + );
}
}
printf("%d %d", l, r);
} int main() {
init();
solve();
return ;
}
Problem D
Codeforces 940E Cashback
题目大意
给定一个长度为$n$的数组和常数$c$，要求你对它进行划分。划分长度为$k$一段的代价是其中所有除去前$\left \lfloor \frac{k}{c} \right \rfloor$小的数的和。定义一个划分的代价是划分的所有段的代价的和。
问最小的代价和。
一段代价可以表示为这一段的和减去前$\left \lfloor \frac{k}{c} \right \rfloor$小的数的和。
那么考虑两段连续的长度为$c$的合并到一起，这样会使得前2小的和变小。所以划分的最长的长度不会超过$2c - 1$
那么考虑长度在$c + 1$和$2c - 1$之间的段。我只需要留一个长度为$c$的段，把它和剩下的分开。这样看的话，划分的一段的长度不会超过$c$。
继续考虑长度小于$c$的段，它的代价直接就是它中间的元素的和。因此可以直接把它分成一些只有1个元素的段。
因此存在一种最优方案满足划分的每一段长度不是1就是$c$。
因此我只用维护连续$c$个元素的最小值，以及它们的和。
于是上单调队列。
时间复杂度$O(n)$。
Code
/**
* Codeforces
* Problem#940E
* Accepted
* Time: 31ms
* Memory: 3700k
*/
#include <bits/stdc++.h>
#ifndef WIN32
#define Auto "%lld"
#else
#define Auto "%I64d"
#endif
using namespace std; #define ll long long const int N = ; int n, c;
int st = , ed = ;
ll f[N];
int ar[N];
int que[N]; inline void init() {
scanf("%d%d", &n, &c);
for (int i = ; i <= n; i++)
scanf("%d", ar + i);
} inline void solve() { f[] = ;
ll sum = ;
for (int i = ; i <= n; i++) {
while (ed >= st && ar[que[ed]] >= ar[i]) ed--;
que[++ed] = i;
f[i] = f[i - ] + ar[i];
sum += ar[i];
while (ed >= st && que[st] <= i - c) st++;
if (i >= c)
sum -= ar[i - c], f[i] = min(f[i], f[i - c] + sum - ar[que[st]]);
} printf(Auto"\n", f[n]);
} int main() {
init();
solve();
return ;
}
Problem E
Codeforces 940F Machine Learning
题目大意
给定一个长度为$n$的数组，要求支持两个操作：
- 询问一个区间中所有数的出现次数组成的集合的mex。
- 修改一个位置上的数。
一个可重集合的mex是这个可重集合中最小的不存在的非负整数。
这种毒瘤题？我也不会做。那就直接莫队好了。
什么？要修改？那就带修莫队好了。
唯一的问题是如何求一个集合的mex？
考虑是出现次数，所以答案不会超过500（因为$C_{500}^{2}= \frac{500 \times 499}{2}>10^{5}$），超过500次的出现次数直接扔，查询操作暴力for。
时间复杂度$O\left(n^{\frac{5}{3}}\right)$
Code
/**
* Codeforces
* Problem#940F
* Accepted
* Time: 1872ms
* Memory: 11700k
*/
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean; #define pii pair<int, int>
#define fi first
#define sc second const int cs3 = , cs2 = ; typedef class Query {
public:
int l, r, t;
int id; Query(int l = , int r = , int t = , int id = ):l(l), r(r), t(t), id(id) { } boolean operator < (Query b) const {
if (l / cs3 != b.l / cs3) return l < b.l;
if (r / cs3 != b.r / cs3) return r < b.r;
return t < b.t;
}
}Query; int n, m;
int cm = , cq = , cd = ;
int* ar;
Query* qs;
pii *ops;
int cnt[];
int exist[];
int cover[cs2];
int *res;
map<int, int> mp; int alloc(int x) {
if (mp.count(x)) return mp[x];
return mp[x] = ++cd;
} inline void init() {
scanf("%d%d", &n, &m);
ar = new int[(n + )];
ops = new pii[(m + )];
qs = new Query[(m + )];
res = new int[(m + )];
for (int i = ; i <= n; i++)
scanf("%d", ar + i), ar[i] = alloc(ar[i]);
for (int i = , opt, l, r; i <= m; i++) {
scanf("%d%d%d", &opt, &l, &r);
if (opt == )
++cq, qs[cq] = Query(l, r, cm, cq);
else
r = alloc(r), ops[++cm] = pii(l, r);
}
exist[] = , cover[] = ;
} inline void update(int x, int sign) {
if (!exist[x] && sign == ) cover[x / cs2]++;
exist[x] += sign;
if (!exist[x] && sign == -)cover[x / cs2]--;
} inline void updatec(int p, int sign) {
int x = ar[p];
update(cnt[x], -);
cnt[x] += sign;
update(cnt[x], );
} inline void update(int op, int l, int r) {
int p = ops[op].fi;
if (l <= p && p <= r)
updatec(p, -);
swap(ar[p], ops[op].sc);
if (l <= p && p <= r)
updatec(p, );
} inline void solve() {
sort(qs + , qs + cq + );
int mdzzl = , mdzzr = , mdzzt = ;
for (int i = ; i <= cq; i++) {
while (mdzzr < qs[i].r) updatec(++mdzzr, );
while (mdzzr > qs[i].r) updatec(mdzzr--, -);
while (mdzzl < qs[i].l) updatec(mdzzl++, -);
while (mdzzl > qs[i].l) updatec(--mdzzl, );
while (mdzzt < qs[i].t) update(++mdzzt, mdzzl, mdzzr);
while (mdzzt > qs[i].t) update(mdzzt--, mdzzl, mdzzr); for (int j = ; j < cs2; j++) {
if (cover[j] < cs2) {
int k = j * cs2;
while (exist[k]) k++;
res[qs[i].id] = k;
break;
}
}
} for (int i = ; i <= cq; i++)
printf("%d\n", res[i]);
} int main() {
init();
solve();
return ;
}
Problem F