Codeforces Round 646 (Div. 2)

概述

不是特别难，F 倒不简单。

A

Description

给出一个 $n$ 项的数列，要求选出 $x$ 个数（不要求连续），使这 $x$ 个数的和为奇数。判断这是否可能。

Solution

这显然是奇数+奇数=偶数和奇数+偶数=奇数这两个结论的简单运用

首先先选一个奇数，如果还要选奇数个数那么必须选一个偶数。

然后尽可能选看最后够不够即可。

Code

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

const int maxn = 1100;

int cnt1, cnt2, n, x;

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        cnt1 = cnt2 = 0;
        cin >> n >> x;
        for (int i = 1, x; i <= n; i++)
            cin >> x, (x % 2 == 0 ? cnt1 : cnt2)++;
        if (cnt2 < 1)
        {
            puts("No");
            continue;
        }
        x--, cnt2--;
        if (cnt1 >= x)
        {
            puts("Yes");
            continue;
        }
        if (x % 2 == 1)
        {
            if (cnt1 < 1)
            {
                puts("No");
                continue;
            }
            cnt1--, x--;
        }
        x -= cnt2 / 2 * 2;
        x -= cnt1;
        puts(x > 0 ? "No" : "Yes");
    }
}

B

Description

对于一个 $01$ 字符串，如果这个字符串没有子序列（可以不连续）是 $101$ 或 $010$，那么它是好的。

给定一个 $01$ 字符串 $s$。你可以选择一些位置，并翻转该位置的数 —— $0$ 变 $1$，$1$ 变 $0$。

你需要求出，至少要选择多少个位置翻转，才能使这个字符串变成好的。

Solution

看一下这个要求，显然符合条件的字符串只有：00000、11111，111000、000111 这四种形式。

做个前缀和看看具体改成哪种即可。

Code

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

const int maxn = 1100;

int sum0[maxn], sum1[maxn], n;
char s[maxn];

int q(int l, int r) { return l > r ? 0 : std::min(sum0[r] - sum0[l - 1], sum1[r] - sum1[l - 1]); }

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        cin >> (s + 1);
        n = strlen(s + 1);
        for (int i = 1; i <= n; i++)
            sum0[i] = sum0[i - 1], sum1[i] = sum1[i - 1], (s[i] - '0' ? sum1[i] : sum0[i])++;
        int ans = 1 << 30;
        for (int i = 1; i <= n; i++)
            ans = std::min(ans, q(1, i) + q(i + 1, n));
        cout << ans << endl;
    }
}

C

Description

给定 $n$ 个节点的无根树。

两名选手轮流操作，每次可以选择一个叶节点并删除它以及所有和它相连的边。叶节点指度数不超过 $1$ 的节点。删除节点 $x$ 的选手胜利。

你需要判断先手是否有必胜策略。具体来讲，如果先手有必胜策略，输出 Ayush，否则输出 Ashish。

Solution

首先，当 $x$ 的度数小于等于 $1$ 时，先手必胜。

而如果度数比 $1$ 大，比如是 $2$，那么先手一定会最后删掉与 $x$ 相邻的点，换成后手也同理。

所以我们直接看 $n$ 的奇偶性就能知道轮流删之后谁能删掉 $x$。

具体地：偶数先手赢，奇数后手赢。

Code

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

const int maxn = 1100;

int deg[maxn], n, x;

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        memset(deg, 0, sizeof(deg));
        cin >> n >> x;
        for (int i = 1, x, y; i < n; i++)
            cin >> x >> y, deg[x]++, deg[y]++;
        if (deg[x] <= 1)
        {
            puts("Ayush");
        }
        else if (n % 2 == 1)
        {
            puts("Ashish");
        }
        else
        {
            puts("Ayush");
        }
    }
}

D

Description

这是一道交互题。

给定长为 $n$ 的数组 $a=[a_1,a_2,…,a_n]$ 和 $k$ 个互不相交的子集 $S_1,S_2,…,S_k$，这些子集中的元素都是 $[1,n]$ 之间的正整数。这些子集两两的交集为空。

