Codeforces Round 344 (Div. 2)

还算良心的比赛。

A

Description

有两个序列 $a,b$，定义 $f(x,l,r)$ 为 $x$ 序列中 $[l,r]$ 的数或起来的结果，求所有 $l,r$ 中，$f(a,l,r)+f(b,l,r)$ 的最大值。

Solution

发现或起来之后数不会变小，那直接全或起来就行。

Code

n = int(input())
a = map(int, input().split())
b = map(int, input().split())
 
x = 0; y = 0
 
for i in a:
    x |= i
 
for i in b:
    y |= i
 
print(x + y)

B

Description

有一个 $n\times m$ 的矩阵，$k$ 次操作，每次可以把一行或一列涂成一个颜色，求最后的矩阵。$n\times m,k\leq10^5,n\leq5000,m\leq5000$。

Solution

对于每个行和列直接维护最后一次修改是什么颜色和这次修改的时间即可，最后直接找时间更晚的颜色输出。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using std::cin;
using std::cout;
using std::endl;
 
const int maxn = 5010;
 
int col[maxn], row[maxn], tc[maxn], tr[maxn];
 
int main()
{
    std::ios::sync_with_stdio(false);
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++)
    {
        int opt, x, c;
        cin >> opt >> x >> c;
        if (opt == 1)
            row[x] = c, tr[x] = i;
        else
            col[x] = c, tc[x] = i;
    }
    for (int i = 1; i <= n; i++, cout << endl)
        for (int j = 1; j <= m; j++)
            cout << (tr[i] > tc[j] ? row[i] : col[j]) << " ";
    
}

C

Description

有一个长度为 $n$ 序列 $\{a_i\}$，有 $m$ 个人依次进行一次操作，每次操作会把序列的一个前缀升序或降序排序，求最后得到的序列。$n\leq2\times10^5$

Solution

注意到如果上一次操作的区间比这一次小，那么上一次操作没有意义，因此我们只需要找到单调递减的一组操作：用单调栈维护。

维护一个从后到前的答案栈。

然后把原序列排个序，升序排序就是把剩下的不会被下一次操作影响的数从大到小压进栈里，降序排序就是从小到大。

Code

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <stack>
using std::cin;
using std::cout;
using std::endl;

const int maxn = 2e5 + 10;

int top = 0;
int a[maxn], n, m;

struct opt
{
    int i, t;
    opt()
    {
        i = t = 0;
    }
    opt(int i_, int t_)
    {
        i = i_, t = t_;
    }
} p[maxn];

std::stack<int> stk;
int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++)
    {
        int x, pos;
        cin >> x >> pos;
        while (top && pos >= p[top].i)
            top--;
        p[++top] = (opt){pos, x};
    }
    int r = n;
    while (r > p[1].i)
        stk.push(a[r--]);
    std::sort(a + 1, a + 1 + p[1].i);
    int lpos = 1, rpos = p[1].i;
    int res = 0;
    for (int i = 1; i <= top; i++)
    {
        int d = p[i].i - (i == top ? 0 : p[i + 1].i);
        if (p[i].t == 1)
            for (int j = 0; j < d; j++)
                stk.push(a[rpos--]);
        else
            for (int j = 0; j < d; j++)
                stk.push(a[lpos++]);
    }
    while (!stk.empty())
        cout << stk.top() << " ", stk.pop();
    cout << endl;
}

D

Description

定义一个字符串压缩后得到的字符串是把连续相同的字符用数字+字符的形式表示。

给出两个压缩后的字符串 A、B（长度分别为 $n$，$m$），求 B 在 A 中出现了几次。

$n,m\leq2\times10^5$。

Solution

这显然是个 KMP，我们把 B 去除掉第一位和最后一位和 A 匹配，然后看一下第一位和最后一位是否也能匹配即可，特判一下 $m<3$ 的情况。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using std::cin;
using std::cout;
using std::endl;

const int maxn = 2e5 + 10;

struct node
{
    char ch;
    long long len;
    bool operator==(const node &b) const { return ch == b.ch && len == b.len; }
    bool operator!=(const node &b) const { return !(*this == b); }
    void print() { cout << ch << " " << len << endl; }
} a[maxn], b[maxn];

char s[20];

int n, m, tota, totb;
long long ans;

void solve1()
{
    for (int i = 1; i <= n; i++)
        if (a[i].ch == b[1].ch && a[i].len >= b[1].len)
            ans += a[i].len - b[1].len + 1;
}

void solve2()
{
    for (int i = 1; i < n; i++)
        if (a[i].ch == b[1].ch && a[i + 1].ch == b[2].ch 
            && a[i].len >= b[1].len && a[i + 1].len >= b[2].len)
            ans++;
}

