题解归档 - cf2227C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2227C
• 本地来源：problems/cf2227C/idea.md
• 题目链接：https://codeforces.com/contest/2227/problem/C
• 原始标题：cf2227C - Snowfall

思路

cf2227C - Snowfall

pattern: constructive grouping by divisibility mask.

claim: classify each number as 0 neither, 1 divisible by 2 only, 2 divisible by 3 only, 3 divisible by 6. Any subarray containing a mask 3 is counted, so all such values should be a single block at an edge. In the remaining suffix, a counted subarray needs both mask 1 and mask 2; placing all mask 0 values between these two groups minimizes this to exactly cnt1 * cnt2, the unavoidable interval for each cross pair.

construction: output mask3, mask1, mask0, mask2.

check: same optimum form as the samples; group order within each class is irrelevant.

代码

来源：problems/cf2227C/solution.cpp

/* Author: likely
 * Time: 2026-06-27
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<ll> g[4];
        for(int i=0;i<n;i++){
            ll x;
            cin>>x;
            int mask=0;
            if(x%2==0) mask|=1;
            if(x%3==0) mask|=2;
            g[mask].push_back(x);
        }
        vector<ll> ans;
        for(ll x:g[3]) ans.push_back(x);
        for(ll x:g[1]) ans.push_back(x);
        for(ll x:g[0]) ans.push_back(x);
        for(ll x:g[2]) ans.push_back(x);
        for(int i=0;i<n;i++){
            if(i) cout<<" ";
            cout<<ans[i];
        }
        cout<<"\n";
    }
    return 0;
}