Codeforces Round #309 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #309 (Div. 2)
过题数：3
排名：143/9399

A. Kyoya and Photobooks

题意

给定一个由小写字母组成的字符串 $s$，可以在字符串的任意位置插入一个字符，从而生成一个新的字符串，问能够生成的不同的新字符串的个数。

数据范围

$1\leq|s|\leq20$

题解

在字符串的每个位置暴力插入，放入 $set$ 中统计即可。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
string str;
set<string> st;
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(cin >> str) {
        st.clear();
        int len = str.length();
        for(int i = 0; i <= len; ++i) {
            for(char ch = 'a'; ch <= 'z'; ++ch) {
                st.insert(str.substr(0, i) + ch + str.substr(i, len - i));
            }
        }
        cout << st.size() << endl;
    }
    return 0;
}

B. Ohana Cleans Up

题意

给定一个 $n\times n$ 的 $01$ 矩阵，每次操作可以将任意一列的所有 $0$ 翻转为 $1$，$1$ 翻转为 $0$，问最多可以使多少行变为全 $0$。

数据范围

$1\leq n\leq100$

题解

由于每次翻转是按列翻转，所以对于一种固定的列的翻转，要使 $x$ 行变为全 $0$，这 $x$ 行的 $01$ 位置必须完全相同，即这些串必须相等，所以用 $map$ 统计每种字符串的个数，求最大的字符串出现个数就是答案。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
int n, ans;
string str;
map<string, int> mp;
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(cin >> n) {
        mp.clear();
        ans = 0;
        for(int i = 0; i < n; ++i) {
            cin >> str;
            ++mp[str];
            ans = max(ans, (int)mp[str]);
        }
        cout << ans << endl;
    }
    return 0;
}

C. Kyoya and Colored Balls

题意

有 $n$ 个球，每个球有一种颜色，总共有 $k$ 种颜色，颜色编号为 $1-k$，第 $i$ 种颜色的球的个数为 $c_i$。现在 $Kyoya~Ootori$ 将这些球都放入袋子中，依次从袋子中抽球，问第 $i$ 种颜色的最后一个抽出来的球，比第 $i+1$ 种颜色的最后一个被抽出的球早抽出的总的方案数有多少种，输出方案对 $10^9+7$ 取模后的结果。

数据范围

$1\leq k\leq1000\\1\leq c_i\leq1000$

题解

