25年8月20日个人赛题解

I题

首先看到题目数据范围很小，发现我们可以 的去检验任意两个数能不能同时被选中。这种关系很自然地让我们把这个题等价转换为 在一个无向图中，去选择顶点，有边相连的点不能同时选，这恰是二分图的等价定义！

那么现在的问题就是二分图中的最小点覆盖问题:我们想找到最少的一些点，使二分图所有的边都至少有一个端点在这些点之中。倒过来说就是，删除包含这些点的边，可以删掉所有边。
我们就是要删除最少的点，使得剩下的点没有边（即二者不能同时被选中）相连

然后上定理
König定理: 一个二分图中的最大匹配数等于这个图中的最小点覆盖数

那么本题答案总点数二分图中的最大匹配数 其实通过观察可以发现 奇偶性相同的数必然可以同时选中，我们可以利用这个预先处理一下二分图，分为两部，简化后边的运算次数
至于二分图中的最大匹配数可以用匈牙利算法解决
代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> g[505];
bool vis[505];
int p[505];
bool match(int u)
{
    for (auto kk : g[u])
    {
        if (vis[kk])
            continue;
        vis[kk] = true;
        if (p[kk] == 0 || match(p[kk]))
        {
            p[kk] = u;
            return true;
        }
    }
    return false;
}
void solve()
{
    int n, ans = 0;
    cin >> n;
    vector<int> a(n + 5);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if ((__gcd(a[i], a[j]) == 1) && (__gcd(a[i] + 1, a[j] + 1) == 1))
            {
                if (a[i] % 2 == 0)
                    g[i].push_back(j);
                else
                    g[j].push_back(i);
            }
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        memset(vis, 0, sizeof(vis));
        if (match(i))
            cnt++;
    }
    cout << n - cnt << '\n';
}
signed main()
{
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}