Codeforces Global Round 7 题解

作者： 作者的头像   逆乾 ,  2020-03-27 12:04:29 ,  所有人可见 ,  阅读 924

2


A. Bad Ugly Numbers

构造题，不难发现，当 $n = 1$ 时无解，而当 $n > 1$ 时，$23333…$ 后续一共 $n - 1$ 个 $3$ 一定满足要求，直接循环输出即可。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        if (n == 1) {
            cout << -1 << endl;
            continue;
        }
        cout << 2;
        while (--n)
            cout << 3;
        cout << endl;
    }
    return 0;
}

B. Maximums

易知，$a_1 = b_1$，由此可得 $x_2 = max(0, a_1)$，又由于 $b_2 = a_2 - x_2$，可以算得 $a_2$，由此更新 $x_3$，再得到 $a_3$.

以此类推，可以得到数组 $a$.

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n, max_val = 0;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        cout << x + max_val << ' ';
        max_val = max(max_val, x + max_val);
    }
    cout << endl;
    return 0;
}

C. Permutation Partitions

根据贪心的思想，可以将前 $k$ 大的值分别放在 $k$ 段区间中，此时得到的 $the\ partition\ value$ 最大。

假设这 $k$ 个值在数组中的位置分别为 $p_1, p_2, …, p_k$，第一段区间的起点必定是 $1$，而终点可以选择 $p_1$ ~ $p_2 - 1$ 当中的任何一个位置；在选定第一段区间的终点之后，第二段区间的起点也随之固定，为 $ 第一段区间终点 + 1$，而终点可以选择 $p_2$ ~ $p_3 - 1$ 的任何一个位置…

以此类推，第 $k - 1$ 段区间的终点的选择区间为 $[p_{k - 1},\ p_k)$，此后第 $k$ 段区间起点固定，而第 $k$ 段区间终点一定为 $n$，所以终点不需要选择。

综上，只需要将每段区间能够选择的终点的位置的方案数相乘即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e5 + 5, mod = 998244353;
int n, k;
PII a[N];

bool mycmp(PII a, PII b)
{
    return a.second < b.second;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a + 1, a + n + 1);
    reverse(a + 1, a + n + 1);
    LL sum = 0;
    for (int i = 1; i <= k; i++)
        sum += a[i].first;
    sort(a + 1, a + k + 1, mycmp);
    LL mul = 1;
    for (int i = 2; i <= k; i++)
        mul = mul * (a[i].second - a[i - 1].second) % mod;
    cout << sum << ' ' << mul << endl;
    return 0;
}

D1. Prefix-Suffix Palindrome (Easy version)

由于选出的回文串一定是给出的字符串中的一段前缀再接上一段后缀。

所以可以先判断出来前缀和后缀回文的最大长度，再在剩余的字符串中找出左端点固定的回文串的最大长度以及右端点固定的回文串的最大长度，再取最大长度拼接在上述的前缀后缀之间即可。

数据范围较小，可以直接暴力。

#include <bits/stdc++.h>

using namespace std;

const int N = 5e3 + 5;
char str[N];

bool check(int l, int r)
{
    while (l <= r && str[l] == str[r])
        l++, r--;
    return l > r;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        cin >> str + 1;
        int len = strlen(str + 1);
        int l = 1, r = len;
        while (l <= r && str[l] == str[r])
            l++, r--;
        if (l > r) {
            cout << str + 1 << endl;
            continue;
        }
        int l_ed = r;
        while (!check(l, l_ed))
            l_ed--;
        int r_ed = l;
        while (!check(r_ed, r))
            r_ed++;
        if (l_ed - l + 1 >= r - r_ed + 1) {
            for (int i = 1; i <= l_ed; i++)
                cout << str[i];
            for (int i = r + 1; i <= len; i++)
                cout << str[i];
            cout << endl;
        } else {
            for (int i = 1; i < l; i++)
                cout << str[i];
            for (int i = r_ed; i <= len; i++)
                cout << str[i];
            cout << endl;
        }
    }
    return 0;
}

D2. Prefix-Suffix Palindrome (Hard version)

相对于 $D1$ 只增加了数据范围，显然这题交暴力会超时，那么如何优化？即：如何快速找出左端点或者右端点固定的最大长度的回文串？

如果不固定左右端点，只是在字符串中寻找最长的回文串，可以用马拉车算法（$Manacher’s\ Algorithm$）

