A.Bad Ugly Numbers

题意：

构造一个长度为n的数字使得其不能被其中的每一位数整除。

题解：

除了n为1以外，其余构造2333333即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
char s[maxn];
void solve()
{
    int n;
    scanf("%d", &n);
    if (n == 1)
    {
        puts("-1");
        return;
    }
    putchar('2');
    for (int i = 1; i < n; i++)
        putchar('3');
    puts("");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.Maximums

题意：

对于数组 $a$ ，数组 $x$ 满足 $x_i=max(0,a_1,…,a_{i−1})$ , $x1=0$ ，数组 $b$ 满足 $b_i = a_i − x_i$ 。现在给定 $b$ ，要求反推 $a$ 。

题解：

因为 $b_i = a_i - x_i$ 所以 $a_i = b_i + x_i$ 在遍历 $a$ 的同时，维护 $x$ 即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int main()
{
    int n;
    scanf("%d", &n);
    ll x = 0, b;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &b);
        b += x;
        x = max(x, b);
        printf("%lld ", b);
    }
    puts("");
    return 0;
}

C.Permutation Partitions

题意：

给定一种 $[1,n]$ 的排列 $p$ ，现在让你分成 $k$ 块，求每块的最大值之和。形式上为 $\sum_{i=1}^{k}{max_{l_i \leq j \leq r_i}(p_j)}$ ，并算出有多少种分法可以达到这个最大值。

题解：

最大值就是 $[n−k+1,n]$ 的区间和，根据这k个数来划分区间即可,记录这k个数的下标，分法总数为 $\prod_{i=1}^{k-1}(idx_{i+1} - idx_i)$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    ll ans = 1, sum = 0, l = -1;
    for (int i = 1; i <= n; i++)
    {
        ll p;
        scanf("%lld", &p);
        if (p > n - k)
        {
            sum += p;
            if (l != -1)
                ans = ans * (i - l) % mod;
            l = i;
        }
    }
    printf("%lld %lld\n", sum, ans);
    return 0;
}

D.Prefix-Suffix Palindrome（马拉车）

题意：

给定串 $s$ ，从 $s$ 的前缀和后缀取任意长度进行拼接成新串 $t$ ，使得 $t$ 为回文串并尽可能长。

题解：

先双端扫描一遍，确定回文的前缀和后缀，获得左区间和右区间，再对中间部分分别正序和逆序跑一遍 $manacher$ ,最终答案就是左区间＋中间部分的前缀和后缀较大者+右区间

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
string Manacher(const string &s)
{
    string t = "#";
    for (char c : s)
        t += c, t += "#";
    int RL[t.size()] = {0};
    int MaxRight = 0;
    int pos = 0;
    for (int i = 0; i < t.size(); i++)
    {
        if (i < MaxRight)
            RL[i] = min(RL[2 * pos - i], MaxRight - i);
        else
            RL[i] = 1;
        while (i - RL[i] >= 0 && i + RL[i] < t.size() && t[i - RL[i]] == t[i + RL[i]])
            RL[i] += 1;
        if (RL[i] + i - 1 > MaxRight)
            pos = i, MaxRight = RL[i] + i - 1;
    }
    int MaxLen = 0;
    for (int i = 0; i < t.size(); i++)
        if (RL[i] == i + 1)
            MaxLen = i;
    return s.substr(0, MaxLen);
}
void solve()
{
    string s;
    cin >> s;
    int l = 0, r = s.size() - 1;
    while (l < r && s[l] == s[r])
        ++l, --r;
    string s1 = s.substr(l, r - l + 1);
    string s2 = s1;
    reverse(s2.begin(), s2.end());
    s1 = Manacher(s1);
    s2 = Manacher(s2);
    cout << s.substr(0, l) << (s1.size() > s2.size() ? s1 : s2) << s.substr(r + 1) << "\n";
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

E.Bombs（线段树）

题意：

给定 $[1,n]$ 的排列 $p$ , $q$ ，将 $p_i$ 依次加入初始为空的集合 $S$ ， $q_i$ 的值表示第 $i$ 次加入的值为雷。若加入的是雷就把当前集合最大值从集合中移出(先加再移出)。现在规定对于每一个 $i$ ， $q_1$ ... $q_{i-1}$ 都是雷。求对于每一个 $i∈[1,n]$ ,操作后集合中的最大值。

题解：

首先雷越多，最大值一定不会变的更大，所以该序列一定为非递增序列。由于 $q$ 描述的是下标，所以我们关心 $p$ 加入集合的顺序。现在我们将 $i$ 从最大值开始遍历，若没有任何的雷，那么最大值一定为 $n$ ，现在我们确定一个最大值后，就要关注雷的位置，也就是什么时候会把这个最大值给 $pop$ 出来。具体实现可以通过区间最大值来进行。首先将区间 $[1,idx_i]$ 的最大值加一，对于 $pos$ 位最大值为 $x$ 的条件为全区间最大值大于 $0$ ，当该位最大值确定后，我们就要将区间 $[1,q_{pos}]$ 的最大值减一。区间最大值的维护用线段树即可。详细过程看代码。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 3e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
struct tree
{
    int mx, lazy;
} tr[maxn << 2];
int n, p[maxn], q[maxn], ans[maxn];
void pushdown(int rt)
{
    if (tr[rt].lazy)
    {
        tr[rt << 1].mx += tr[rt].lazy;
        tr[rt << 1].lazy += tr[rt].lazy;
        tr[rt << 1 | 1].mx += tr[rt].lazy;
        tr[rt << 1 | 1].lazy += tr[rt].lazy;
        tr[rt].lazy = 0;
    }
}
void pushup(int rt)
{
    tr[rt].mx = max(tr[rt << 1].mx, tr[rt << 1 | 1].mx);
}
void update(int rt, int l, int r, int L, int R, int val)
{
    if (L <= l && r <= R)
    {
        tr[rt].mx += val;
        tr[rt].lazy += val;
        return;
    }
    pushdown(rt);
    int mid = l + r >> 1;
    if (L <= mid)
        update(rt << 1, l, mid, L, R, val);
    if (R > mid)
        update(rt << 1 | 1, mid + 1, r, L, R, val);
    pushup(rt);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++)
    {
        scanf("%d", &x);
        p[x] = i;
    }
    for (int i = 1; i <= n; i++)
        scanf("%d", &q[i]);
    int idx = 0;
    for (int i = n; i >= 1; i--)
    {
        update(1, 1, n, 1, p[i], 1);
        while (idx < n && tr[1].mx > 0)
        {
            idx++;
            ans[idx] = i;
            update(1, 1, n, 1, q[idx], -1);
        }
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", ans[i]);
    puts("");
    return 0;
}

Codeforces Global Round 7

A.Bad Ugly Numbers

题意：

题解：

B.Maximums

题意：

题解：

C.Permutation Partitions

题意：

题解：

D.Prefix-Suffix Palindrome（马拉车）

题意：

题解：

E.Bombs（线段树）

题意：

题解：