题解 | #素数伴侣#

#include <iostream>
#include <vector>
using namespace std;
/*
一看这题上来想是否能用动态规划，越想越觉得dp出来像是枚举而且还没法得出结论
看了其他大佬的解答，结合官方视频代码，搞了一个多小时终于搞懂了

解题思路：
首先明确一点，想获得素数对必须是：一个奇数加上一个偶数
根据奇偶划分成两堆点
以奇数点堆为锚定(也可用偶数，可灵活互换)
先将每个奇数点与每个偶数点一一匹配是素数对的标记true(G[i][j] == true)
接下来再按偶数点的下标开始遍历，以其每个下标j看是否有奇数占领
    遍历每个奇数点 下标i
        若下标j的偶数点暂未被占领且与目前i号奇数点匹配
        (若下标i的奇数点已有匹配且与目前j号偶数点匹配——让出该j号偶数点给后面的奇数点)
        ——将符合的奇数点都匹配上即 match[i] = j     
将占领的偶数点数统计即为所求
*/
int count = 0;
vector<int> odd;//奇数组
vector<int> even;//偶数组
vector<bool> prime(60010,true);//素数表

void getPrimeTable();//获取素数表
bool find(const int &n, vector<vector<bool> >& G, vector<int>& match, vector<bool>& visited );

int main() {
    int n;
    getPrimeTable();
    
    while (cin >> n) {
        int num;
        for(int i = 0; i < n; i++){
            cin >> num;
            if(num & 1) odd.push_back(num);//奇数
            else even.push_back(num);//偶数
        }

        if(odd.empty() || even.empty()){//素数对必是一奇+一偶，若奇数组或偶数组为空则无素数对
            cout << count << endl;
            return 0;
        }

        vector<vector<bool> > G(odd.size(),vector<bool>(even.size(),false));

        for(int i = 0; i < odd.size(); i++){//奇数与每个偶数匹配一次
            for(int j = 0; j < even.size(); j++){
                if(prime[odd[i] + even[j]]){//匹配是素数对
                    G[i][j] = true;//标记
                }
            }
        }
        
        vector<int> match(odd.size(), -1);//匹配结果数组        
        for(int j = 0; j < even.size(); j++){//针对每个偶数点
            vector<bool> visited(odd.size(), false);//每遍历一次偶数点初始化一次
            if(find(j,G,match,visited)) count++;
        }

        cout << count << endl;
    }
}

bool find(const int &j, vector<vector<bool> >& G, vector<int>& match, vector<bool>& visited ){
    for(int i = 0; i < odd.size(); i++){
        if(!visited[i] && G[i][j]){//如果奇数组中下标i的奇数点未被访问过且和下标j的偶数点匹配
            visited[i] = true;//避免后续重复访问
            if(match[i] == -1 || find(match[i], G, match, visited)){//如果i号奇数点暂未匹配 或者 之前匹配过那么就不参加该次匹配，让出该偶数点
                match[i] = j;
                return true;
            }
        }
    }
    return false;
}

void getPrimeTable(){//获取素数表,埃氏筛法在量级更大时比模更优秀
    for(int i = 2; i < 60010; i++){
        if(prime[i]){//如果未被筛过就是素数
            for(int j = i + i; j < 60010; j += i){//筛选目前素数的n倍的数，必不是素数
                prime[j] = false;
            }
        }
    }
}
// 64 位输出请用 printf("%lld")