H. Hot Black Hot White

题目：

思路：

式子化简 + 找规律

我们首先要知道 ，且，而 concat 这个函数无非就是在 ai 和 aj 前乘上了 100...，所以我们可以将原式化简为

1000...*a[i] * 1000...*a[j] + a[i]*a[j]  Z mod 3

根据上诉结论，进一步化简可得

将前式子拆解，得

由于有一个 3，那么就可以直接消去，即最后可得

所以我们观察到最后的结果只和 a[i]² 有关，不难发现，一个数的平方 mod 3 的结果只能是 0 or 1（这里假设 x 为 3*k + 0/1/2 然后平方计算即可看出），所以我们将 a[i]² mod 3 的结果进行分组

这里我们将 0/1 代表余数为 0/1 的数，那么最后就有三种情况

①.0 = 1，那么此时0黑，1白即可，这样任意选两个最后余数相加都是 1，此时 Z 可选 0 or 2

②.0 > 1，此时 0 多，那么肯定会将 0 的一部分分给白，此时白既有 0 又有 1，此时配对结果就有 0 + 0 或 0 + 1，此时 Z 只能选 2

③.0 < 1，同上，此时黑有 1 和 0，配对结果就有 1 + 1 或 1 + 0，此时 Z 只能选 0

综上我们模拟即可，具体看代码

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n),cnt(2,0),color(n,0);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        int yu = a[i] * a[i] % 3;
        cnt[yu]++;
        color[i] = yu;
    }
    if(cnt[0] <= cnt[1])
    {
        cout << "0\n";
        for (int i = 0; i < n; i++)
        {
            if(cnt[0] != cnt[1])
            {
                if(color[i] == 1) color[i] = 0,cnt[1]--,cnt[0]++;
            }    
        }
    }
    else
    {
        cout << "2\n";
        for (int i = 0; i < n; i++)
        {
            if(cnt[0] != cnt[1])
            {
                if(color[i] == 0) color[i] = 1,cnt[1]++,cnt[0]--;
            }    
        }
    }
    for (int i = 0; i < n; i++)
        cout << color[i];
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}

---

M. Moving Both Hands

题目：

思路：

遇到的新型分层图

我们发现这是一个有向图，那么要将两只手移动到同一个端点，我们就有两种操作方式

①.只移动其中一只手

②.两只都移动

那么显然对于有向图第一种方法很多情况下是无法完成的，所以考虑如何两只手都移动该怎么走

显然我们如果对于 节点1 跑一边最短路，然后对其余所有节点也都跑一遍最短路，这种方法显然会超时，所以我们考虑优化

我们利用分层图的思想，我们将另一个点的移动过程也交给 节点1 完成，具体的，我们将每一条边反向，这样就相当于其余节点走向 节点1 的过程变为了 节点1 自己走了

即第一层为正向图，第二层为反向图，那么我们就可以在第一层到第二层建一条权值为 0 的边，但是不能往第二层往第一层再建一条边，否则所有边就都变成无向边了

具体实现看代码

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

void solve()
{
    int n,m;
    cin >> n >> m;
    vector<vector<pair<int,int>>> g(2*n+1);
    vector<int> dis(2*n+1,1e18);
    for (int i = 0; i < m; i++)
    {
        int u,v,w;
        cin >> u >> v >> w;
        g[u].push_back({v,w});
        g[v+n].push_back({u+n,w});
    }
    for (int i = 1; i <= n; i++)
    {
        g[i].push_back({i+n,0});
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
    dis[1] = 0;
    pq.push({0,1});
    while (!pq.empty())
    {
        auto [val,fa] = pq.top();
        pq.pop();
        if(val > dis[fa]) continue;
        for(auto & [son,w] : g[fa])
        {
            if(dis[son] > val + w)
            {
                dis[son] = val+w;
                pq.push({dis[son],son});
            }
        }
    }
    for (int i = 2; i <= n; i++)
    {
        cout << (dis[i+n] == 1e18 ? -1 : dis[i+n]) << " ";
    } 
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}