Codeforces Round 380 (Div. 2)

好像不是非常难。

A

Description

给一个字符串，将所有形如 ogo + gogogogo... 的串变为 ***，输出字符串。

Solution

模拟。

Code

尝试用 python 水过去（）

n = int(input())
s = input()

l = 0

while l < n:
    pos = s.find('ogo', l)
    if pos == -1:
        break
    print(s[l:pos], end = '')
    l = pos
    while l < n - 2 and s[l + 1:l + 3] == 'go':
        l += 2
    print('***', end = '')
    l += 1

print(s[l:])

B

Description

有一个 $n\times m$ 的舞台，给出每个点有没有人，在空的地方可以放灯，往上下左右其中一个方向打光。一个灯光合法当且仅当这个方向有人，位置相同方向不同的灯光算不同的灯光，求合法灯光总数。

Solution

对每个方向做一个前缀和，然后算一下就行。

Code

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

const int maxn = 1e3 + 10;

int up[maxn][maxn], down[maxn][maxn], left[maxn][maxn], right[maxn][maxn];
int a[maxn][maxn], n, m;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            left[i][j] = left[i][j - 1] + a[i][j];
        for (int j = m; j >= 1; j--)
            right[i][j] = right[i][j + 1] + a[i][j];
    }
    for (int j = 1; j <= m; j++)
    {
        for (int i = 1; i <= n; i++)
            up[i][j] = up[i - 1][j] + a[i][j];
        for (int i = n; i >= 1; i--)
            down[i][j] = down[i + 1][j] + a[i][j];
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (!a[i][j])
            {
                ans += up[i][j] ? 1 : 0;
                ans += left[i][j] ? 1 : 0;
                ans += down[i][j] ? 1 : 0;
                ans += right[i][j] ? 1 : 0;
            }
    cout << ans << endl;
}

C

Description

你在 $0$ 处，需要在 $t$ 时间之前沿直线开车到达距离为 $s$ 的电影院，路上有 $k$ 个加油站，经过一个加油站时会免费加满油，有 $n$ 辆车，每辆车有价钱和油箱容量，初始时油箱会满油，一升油可以在 2min 中走 1km，也可以在 0.5min 中走 0.5km。问最少需要花多少钱。

Solution

不难发现油箱容量是有单调性的，二分出最小的能满足题意的油箱容量（check 只需要模拟即可）。

然后找一个油箱不小于它的价钱最小的车即可。注意若 $s>t$，肯定无解。

Code

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

const int maxn = 2e5 + 10;

struct car
{
    int c, v;
} cars[maxn];

int n, k, s, t;
int a[maxn];

bool check(int x)
{
    int now = 0, time = 0;
    for (int i = 1; i <= k; i++)
    {
        int dis = a[i] - now;
        if (dis * 2 <= x)
            time += dis, now = a[i];
        else if (x >= dis)
            time += dis * 2 - (x - dis), now = a[i];
        else
            return false;
    }
    return time <= t;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n >> k >> s >> t;
    for (int i = 1; i <= n; i++)
        cin >> cars[i].c >> cars[i].v;
    for (int i = 1; i <= k; i++)
        cin >> a[i];
    a[++k] = s;
    if (s > t)
    {
        puts("-1");
        return 0;
    }
    std::sort(a + 1, a + 1 + k);
    int l = 1, r = s + 1, ans = r;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (check(mid))
            r = mid - 1, ans = mid;
        else
            l = mid + 1;
    }
    int mi = 1 << 30;
    for (int i = 1; i <= n; i++)
        if (cars[i].v >= ans)
            mi = std::min(mi, cars[i].c);
    if (mi == 1 << 30)
        puts("-1");
    else
        cout << mi << endl;
}

D

Description

有 $a$ 艘船，每艘船长度为 $b$，总共有 $n$ 个位置，其中给出 $k$ 个已经进行过射击且没有船的位置，问最少打几次一定能打到船并输出方案。（建议看原题面加强理解）

Solution

一个地方可能有船当且仅当有连续 $b$ 个 $0$，对于这种地方，我们打最后面就行。

然后处理出可能有船的所有地方，根据雀巢原理（？），设所有可能有船的地方有 $x$ 个，我们只需要打其中 $x-a+1$ 个地方即可。

Code

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

const int maxn = 2e5 + 10;

char s[maxn];
int n, a, b, k;

int main()
{
    cin >> n >> a >> b >> k >> s;
    std::vector<int> ans;
    int now = 0;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == '1')
            now = 0;
        else
        {
            now++;
            if (now == b)
                now = 0, ans.push_back(i + 1);
        }
    }
    cout << ans.size() - a + 1 << endl;
    for (int i = 0; i < ans.size() - a + 1; i++)
        cout << ans[i] << " ";
    cout << endl;
}

E

Description

有一颗 $n$ 个点的树，给出每个点的祖先数，并指定一个点是根。问最少有几个点的祖先数是错的。

Solution

