Codeforces 1368B: Codeforces Subsequences

原帖:https://blog.imakiseki.cf/acmoi/codeforces/1368b/

连续发了几个题解,挑了篇调试时间相对比较长、数学推导相对比较多的题目。

PS: 博客用的是 KaTeX,有的公式不支持,但这里使用 MathJax 就可以正常显示。


Codeforces 1368B C++ 和 Python 一解.

终于看到一道比较有趣的 constructive algorithm 的题目了.

分析

本题是 “乘法原理” 的经典应用之一: 每一个内容为 codeforces 子序列都需要在源串中各选择十个字符连续重复的字符串 (指连续的 c, o, d 等十个字符串) 中的一个字符. 若假定源串 sc, o, d 等字符各连续重复 a_0,a_1,a_2,\cdots,a_9 次, 则最终能生成的 codeforces 子序列共有 l=a_0a_1a_2\cdots a_9 个. 而为满足题意, 需要选择合适的 a_0,a_1,a_2,\cdots,a_9, 使得 l\geq kL=a_0+a_1+a_2+\cdots+a_9 尽可能小.

一种贪心的策略

我们知道, 根据均值不等式, 对于长度为 n 的正有限实数列 \{a_i\}, 有

\sqrt[n]{\prod^{n}_{i=1}{a_i}}\leq\sum^{n}_{i=1}{a_i},

当且仅当 \{a_i\} 是常数列时取等号. 对于本题, 可以猜想: 当左式恒定, 即 l 恒定时, 若要使右式 (也即 L) 尽可能小, 则需要选择相差不大的 a_i(i=0,1,\cdots,9). 这即是一种贪心策略.

我们希望 a_i 的极差尽可能小, 一种选择方法是令其中一部分 a_i 比另一部分恰好大 1 (当然理想情况是这些 a_i 都相等). 不妨假设 a_0,a_1,\cdots,a_{m-1} (m=0,1,\cdots,10, 当 m=0 时规定 a_i=a, 当 m=10 时规定 a_i=a+1) 都等于 a+1(a\in\mathbb{N}^{*}), a_m,a_{m+1},\cdots,a_9 都等于 a. 那么

l=(a+1)^{10-m}a^m,\\ L=(10-m)(a+1)+ma=10a-m+10.

am 的确定

首先我们关注 m=10l=a^{10} 的情况. 注意到此时若要使 l\geq k, 则 a\geq\sqrt[10]{k}.

而当 a 固定时, 对于不同的 m, 有 \sup l=(a+1)^{10}, \inf l=a^{10}, 且考虑到当 a_p>a_q 时恒有 \left.L\right|_{a=a_p}\geq\left.L\right|_{a=a_q}, 则 a 可以选取 \lfloor\sqrt[10]{k}\rfloor.

对于 m, 理论上根据 l\geq k 可以推导得到 m\leq\dfrac{10\ln(a+1)-\ln k}{\ln(a+1)-\ln a}, 但在实际编程中考虑到浮点数存在的误差 (直接用此式计算无法通过 Codeforces 测试集), 我们需要利用大整数 (long long unsigned 足够) 从 m=0m=10 开始逐个测试 (理论上也可以使用二分查找, 但本题的数据规模下不必要), 直到找到符合要求的 m. 为方便起见, 确定 a 的过程依然使用了对数法, 同时为尽可能保证计算准确, 代码中使用了自定义的下取整函数 better_floor().

在 Python 中, 考虑到其原生支持处理超长整数, 对上述推导公式修改为 k(a+1)^m\leq a^m(a+1)^{10}, 同样可以达到题意所需要求, 而这式两边即对应下述代码中的 leftright.

代码

C++

#include <cmath>
#include <cstring>
#include <iostream>
#define EPS (1e-14)

using namespace std;

const string base("codeforces");

double better_floor(double x)
{
    double y = ceil(x);
    
    return (y - x < EPS ? y : floor(x));
}

int calc_m(long long unsigned k, int a)
{
    long long unsigned l = 1;
    int m = 10;

    for (int i = 0; i < m; ++i)
    {
        l *= a;
    }
    while (l < k && m-- >= 0)
    {
        l = l * (a + 1) / a;
    }

    return m;
}

int main()
{
    long long unsigned k;
    int a, m;

    cin >> k;

    a = int(better_floor(pow(k, 0.1)));
    m = calc_m(k, a);

    for (int i = 0; i < 10 - m; ++i)
    {
        cout << string(a + 1, base[i]);
    }
    for (int i = 10 - m; i < 10; ++i)
    {
        cout << string(a, base[i]);
    }

    return 0;
}

Python

def calc_m3(k, a):
    left, right = k, (a + 1) ** 10
    for i in range(1, 12):
        left *= a + 1
        right *= a
        if left > right:
            return i - 1
    return -1

k = int(input())

base = 'codeforces'
a = int(k ** 0.1)
m = calc_m3(k, a)
for i in range(10 - m):
    print(base[i] * (a + 1), end='')
for i in range(10 - m, 10):
    print(base[i] * a, end='')
1 Like