【Atcoder】ARC 080 F

【算法】数论，二分图最大匹配

【题意】有无限张牌，给定n张面朝上的牌的坐标(N<=100)，其它牌面朝下，每次操作可以选定一个>=3的素数p，并翻转连续p张牌，求最少操作次数使所有牌向下。

【题解】

1.定义bi，当ai和ai-1的朝向相同时，bi=0，否则bi=1。特别的，a0朝向下。

则问题转化为：给定01序列b[]，每次选L(正数)和P(奇素数)，翻转b_L和b_P，求最少操作次数使序列全0。

这么转化的关键在于差分，对于区间翻转，区间内的点bi都不会变化，只有区间左端和区间右端+1变化，将区间差分为两点。

如此每次操作变成了对两点操作！大大简化了题目。

2.由于每次只能翻转2个数，考虑所有1之间的两两关系：

若|i-j|是一个奇素数，操作次数为1。

若|i-j|是一个偶数，操作次数为2。（不严格，此处的意思是一个偶数可以分解为两个奇素数的加减结果）

若|i-j|是一个奇合数(或1)，操作次数为3。（分解为偶数减奇素数的差）

素数与合数的关系通过手算小数据就可以得出，然后大胆推广到自然数范围内。

1的总数是偶数？证明：对于a[]中的一段1，b[]对应有2个1。

为什么每次处理两个1是最优的？感性理解：另外把0翻转成1没有收益，把1翻转成0不满足操作。

3.按照每个1所在位置是奇数和偶数分成两组m1,m2，同组内配对是偶数，不同组配对是奇数，定义k为两组配对产生的奇素数的对数。

ans=k*1+(m1-k)/2*2+(m2-k)/2*2+(m1-k)%2*3。

k为1次，剩余的组内配对为2次，最后各组有剩1个再配对为3次。

显然k要尽可能大，对两组建立二分图，差为奇素数连边，跑二分图最大匹配即可。

最坏复杂度O(n^3)。

#include<cstdio>

#include<cstring>

#include<queue>

#include<algorithm>

using namespace std;

const int maxn=,maxL=,inf=0x3f3f3f3f;

struct cyc{int v,flow,from;}e[maxn*maxn*];

int tot=,cnt,n,first[maxn],d[maxn],S,T,num[maxn],b[maxn],cur[maxn];

bool c[maxL];

inline int ab(int x){return x>?x:-x;}

bool isprime(int x){

    if(x<=)return ;

    for(int i=;i*i<=x;i++)if(x%i==)return ;

    return ;

}

void insert(int u,int v,int w){

    tot++;e[tot].v=v;e[tot].flow=w;e[tot].from=first[u];first[u]=tot;

    tot++;e[tot].v=u;e[tot].flow=;e[tot].from=first[v];first[v]=tot;

}

queue<int>q;

bool bfs(){

    memset(d,-,sizeof(d));

    q.push(S);d[S]=;

    while(!q.empty()){

        int x=q.front();q.pop();

        for(int i=first[x];i;i=e[i].from)

        if(d[e[i].v]==-&&e[i].flow){

            d[e[i].v]=d[x]+;

            q.push(e[i].v);

        }

    }

    return d[T]!=-;

}

int dinic(int x,int a){

    if(x==T||a==)return a;

    int f,flow=;

    for(int& i=cur[x];i;i=e[i].from)

    if(d[e[i].v]==d[x]+&&e[i].flow&&(f=dinic(e[i].v,min(a,e[i].flow)))>){

        e[i].flow-=f;

        e[i^].flow+=f;

        a-=f;

        flow+=f;

        if(a==)break;

    }

    return flow;

}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++){scanf("%d",&num[i]);c[num[i]]=;}

    for(int i=;i<=maxL-;i++)if(c[i]!=c[i-])b[++cnt]=i;

    S=;T=cnt+;

    int m1=;

    for(int i=;i<=cnt;i++)if(b[i]&){

        m1++;

        insert(S,i,);

        for(int j=;j<=cnt;j++)if(!(b[j]&)&&isprime(ab(b[i]-b[j])))insert(i,j,);

    }else{

        insert(i,T,);

    }

    int ans=;

    while(bfs()){

        for(int i=S;i<=T;i++)cur[i]=first[i];

        ans+=dinic(S,inf);

    }

    printf("%d",cnt-ans+(m1-ans)%);

    return ;

}

巴特西

【Atcoder】ARC 080 F - Prime Flip

最新文章

热门文章