题解：P12551 [UOI 2025] Simple Task

序列其实是假的，就是集合。接下来称最少的和为质数的子序列数为答案。

题意等价于一次操作可以删掉两个数

x,y

加入

x+y

，求恰好操作

n-k

次使得集合中质数尽可能少的方案数。称这个操作为合并。

跟着子任务分析。子任务三和正解关系不大，略。下面默认后面的子任务已经判掉了前面的子任务。

子任务一 $k=1$

全部加起来判和是否为质数即可。

子任务六 $2k\ge n+1$

你发现每次合并至多减少两个质数，所以答案的下界是

n-2(n-k)=2k-n

和

0

取

\max

。当然在这个子任务下界直接就是

2k-n

。

你发现我们每次合并要么取两个

2

要么取两个奇质数就可以做到每次质数个数

-2

了。由于

2k\ge n+1

我们可以一直这样合并，所以可以取到下界。

子任务二 $n\le 4$

判掉子任务一、六，只需要考虑

n=4,k=2

。枚举两个分一组的

3

种情况，取答案最小的划分方式即可。

由于

4

个元素中一定存在两个奇偶性相同，把这两个合并剩下两个合并答案至多为

1

。而一组

3

个一组

1

个答案至少为

1

，所以不需要考虑一组三个一组一个。

子任务四 $2|n,a_i>2$

下面认为

1<k\le\lfloor\dfrac n 2\rfloor,n\ge 5

。由于

n

是偶数可以加强成

n\ge 6

。

由于现在全部都是奇数，可以直接先把奇数两两合并，没有奇数了随意合并，答案可以取到

0

。

子任务七 $2|n$

现在多了

2

怎么办？

我们对

2

个数的奇偶性分类。

若

2

有偶数个，由于

2|n

，因此奇质数也有偶数个。把奇质数两两合并，

2

两两合并，剩下的随意合并可以让答案取到

0

。

若

2

有奇数个，我们尝试找到一个奇质数

x

，使得

x+2

为合数。

如果我们找到了这样的

x

，则合并

2,x

，剩下的奇质数两两合并，

2

两两合并。此时只有一个元素是奇合数，其他都是偶数。因为

k>1

，最后至少可以剩下两个元素。把偶数随意合并，答案可以取到下界

0

。

如果我们找不到这样的

x

，那么我们继续分类。

若

k=\dfrac n 2

，你把一个

2

和随便一个奇质数合并，剩下的和上面一样做，得到答案为

1

。不难发现答案无法等于

0

。

否则，至少可以合并

\dfrac{n+2}2

次。我们先进行

\dfrac{n+2}2

次合并，有如下四种情况：

至少有 $3$ 个 $2$ 和 $1$ 个 $3$ 。这时可以用 $3$ 次合并把这四个数变成 $9$ ，然后剩下 $n-4$ 个数 $2$ 和奇质数分别两两合并。共合并 $\dfrac{n+2}2$ 次。
至少有 $5$ 个 $2$ 。由于不存在元素 $x$ 使得 $x+2$ 为合数，故 $a$ 中所有奇质数 $x$ 均满足 $x\equiv 2\pmod 3$ （因为模 $3$ 余 $1$ 则 $+2$ 为合数）或 $x=3$ 。刚刚已经判掉了有 $3$ 的情况，因此现在没有 $3$ ，于是先将其中 $3$ 个 $2$ 合并，再将 $2$ 个 $2$ 和任意奇质数合并，剩下的 $n-6$ 个数 $2$ 和奇质数分别两两合并。共合并 $\dfrac{n+2}2$ 次。
恰好有 $3$ 个 $2$ 。因为 $n\ge 6$ ，所以至少有 $3$ 个奇质数。刚刚分析过 $a$ 中奇质数模 $3$ 余 $2$ ，故把 $3$ 个奇质数合并会得到合数。再把 $3$ 个 $2$ 合并，剩下的同理。共合并 $\dfrac{n+2}{2}$ 次。
恰好有 $1$ 个 $2$ 。这个时候可以有 $3$ ，至少有 $5$ 个奇质数。你发现任意 $5$ 个质数中，都能选出 $3$ 个使得它们的和不是质数。因为质数模 $3$ 的余数只能为 $1,2$ ，根据鸽巢原理总有一个余数至少出现了 $3$ 次。又因为任意三个质数的和 $>3$ ，故为 $>3$ 的 $3$ 的倍数。选出和为合数的 $3$ 个奇质数合并，将 $1$ 个 $2$ 和另外 $2$ 个奇质数合并，剩下同理。共合并 $\dfrac{n+2}{2}$ 次。