考虑一个点的祖先数一定是他父亲的祖先数加上一，那么所有点的祖先数排序之后一定是一个连续的非严格单调递增的序列。

我们从小到大枚举祖先数，当没有任何一个点的祖先数是当前这个点时，我们把一个祖先数最大的点改过来就行，直到所有点都处理完。注意处理一下根。

Code

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

const int maxn = 2e5 + 10;

int a[maxn], b[maxn], n, s, ans;

int main()
{
    cin >> n >> s;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (i == s)
            ans += a[i] > 0;        
        else
            b[a[i]]++;
    }
    int cnt = 1;
    for (int i = 1; cnt < n; i++)
    {
        if (!b[i])
            cnt++, ans++;
        else
            cnt += b[i];
    }
    cout << ans << endl;
}

F

Description

有 $n$ 个数。A、B 两个人轮流取数，A 从左取，B 从右取。A 先取。假如上一个人取了 $k$ 个数，那么这个人只能取 $k$ 或 $k+1$ 个数。初始时 $k=1$。当取不了或取完时，游戏结束。A 想最大化他取的数的和 $a$，B 想最小化他去的数 $b$。求这两个数差的最大值。$n\leq4000$，空间 512MB。

Solution

我以前对博弈论有个误解，以为只要是玩游戏就是博弈论，今天才知道博弈论是研究谁必胜的，这种最优化问题和 $SG$ 函数没关系。

最优化，考虑一个 DP，$f(l,r,k,0/1)$ 表示当前左面该取 $l$，右面该取 $r$，当前的 $k$，轮到 A/B 取的答案。

状态数看起来是 $O(n^3)$ 的，转移是 $O(1)$ 的。但实际上发现 $k$ 是 $O(\sqrt n)$ 级别的，又发现对于一个确定的 $l$，可能的 $r$ 总数是 $O(k)=O(\sqrt n)$ 级别的，也就是说合法的状态数总共只有 $O(n^2)$ 个。转移挺简单的，但是需要注意一些细节。

那么我们可以使用记忆化搜索来找到答案。

注意直接开数组会 MLE，我们可以把所有可行的状态哈希一下用哈希表存储。（新学到的点）

Code

不知道为什么，用 unordered_map 会 TLE，手写就不会，看来还是慎用比较好。

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

const int maxn = 4e4 + 10, maxm = 5e7 + 10, mod = 10000019;

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

inline int s(int l, int r) { return l > r ? 0 : sum[r] - sum[l - 1]; }

struct node
{
    int l, r, k, pos;
    node() {}
    node(int l_, int r_, int k_, int pos_) : l(l_), r(r_), k(k_), pos(pos_) {}
};

long long hash(const node &x)
{
    return (long long)((long long)800000 * x.l + 200 * x.r + x.k * 2 + x.pos);
}
struct hash_map
{
    struct data
    {
        long long u;
        int v, nex;
    };
    data e[mod << 1];
    int h[mod], cnt;
    int hash(long long u) { return u % mod; }
    int &operator[](long long u)
    {
        int hu = hash(u);
        for (int i = h[hu]; i; i = e[i].nex)
            if (e[i].u == u)
                return e[i].v;
        return e[++cnt] = (data){u, -1, h[hu]}, h[hu] = cnt, e[cnt].v;
    }
    hash_map()
    {
        cnt = 0;
        memset(h, 0, sizeof(h));
    }
} mp;

int dp(int l, int r, int k, int pos)
{
    if (r - l + 1 < k)
        return 0;
    else if (r - l + 1 == k)
        return s(l, r) * (pos == 1 ? -1 : 1);
    int nowst = hash(node(l, r, k, pos));
    if (mp[nowst] != -1)
        return mp[nowst];
    if (pos == 0)
    {
        int tmp = dp(l + k, r, k, pos ^ 1) + s(l, l + k - 1);
        if (l + k <= r)
            tmp = std::max(tmp, dp(l + k + 1, r, k + 1, pos ^ 1) + s(l, l + k));
        return mp[nowst] = tmp;
    }
    else
    {
        int tmp = dp(l, r - k, k, pos ^ 1) - s(r - k + 1, r);
        if (r - k >= l)
            tmp = std::min(tmp, dp(l, r - k - 1, k + 1, pos ^ 1) - s(r - k, r));
        return mp[nowst] = tmp;
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], sum[i] = sum[i - 1] + a[i];
    cout << dp(1, n, 1, 0) << endl;
}

A¶

Description¶

Solution¶

Code¶

B¶

Description¶

Solution¶

Code¶

C¶

Description¶

Solution¶

Code¶

D¶

Description¶

Solution¶

Code¶

E¶

Description¶

Solution¶

Code¶

F¶

Description¶

Solution¶

Code¶

A

Description

Solution

Code

B

Description

Solution

Code

C

Description

Solution

Code

D

Description

Solution

Code

E

Description

Solution

Code

F

Description

Solution

Code