首页 > 其他分享 >【ARC080F】Prime Flip(二分图匹配,差分)

【ARC080F】Prime Flip(二分图匹配,差分)

时间:2022-10-28 18:46:01浏览次数:77  
标签:Prime prime cnt int ARC080F Flip 取反 偶数 textit

这种区间反转的题,套路就是差分。

设 \(a_i\) 表示第 \(i\) 枚硬币是否正面朝上,显然只有 \(a_{x_1},a_{x_2},\cdots,a_{x_n}\) 等于 \(1\),其他都是 \(0\)。那么我们的目标是把 \(a\) 数组全部变成 \(0\)。

设 \(b_i\) 表示第 \(i\) 枚硬币和第 \(i-1\) 枚硬币是否不同,即 \(b_i=a_i\operatorname{xor} a_{i-1}\)。那么我们的目标就变成了把 \(b\) 数组全部变成 \(0\),即让每个数都相同。

设 \(\textit{prime}\) 为所有奇数质数的集合,\(p\in \textit{prime}\),那么一次反转可以看做将 \(a_i\sim a_{i+p-1}\) 全部取反。

发现将 \(a_i\sim a_{i+p-1}\) 取反后其实等价于 \(b_i\) 和 \(b_{i+p}\) 两个数取反。

所以现在操作就变成了:任意选择两个正整数 \(i,j\),且满足 \(j-i\in\textit{prime}\),然后将 \(b_i\) 和 \(b_j\) 取反。

然后在所有值为枚举满足 \(b_i=b_j=1\) 的任意一对 \(i,j\)(\(i<j\)),考虑如何操作才能将 \(b_i\) 和 \(b_j\) 都变为 \(0\) 且操作数最少,分情况讨论:

  1. \(j-i\in\textit{prime}\)。此时我们可以直接将 \(b_i\) 和 \(b_j\) 变为 \(0\),共 \(1\) 次操作。

  2. \(j-i\) 为正偶数。

    那么当 \(j-i=2\) 时,我们可以对 \(b_i\)、\(b_{i+5}\) 取反,然后再对 \(b_{i+2}\)、\(b_{i+5}\) 取反,共 \(2\) 次操作;

    当 \(j-i=4\) 时,我们可以对 \(b_i\)、\(b_{i+7}\) 取反,然后再对 \(b_{i+4}\)、\(b_{i+7}\) 取反,共 \(2\) 次操作;

    当 \(j-i\) 为其他正偶数时,由哥德巴赫猜想在 \(10^7\) 范围内的正确性,可知 \(j-i\) 可以分为两个奇质数的和。即存在 \(p_1+p_2=j-i\),且 \(p_1,p_2\in\textit{prime}\)。那么我们可以对 \(b_i\)、\(b_{i+p_1}\) 取反,然后再对 \(b_{i+p_1}\)、\(b_{i+p_1+p_2}\) 取反,共 \(2\) 次操作。

    综述,当 \(j-i\) 为正偶数时,最小的操作数都是 \(2\) 次。\((2)\)

  3. \(j-i\) 为除 \(\textit{prime}\) 以外的正奇数。

    当 \(j-i=1\) 时,我们可以对 \(b_i\)、\(b_{i+7}\) 取反,然后对 \(b_{i+4}\)、\(b_{i+7}\) 取反,对 \(b_{i+1}\)、\(b_{i+4}\) 取反,共 \(3\) 次操作。

    类似地,可知当 \(j-i=3\) 时,也存在一种方案且最小操作数为 \(3\)。

    当 \(j-i\) 为其他正奇数时,即 \(j-i>3\) 且 \(j-i\) 为奇数时,我们可以将 \(j-i\) 分解成 “\(3+\text{正偶数}\)” 的形式,然后再由 \((2)\) 得此时最少的操作数为 \(3\) 次。

    综述,当 \(j-i\) 为除 \(\textit{prime}\) 以外的正奇数时,最小的操作数都是 \(3\) 次。

所以为了使得操作数最少,我们应该优先使用第 \(1\) 种情况。

设有 \(k\) 个 \(b_i=1\),并且将他们的下标用集合 \(S=\{c_1,c_2,\cdots,c_k\}\) 表示。

那么 \(k\) 肯定是偶数,因为考虑将 \(a_i\) 中连续的 \(1\) 当做一个块。那么对于每个块 \(a_{\textit{head}}\sim a_{\textit{tail}}\),块头贡献一个 \(b_{\textit{head}}=1\),块尾贡献一个 \(b_{\textit{tail}+1}\),所以总贡献就是偶数个。

发现如果有 \(c_i-c_j\in\textit{prime}\),那么 \(c_i\) 和 \(c_j\) 的奇偶性必定不同。

于是想到将 \(c_i\) 奇偶分类,并对于所有的 \(c_i-c_j\in\textit{prime}\),连边 \((i,j)\),那么这就是一个二分图的形式。

显然对这个二分图跑最大匹配就是第 \(1\) 种情况的最多使用数。

将这些点取反之后,还剩下一些点需要取反,于是考虑使用第 \(2\) 种情况。

显然,若 \(c_i-c_j\) 为正偶数,那么 \(c_i\) 和 \(c_j\) 的奇偶性相同。

所以将奇类中剩下的 \(c_i\) 进行两两取反,将偶类中剩下的 \(c_i\) 进行两两取反。

然后再考虑第 \(3\) 种情况,此时奇类和偶类肯定要么都剩下 \(0\) 个未取反、要么都剩下 \(1\) 个未取反,因为 \(k\) 为偶数。然后对于各剩下 \(1\) 个未取反的情况下,将他们两个按第 \(3\) 种情况处理。

