cf1725 H. Hot Black Hot White（魔幻数论+构造）

妙妙题

题意

有 $N$（偶数） 个石头，每个石头具有权值，现需要对这些石头涂色，使一半为黑色一半为白色。

对于不同色的石头，定义反应公式如下：

$W=concat(Ai,Aj)\times concat(Aj,Ai)+Ai\times Aj$

其中 $concat(x,y)$ 表示不改变顺序直接将x，y拼接，即 $concat(10,24)=1024$

你可以在 $[0,2]$ 区间中选取一个数作为 $Z$，使得对于所有不同色的石头，其反应值模 $3$ 均不等于 $Z$。求选定的 $Z$ 值，并构造出一种涂色方案。

---

官方推导过程如下：

由上述推导可以看出，先取模再反应得到的最终结果不变，因此对于给定的每个权值，可以先模 3 进行考虑，此时存在三种情况：

$0$ 与 $1/2=1$

$0$ 与 $0=0$

$1/2$ 与 $1/2=2$

对所有权值 $\%3=0$ 和 $\%3!=0$ 分别计数，当等于 $0$ 的权值更多时，令 $Z=2$ ，并优先给所有不等于 $0$ 的权值进行同色处理，剩余颜色对等于 $0$ 的权值随意分配，此时可保证所有不等于 $0$ 的权值因为同色而无法反应，而 $0$ 与任何非同色反应都不会得到 $Z=2$ 的结果。同理当等于 $0$ 的权值更少时，令 $Z=0$，并优先给所有等于 $0$ 的权值进行同色处理，剩余颜色对其他不等于 $0$ 的权值随意分配。

---

参考代码

#include 
#define itn int
#define int long long
#define endl "\n"
#define PII pair<int, int>
using namespace std;
const int N = 2e5 + 10;
const itn inf = 0x3f3f3f3f;
const int mod = 998244353;

int a[N], col[N];

void solve() {
    int n;
    cin >> n;
    int sum1 = 0, sum2 = 0;
    // sum1-0  sum2-非0
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] %= 3;
        if (a[i] == 0)
            sum1++;
        else
            sum2++;
    }
    //取模最后同余答案不变
    //模3=0的数和其他任何数反应 都同余1
    // 1-1 1-2 2-2 组合都同余2
    // 0-0 同余0
    int cnt = n / 2;
    if (sum1 > sum2) {  // 0数目多 保证非0同色
        cout << 2 << endl;
        cnt -= sum2;
        for (int i = 1; i <= n; i++) {
            if (a[i] == 0 && cnt) {
                cout << 0;
                cnt--;
            } else if (a[i] == 0 && cnt == 0)
                cout << 1;
            else if (a[i] != 0)
                cout << 0;
        }
    } else {  //保证0同色
        cout << 0 << endl;
        cnt -= sum1;
        for (int i = 1; i <= n; i++) {
            if (a[i] == 0)
                cout << 0;
            else if (a[i] != 0 && cnt) {
                cout << 0;
                cnt--;
            } else if (a[i] != 0 && cnt == 0) {
                cout << 1;
            }
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(12);
    // init();
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++) {
        // cout << "Case #" << i << ": ";
        solve();
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70