think-cell Round 1

Permutation Printing

题目

输入一个整数 \(n\)，输出长度为 \(n\) 的排列，满足不存在两个不同的索引 \(1\leq i,j< n\)，使得 \(p_{i}\) 整除 \(p_{j}\) 且 \(p_{i+1}\) 整除 \(p_{j+1}\)。

数据范围：\(3\leq n\leq 10^{5}\)。

思路

可以构造排列 \(1,n,2,n-1,\dots,\lceil\frac{n+1}{2}\rceil\)。如果 \(i<j\)，则有 \(p_{i+1}>p_{j+1}\)，必定不能整除，反之亦然。

代码

public static void solve() {
    int n = io.nextInt();
    int l = 1, r = n;
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            io.print(l++ + " ");
        } else {
            io.print(r-- + " ");
        }
    }
    io.println();
}

Lexicographically Largest

题目

输入长度为 \(n\) 的数组 \(a\)，初始时有一个空集 \(S\)，执行以下三步操作恰好 \(n\) 次：

• 选择一个索引 \(i\)，\(1\leq i\leq |a|\)。
• 将 \(a_{i}+i\) 插入集合 \(S\)。
• 从 \(a\) 中删除 \(a_{i}\)，\(a_{i}\) 之后的所有元素的索引将减少 \(1\)。

将得到的集合 \(S\) 中的元素按照递减顺序排列，输出能够得到的字典序最大的排列。

数据范围：\(1\leq n\leq 3\cdot 10^{5}\)，\(1\leq a_{i}\leq 10^{9}\)。

思路

可以发现字典序最大的排列总是包含 \(n\) 个元素。暴力的想法是，可以首先将所有 \(a_{i}+i\) 从小到大排序，我们总是优先选择最大的元素，如果有多个元素最大，就优先选择其中索引 \(i\) 最小的元素，从而可以保证得到字典序最大的排列。通过观察可以发现，如果从小到大排列 \(a_{i}+i\)，然后倒序遍历数组，我们可以得到的最大元素为 \(\min(a[i],a[i+1]-1)\)，对所有 \(1\leq i< n\) 都成立。比赛时没发现，使用的是更复杂的方法，其实不难。

public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
        a[i] += i + 1;
    }
    Arrays.sort(a);
    for (int i = n - 2; i >= 0; i--) {
        a[i] = Math.min(a[i], a[i + 1] - 1);
    }
    for (int i = n - 1; i >= 0; i--) {
        io.print(a[i] + " ");
    }
    io.println();
}

Sum over all Substrings (Hard Version)

题目

输入长度为 \(n\) 的二进制字符串 \(s\)，输出 \(\sum_{i=1}^{n}\sum_{j=i}^{n}f(s_{i}s_{i+1}\cdots s_{j})\)。对于某个二进制模式串 \(p\)，\(f(p)\) 表示满足以下条件的二进制字符串 \(q\)，其中 \(1\) 的最小可能数量：假设 \(p\) 和 \(q\) 的长度均为 \(m\)，对于所有 \(1\leq i\leq m\)，存在 \(l\) 和 \(r\)（\(1\leq l\leq i\leq r\leq m\)），使得 \(p_{i}\) 在 \(q_{l}q_{l+1}\cdots q_{r}\) 中的出现次数至少为 \(\lceil \frac{m}{2}\rceil\)。

数据范围：\(1\leq n\leq 10^{6}\)。

思路

暴力的想法是枚举所有子串，然后对于每个子串计算 \(f\) 值。现在思考对于给定的 \(p\)，如何计算 \(f\) 值。正序遍历子串，基本算法如下：如果 \(p_{i}=0\)，则直接在 \(q_{i}\) 放置 \(0\)；如果 \(p_{i}=1\)，则可以在 \(q_{i+1}\) 放置 \(1\)，\(q_{i}\) 和 \(q_{i+2}\) 放置 \(0\)，从而不论 \(p_{i+1}\) 和 \(p_{i+2}\) 是什么，都存在满足条件的 \(l\) 和 \(r\)（在区间 \([i,i+2]\) 范围内）。时间复杂度为 \(O(n^{3})\)，如果在遍历的同时计算子串，则时间复杂度为 \(O(n^{2})\)。可以使用动态规划将时间复杂度降低为 \(O(n)\)，定义 \(dp_{i}\) 表示 \(\sum_{j=i}^{n}f(s_{i}s_{i+1}\cdots s_{j})\)，转移方程见代码。

代码

public static void solve() {
    int n = io.nextInt();
    char[] s = io.next().toCharArray();

    long ans = 0L;
    long[] dp = new long[n + 3];
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '1') {
            dp[i] = dp[i + 3] + n - i;
        } else {
            dp[i] = dp[i + 1];
        }
        ans += dp[i];
    }
    io.println(ans);
}