你可以进行最多 $12$ 次询问。每次询问你可以给出 $c$ 个互不相同且在 $[1,n]$ 之间的正整数 $v_1,v_2,…,v_c$，然后你会得到 $\max\{v_i\}$。

对于每个子集 $S_i$，你需要求出 $P_i=\max\limits_{j \notin S_i} a_j$。

$2 \leq n \leq 1000,1 \leq a_i,k \leq n,1 \leq c< n$。

Solution

看到 $12$ 次询问，显然我们需要询问 $\log n$ 次。可以向二分的思路上靠。

注意到子集无交，那么有一个重要的结论：除了包含数组中最大数的集合，其他集合的答案一定是这个最大的数。

我们可以通过 $1$ 次询问得到最大的数，再通过 $\log_2n$ 次询问找到这个最大的数的位置。

最后再通过一次询问得到这个包含最大数的答案即可，正好 $12$ 次。

Code

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

const int maxn = 1100;

int n, k;

std::vector<int> a[maxn];
int ans[maxn];
char s[maxn];

int ask(int l, int r)
{
    cout << "?" << " " << r - l + 1 << " ";
    for (int i = l; i <= r; i++)
        cout << i << " ";
    cout << endl;
    int x;
    cin >> x;
    return x;
}

void clear()
{
    for (int i = 1; i <= k; i++)
        a[i].clear();
    memset(ans, 0, sizeof(ans));
}

int main()
{
    std::ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n >> k;
        for (int i = 1, x; i <= k; i++)
        {
            int c;
            cin >> c;
            while (c--)
                cin >> x, a[i].push_back(x);
            std::sort(a[i].begin(), a[i].end());  
        }
        int mx = ask(1, n);
        int l = 1, r = n, pos = n;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (ask(1, mid) == mx)
                pos = mid, r = mid - 1;
            else
                l = mid + 1;
        }
        //cout << pos << endl;
        for (int i = 1; i <= k; i++)
        {
            auto p = std::lower_bound(a[i].begin(), a[i].end(), pos);
            if (p == a[i].end() || *p != pos)
                ans[i] = mx;
            else
            {
                cout << "?" << " " << n - a[i].size() << " ";
                for (int j = 1; j <= n; j++)
                {
                    auto p = std::lower_bound(a[i].begin(), a[i].end(), j);
                    if (p == a[i].end() || *p != j)
                        cout << j << " ";
                }
                cout << endl;
                cin >> ans[i];
            }
        }
        cout << "!" << " ";
        for (int i = 1; i <= k; i++)
            cout << ans[i] << " ";
        cout << endl;
        cin >> s;
        clear();
    }
}

E

Description

给定 $n$ 个节点标号为 $1$ 到 $n$ 的树，且 $1$ 为树根，每个节点上有三个数字 $a_i,b_i,c_i$。$a_i$ 表示修改代价。$b_i,c_i$ 的值为 $0$ 或 $1$ ， $b_i$为初始值，$c_i$为目标值。

每次可以选择以节点 $u$ 为根节点的子树，去把该子树的所有结点从初始值修改成目标值。修改方法为：可以选择该子树中任意 $k$ 个节点进行交换初始值，使之与该节点的目标值相等，代价为 $k\times a_u$。

判断能否把左右点从初始值变为目标值，并输出最小的代价。

Solution

很水的一个题。

对于一个点，在哪里交换是一样的，区别只有代价。

那么我们显然应该用这个点到根路径上所有点代价的最小值去修改它。

直接把代价下放然后取最小值即可，这样我们就可以非常贪心，如果能改直接在深度大的点改即可。

具体到一个子树需要修改几次呢？

随便写个 DP：$f(i,0/1)$ 表示以 $i$ 为根子树内还有多少个初始值为 $0/1$ 的点未被修改。

然后对于一个子树我们能修改的就是 $\min(f(i,0),f(i,1))$ 个点，算一下代价然后修改 $f$ 数组即可。

