A.Points on the line

题意就是给你一个数列，求删掉最少的数使得最大值和最小值之差不超过$d$。

显然先对数列排序一下，显然删中间的数肯定不会影响最大最小值，因此贪心地按照某个数产生的超过$d$的数对从来选择删最小值或最大值，直到不存在这样的数对为止。

代码：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e5 + 7;
int arr[N];

int main(void)
{
    int n, d, i, j;
    scanf("%d%d", &n, &d);
    for (i = 1; i <= n; ++i)
        scanf("%d", &arr[i]);
    sort(arr + 1, arr + 1 + n);
    int ans = 0;
    i = 1, j = n;
    while (j - i + 1 > 1)
    {
        int pb = 0, ps = 0;
        for (int k = i; k <= j; ++k)
        {
            if (arr[k] - arr[i] > d)
                ++pb;
            if (arr[j] - arr[k] > d)
                ++ps;
        }
        if (pb == 0 && ps == 0)
            break;
        if (pb >= ps)
            ++i, ++ans;
        else
            --j, ++ans;
    }
    cout << ans << endl;
    return 0;
}

B.Our Tanya is Crying Out Loud

题意就是给你$n$和$k$，每次你可以把$n$减去$1$，花费为$A$，或者在能被$k$整除的时候除以$k$，花费为$B$，求将$n$变成$1$的最小花费。

先特判掉$k=1$的情况，然后再贪心地做，每次的最优的选择总是做一次$B$操作或者$n\%k$次$A$操作，然后取花费小的那个，直到$n=1$为止。

代码：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
LL n, k, A, B;