那么加上左端点或者右端点的限制呢？

只需要在 $manacher$ 中增加一个判断，在当前找到的回文串的起点为整个字符串的起点，或者终点为整个字符串的终点时，再来更新答案，当然，此处的整个字符串是指 $D1$ 提到的中间那一段。

最后合并字符串即为答案。

$Q:$ 能否用字符串哈希来做？就是把 $D1$ 中的代码先预处理出哈希值，再将 $check$ 部分的循环变为判断两个哈希值是否相等。

$A:$ 亲测这题以及上一题均存在令哈希产生冲突的数据，所以不能用哈希。

Update 2020/03/28: 感谢 @胡图图 在评论中提到的 $KMP$ 做法，将中间的那一串倒序接在末尾，做一遍 $KMP$，此时 $ne[n]$ 即为和前缀匹配的最大长度，再反过来对称做一遍，取匹配长度较大的即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 5;
int p[N];
char str[N], a[N], b[N];

void manacher(int n)
{
    int m = 0;
    b[m++] = '$';
    b[m++] = '#';
    for (int i = 0; i < n; i++) {
        b[m++] = a[i];
        b[m++] = '#';
    }
    b[m++] = '%';
    int mx, id, r, c;
    mx = id = r = c = 0;
    for (int i = 2; i < m - 2; i++) {
        p[i] = mx > i ? min(p[id * 2 - i], mx - i) : 1;
        while (b[i + p[i]] == b[i - p[i]])
            p[i]++;
        if (i + p[i] > mx) {
            id = i;
            mx = i + p[i];
        }
        if ((i - p[i] + 1 <= 2 || i + p[i] - 1 >= 2 * n) && p[i] > r) {
            c = i;
            r = p[i];
        }
    }
    for (int i = c - r + 1; i <= c + r - 1; i++)
        if (b[i] >= 'a' && b[i] <= 'z')
            printf("%c", b[i]);
    return;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%s", str + 1);
        int len = strlen(str + 1);
        int l = 1, r = len;
        while (l <= r && str[l] == str[r])
            l++, r--;
        if (l > r) {
            printf("%s\n", str + 1);
            continue;
        }
        for (int i = 1; i < l; i++)
            printf("%c", str[i]);
        int n = 0;
        for (int i = l; i <= r; i++)
            a[n++] = str[i];
        manacher(n);
        for (int i = r + 1; i <= len; i++)
            printf("%c", str[i]);
        printf("\n");
    }
    return 0;
}

E. Bombs

首先不难发现，输出的答案序列一定是递减的，否则的话就会与题意要求的产生矛盾。

因此，我们可以从大到小来判定答案，如果不成立就将答案 $-1$，继续判断，否则就输出当前答案，加进下一个炸弹后再来判定答案是否依然成立。

假设当前判定的答案为 $res$，那么在 $res$ 对应的下标之前出现的炸弹都不会对其产生影响，我们来考虑在对应下标之后出现的炸弹。

如果在其对应的下标之后有一个比 $res$ 大的数，那么在该数之后至少要有一个炸弹的位置；如果还有另一个数比 $res$ 大，那么在该数后也得至少有一个炸弹的位置。

整理一下就能发现：

  • 在 $res$ 对应的下标之后的最右侧的比 $res$ 大的数后，至少得有一个炸弹位。
  • 在 $res$ 对应的下标之后的第二右侧的比 $res$ 大的数后，至少得有两个炸弹位。
  • …

即：在 $res$ 对应的下标之后的每一个比 $res$ 大的数之后，都必须有一个相应炸弹位弹出该数。

考虑用线段树来维护这样一个值：
$$ b_i = (以\ i\ 为起点的后缀中 \geq res\ 的数的数量) - (以\ i\ 为起点的后缀中的炸弹的数量) $$
若线段树中任何一个 $b_i$ 均小于等于零，则说明当前枚举的 $res$ 一定会被炸弹炸毁，此时将 $res-1$ 后继续判断；否则，又由于我们的 $res$ 是从大到小枚举的，所以 $res + 1$ 一定不满足条件，而此时 $res$ 即为当前炸弹分布的情况下的答案。

现在的问题就是如何维护线段树上的值？