现在我们手上只会有

1

个奇合数和

n-1

个偶数。多出来的合并次数拿来随意合并偶数即可，答案为

0

。

子任务五 $2\nmid n,a_i>2$

首先

1<k\le \dfrac{n-1}2,n\ge 5

。

直接在前

5

个数中找到和为合数的三个数，剩下的数两两合并，多出来的合并次数同子任务七。答案为

0

。

子任务八 $2\nmid n$

仿照子任务七进行分类讨论。

若

2

的个数为奇数，则奇质数个数为偶数。先丢掉一个

2

，剩下的奇质数两两合并，

2

两两合并，再将丢掉的

2

和合并后的随意一个元素合并。多出来的合并次数同上。答案为

0

。

若

2

的个数为偶数，则奇质数个数为奇数。我们尝试找到一个奇质数的三元组，使得这三个奇质数之和为合数。

如果能找到，那么把这三个合并，剩下同理。多余的合并次数同上。答案为

0

。

否则奇质数最多

3

个，那么

2

至少

2

个。还有以下两种情况：

至少存在一个 $\neq 3$ 的元素 $x$ 。将 $x$ 和 $2$ 个 $2$ 单独拎出来，剩下的奇质数和 $2$ 分别两两合并。如果 $x\equiv 1\pmod 3$ ，就将 $x$ 和 $1$ 个 $2$ 合并，另一个 $2$ 和合并后的随意一个偶数合并；如果 $x\equiv 2\pmod 3$ ，就将 $x$ 和 $2$ 个 $2$ 合并。这样只会进行 $\dfrac{n+1}2$ 次合并，多余的合并次数同上。
所有元素都 $=3$ ，那么就只可能有 $1$ 个奇质数（否则可以选择 $3+3+3=9$ 为合数）。模仿子任务七，按照 $k$ 的取值分类：
- 当 $k=\dfrac{n-1}2$ ，你的操作次数不足以支撑 $3$ 和 $3$ 个 $2$ 合并，因此答案至少为 $1$ 。把所有 $2$ 两两合并再把 $3$ 和随意一个合并后的元素合并即可取到下界。
- 否则， $k\le\dfrac{n-3}2$ 。又因为 $n=5$ 时只能 $k=1$ 已经被子任务一判掉了，所以 $n\ge 7$ ，至少有 $6$ 个 $2$ 。那么就可以将其中 $3$ 个 $2$ 与 $3$ 合并， $3$ 个 $2$ 合并，剩下的 $2$ 两两合并，多余的合并次数同子任务七。答案为 $0$ 。

综上，我们只要实现子任务一、二、六、七、八即可。输入的

a

已经给你排好序，所以时间复杂度

O(\sum n)

，根据实现可能还会带一个筛质数的

O(V)

或

O(V\log\log V)

（线性筛或埃氏筛）以及判断质数的

O(\sqrt V\sum n)

或

O(T\log V)

（暴力判或 Miller-Rabin），可能还需要并查集之类的维护带个

\log n

或

\alpha(n)

。

代码

CPP

