CF 教育场 135 题解

标签：10 int 题解 CF dfs else leq 135 SG

比赛链接

A题 Colored Balls: Revisited（签到）

给定 \(n\) 种颜色的球，其中颜色 \(i\) 的球的数量是 \(cnt_i\)，保证 \(\sum\limits_{i=1}^n cnt_i\) 是奇数。

在一次操作中，我们可以选择两种不同颜色的球，然后各拿走一个。我们不断进行该操作，直到全场只剩下一个球，问这个球的颜色可能是什么？（如果有多种可能，输出其中一种即可）

\(T\leq 10^3,n\leq 20,1\leq cnt_i\leq 100\)

我写的时候是认为，数量最多的更容易剩下来，直接输出数量最多的那种颜色即可，现在小小证明一下（其实也很简单）：按照从小到大排个序，然后依次消掉当前剩下来数量最小的数量即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 30;
int n, a[N];
int solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    int p = 1;
    for (int i = 2; i <= n; ++i)
        if (a[p] < a[i]) p = i;
    return p;
}
int main() {
    int T;
    cin >> T;
    while (T--) cout << solve() << endl;
    return 0;
}

B题 Best Permutation（构造）

给定一个排列 \(\{a_n\}\)，现在执行如下函数：

int solve(int n, int *a) {
 int x = 0;
 for (int i = 1; i <= n; ++i)
     if (x < a[i]) x += a[i];
 	else x = 0;
	return x;
}

给定 \(n\)，要求我们构造一个排列，使得返回的值尽可能大，并输出该排列。

\(T\leq 97,4\leq n\leq 100\)

假定最后一个数是 \(x\)，那么得到的返回值不会超过 \(2x-1\)：如果前面 \(n-1\) 个值得到的数是 \(y\)，那么

1. \(y<x\)，得 \(y+x\leq (x-1)+x=2x-1\)
2. \(y>x\)，最后的值直接变成 0

那么显然，最后一个数应该填 \(n\)，倒数第二个填 \(n-1\)，随后让前 \(n-2\) 个数得到的值变成 0 即可：

1. 随机法：倒数第三个填 1，然后前面 \(n-3\) 个数全部随机（得到正数的概率要远大于得到 0 吧，然后直接被 1 压成 0 了）
2. 构造法：如果 \(n-2\) 是偶数，那么直接类似 \(2,1,4,3,\cdots,n-2,n-3\) 即可；是奇数，就直接 \(1,2,3,5,4,7,6,\cdots,n-2,n-3\)

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n, a[N];
void solve() {
    cin >> n;
    a[n] = n, a[n - 1] = n - 1;
    if (n % 2 == 0) {
        for (int i = 1; i < n - 1; i += 2) a[i] = i + 1, a[i + 1] = i;
    }
    else {
        a[1] = 1, a[2] = 2, a[3] = 3;
        for (int i = 4; i < n - 1; i += 2) a[i] = i + 1, a[i + 1] = i;
    }
    //
    for (int i = 1; i <= n; ++i) cout << a[i] << " ";
    cout << endl;
}
int main() {
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

C题 Digital Logarithm（数据结构，贪心）

我们可以对一个数 \(x\) 进行操作 \(f(x)\)，而 \(f(x)\) 函数返回 \(x\) 的十进制位数。

给定两个长度为 \(n\) 的数列 \(\{a_n\},\{b_n\}\)，我们可以选定某个数列的某个数，并执行操作 \(f(x)\)，问至少需要执行多少次操作，才能使得两个数列“相同”？（数列排序后完全相同，就可以视为“相同”）

\(T\leq 10^4,n,\sum n\leq 2*10^5,1\leq a_i,b_i\leq 10^9\)

有相同的数就先过滤掉，保证剩下来的数没有交集（这部分直接用 map 啥的统计一下，整体 \(O(n)\) 的）。

注意到 \(a_i,b_i\leq 10^9\)，这意味着所有数操作一次后都变成了个位数，所以我们先对两个数列里面大于等于 10 的都操作一下，随后再过滤一遍，之后对所有大于 1 的且剩下来的个位数操作一次即可。

整体复杂度：第一次过滤交集的复杂度是 \(O(n\log n)\)（我用的 map，如果手写哈希或者 unordered_map 可以变成 \(O(n)\)），后面操作的流程就是 \(O(n+10)\) 了。

#include<bits/stdc++.h>
using namespace std;
int f(int x) {
    int tot = 0;
    for (; x; x /= 10) ++tot;
    return tot;
}
const int N = 200010;
int n, a[N], b[N], c[N];
int solve() {
    //read
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];
    memset(c, 0, sizeof(int) * (n + 1));
    //solve
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    int tot = 0;
    map<int, int> vis1;
    for (int i = 1; i <= n; ++i) ++vis1[a[i]];
    for (int i = 1; i <= n; ++i)
        if (vis1.find(b[i]) != vis1.end()) {
            c[i] = 1;
            if (--vis1[b[i]] == 0)
                vis1.erase(vis1.find(b[i]));
        }
    int cnt1[10], cnt2[10];
    memset(cnt1, 0, sizeof(cnt1));
    memset(cnt2, 0, sizeof(cnt2));
    for (auto p : vis1) {
        int x = p.first, y = p.second;
        if (y == 0) continue;
        if (x < 10) cnt1[x] += y;
        else cnt1[f(x)] += y, tot += y;
    }
    for (int i = 1; i <= n; ++i)
        if (c[i] == 0) {
            if (b[i] < 10) ++cnt2[b[i]];
            else ++cnt2[f(b[i])], ++tot;
        }
    for (int i = 1; i < 10; ++i) {
        int d = min(cnt1[i], cnt2[i]);
        cnt1[i] -= d, cnt2[i] -= d;
    }
    for (int i = 2; i < 10; ++i)
        tot += cnt1[i] + cnt2[i];
    return tot;
}
int main() {
    int T;
    cin >> T;
    while (T--) cout << solve() << endl;
    return 0;
}

