📝 题目大意

给定 $N$ 个数，判断能否将它们重新排列，使得任意相邻两个数的乘积都是 $4$ 的倍数。

💡 解题思路

1. 题目分析：相邻两数乘积是 $4$ 的倍数，意味着这两个数所含的因子 $2$ 的个数之和至少为 $2$。按模 $4$ 和模 $2$ 的余数，可将所有数分为三类：

   • 4 的倍数（cnt[2]）：含至少 $2$ 个因子 $2$，与任何数相邻都满足条件。
   • 2 的倍数但不是 4 的倍数（cnt[1]）：含恰好 $1$ 个因子 $2$，只能与同类或 4 的倍数相邻。
   • 奇数（cnt[0]）：不含因子 $2$，只能与 4 的倍数相邻。

2. 算法推导：

   • Case 1：没有"2 的倍数但不是 4 的倍数"（cnt[1] == 0）
     此时只有 4 的倍数和奇数。奇数之间不能相邻，必须用 4 的倍数隔开。$cnt[0]$ 个奇数至少需要 $cnt[0] - 1$ 个 4 的倍数作为分隔符，因此条件为 cnt[2] + 1 >= cnt[0]。一种可行的构造方式为：4, 奇数, 4, 奇数, ..., 4（奇数结尾）或 奇数, 4, 奇数, 4, ..., 奇数（4 结尾）。

   • Case 2：存在"2 的倍数但不是 4 的倍数"（cnt[1] > 0）
     将所有 cnt[1] 个数聚成一个连续块，块内部任意相邻乘积均为 4 的倍数（$2 \times 2 = 4$）。该块的两端只需与 4 的倍数相邻即可。构造方式为：[cnt[1] 块], 4, 奇数, 4, 奇数, ..., 4, 奇数，其中每个奇数前都放置一个 4 的倍数。共需 cnt[0] 个 4 的倍数（每个奇数前一个），因此条件为 cnt[2] >= cnt[0]。

3. 边界与细节：

   • 当 $N = 1$ 时，没有相邻对，任何排列都满足条件。此时 cnt[1] == 0，cnt[2] + 1 >= cnt[0] 恒成立，输出 Yes。
   • 当所有数都是 2 的倍数但不是 4 的倍数（cnt[0] = 0, cnt[1] > 0, cnt[2] = 0）时，cnt[2] >= cnt[0] 即 $0 \ge 0$ 成立，输出 Yes。确实任意相邻乘积均为 4 的倍数。
   • 注意 cnt[2] + 1 >= cnt[0] 与 cnt[2] >= cnt[0] - 1 等价，但直接用 cnt[2] + 1 >= cnt[0] 可避免 cnt[0] = 0 时出现负数比较的歧义。

⏱️ 复杂度分析

• 时间复杂度：只需遍历 $N$ 个数一次，统计三类计数，每次操作 $O(1)$，总复杂度 $O(N)$。
• 空间复杂度：仅需常数大小的 cnt 数组（大小为 $3$）和若干临时变量，空间复杂度 $O(1)$。

💻 标准代码 (C++)

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    // cnt[0]: 奇数个数, cnt[1]: 2的倍数但不是4的倍数, cnt[2]: 4的倍数
    vector<int> cnt(3, 0);
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        if(a % 4 == 0) cnt[2]++;       // 4的倍数，含至少2个因子2
        else if(a % 2 == 0) cnt[1]++;  // 2的倍数但不是4的倍数，含恰好1个因子2
        else cnt[0]++;                  // 奇数，不含因子2
    }
    // 情况1：没有"仅含1个因子2"的数，需用4的倍数隔开所有奇数
    if(cnt[1] == 0 && cnt[2] + 1 >= cnt[0]) cout << "Yes" << endl;
    // 情况2：存在"仅含1个因子2"的数，可将它们聚成一个块，两端靠4的倍数
    else if(cnt[2] >= cnt[0]) cout << "Yes" << endl;
    else cout << "No" << endl;
}