int main(void)
{
    while (cin >> n >> k >> A >> B)
    {
        if (k == 1)
        {
            cout << (n - 1)*A << endl;
            continue;
        }
        LL ans = 0;
        while (n != 1)
        {
            LL res = n % k;
            if (res == 0)
            {
                LL t = n;
                n /= k;
                if (n == 0)
                {
                    ans += (t - 1LL) * A;
                    break;
                }
                else
                    ans += min(A * (t - n), B);
            }
            else
            {
                n -= res;
                ans += (res * A);
            }
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

C.Phone Numbers

题意就是给你给你一个长度为$n$的字符串$s$，仅用$s$中的字符集构造一个长度为$k$的串$t$，其字典序严格大于$s$

的前提下$t$的字典序最小。

考虑到可能出现多种情况，加上字典序比较是基于前缀的，因此就分类讨论一下$k$和$n$的关系：

当$k \le n$时，考虑从某一个位置开始让$t_i$大于$s_i$，且要使得这个$i$尽量地靠后，因此从$s$的前$k$个位置中找到最后一个不是字符集最大值的位置，这个位置就是要找的$i$，此时只要让前$i-1$个字母与$s$相同，第$i$个字母用第一个大于该位置的字符集字母代替，剩下的用字符集最小的字母填充即可
当$k>n$时，前$n$个字母与$s$相同，剩下的用字符集中最小字母填充即可

代码：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 100010;
char s[N], t[N];
int vis[300];
vector<char>st;

int main(void)
{
    int n, k, i, j;
    while (~scanf("%d%d", &n, &k))
    {
        scanf("%s", s);
        for (int i = 0; i < n; ++i)
        {
            if (!vis[s[i]])
                vis[s[i]] = 1, st.push_back(s[i]);
        }
        sort(all(st));
        if (k > n)
        {
            printf("%s", s);
            for (int i = 0; i < k - n; ++i)
                printf("%c", st[0]);
            puts("");
        }
        else
        {
            int sz = st.size();
            if (st.size() > 1)
            {
                int pos = 0;
                for (int i = 0; i < k; ++i)
                {
                    if (s[i] != st[sz - 1])
                        pos = i;
                }
                int res = k;
                for (int i = 0; i < pos; ++i)
                    printf("%c", s[i]);
                res -= (pos);
                char tar = 0;
                for (int i = 0; i < sz; ++i)
                {
                    if (st[i] > s[pos])
                    {
                        tar = st[i];
                        break;
                    }
                }
                printf("%c", tar);
                --res;
                while (res--)
                    printf("%c", st[0]);
                puts("");
            }
        }
    }
    return 0;
}

D.Alena And The Heater

题意就是给你一个序列${a_i}$和${b_i’}$，后者是根据题目所给规律（涉及到$L$和$R$）用${a_i}$构造的，根据这个规律构造出另外一个数组${b}$与${b_i’}$相同，求$L$和$R$的值，答案不能超过$10^9$

根据题目的规律，$O(n)$地维护$L$和$R$的值就好，~~奇奇怪怪的题目，初始化的时候习惯性设为1e9+7然后就GG了~~

代码：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e5 + 7;
int a[N], b[N], tb[N];
char s[N];

int main(void)
{
    int n, i, j;
    scanf("%d", &n);
    for (i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    scanf("%s", s + 1);
    for (i = 1; i <= n; ++i)
        b[i] = s[i] - '0';
    int L = -1e9, R = 1e9;//别设成1e9+7……
    for (i = 5; i <= n; ++i)
    {
        if (b[i] == 0)
        {
            int Min = min({a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]});
            if (b[i - 1] && b[i - 2] && b[i - 3] && b[i - 4])
                R = min(R, Min - 1);
        }
        else
        {
            int Max = max({a[i], a[i - 1], a[i - 2], a[i - 3], a[i - 4]});
            if ((!b[i - 1]) && (!b[i - 2]) && (!b[i - 3]) && (!b[i - 4]))
                L = max(L, Max + 1);
        }
    }
    printf("%d %d\n", L,  R);
    return 0;
}

E.Cashback

题意就是给你一个长度为$n$的序列和$c$，定义一个子区间的价值为除了前$\left\lfloor k \over c\right\rfloor$小（不去重）的数的加和，比如$[3, 1, 6, 5, 2]$， $c = 2$ ，序列价值为$3 + 6 + 5 = 14$，求如此分割序列使得价值总和最小。

看范围可以知道这玩意儿不太可能是二维$DP$，然后就考虑$dp[i]$为序列$1-i$的分割最少价值。

那么就有转移方程：

$dp[i] = min(dp[i], dp[j]+calc(j+1,i))$

然后我用最暴力的方法实现一下发现这个复杂度是$O(n^3logn)$的（至少样例能过说明蒟蒻我这个转移方程是没问题的2333），无解，看了Tutorial的解释是说最优分割方案只有两种：要么分割长度为$1$，要么分割长度为$c$，想了一下确实是这样。

假设分割区间小于$c$，那么价值是这个区间的总和，还不如凑到$c$能还能去掉最小的那个数；假设分割区间大于$c$，那么和前$c$个一段，剩下成为一段价值之和并没有什么区别，主要思路就是分割成$k$个$c$长度的区间是肯定不会比一个$k*c$长度为区间的差。因此用单调队列或者其他什么数据结构~~（主席树之类的）~~维护一下连续的长度为$c$的子区间最小值即可。~~蒟蒻没怎么写过单调队列，把deque写成queue debug半天…………~~

代码：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e5 + 7;
LL arr[N], dp[N], pre[N];

void init()
{
    CLR(dp, INF);
    dp[0] = 0;
}
inline LL sum(int l, int r)
{
    return pre[r] - pre[l - 1];
}
int main(void)
{
    int n, i, c;
    while (~scanf("%d%d", &n, &c))
    {
        for (i = 1; i <= n; ++i)
            scanf("%I64d", arr + i), pre[i] = pre[i - 1] + arr[i];
        if (c == 1)
            puts("0");
        else
        {
            init();
            LL inf = dp[1];
            deque<int>Q;
            for (i = 1; i <= n; ++i)
            {
                while (!Q.empty() && arr[i] <= arr[Q.back()])
                    Q.pop_back();
                Q.push_back(i);
                while (!Q.empty() && Q.front() < i - c + 1)
                    Q.pop_front();
                dp[i] = min<LL>({dp[i], dp[i - 1] + arr[i], i - c < 0 ? inf : dp[i - c] + sum(i - c + 1, i) - arr[Q.front()]});
            }
            printf("%I64d\n", dp[n]);
        }
    }
    return 0;
}

F.Machine Learning

题意就是给你一个长度为$n$的序列，和$m$个操作，每次操作你可以查询$[l,r]$中所有数的出现次数组成的序列的$mex$值，或者令$a_p=x$

这题很明显的带修改莫队算法，虽然比赛的时候过了样例，但是实际存在好几处$bug$和排序的问题，$pretest$都过不了。赛后发现是自己naive了，带修改的莫队姿势和普通莫队是有一些区别的。

块大小一般设为$n^{2/3}$，因此块数为$n^{1/3}$
询问排序规则是先按照左端点所在块排序，再按照右端点所在块排序，再按照操作的时间顺序排序

然后动态维护数的出现次数和出现次数的出现次数即可，由于是出现次数序列的$mex$值，最坏情况是$1+2+…+n$，是$n^2$的级别，那么这个$mex$范围是在$sqrt(n)$内的，也不用什么数据结构就直接暴力$for$一遍找$mex$就好了，一开始记得把初始序列和修改的数放到一起离散化一下

代码：

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
const int N = 100010;
const int unit = 3000;
struct query
{
    int l, r, bl, br, t, id;
    bool operator<(const query &rhs)const {
        if (bl != rhs.bl)
            return bl < rhs.bl;
        if (br != rhs.br)
            return br < rhs.br;
        return t < rhs.t;
    }
} Q[N];
struct op
{
    int x, v;
} C[N];
int arr[N], vis[N], cnt[N * 3], cq, cc, L, R, T, ans[N];
vector<int>v;

inline void add(int &x)
{
    --vis[cnt[x]];
    ++vis[++cnt[x]];
}
inline void del(int &x)
{
    --vis[cnt[x]];
    ++vis[--cnt[x]];
}
inline void F(op &c)
{
    if (L <= c.x && c.x <= R)
    {
        del(arr[c.x]);
        add(c.v);
    }
    swap(arr[c.x], c.v);
}
int main(void)
{
    int n, m, i, o, l, r;
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; ++i)
        scanf("%d", arr + i), v.push_back(*(arr + i));
    for (i = 1; i <= m; ++i)
    {
        scanf("%d%d%d", &o, &l, &r);
        if (o == 1)
        {
            ++cq;
            Q[cq] = {l, r, l / unit, r / unit, cc, cq};
        }
        else
        {
            ++cc;
            C[cc] = {l, r};
            v.push_back(r);
        }
    }
    sort(all(v));
    v.erase(unique(all(v)), v.end());
    for (i = 1; i <= n; ++i)
        *(arr + i) = lower_bound(all(v), *(arr + i)) - v.begin() + 1;
    for (i = 1; i <= cc; ++i)
        (*(C + i)).v = lower_bound(all(v), (*(C + i)).v) - v.begin() + 1;
    sort(Q + 1, Q + 1 + cq);
    L = 1, R = 0;
    for (i = 1; i <= cq; ++i)
    {
        query &tmp = Q[i];
        while (T < tmp.t)
            F(C[++T]);
        while (T > tmp.t)
            F(C[T--]);
        while (R < tmp.r)
            add(*(arr + (++R)));
        while (R > tmp.r)
            del(*(arr + (R--)));
        while (L < tmp.l)
            del(*(arr + (L++)));
        while (L > tmp.l)
            add(*(arr + (--L)));
        for (int j = 1; ; ++j)
        {
            if (!vis[j])
            {
                ans[Q[i].id] = j;
                break;
            }
        }
    }
    for (i = 1; i <= cq; ++i)
        printf("%d\n", ans[i]);
    return 0;
}

Blackops

CF #466 Div.2题解