当前位置: 首页 > 工具软件 > Flip! > 使用案例 >

【AT2689】Prime Flip

汲睿
2023-12-01

中文题面:洛谷AT2689(在讨论中有翻译)

解法:线性差分+二分图匹配

感觉这是道神题啊(还是因为我太弱了)
设最小翻转步数为 p p ,若只要翻转一段长度为 x 区间,那么根据哥德巴赫猜想:
1、若 x3 x ⩾ 3 为素数,那么 p=1 p = 1
2、若 x6 x ⩾ 6 为偶数,那么 p=2 p = 2
3、若 x9 x ⩾ 9 为奇非素数,那么 p=3 p = 3
4、若 x=4 x = 4 ,那么 p=2 p = 2 (翻转 [1,7] [ 1 , 7 ] [5,7] [ 5 , 7 ] ),归类到2。
5、若 x=2 x = 2 ,那么 p=2 p = 2 (翻转 [1,5] [ 1 , 5 ] [3,5] [ 3 , 5 ] ),归类到2。
6、若 x=1 x = 1 ,那么 p=3 p = 3 (翻转 [4,6] [ 4 , 6 ] [2,6] [ 2 , 6 ] [1,3] [ 1 , 3 ] ),归类到3。
对于每个要翻回的一段连续区间 [l,r] [ l , r ] l l r 放入两个桶中,两个桶分别装奇数与偶数。对于任意两个在不同桶中的数,若它们的差为奇素数,在它们之间连边,然后跑二分图匹配(匈牙利或dinic均可)。剩余未匹配到的数尽量选同一个桶中的两个数(差为偶数),这样最后只有两种可能性:两个桶均有一个数未被选择或两个数均无数未被选择(差分是成对的,所以两个桶中的数的个数之和一定为偶数),若有剩下的,则 AnsAns+3 A n s ← A n s + 3

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;

vector<int> prime,point[201],v1,v2;
int match[201],N,x,cnt;
bool check[10000001],rev[10000002],vis[201];

void sieve(){
    check[1]=true;for(int i=2;i<=10000000;++i){
        if(!check[i])prime.push_back(i);
        for(int j:prime){if(1ll*i*j>10000000)break;check[i*j]=true;if(i%j==0)break;}
    }
}

bool dfs(int x){
    for(int y:point[x])if(!vis[y]){vis[y]=true;if(match[y]<0||dfs(match[y])){match[y]=x;return true;}}
    return false;
}

int main(){
    sieve();
    scanf("%d",&N);for(int i=1;i<=N;++i)scanf("%d",&x),rev[x]^=true;
    for(int i=1;i<=10000001;++i)if(rev[i]!=rev[i-1])if(i&1)v1.push_back(i);else v2.push_back(i);
    for(int i=0;i<v1.size();++i)for(int j=0;j<v2.size();++j)if(!check[abs(v1[i]-v2[j])])point[i].push_back(j);
    memset(match,-1,sizeof(match));for(int i=0;i<v1.size();++i){memset(vis,false,sizeof(vis));if(dfs(i))++cnt;}
    printf("%d",cnt+(v1.size()-cnt>>1<<1)+(v2.size()-cnt>>1<<1)+((v1.size()-cnt)&1)*3);
}
 类似资料:

相关阅读

相关文章

相关问答