D题 Letter Picking（SG博弈）

给定一个长度为 \(n\) 的字符串 \(s\)（保证 \(n\) 是偶数）。

现在 Alice 和 Bob 进行游戏，Alice 先手，初始状态下每个人都有一个空的字符串。在每一个回合，玩家可以从字符串 \(s\) 的开头或者结尾拿走一个字符，放在自己的字符串的头部。游戏整体结束后（\(s\) 变空），字典序更小的那个人赢（在相同的情况下是平局）。

\(T\leq 10^3,|s|\leq 2*10^3\)

一个不是很典型的 SG 博弈题（一个是因为有平局，还有一个是因为两轮操作才被认为是一个阶段），我们记 0 为 Bob 赢，1 为平局，2 为 Alice 赢（只记录 Alice 先手的状况，因为 Bob 纯被动应付的）。

假设此时区间是 \([l,r]\)，那么接下来有四种走向：

1. 我拿头部，对方拿头部，变成子问题 \([l+2,r]\)，得到 SG 值为 \(x_1\)
2. 我拿头部，对方拿尾部，变成子问题 \([l+1,r-1]\)，得到 SG 值为 \(x_2\)
3. 我拿尾部，对方拿头部，变成子问题 \([l+1,r-1]\)，得到 SG 值为 \(x_3\)
4. 我拿尾部，对方拿尾部，变成子问题 \([l,r-2]\)，得到 SG 值为 \(x_4\)

假设我们拿了 \(c_1\)，对方拿了 \(c_2\)，后续的新区间是 \([l',r']\)，那么有：

1. 当 \(c_1=c_2\) 时，当前状态的 SG 和 \([l',r']\) 的SG完全相同
2. 当 \(c_1<c_2\) 时，当前状态的 SG 视情况而定：
   1. 如果 \([l',r']=0\)，那么该状态就是 0
   2. 如果 \([l',r']>0\)，那么该状态就是 2
3. 当 \(c_1>c_2\) 时，当前状态的 SG 视情况而定：
   1. 如果 \([l',r']=2\)，那么该状态就是 2
   2. 如果 \([l',r']<2\)，那么该状态就是 0

边界条件：当 \(l=r+1\) 时，\(SG=0\)。

最终 SG，我们需要小处理一下：对方的行动往坏处想，我方的行动往好处用，所以是 \(\max(\min(x_1,x_2),\min(x_3,x_4))\)。

直接记忆化奔着搜一遍就行，复杂度 \(O(n^2)\)。

#include<bits/stdc++.h>
using namespace std;
const int N = 2010;
int n;
char s[N];
/*
0 : Bob win
1 : Draw
2 : Alice win
*/
//
int SG[N][N];
int dfs(int l, int r) {
    if (l == r + 1) return 1;
    if (SG[l][r] != -1) return SG[l][r];
    //
    int x1, x2, x3, x4;
    //choice 1
    if (s[l] == s[l + 1])
        x1 = dfs(l + 2, r);
    else if (s[l] < s[l + 1])
        x1 = dfs(l + 2, r) > 0 ? 2 : 0;
    else
        x1 = dfs(l + 2, r) < 2 ? 0 : 2;
    //choice 2
    if (s[l] == s[r])
        x2 = dfs(l + 1, r - 1);
    else if (s[l] < s[r])
        x2 = dfs(l + 1, r - 1) > 0 ? 2 : 0;
    else
        x2 = dfs(l + 1, r - 1) < 2 ? 0 : 2;
    //choice 3
    if (s[r] == s[r - 1])
        x3 = dfs(l, r - 2);
    else if (s[r] < s[r - 1])
        x3 = dfs(l, r - 2) > 0 ? 2 : 0;
    else
        x3 = dfs(l, r - 2) < 2 ? 0 : 2;
    //choice 4
    if (s[l] == s[r])
        x4 = dfs(l + 1, r - 1);
    else if (s[r] < s[l])
        x4 = dfs(l + 1, r - 1) > 0 ? 2 : 0;
    else
        x4 = dfs(l + 1, r - 1) < 2 ? 0 : 2;
    //make choice
    int x = max(min(x1, x2), min(x3, x4));
    return SG[l][r] = x;
}
int solve() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (int i = 0; i <= n + 1; ++i)
        for (int j = 0; j <= n + 1; ++j)
            SG[i][j] = -1;
    return dfs(1, n);
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        string ans[3] = {"Bob", "Draw", "Alice"};
        cout << ans[solve()] << endl;
    }
    return 0;
}

（似乎也有人是直接贪心过的）

标签：10,int,题解,CF,dfs,else,leq,135,SG
From： https://www.cnblogs.com/cyhforlight/p/16725555.html