题目链接：https://codeforces.com/contest/1368/problem/B

题意

构造最短的至少含有 $k$ 个 $codeforces$ 子序列的字符串。

题解

如下表：

	c	o	d	e	f	o	r	c	e	s	子序列个数
个数	1	1	1	1	1	1	1	1	1	1	$1^{10}$
	2	2	2	2	2	2	2	2	2	2	$2^{10}$
	3	3	3	3	3	3	3	3	3	3	$3^{10}$

依次构造每个字符的个数即可。

证明

	c	o	d	e	f	o	r	c	e	s	子序列个数
个数	2	2	1	1	1	1	1	1	1	1	$4$
	2	3	1	1	1	1	1	1	1	1	$6$
	2	2	2	1	1	1	1	1	1	1	$8$

向第一行的构造方案中再添加一个字符有第二、三行两种方式，显然第三行的方式子序列更多。

因为第二行增加的是 $2 \times 1^8$，第三行增加的是 $2^2 \times 1^7$，即每增加一个字符增加子序列个数的为其他字符个数的乘积，所以每个字符的个数一定会如上表依次增大。

代码

C++

#include <bits/stdc++.h>

using ll = long long;

using namespace std;

string s = "codeforces";

int main() {

    ll k; cin >> k;

    vector<int> cnt(10, 1);

    ll tot = 1;

    for (int loop = 2; tot < k; loop++) {

        for (int j = 0; j < 10; j++) {

            if (tot < k) {

                tot = tot / cnt[j] * loop;

                cnt[j] = loop; //同cnt[j]++

            }

        }

    }

    for (int i = 0; i < 10; i++)

        cout << string(cnt[i], s[i]);

}

Python3

from functools import reduce

s = "codeforces"

a = [0] * 10

k = int(input())

p = 0

while reduce(lambda x, y : x * y, a) < k:

    a[p % 10] += 1;

    p += 1

for i in range(10):

    print(s[i] * a[i], end = "")

巴特西

Codeforces Global Round 8 B. Codeforces Subsequences（构造）

题意

题解

证明

代码

C++

Python3

最新文章

热门文章