Visits: 658

Codeforces Global Round 7

Bad Ugly Numbers

特判掉 $n=1$ 的情况，然后 $8999\cdots 9$ 就符合要求。

inline void solve() {
    int n;
    rd(n);
    if (n == 1) return puts("-1"), void();
    putchar('8');
    while (--n) putchar('9');
    puts("");
}

int main() {
    int T;
    rd(T);
    while (T--) solve();
    return 0;
}

Maximums

依照题意，我们可以得到一个递推式 $a_n = \max_{i=1}^{n-1} a_i + b_n$，时间复杂度 $\mathcal O(n)$。

const int N = 2e5 + 7;
int n;
ll a[N], x;

int main() {
    rd(n), rda(a, n);
    for (int i = 1; i <= n; i++)
        print(x + a[i], " \n"[i==n]), x = max(x, x + a[i]); 
    return 0;
}

Permutation Partitions

最大值肯定可以选择 $n,n-1,\cdots,n-k+1$ 这 $k$ 个数相加。

求方案数时，相邻两个区间的间隔一定在两个选择的数中间，因此将位置之差相乘即可。

时间复杂度 $\mathcal O(n)$。

const int N = 2e5 + 7;
int n, k;
ll a[N], ans;
modint Ans = 1;

int main() {
    rd(n), rd(k), rda(a, n);
    for (int i = 1; i <= k; i++) ans += n + 1 - i;
    print(ans, ' ');
    vi p;
    for (int i = 1; i <= n; i++)
        if (a[i] > n - k) p.pb(i);
    for (ui i = 1; i < p.size(); i++)
        Ans *= p[i] - p[i-1];
    print(Ans);
    return 0;
}

Prefix-Suffix Palindrome

显然可以先贪心地取互为反串的最长前后缀。

取完扔掉之后，相当于要在剩下的字符串的前缀或后缀找到一个最长的回文串。

manacher 即可，时间复杂度 $\mathcal O(n)$。

const int N = 1e6 + 7;
int n, m;
char s[N], t[N];

inline int work(char *s, int n) {
    string ss = "$#";
    vi p;
    for (int i = 1; i <= n; i++) ss += s[i], ss += "#";
    p.pb(1);
    int mx = 0, id = 0, ans = 1;
    for (int i = 1; i < (int)ss.length(); i++) {
        p.pb(mx > i ? min(p[2*id-i], mx - i) : 1);
        while (i + p[i] < (int)ss.length() && ss[i+p[i]] == ss[i-p[i]]) ++p[i];
        if (i == p[i]) ans = max(ans, p[i]);
        if (i + p[i] > mx) mx = i + p[i], id = i;
    }
    return ans - 1;
}

inline void solve() {
    rds(s, n);
    int p = 1;
    while (p <= n && s[p] == s[n+1-p]) ++p;
    if (p == n + 1) {
        for (int i = 1; i <= n; i++) putchar(s[i]);
        return puts(""), void();
    }
    m = 0;
    for (int i = p; i <= n + 1 - p; i++) t[++m] = s[i];
    int l = work(t, m);
    reverse(t + 1, t + m + 1);
    int r = work(t, m);
    reverse(t + 1, t + m + 1);
    if (l < r) reverse(t + 1, t + m + 1), swap(l, r);
    for (int i = 1; i < p; i++) putchar(s[i]);
    for (int i = 1; i <= l; i++) putchar(t[i]);
    for (int i = p - 1; i; i--) putchar(s[i]);
    puts("");
}

int main() {
    int T;
    rd(T);
    while (T--) solve();
    return 0;
}

Bombs

首先有答案是递减的。

对于当前答案 $x$，我们如何判断它时候能被保留下来呢？

可以发现，$x$ 能留下当且仅当存在一个位置满足它右边 $\ge x$ 的数大于它右边的炸弹数。

于是线段树维护全局 $\max$ 和区间修改即可，时间复杂度 $\mathcal O(n \log n)$。

const int N = 3e5 + 7;
int n, a[N], b[N], p[N], ans;
struct T {
    int l, r, x, z;
} t[N<<2];

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r) return;
    build(ls, l, md), build(rs, md + 1, r);
    t[p].x = max(t[ls].x, t[rs].x);
}

void spd(int p) {
    if (t[p].z) {
        t[ls].x += t[p].z;
        t[ls].z += t[p].z;
        t[rs].x += t[p].z;
        t[rs].z += t[p].z;
        t[p].z = 0;
    }
}

void add(int p, int l, int r, int k) {
    if (t[p].l >= l && t[p].r <= r) return t[p].x += k, t[p].z += k, void();
    spd(p);
    if (l <= md) add(ls, l, r, k);
    if (r > md) add(rs, l, r, k);
    t[p].x = max(t[ls].x, t[rs].x);
}

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) rd(a[i]), p[a[i]] = i; 
    for (int i = 1; i <= n; i++) rd(b[i]);
    build(1, 1, n), ans = n, print(n, ' ');
    add(1, 1, p[n], 1);
    for (int i = 1; i < n; i++) {
        add(1, 1, b[i], -1);
        while (t[1].x <= 0) add(1, 1, p[--ans], 1);
        print(ans, ' ');
    }
    return 0;
}

Wise Men

题目太神仙了，先咕咕咕着。

Spiderweb Trees

题目太神仙了，先咕咕咕着。