将 \(3\) 种情况的总操作数加起来,就是最后的答案了。

代码如下:

#include<bits/stdc++.h>

#define N 110
#define INF 0x7fffffff

using namespace std;

int n,a[N];
int tot,odd,b[N<<1];
int cnt=1,head[N<<1],cur[N<<1],nxt[N*N*8+N*4],to[N*N*8+N*4],c[N*N*8+N*4];
int s,t,num[N<<1];

queue<int>q;

void adde(int u,int v,int ci)
{
	to[++cnt]=v;
	c[cnt]=ci;
	nxt[cnt]=head[u];
	head[u]=cnt;
	
	to[++cnt]=u;
	c[cnt]=0;
	nxt[cnt]=head[v];
	head[v]=cnt;
}

bool check(int x)//判断一个数是否属于prime
{
	if(x<=2) return false;
	if(!(x&1)) return false;
	for(int i=2,maxn=sqrt(x);i<=maxn;i++)
		if(!(x%i)) return false;
	return true;
}

bool bfs()
{
	memcpy(cur,head,sizeof(cur));
	memset(num,-1,sizeof(num));
	q.push(s);
	num[s]=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=nxt[i])
		{
			int v=to[i];
			if(c[i]&&num[v]==-1)
			{
				num[v]=num[u]+1;
				q.push(v);
			}
		}
	}
	return num[t]!=-1;
}

int dfs(int u,int minflow)
{
	if(u==t||!minflow) return minflow;
	int preflow=0,nowflow;
	for(int i=cur[u];i;i=nxt[i])
	{
		cur[u]=i;
		int v=to[i];
		if(num[v]==num[u]+1&&(nowflow=dfs(v,min(c[i],minflow-preflow))))
		{
			preflow+=nowflow;
			c[i]-=nowflow;
			c[i^1]+=nowflow;
			if(!(minflow-preflow)) break;
		}
	}
	return preflow;
}

int dinic()//用dinic跑最大匹配
{
	int maxflow=0;
	while(bfs())
		maxflow+=dfs(s,INF);
	return maxflow;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	b[++tot]=a[1];
	for(int i=2;i<=n;i++)
	{
		if(a[i]-a[i-1]>1)
		{
			b[++tot]=a[i-1]+1;//块尾贡献
			b[++tot]=a[i];//块头贡献
		}
	}
	b[++tot]=a[n]+1;
	s=1,t=1+tot+1;
	for(int i=1;i<=tot;i++)
	{
		if(b[i]&1)
		{
			odd++;
			adde(s,1+i,1);
			for(int j=1;j<=tot;j++)
				if(check(abs(b[i]-b[j]))) adde(1+i,1+j,1);
		}
		else adde(1+i,t,1);
	}
	int sum1=dinic();
	printf("%d\n",sum1+(odd-sum1)/2*2+((tot-odd)-sum1)/2*2+((odd-sum1)&1)*3);
	return 0;
}

标签:Prime,prime,cnt,int,ARC080F,Flip,取反,偶数,textit
From: https://www.cnblogs.com/ez-lcw/p/16837094.html

相关文章

  • How many prime numbers
    题目链接Howmanyprimenumbers大素数的判定解题思路miller_rabinmiller_rabin是一种概率性素数测试,原理基于费马素数测试,即如果\(n\)为素数,则在\(1\simn\)......
  • HDU 4135 Co-prime
    题目链接:​​传送门​​多组数据问区间内与互质的数的个数区间问题显然要转化成两个区间相减的问题也就是的答案减去的答案这里反过来求不互质的数的个数筛法可以提示我......
  • Prime Factors (25)
    题目描述GivenanypositiveintegerN,youaresupposedtofindallofitsprimefactors,andwritethemintheformatN=p1^k1*p2^k2*...*pm^km.输入描述:......
  • [ARC081F] Flip and Rectangles
    考虑转换题目给出的条件。可以观察到一些性质若某个矩形能被操作为全\(1\),那么其任意子矩形也一定可以。任意行列交换不影响矩阵是否能变为全\(1\)然后重要的来了......
  • AtCoder Beginner Contest 263 Erasing Prime Pairs
    AtCoder传送门洛谷传送门题意有\(i\)种数,第\(i\)种数是\(a_i\),有\(b_i\)个。每次可以选择两个数\(x,y\)满足\(x+y\)为质数,将它们删除。问最多能删多少次。......
  • C++Primer笔记
    数据类型类型转换当赋给无符号类型一个超出它表示范围的值时,结果是初始值对无符号类型所能表示数值的总数取模之后的余数,例如:8bit的unsignedchar可以表示0至255这256个......
  • [Typescript] 56. Medium - Flip Arguments
    Implementthetypeversionoflodash's _.flip.Type FlipArguments<T> requiresfunctiontype T andreturnsanewfunctiontypewhichhasthesamereturnty......
  • C++ Primer 15.9文本查找程序
    可以通过查询语句的组合进行检索,VS2015.main函数,读取存有数据的文件,进行检索。提供两种入口。查词,与按照表达式查询。1#include<iostream>2#include<fstream>3......
  • [LeetCode] 1318. Minimum Flips to Make a OR b Equal to c 或运算的最小翻转次数
    Given3positivesnumbers a, b and c.Returntheminimumflipsrequiredinsomebitsof a and b tomake( a OR b == c ).(bitwiseORoperation).......
  • C++ Primer Plus学习笔记之开始学习C++
    前言个人觉得学习编程最有效的方法是阅读专业的书籍,通过阅读专业书籍可以构建更加系统化的知识体系。一直以来都很想深入学习一下C++,将其作为自己的主力开发语言。现在为......