Codeforces Round #466 (Div. 2) 题解
A.Points on the line
题目大意：
给你一个数列，定义数列的权值为最大值减去最小值，问最少删除几个数，使得数列的权值小于等于给定值d
题解：
排序，每次挑最大的和最小的，看看最小的能跟多少个数差\(>d\)，看看最大的能跟多少个数差\(>d\)，取个数大的那个删除。复杂度\(n^2 + n\log n\)
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define abs(x) ((x) < 0 ? -1 * (x) : (x))
template <class T>
inline void swap(T &x, T &y)
{
T tmp = x;x = y, y = tmp;
}
template <class T>
inline void read(T &x)
{
x = 0;char ch = getchar(), c = ch;
while(ch < '0' || ch > '9') c = ch, ch = getchar();
while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();
if(c == '-') x = -x;
}
const int INF = 0x3f3f3f3f;
const int MAXN = 100 + 10;
int n,d,num[MAXN];
int main()
{
// freopen("data.txt", "r", stdin);
read(n), read(d);
for(int i = 1;i <= n;++ i) read(num[i]);
std::sort(num + 1, num + 1 + n);
int l = 1, r = n, ans = 0;
while(l <= r)
{
int tmp1 = r, tmp2;
while(num[tmp1] - num[l] > d) -- tmp1;
tmp2 = r - tmp1;
int tmp3 = l, tmp4;
while(num[r] - num[tmp3] > d) ++ tmp3;
tmp4 = tmp3 - l;
if(tmp2 == 0 && tmp4 == 0) break;
if(tmp2 >= tmp4) ++ l;
else -- r;
++ ans;
}
printf("%d", ans);
return 0;
}
B.Our Tanya is Crying Out Loud
题目大意：
给你一个数\(n\)，可以对它指向两种操作。第一种操作令\(n\)减去\(1\)，花费\(A\)；第二种操作，当且仅当\(n\)为\(k\)的倍数时可以执行，使得\(n /= k\)，花费\(B\)，求让\(n\)变为\(1\)的最小花费
题解：
直接模拟即可，如果不是\(k\)的倍数就暴力减到\(k\)的倍数；如果是\(k\)的倍数，看是\(\div k\)优还是一步一步\(-1\)到\(\frac{n}{k}\)优即可。复杂度\(\log_kn\)，注意特判\(k = 1\)的情况。因为脑残\(fst\)掉了。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define abs(x) ((x) < 0 ? -1 * (x) : (x))
template <class T>
inline void swap(T &x, T &y)
{
T tmp = x;x = y, y = tmp;
}
template <class T>
inline void read(T &x)
{
x = 0;char ch = getchar(), c = ch;
while(ch < '0' || ch > '9') c = ch, ch = getchar();
while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();
if(c == '-') x = -x;
}
const long long INF = 0x3f3f3f3f;
long long n,k,a,b;
int main()
{
// freopen("data.txt", "r", stdin);
read(n), read(k), read(a), read(b);
if(k == 1) printf("%I64d", (n - 1) * a);
else
{
long long ans = 0;
while(n > 1)
{
if(n % k == 0)
{
if(b < (n - n/k) * a) ans += b, n /= k;
else ans += (n - n/k) * a, n /= k;
}
else
{
if(n - n%k > 1) ans += a * (n%k), n -= n%k;
else ans += a * (n % k - 1), n = 1;
}
}
printf("%I64d", ans);
}
return 0;
}
C. Phone Numbers
题目大意：
给你一个长度为\(n\)字符串，要求你用字符串里的字符拼凑出一个字典序最小的比该字符串字典序大的长度为\(k\)字符串
题解：
贪心即可。若\(n < k\)，直接输出原串，并在末尾加字典序最小的字符；若\(n>=k\)，从给的字符串第\(k\)位往前扫，尝试某一位换位字典序比他大的字符里字典序最小的哪一个，如果能换，那么就换掉，后面的用字典序最小的字符填满\(k\)位，就是答案
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define abs(x) ((x) < 0 ? -1 * (x) : (x))
template <class T>
inline void swap(T &x, T &y)
{
T tmp = x;x = y, y = tmp;
}
template <class T>
inline void read(T &x)
{
x = 0;char ch = getchar(), c = ch;
while(ch < '0' || ch > '9') c = ch, ch = getchar();
while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();
if(c == '-') x = -x;
}
const int INF = 0x3f3f3f3f;
const int MAXN = 100000 + 10;
char s[MAXN];
int n,k;
int a[30],tot,b[30], nxt[30];
int main()
{
// freopen("data.txt", "r", stdin);
read(n), read(k);
scanf("%s", s + 1);
for(int i = 1;i <= n;++ i)
if(!b[s[i] - 'a' + 1])
b[s[i] - 'a' + 1] = ++ tot, a[tot] = s[i] - 'a' + 1;
std::sort(a + 1, a + 1 + tot);
for(int i = 1;i <= tot;++ i)
nxt[a[i]] = a[i + 1];
if(k <= n)
{
for(int i = k;i >= 1;-- i)
{
if(nxt[s[i] - 'a' + 1])
{
for(int j = 1;j < i;++ j) printf("%c", s[j]);
printf("%c", nxt[s[i] - 'a' + 1] + 'a' - 1);
for(int j = i + 1;j <= k;++ j) printf("%c", a[1] + 'a' - 1);
return 0;
}
}
}
else
{
printf("%s", s + 1);
for(int i = n + 1;i <= k;++ i) printf("%c", a[1] + 'a' - 1);
}
return 0;
}
D. Alena And The Heater
题目大意：
给你两个长度均为\(n\)的数列\(a\)和\(b\)，要求找到任意一组\(l\),\(r\),对于任意\(5 <= i <= n\),满足:
\(b_i = 0\),如果\(a_i, a_{i-1}, a_{i-2}, a_{i-3}, a_{i-4} > r\)并且\(b_{i-1}=b_{i-2}=b_{i-3}=b_{i-4}=1\)
\(b_i = 1\),如果\(a_i, a_{i-1}, a_{i-2}, a_{i-3}, a_{i-4} < l\)并且\(b_{i-1}=b_{i-2}=b_{i-3}=b_{i-4}=0\)
其余情况\(b_i = b_{i-1}\)
题解：
如果\(b_{i-1}=b_{i-2}=b_{i-3}=b_{i-4}=1\)
如果\(b_i = 0\) 那么 \(a_i, a_{i-1}, a_{i-2}, a_{i-3}, a_{i-4} > r\)
如果\(b_i = 1\) 那么 \(a_i, a_{i-1}, a_{i-2}, a_{i-3}, a_{i-4} \leq\ r\)
如果\(b_{i-1} = b_{i-2} = b_{i-3} = b_{i-4} = 0\)
如果\(b_i = 0\) 那么 \(a_i, a_{i-1}, a_{i-2}, a_{i-3}, a_{i-4} \geq\ r\)
如果\(b_i = 1\) 那么 \(a_i, a_{i-1}, a_{i-2}, a_{i-3}, a_{i-4} < l\)
于是可以把l = -INF，r = INF，往里缩小，由于答案一定存在，我们只需让\(a_i, a_{i-1}, a_{i-2}, a_{i-3}, a_{i-4} > r\)的条件令\(r = min(a_i + 1, a_{i-1} + 1, a_{i-2} + 1, a_{i-3} + 1, a_{i-4} + 1)\)，即满足条件的最小值，这样由于答案存在，也就一定能满足所有的\(b_i = 1\) 那么 \(a_i, a_{i-1}, a_{i-2}, a_{i-3}, a_{i-4} \leq\ r\)。l同理。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define abs(x) ((x) < 0 ? -1 * (x) : (x))
template <class T>
inline void swap(T &x, T &y)
{
T tmp = x;x = y, y = tmp;
}
template <class T>
inline void read(T &x)
{
x = 0;char ch = getchar(), c = ch;
while(ch < '0' || ch > '9') c = ch, ch = getchar();
while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();
if(c == '-') x = -x;
}
const long long INF = 1000000000;
const long long MAXN = 1000000 + 10;
/*
如果bi-1 = bi-2 = bi-3 = bi-4 = 1
如果bi = 0 那么 ai,ai-1,ai-2,ai-3,ai-4 > r
如果bi = 1 那么 ai,ai-1,ai-2,ai-3,ai-4 <= r
如果bi-1 = bi-2 = bi-3 = bi-4 = 0
如果bi = 0 那么 ai,ai-1,ai-2,ai-3,ai-4 >= l
如果bi = 1 那么 ai,ai-1,ai-2,ai-3,ai-4 < l
*/
long long l = - INF, r = INF, n, a[MAXN], b[MAXN];
char s[MAXN];
int main()
{
freopen("data.txt", "r", stdin);
read(n);
for(long long i = 1;i <= n;++ i) read(a[i]);
scanf("%s", s + 1);
for(long long i = 1;i <= n;++ i) b[i] = s[i] - '0';
for(long long i = 5;i <= n;++ i)
{
if(b[i - 1] && b[i - 2] && b[i - 3] && b[i - 4])
{
if(!b[i])
r = min(r, min(a[i - 1] - 1, min(a[i - 2] - 1, min(a[i - 3] - 1, min(a[i - 4] - 1, a[i] - 1)))));
}
else if(!b[i - 1] && !b[i - 2] && !b[i - 3] && !b[i - 4])
{
if(b[i])
l = max(l, max(a[i - 1] + 1, max(a[i - 2] + 1, max(a[i - 3] + 1, max(a[i - 4] + 1, a[i] + 1)))));
}
}
printf("%I64d %I64d\n", l, r);
return 0;
}
E
题目大意：
给你一个数列和正数\(c\)，你可以把它分成很多段，每个长度为\(l\)的段将会删除前\(\lfloor\frac{l}{c}\rfloor\)小的数，求一种划分，使得划分并删除数字后剩余数字的和最小。
题解：
首先是一个显而易见的套路\(DP\).
\(dp[i]\)表示到i的最小和，\(dp[i] = min(dp[i], dp[i - k] + calc(i - k + 1, i))\);
\(calc(l,r)\)表示\([l,r]\)单独分为一段，删除数后的和
然后就GG了。
想了两分钟想不动了，翻了翻别人的代码。。
cnm。。。
早知道再想想了。。。
首先考虑一个最优解，每一个最优解中\(kc + r\),\(k \geq 1\), \(1 \leq r < c\)长度的区间，等价于划分为一个\(kc\)长度的区间和一个\(r\)长度的区间。因为对于区间\([l, l + kc + r - 1]\),前\(k\)小的数一定在区间\([l, l + kc - 1]\)中。
为什么？反证法即可。如果有被删除的数存在于后面的区间\([l + kc, l + kc + r - 1]\)中，那么把区间\([l, l + kc + r - 1 ]\)重新划分成\([l, l + kc - 1]\)和\([l + kc, l + kc + r - 1]\)，不会选\([l + kc, l + kc + r - 1]\)中原来被删除的数，而会删除\([l, l + kc - 1]\)中比原来被删除的数更大的数，答案更优。
接下来考虑每一个\(kc\),\(k > 1\)的区间
把它分为\(k\)个长度为\(c\)的区间，会发现每个区间都有一个在大区间里被删除的数，而且这个数也是小区间内该被删除的数
为什么？反证法即可，跟上面思路类似。如果大区间选的两个数在同一个长度为\(c\)的小区间里，鸽巢原理会导致一个区间空着，空着的那个区间删的数肯定比小区间的数大（否则就会被在大区间里被选了），那这种划分显然不是最优的。
于是可以发现，只需要\(c\)长度的区间就行了！问题转化为从一个数列里选一些长度为\(c\)的小区间，删掉里面最小的数。\(DP\)方程可以这样写：
\(dp[i] = min(dp[i - 1], dp[i - c] + sum[i] - sum[i - c] - min(i - c + 1, i))\)
\(min(i - c + 1, i)\)表示区间\([i - c + 1, i]\)的最小值
sgt或st表或单调队列维护即可
但是为了方便，我代码里的\(dp\)不是这么写的。。
\(dp[i]\)表示到i为止的最优化分，删除的数字的最大和
\(dp[i] = max(dp[i-1], di[i-c] + min(i - c + 1, i))\)
最后用总和减去即可
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#define max(a, b) ((a) > (b) ? (a) : (b))
//#define min(a, b) ((a) < (b) ? (a) : (b))
#define abs(x) ((x) < 0 ? -1 * (x) : (x))
inline long long min(long long a, long long b)
{
return a < b ? a : b;
}
template <class T>
inline void swap(T &x, T &y)
{
T tmp = x;x = y, y = tmp;
}
template <class T>
inline void read(T &x)
{
x = 0;char ch = getchar(), c = ch;
while(ch < '0' || ch > '9') c = ch, ch = getchar();
while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();
if(c == '-') x = -x;
}
const long long INF = 0x3f3f3f3f3f3f3f3f;
const long long MAXN = 400000 + 10;
long long mi[MAXN << 2], n, c, a[MAXN], dp[MAXN], sum, ans;
void build(long long o = 1, long long l = 1, long long r = n)
{
if(l == r)
{
mi[o] = a[l];return;
}
long long mid = (l + r) >> 1;
build(o << 1, l, mid);
build(o << 1 | 1, mid + 1, r);
mi[o] = min(mi[o << 1], mi[o << 1 | 1]);
}
long long ask(long long ll, long long rr, long long o = 1, long long l = 1, long long r = n)
{
if(ll <= l && rr >= r) return mi[o];
long long mid = (l + r) >> 1, re = INF;
if(mid >= ll) re = ask(ll, rr, o << 1, l, mid);
if(mid < rr) re = min(re, ask(ll, rr, o << 1 | 1, mid + 1, r));
return re;
}
int main()
{
//freopen("data.txt", "r", stdin);
read(n), read(c);
for(long long i = 1;i <= n;++ i) read(a[i]), sum += a[i];
build(1,1,n);
for(long long i = c;i <= n;++ i)
dp[i] = max(dp[i - 1], dp[i - c] + ask(i - c + 1, i,1,1,n)), ans = max(ans, dp[i]);
printf("%I64d", sum - ans);
return 0;
}
F
题目大意：
给你一串序列，支持两种操作：
1：询问一段区间\([l,r]\)中数字出现次数的mex;
2：单点修改
题解：
带修改的莫队，敢打就能A。网上很多求mex的方法是把次数分块，但我发现有人暴力扫一遍求mex也能A，于是我就暴力扫了，居然没被卡。由于忘记给处理last的t赋初值，WA了一上午。。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define abs(x) ((x) < 0 ? -1 * (x) : (x))
template <class T>
inline void read(T &x)
{
x = 0;char ch = getchar(), c = ch;
while(ch < '0' || ch > '9') c = ch, ch = getchar();
while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();
if(c == '-') x = -x;
}
const long long INF = 0x3f3f3f3f;
const long long MAXN = 2000000 + 10;
long long n,q,size,num[MAXN],tmp[MAXN],ci[MAXN],cnt[MAXN],a[MAXN],tot,qtot,ctot,val[MAXN],p[MAXN],c[MAXN],last[MAXN],t[MAXN],pos[MAXN],tong[MAXN];
bool cmp1(long long a, long long b)
{
return tmp[a] < tmp[b];
}
struct Node
{
long long l, r, t, rank;
}node[MAXN];
bool cmp2(Node a, Node b)
{
return pos[a.l] == pos[b.l] ? (pos[a.r] == pos[b.r] ? a.t < b.t : pos[a.r] < pos[b.r]) : pos[a.l] < pos[b.l];
}
long long l = 1, r = 0, ans, now = 0;
void add(long long x)
{
-- tong[ci[x]];
++ ci[x];
++ tong[ci[x]];
}
void del(long long x)
{
-- tong[ci[x]];
--ci[x];
++ tong[ci[x]];
}
void change(long long p, long long c)
{
if(l <= p && p <= r) del(num[p]), add(c);
num[p] = c;
}
int main()
{
read(n), read(q);
for(long long i = 1;i <= n;++ i) read(num[i]), tmp[i] = num[i], cnt[i] = i;
for(long long i = 1;i <= q;++ i)
{
long long tmp;read(tmp);
if(tmp == 1)
{
++ qtot;read(node[qtot].l), read(node[qtot].r);
node[qtot].t = ctot, node[qtot].rank = qtot;
}
else
{
++ ctot, read(p[ctot]), read(c[ctot]);
num[n + ctot] = ::tmp[n + ctot] = c[ctot], cnt[n + ctot] = n + ctot;
}
}
std::sort(cnt + 1, cnt + 1 + n + ctot, cmp1);
tmp[0] = -1;
for(long long i = 1;i <= n + ctot;++ i)
{
if(tmp[cnt[i]] != tmp[cnt[i - 1]])
++ tot, val[tot] = tmp[cnt[i]];
num[cnt[i]] = tot;
t[cnt[i]] = tot;
}
for(long long i = 1;i <= ctot;++ i)
c[i] = num[n + i], last[i] = t[p[i]], t[p[i]] = c[i];
size = pow(n, 0.666667);
for(long long i = 1;i <= n;++ i)
if((i - 1) % size == 0) pos[i] = pos[i - 1] + 1;
else pos[i] = pos[i - 1];
std::sort(node + 1, node + 1 + qtot, cmp2);
tong[0] = 1000000000;
for(long long i = 1;i <= qtot;++ i)
{
while(now < node[i].t) ++ now, change(p[now], c[now]);
while(now > node[i].t) change(p[now], last[now]), -- now;
while(r < node[i].r) ++ r, add(num[r]);
while(r > node[i].r) del(num[r]), -- r;
while(l < node[i].l) del(num[l]), ++ l;
while(l > node[i].l) -- l, add(num[l]);
ans = 0;
while(tong[ans]) ++ ans;
a[node[i].rank] = ans;
}
for(long long i = 1;i <= qtot;++ i) printf("%I64d\n", a[i]);
return 0;
}