int nxt[maxn];
node tmpb[maxn];
int tmpm;

void get_nxt()
{
    for (int i = 2; i < m; i++)
        tmpb[i - 1] = b[i];
    tmpm = m - 2;
    for (int i = 2, j = 0; i <= tmpm; i++)
    {
        while (j && tmpb[i] != tmpb[j + 1])
            j = nxt[j];
        if (tmpb[i] == tmpb[j + 1])
            j++;
        nxt[i] = j;
    }
}

void solve()
{
    get_nxt();
    for (int i = 2, j = 0; i < n; i++)
    {
        while (j && a[i] != tmpb[j + 1])
            j = nxt[j];
        if (a[i] == tmpb[j + 1])
            j++;
        if (j == tmpm)
        {
            int pos = i - tmpm + 1;
            if (a[pos - 1].ch == b[1].ch && a[pos - 1].len >= b[1].len 
                && a[pos + m - 2].ch == b[m].ch && a[pos + m - 2].len >= b[m].len)
                ans++;        
            j = nxt[j];
        }

    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n >> m;
    a[0].ch = b[0].ch = '#', a[0].len = b[0].len = 1;
    for (int i = 1; i <= n; i++)
    {
        cin >> s;
        int len = strlen(s), x = 0;
        for (int i = 0; i < len - 2; i++)
            x = x * 10 + s[i] - '0';
        if (s[len - 1] == a[tota].ch)
            a[tota].len += x;
        else
            a[++tota] = {s[len - 1], x};
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> s;
        int len = strlen(s), x = 0;
        for (int i = 0; i < len - 2; i++)
            x = x * 10 + s[i] - '0';
        if (s[len - 1] == b[totb].ch)
            b[totb].len += x;
        else
            b[++totb] = {s[len - 1], x};
    }
    n = tota, m = totb;
    if (m == 1)
        solve1();
    else if (m == 2)
        solve2();
    else
        solve();
    cout << ans << endl;
}

E

Description

给出一个长度为 $n$ 的序列 $\{a_i\}$，定义它的权值是 $\sum\limits_{i=1}^ni\times a_i$，你可以将序列中一个数移动一次，求能得到的最大的权值。$n\leq2\times10^5$。

Solution

我们只需要最大化操作后增加的权值即可。

设 $f_i$ 表示把第 $i$ 个数移动后能得到的最大权值增加量，$sum_i$ 为序列的前缀和。

$f_i=\max\limits_0^n\{(j-i)\times a_i+sum_i-sum_j\}$，直接枚举 $j$，是 $O(n^2)$。

发现这是个斜率优化的形式。

$sum_j=j\times a_i+(sum_i-i\times a_i-f_i)$。

那么 $y=sum_j,x=j,k=a_i,b=sum_i-i\times a_i-f_i$。

我们要最小化截距，维护一个下凸包即可。

这个题一开始所有的 $j$ 都是可以用的，于是我们的下凸包是固定的，用单调栈维护。

斜率没有单调性，我们直接在单调栈上二分即可。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using std::cout;
using std::cin;
using std::endl;

const int maxn = 2e5 + 10;
typedef long long ll;

int a[maxn], n;
ll sum[maxn];

struct node
{
    ll x, y;
    node() { x = y = 0; }
    node(ll x_, ll y_) { x = x_, y = y_; }
} p[maxn];
int top = 0;

inline double slope(const node &x, const node &y) { return (double)(double(y.y - x.y)) / (double(y.x - x.x)); }

node solve(ll x)
{
    int l = 2, r = top, ans = 1;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (slope(p[mid - 1], p[mid]) <= double(x))
            ans = mid, l = mid + 1;
        else
            r = mid - 1;
    }
    return p[ans];
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n;
    ll res = 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i], sum[i] = sum[i - 1] + a[i], res += 1ll * a[i] * i;
    top = 1;
    for (int i = 1; i <= n; i++)
    {
        node now(i, sum[i]);
        while (top > 1 && slope(p[top - 1], p[top]) >= slope(p[top], now))
            top--;
        p[++top] = now;
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        auto now = solve(a[i]);
        ans = std::max(ans, -now.y + now.x * a[i] - 1ll * i * a[i] + sum[i]);
    }
    cout << res + ans << endl;
}

A¶

Description¶

Solution¶

Code¶

B¶

Description¶

Solution¶

Code¶

C¶

Description¶

Solution¶

Code¶

D¶

Description¶

Solution¶

Code¶

E¶

Description¶

Solution¶

Code¶

A

Description

Solution

Code

B

Description

Solution

Code

C

Description

Solution

Code

D

Description

Solution

Code

E

Description

Solution

Code