Code

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

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

int a[maxn], b[maxn], c[maxn], n;
ll ans;

int f[maxn][2];

std::vector<int> e[maxn];
inline void add(int x, int y) { e[x].push_back(y), e[y].push_back(x); }

void dfs(int x, int fa)
{
    a[x] = std::min(a[x], a[fa]);
    if (b[x] != c[x])
        f[x][b[x] == 1]++;
    for (int v : e[x])
        if (v != fa)
            dfs(v, x), f[x][0] += f[v][0], f[x][1] += f[v][1];
    int need = std::min(f[x][0], f[x][1]);
    ans += 1ll * 2 * need * a[x];
    f[x][0] -= need, f[x][1] -= need;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i] >> c[i];
    for (int i = 1, x, y; i < n; i++)
        cin >> x >> y, add(x, y);
    a[0] = 1 << 30;
    dfs(1, 0);
    if (f[1][0] != 0 || f[1][1] != 0)
        cout << -1 << endl;
    else
        cout << ans << endl;
}

F

Description

给定两个长度为 $n$ 的字符串 $s$，$t$。定义一次操作为选择 $s$ 的一个子串 $s_{l, l +1, \dots, r}$，然后将之修改为 $s_{r, l, l + 1, l + 2, \dots, r - 1 }$。请求助使 $s$ 与 $t$ 相等的最小操作次数。无解输出 $-1$。

多组数据，$\sum n \leq 2000$，$s, t$ 中只有小写字母。

Solution

这个操作的实质就是把一个字符提到前面去。

首先如果有一种字符出现次数不同就一定无解，否则一定能构造出一组解。

可以想到一个 DP：$f_{i,j}$ 表示 $s$ 匹配到第 $i$ 位，$t$ 匹配到第 $j$ 位的最小操作次数，这里限制 $j\geq i$。

为什么 $j$ 可以比 $i$ 大呢？意思就是在匹配时我们可以把 $s$ 串中后面的移到前面来。

转移有三种情况：

当 $s_i=t_j$，$f_{i,j}=f_{i-1,j-1}$，很显然；
当出现次数允许（即 $i$ 后面有多的 $t_j$），我们可以从后面拿一个字符过来，即 $f_{i,j}=f_{i,j-1}$。这个东西看着很不对，但我们还有下面的转移：
$f_{i,j}=f_{i-1,j}+1$。这个就是我们之前拿的字符，现在计算代价。

好像很不对，但其实是对的：假如根本没拿过来，那就不会被转移到。

Code

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

const int maxn = 2010;

char s[maxn], t[maxn];

int f[maxn][maxn];
int sum1[maxn][30], sum2[maxn][30];
int n;

inline void updmi(int &x, int y) { x = std::min(x, y); }

bool check()
{
    for (int i = 0; i < 26; i++)
    {
        if (sum1[n][i] != sum2[n][i])
        {
            cout << -1 << endl;
            return 0;
        }
    }
    return 1;
}

int main()
{
    std::ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n;
        cin >> (s + 1) >> (t + 1);
        memset(sum1, 0, sizeof(sum1)), memset(sum2, 0, sizeof(sum2));
        for (int i = 1; i <= n; i++)
            sum1[i][s[i] - 'a']++, sum2[i][t[i] - 'a']++;
        for (int i = 1; i <= n; i++)
            for (int j = 0; j < 26; j++)
                sum1[i][j] += sum1[i - 1][j], sum2[i][j] += sum2[i - 1][j];
        if (check() == 0)
            continue;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                f[i][j] = 1 << 25;
        for (int i = 1; i <= n; i++)
            f[0][i] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = i; j <= n; j++)
            {
                f[i][j] = f[i - 1][j] + 1;
                if (s[i] == t[j])
                    updmi(f[i][j], f[i - 1][j - 1]);
                if (sum1[i][t[j] - 'a'] < sum2[j][t[j] - 'a'])
                    updmi(f[i][j], f[i][j - 1]);
            }
        cout << f[n][n] << 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