Snowfall 的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题要求重新排列数组，使乘积能被 $6$ ~6~ 整除的子数组数量最小。
核心解法是将所有被 $6$ ~6~ 整除的数放在一端，再将偶数（但不被 $3$ ~3~ 整除）与 $3$ ~3~ 的倍数（但不被 $2$ ~2~ 整除）分开，中间放置其他数，从而最小化同时包含 $2$ ~2~ 因子和 $3$ ~3~ 因子的子数组数量。

分析

核心观察

乘积能被 $6$ ~6~ 整除当且仅当子数组中至少有一个偶数（含因子 $2$ ~2~）且至少有一个 $3$ ~3~ 的倍数（含因子 $3$ ~3~）。
被 $6$ ~6~ 整除的数同时提供两种因子，包含它的任意子数组都满足条件，因此应集中放在一端以减少其参与的子数组数量。

思路

将每个数按因子分类：

$C$ ~C~：被 $6$ ~6~ 整除（提供因子 $2$ ~2~ 和 $3$ ~3~）；
$A$ ~A~：能被 $2$ ~2~ 整除但不能被 $3$ ~3~ 整除（仅提供因子 $2$ ~2~）；
$B$ ~B~：能被 $3$ ~3~ 整除但不能被 $2$ ~2~ 整除（仅提供因子 $3$ ~3~）；
$D$ ~D~：既不能被 $2$ ~2~ 整除也不能被 $3$ ~3~ 整除（不提供任何因子）。

设数量分别为 $c, a, b, d$ ~c, a, b, d~。

所有包含 $C$ ~C~ 的子数组一定满足条件。若将全部 $C$ ~C~ 连续放在数组的一端，则包含 $C$ ~C~ 的子数组数量最小，为：

$\displaystyle n(n+1)/2 - (n-c)(n-c+1)/2$

其中 $n$ ~n~ 为总长度。

不包含 $C$ ~C~ 的剩余部分长度为 $m = n-c$ ~m = n-c~，只由 $A, B, D$ ~A, B, D~ 组成。这部分中，满足条件的子数组必须同时包含至少一个 $A$ ~A~ 和一个 $B$ ~B~。对于任意 $A$ ~A~ 位置和 $B$ ~B~ 位置，它们之间（无论中间有什么）构成的子数组都满足条件，因此这类子数组数量至少为 $a \cdot b$ ~a \cdot b~。通过将全部 $A$ ~A~ 放在一侧、全部 $B$ ~B~ 放在另一侧，中间放置所有 $D$ ~D~，恰好达到这个下界。所以总最小数量为：

$\displaystyle \frac{n(n+1)}{2} - \frac{(n-c)(n-c+1)}{2} + a \cdot b$

具体示例

以样例 $1$ ~1~ 的数组 $[12,7,9,4,18,5]$ ~[12,7,9,4,18,5]~ 为例。分类得 $C=[12,18]$ ~C=[12,18]~（ $c=2$ ~c=2~）， $A=[4]$ ~A=[4]~（ $a=1$ ~a=1~）， $B=[9]$ ~B=[9]~（ $b=1$ ~b=1~）， $D=[7,5]$ ~D=[7,5]~（ $d=2$ ~d=2~）。采用排列 $[12,18,4,7,5,9]$ ~[12,18,4,7,5,9]~，包含 $C$ ~C~ 的子数组数量为总子数组数 $21$ ~21~ 减去不包含 $C$ ~C~ 的右侧部分 $[4,7,5,9]$ ~[4,7,5,9]~ 的子数组数 $10$ ~10~，即 $11$ ~11~；跨 $A-B$ ~A-B~ 的子数组数为 $a \times b = 1$ ~a \times b = 1~；总数为 $12$ ~12~，与样例一致。

算法步骤

读入测试用例数 $t$ ~t~。
对每个测试用例，读入 $n$ ~n~ 和数组 a。
创建四个列表：c_list, a_list, d_list, b_list。
遍历每个数 val：
- 若 val % 6 == 0，加入 c_list；
- 否则若 val % 2 == 0，加入 a_list；
- 否则若 val % 3 == 0，加入 b_list；
- 否则加入 d_list。
按顺序连接：c_list + a_list + d_list + b_list，并输出。

复杂度分析

时间复杂度： $O(n)$ ~O(n)~，每个测试用例遍历一次数组。
空间复杂度： $O(n)$ ~O(n)~，存储分类后的元素。

实现注意事项

分类条件按先后顺序：先判断是否能被 $6$ ~6~ 整除，否则再判断能被 $2$ ~2~ 整除等。
输出时元素间用空格分隔，行尾无多余空格。
使用快速 I/O 处理大量数据。

源代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> c, a, d, b;
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            if (x % 6 == 0) c.push_back(x);
            else if (x % 2 == 0) a.push_back(x);
            else if (x % 3 == 0) b.push_back(x);
            else d.push_back(x);
        }
        vector<int> ans;
        ans.insert(ans.end(), c.begin(), c.end());
        ans.insert(ans.end(), a.begin(), a.end());
        ans.insert(ans.end(), d.begin(), d.end());
        ans.insert(ans.end(), b.begin(), b.end());
        for (size_t i = 0; i < ans.size(); ++i) {
            if (i) cout << ' ';
            cout << ans[i];
        }
        cout << '\n';
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    idx = 1
    out_lines = []
    for _ in range(t):
        n = int(data[idx]); idx += 1
        c, a, d, b = [], [], [], []
        for _ in range(n):
            x = int(data[idx]); idx += 1
            if x % 6 == 0:
                c.append(x)
            elif x % 2 == 0:
                a.append(x)
            elif x % 3 == 0:
                b.append(x)
            else:
                d.append(x)
        ans = c + a + d + b
        out_lines.append(' '.join(map(str, ans)))
    sys.stdout.write('\n'.join(out_lines))

if __name__ == "__main__":
    main()

目前没有评论。