题目要算的其实是排列的方案数，我们可以通过这种方式生成合法的排列：将第 $1$ 到第 $k$ 种颜色的球依次放入排列中，在放第 $i$ 种颜色的球时，先将一个球放在最后的位置，剩下的 $c_i-1$ 个球就可以任意插入到前 $\sum_{j=1}^{i-1} c_j$ 个球的排列中，这就相当于计算在 $\sum_{j=1}^{i-1} c_j$ 个球中插入 $c_i-1$ 个隔板的方案数，方案数为：$C_{c_i-1+\sum_{j=1}^{i-1}c_j}^{c_i-1}$。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const LL MOD = 1000000007;
const int maxn = 1000000 + 100;
int n;
LL fac[maxn];
LL num[maxn], sum[maxn];
void exgcd(LL a, LL b, LL &d, LL &x, LL &y) {
    if(b == 0) {
        d = a;
        x = 1;
        y = 0;
    } else {
        exgcd(b, a % b, d, y, x);
        y -= x * (a / b);
    }
}
LL inv(LL n) {
    LL x, y, d;
    exgcd(n, MOD, d, x, y);
    x = (x % MOD + MOD) % MOD;
    return x;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    fac[0] = 1;
    for(int i = 1; i < maxn; ++i) {
        fac[i] = fac[i - 1] * i % MOD;
    }
    while(scanf("%d", &n) != EOF) {
        for(int i = 1; i <= n; ++i) {
            scanf("%I64d", &num[i]);
            sum[i] = sum[i - 1] + num[i];
        }
        LL ans = 1;
        for(int i = 1; i <= n; ++i) {
            ans =  ((ans * (fac[sum[i] - 1] * inv(fac[sum[i - 1]]) % MOD) % MOD) * inv(fac[num[i] - 1])) % MOD;
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

D. String Game

题意

对于一个给定的 $1-n$ 的排列，可以通过值 $\rightarrow$ 下标找到许多个环，例如：序列 $p=[4,1,6,2,5,3]$，可以找到环 $(142)(36)(5)$，在每个环内，将数字按从大到小排序，再以每个环为整体，按字典序排序，可以得到：$(421)(5)(63)$，得到新的序列 $p=[4,2,1,5,6,3]$，对于某些特殊的序列，通过这样的变换后仍是它自己。给定 $n$，找到 $n$ 的全排列中，满足以上关系的第 $k$ 小的排列。

数据范围

$1\leq n\leq50,1\leq k\leq\min(10^{18}, l)$，其中 $l$ 表示所有满足条件的排列数。

题解

首先通过打一个 $n=5$ 的表可以找到以下满足条件的排列：

$$1~2~3~4~5\\ 1~2~3~5~4\\ 1~2~4~3~5\\ 1~3~2~4~5\\ 1~3~2~5~4\\ 2~1~3~4~5\\ 2~1~3~5~4\\ 2~1~4~3~5$$
可以发现，这些满足条件的排列，相比于排列 $1~2~3~4~5$ 只有相邻两个数字之间存在交换，我们将交换的两个数字标为 $1$，其他位标为 $0$，可以产生下面的序列：
$$\left. \begin{array}{l} 0~0~0~0~0 \end{array} \right\} \rightarrow1\\ \left. \begin{array}{l} 0~0~0~1~1 \end{array} \right\} \rightarrow2\\ \left. \begin{array}{l} 0~0~1~1~0 \end{array} \right\} \rightarrow3\\ \left. \begin{array}{l} 0~1~1~0~0\\ 0~1~1~1~1 \end{array} \right\} \rightarrow4\\ \left. \begin{array}{l} 1~1~0~0~0\\ 1~1~0~1~1\\ 1~1~1~1~0 \end{array} \right\} \rightarrow5\\ $$
箭头右边的数字表示交换位置的数字的最高位（假设右边为最低位，且下标从 $1$ 开始），可以发现，数字 $4$ 对应的序列的最高两位都为 $1$，最低两位与数字 $1-2$ 对应的序列的最低两位相同，数字 $5$ 对应的序列的最高两位都为 $1$，最低三位与数字 $1-3$ 对应的序列的最低三位相同，再往后推（将 $n$ 扩大到 $6$ 或者更大）可以发现，数字 $x$ 对应的序列的最高两位总是 $1$，最低 $x-2$ 位与数字 $1$ 到 $x-2$ 对应的序列的最低 $x-2$ 位相同，如果我们将 $num_i$ 记为数字 $i$ 对应的序列个数，令 $sum_i=\sum_{j=1}^inum_j$，则 $sum_i=sum_{i-1}+num_i=sum_{i-1}+sum_{i-2}$，这正好是一个斐波那契数列，因此可以对斐波那契数列进行二分查找，找到需要交换的最高位的位置，交换后将 $k$ 减去 $sum_{i-1}$，继续二分查找，直到 $k=1$。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
typedef long long LL;
const int maxn = 100 + 100;
int n, cnt;
LL k;
int ans[maxn];
LL fib[maxn];
LL *it;
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    fib[0] = 1;
    fib[1] = 1;
    for(int i = 2; i < maxn; ++i) {
        fib[i] = fib[i - 1] + fib[i - 2];
        if(fib[i] > 1000000000000000000LL) {
            cnt = i;
            break;
        }
    }
    while(scanf("%d%I64d", &n, &k) != EOF) {
        for(int i = 1; i <= n; ++i) {
            ans[i] = i;
        }
        while(k > 1) {
            it = lower_bound(fib, fib + cnt, k);
            int pos = n - (it - fib) + 1;
            swap(ans[pos], ans[pos + 1]);
            --it;
            k -= *it;
        }
        for(int i = 1; i <= n; ++i) {
            if(i != 1) {
                printf(" ");
            }
            printf("%d", ans[i]);
        }
        printf("\n");
    }
    return 0;
}