当 $res$ 更新后，我们需要在所有后缀包含更新后的 $res$ 的位置上 $+1$，即：在 $[1, 更新后的\ res\ 对应的下标]$ 这段区间上的值 $+1$；

当新加入一个炸弹后，需要在所有后缀包含这个炸弹的位置上 $-1$，即：在 $[1, 新加入炸弹的位置]$ 这段区间上的值 $-1$。

在线段树上只需要维护最大值即可。

会递减着判定 $n$ 次 $res$，每次递减会执行一次修改操作，每次新添加一个炸弹也会进行一次修改操作，所以时间复杂度为 $O(nlogn)$.

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5;
int n;
int a[N], pos[N], q[N];

struct segment_tree {
    int l, r;
    int val, add;
} T[N << 2];

void update(int p)
{
    int lp = p << 1, rp = lp | 1;
    T[p].val = max(T[lp].val, T[rp].val);
    return;
}

void push_down(int p)
{
    if (!T[p].add || T[p].l == T[p].r)
        return;
    int lp = p << 1, rp = lp | 1;
    T[lp].val += T[p].add;
    T[rp].val += T[p].add;
    T[lp].add += T[p].add;
    T[rp].add += T[p].add;
    T[p].add = 0;
    return;
}

void build(int p, int l, int r)
{
    T[p].l = l, T[p].r = r;
    if (l == r)
        return;
    int mid = l + r >> 1, lp = p << 1, rp = lp | 1;
    build(lp, l, mid);
    build(rp, mid + 1, r);
    return;
}

void change(int p, int l, int r, int c)
{
    if (l <= T[p].l && r >= T[p].r) {
        T[p].val += c;
        T[p].add += c;
        return;
    }
    push_down(p);
    int mid = T[p].l + T[p].r >> 1, lp = p << 1, rp = lp | 1;
    if (l <= mid)
        change(lp, l, r, c);
    if (r > mid)
        change(rp, l, r, c);
    update(p);
    return;
}

int query()
{
    return T[1].val;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        pos[a[i]] = i;
    }
    for (int i = 1; i <= n; i++)
        scanf("%d", q + i);
    build(1, 1, n);
    int res = n;
    change(1, 1, pos[res], 1);
    for (int i = 1; i <= n; i++) {
        while (query() <= 0)
            change(1, 1, pos[--res], 1);
        printf("%d%c", res, " \n"[i == n]);
        change(1, 1, q[i], -1);
    }
    return 0;
}

F1. Wise Men (Easy Version)

F2. Wise Men (Hard Version)

G. Spiderweb Trees

等自己以后变强了再来补这三题，如果自己还记得的话~~

4 评论

用户头像
胡图图   2020-03-27 17:01         踩      回复

D2榜上一堆马拉车，出题人哭了，白出这么好的题了（我也用马拉车恰了烂分）。贴个正解KMP。

#include <bits/stdc++.h>

using namespace std;

const int N = 3e6 + 100;

int Next[N];

string KMP(string s)
{
    string t = "." + s + '#' + string(s.rbegin(),s.rend()); 
    int n = t.size() - 1;
    for(int i=2,j=0;i<=n;i++)
    {
        while(j && t[j + 1] != t[i]) j = Next[j];
        if(t[j + 1] == t[i]) j ++ ;
        Next[i] = j;
    }
    return t.substr(1,Next[n]);
}

string get(string s)
{
    if(s.size() == 0) return "";
    string a = KMP(s);
    string b = KMP(string(s.rbegin(),s.rend()));

    if(a.size() >= b.size()) return a;

    return b;
}

void solve()
{
    string s;

    cin >> s;

    int n = s.size();

    int l = 0 , r = n - 1;

    string res;
    while(l < r && s[l] == s[r])
    {
        res += s[l];
        l ++ ;
        r -- ;
    }

    res = res  + get(s.substr(l,r-l+1)) +string(res.rbegin(),res.rend());

    cout << res << endl;
}

int main(){

    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);

    ios :: sync_with_stdio(false);
    cin.tie(0);

    int T;

    cin >> T;

    while(T--) solve();

    return 0;
}
用户头像
逆乾   2020-03-28 10:59         踩      回复

(๑•̀ㅂ•́)و✧
万分感谢
%%%

用户头像
胡图图   2020-03-27 16:36         踩      回复

前排%%%

用户头像
zmj2008   2020-03-27 12:54         踩      回复

ORZ