#include<bits/stdc++.h>
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
#define ll long long
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
using namespace std;
const int MAXN=3e5+1;
int n,k,ans;
bitset<MAXN>isp;
vector<int>seq[MAXN];
namespace Sub1{
inline void main(){
	ll sum=0;seq[1].resize(n);ans=1; 
	F(i,1,n){int a;cin>>a;sum+=a;seq[1][i-1]=a;}
	for(ll i=2;i*i<=sum;++i) if(sum%i==0) return ans=0,void();
}
}
namespace Sub6{
int c2;
vector<int>odd;
inline void main(){
	c2=0;vector<int>().swap(odd);ans=2*k-n;
	F(i,1,n){int a;cin>>a;if(a==2) ++c2;else odd.push_back(a);}
	F(i,1,n-k){
		if(c2>=2) seq[i].push_back(2),seq[i].push_back(2),c2-=2;
		else seq[i].push_back(odd.back()),odd.pop_back(),seq[i].push_back(odd.back()),odd.pop_back(); 
	}
	F(i,n-k+1,k){
		if(c2) seq[i].push_back(2),--c2;
		else seq[i].push_back(odd.back()),odd.pop_back();
	}
}
}
int a[MAXN],dsu[MAXN],id[MAXN];
int find(int x){return dsu[x]==x?x:dsu[x]=find(dsu[x]);}
inline void merge(int cnt,queue<int>&q){
	for(int i=cnt,x,y;i;--i){
		x=q.front();q.pop();y=q.front();q.pop();
		x=find(x),y=find(y);
		dsu[x]=y;q.push(y);
	}
	memset(id,0,sizeof(int)*(n+1));
	int qwq=0;
	F(i,1,n) if(dsu[i]==i) id[i]=++qwq;
	F(i,1,n) seq[id[find(i)]].push_back(a[i]);
}
namespace Sub2{
inline void main(){
	ll sum=0;ans=2;
	F(i,1,n) cin>>a[i],sum+=a[i];
	F(i,2,4){
		if(!isp[a[1]+a[i]]&&isp[sum-a[1]-a[i]]<ans){
			ans=isp[sum-a[1]-a[i]];seq[1].clear(),seq[2].clear();
			seq[1]={a[1],a[i]};
			F(j,2,4) if(j!=i) seq[2].push_back(a[j]); 
		}
		if(!isp[sum-a[1]-a[i]]&&isp[a[1]+a[i]]<ans){
			ans=isp[a[1]+a[i]];seq[1].clear(),seq[2].clear();
			seq[1]={a[1],a[i]};
			F(j,2,4) if(j!=i) seq[2].push_back(a[j]); 
		}
	}
}
}
namespace Sub7{
int c2;
inline void main(){
	c2=0;iota(dsu+1,dsu+n+1,1);ans=0;
	F(i,1,n) cin>>a[i],c2+=(a[i]==2);
	if(c2&1){
		int x=-1;
		F(i,1,n) if((a[i]&1)&&!isp[a[i]+2]){x=i,dsu[i]=c2;break;}
		if(x!=-1){
			queue<int>q;
			F(i,1,c2-1) q.push(i);
			F(i,c2+1,n) if(x!=i) q.push(i);
			return merge(n-k-1,q);
		}
		if(k==n/2){
			queue<int>q;ans=1;
			F(i,1,n) q.push(i);
			return merge(n-k,q);
		}
		if(c2>=3&&a[c2+1]==3){
			dsu[c2]=dsu[c2-1]=dsu[c2-2]=c2+1;
			queue<int>q;
			F(i,1,c2-3) q.push(i);
			F(i,c2+2,n) q.push(i);
			return merge(n-k-3,q);
		}
		if(c2>=5){
			dsu[c2]=dsu[c2-1]=c2+1;
			dsu[c2-3]=dsu[c2-4]=c2-2;
			queue<int>q;
			F(i,1,c2-5) q.push(i);
			F(i,c2+2,n) q.push(i);
			q.push(c2-2);
			return merge(n-k-4,q);
		}
		if(c2==3){
			dsu[c2-1]=dsu[c2-2]=c2;
			dsu[c2+1]=dsu[c2+2]=c2+3;
			queue<int>q;
			F(i,c2+4,n) q.push(i);
			q.push(c2);
			return merge(n-k-4,q);
		}
		if(c2==1){
			int x=0,y=0,z=0;
			F(i,2,6) F(j,i+1,6) F(t,j+1,6) if(!isp[a[i]+a[j]+a[t]]){x=i,y=j,z=t;break;}
			dsu[x]=dsu[y]=z;
			F(i,2,6) if(i!=x&&i!=y&&i!=z) dsu[i]=1;
			queue<int>q;
			F(i,7,n) q.push(i);
			q.push(1);
			return merge(n-k-4,q);
		}
		return;
	}
	queue<int>q;
	F(i,1,n) q.push(i);
	merge(n-k,q);
}
}
namespace Sub8{
int c2;
inline void main(){
	c2=0;iota(dsu+1,dsu+n+1,1);ans=0;
	F(i,1,n) cin>>a[i],c2+=(a[i]==2);
	if(c2&1){
		queue<int>q;dsu[1]=3;
		for(int i=2;i<=n;i+=2) dsu[i]=i+1,q.push(i+1);
		return merge((n-1)/2-k,q);
	}
	int x=-1,y,z,lim=min(c2+5,n);
	F(i,c2+1,lim) F(j,i+1,lim) F(t,j+1,lim) if(!isp[a[i]+a[j]+a[t]]){x=i,y=j,z=t;break;}
	if(x!=-1){
		dsu[x]=dsu[y]=z;
		queue<int>q;
		F(i,1,n) if(i!=x&&i!=y&&i!=z) q.push(i);
		return merge(n-k-2,q);
	}
	F(i,c2+1,n) if(a[i]!=3){x=i;break;}
	queue<int>q;
	if(x==-1){
		if(k==(n-1)/2){
			F(i,1,n) q.push(i);ans=1;
			return merge(n-k,q); 
		}
		dsu[c2]=dsu[c2-1]=dsu[c2-2]=c2+1;
		dsu[c2-4]=dsu[c2-5]=c2-3;
		F(i,1,c2-6) q.push(i);
		q.push(c2-3);
		return merge(n-k-5,q);
	}
	if(a[x]%3==1){
		dsu[1]=x;
		F(i,3,n) if(i!=x) q.push(i);
		q.push(2);
		merge(n-k-1,q);
	}else{
		dsu[1]=dsu[2]=x;
		F(i,3,n) if(i!=x) q.push(i);
		merge(n-k-2,q);
	}
}
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	int T;
	isp[1]=1;
	for(int i=2;i*i<MAXN;++i) if(!isp[i]) for(int j=i*i;j<MAXN;j+=i) isp[j]=1;
	isp.flip();
	for(cin>>T;T;--T){
		F(i,1,k) vector<int>().swap(seq[i]);
		cin>>n>>k;
		if(k==1) Sub1::main();
		else if(2*k>=n+1) Sub6::main();
		else if(n<=4) Sub2::main();
		else if(n&1) Sub8::main();
		else Sub7::main();
		cout<<ans<<"\n";
		F(i,1,k){
			cout<<seq[i].size()<<" ";
			for(int j:seq[i]) cout<<j<<" ";
			cout<<"\n";
		}
	}
	return 0;
}

题解：P12551 [UOI 2025] Simple Task

文章操作

子任务一 $k=1$

子任务六 $2k\ge n+1$

子任务二 $n\le 4$

子任务四 $2|n,a_i>2$

子任务七 $2|n$

子任务五 $2\nmid n,a_i>2$

子任务八 $2\nmid n$

代码

相关推荐

评论

题解：P12551 [UOI 2025] Simple Task

文章操作

子任务一 k=1k=1k=1

子任务六 2k≥n+12k\ge n+12k≥n+1

子任务二 n≤4n\le 4n≤4

子任务四 2∣n,ai>22|n,a_i>22∣n,ai​>2

子任务七 2∣n2|n2∣n

子任务五 2∤n,ai>22\nmid n,a_i>22∤n,ai​>2

子任务八 2∤n2\nmid n2∤n

代码

相关推荐

评论

子任务一 $k=1$

子任务六 $2k\ge n+1$

子任务二 $n\le 4$

子任务四 $2|n,a_i>2$

子任务七 $2|n$

子任务五 $2\nmid n,a_i>2$

子任务八 $2\nmid n$