[AGC057D] Sum Avoidance

Link

本篇题解大部分内容来自这篇文章

首先题意翻译:

给定一个正整数 $S$ ，称一个正整数集合 $A$ 是好的，当且仅当它满足以下条件：

$A$ 中元素在 $(0,S)$ 之间
不能用 $A$ 中元素多次相加得到 $S$

考虑所有好的集合中元素数量最大且字典序最小的集合 $A$ ，多次询问，求集合 $A$ 从小到大排序后的第 $k$ 项，或集合大小小于 $k$

$ T \le 1000 , S \le 10^{18} $

解法

这什么神仙题啊光是理解题解就好困难啊

先考虑性质2：

首先容易发现 $i,S-i$ 只能在集合中存在一个，若 $S$ 为偶数则 $\frac{S}{2}$ 也不能存在于集合中，所以集合的大小小于等于$\left\lfloor\dfrac{S-1}{2}\right\rfloor$。

其次，把所有大于 $\left\lfloor\dfrac{S}{2}\right\rfloor$ 的整数取进集合必然满足条件，所以最大集合的大小一定为$\left\lfloor\dfrac{S-1}{2}\right\rfloor$。

且若要满足集合大小最大，对于 $i< \dfrac{S}{2}$，$n-i$ 和 $i$ 一定有一个在集合中。

我们设所有集合 $A$ 中 $< \dfrac{S}{2}$的元素构成集合 $B$，显然 $B$ 是 $A$ 的子集，且确定 $B$ 即可确定 $A$。

则 $B$ 有以下性质：

\[如果 a,b \in B ，且 a+b < \dfrac{S}{2}，则 a+b \in B。
\]

原因是如果 $a+b \notin B$，则 $n-(a+b)$，一定在 $A$中，那么 $a,b,n-(a+b)$ 同时在集合 $A$ 中，显然不满足条件。

考虑满足该性质的集合 $B$ 及对应的 $A$，当它不合法，即 $A$ 中的数多次相加能拼成 $S$ 时，若拼成 $S$ 的数中有一个大于等于 $\dfrac{S}{2}$（即在集合 $A$ 但不在集合 $B$ 中），则这种情况必定不满足性质1，所以我们只需要考虑集合 $B$ 是否合法即可。

那么接下来就是构造了，由于我们要构造字典序最小的 $A$ ，所以只需从小往大依次枚举每个数，尝试贪心的将其加入 $B$ ，最后得到的 $B$ 及其对应的 $A$ 就是我们所需要的集合 $A$ 了。

加入数时有两种情况：

1.该数能被已经在 $B$ 中的数组合出，那么这个数必须加，显然加入它之后集合仍旧合法。

2.当非第一种情况时，若加入该数不会使集合 $B$ 不合法，加入该数。

我们设第一个加入集合 $B$ 的数为 $d$ ，容易发现，$d$ 一定是最小的与 $S$ 互质的数，并且在此之后每当我们用第 $2$ 种方式加入新数时，该数一定与已经在集合中的所有数模 $d$ 不同余（同余的话可以由已经在集合中的同余的数和若干个 $d$ 组合出）。也就是说，以第二种方式加入的数最多只有 $d$ 个。

接下来就来到了同余最短路的相关部分，考虑对于每个 $i\in{0,1,···,d-1}$ 记录一个 $f_i$ 表示已经在 $B$ 的数可以构造出的 $\equiv i (\mod d )$的最小值。

显然，$f$ 不会被第一种情况加入的数影响，且最后由 $f$ 可以得到整个 $B$ 集合（下文讲具体方法）。

先考虑以第二种方式加入一个数 $v \equiv x (\mod d)$，首先一定有 $f_x>v$ （否则就是以第一种方式加入了），可以通过枚举加入的 $v$ 用了多少次更新 $f$ 数组，即:

\[f_i=\min\limits_{k=0}^{d-1}f_{i-k*x \mod d}+v*k
\]

一个数$v$能被加入当且仅当 $f_x>v$ 且加入后 $f_{S \mod d}>S$。我们不妨枚举 $x$，容易发现，对于每个 $x$ ，加入的合法的 $v$ 有其下界 $dn$ ，大于等于 $dn$ 且 $\equiv x(\mod d)$ 且小于 $f_x$ 的数均可加入，从而可以得到当前 $x$ 下第一个能加入的数。（当然也可能根本不存在能加入的数）

于是我们可以对每一个 $x$ 找到其能加的数，取其中最小的就是下一个能加的数，重复至多 $d$ 次即可得到最终的 $f$ 数组。

接下来就可以还原 $B$ 了，若一个数 $t\in B$，当且仅当 $t < \frac{S}{2}$ 且 $t\ge f_{t \mod d}$。

此时容易$O(d)$求得 $B$ 集合内小于等于某个数的元素个数，于是可以二分求得最终答案。复杂度为 $O(d \log S)$，若答案$> \frac{S}{2}$，也可以反向类似二分。

考虑 $d$ 的范围，容易发现 $d$ 在 $10^{18}$ 次以内最大为 $43$ （$lcm(1,2,···,43)\geq 10^{18}$）。而事实上，$d=O(\log S)$

点击查看代码

#include <bits/stdc++.h>

#define N 50

#define M 2000010

#define pii pair<int,int>

#define mkp make_pair

#define pb push_back

#define fi first

#define se second

#define int long long

//#define MOD

#define INF 1061109567

#define int_edge int to[M],nxt[M],head[N],cnt=0;

using namespace std;

int S,k,d,f[N],in[N];

//int_edge;void add_edge(int x,int y ){to[++cnt]=y;nxt[cnt]=head[x];head[x]=cnt;}

//int_edge;int val[M];void add_edge(int x,int y,int z){to[++cnt]=y;val[cnt]=z;nxt[cnt]=head[x];head[x]=cnt;}

int check(int nw){

	int tmp=0;

	for(int i=0;i<d;i++)

		if(nw>=f[i])tmp+=(nw-f[i])/d+1;

	return tmp;

}

queue<int>q;

void spfa(int nw){

	for(int i=0;i<d;i++)q.push(i),in[i]=1;

	while(!q.empty()){

		int u=q.front(),v=(u+nw)%d;q.pop();in[u]=0;

		if(f[v]>f[u]+nw){f[v]=f[u]+nw;if(!in[v])q.push(v),in[v]=1;}

	}

}

int solve(){

	scanf("%lld %lld",&S,&k);

	if(k>(S-1)/2)return -1;

	if(S==3)return 2;

	if(S==4)return 3;

	if(S==6)return k+3;//d>=S/2

	d=1;while(S%d==0)d++;

	for(int i=1;i<d;i++)f[i]=1e18;

	while(1){

		int v=1e18;

		for(int x=1;x<d;x++){//枚举x，容易发现x肯定不是0

			int dn=0;

			for(int k=1;k<d;k++){//枚举k，容易发现k取0肯定也不优

				int lst=(S-x*k+d*d)%d;//加上d*d用于防负数

				dn=max(dn,(S-f[lst])/k+1);

			}

			if((dn+d-x)%d)dn+=d-(dn+d-x)%d;//确保算出来的下界mod d = x

			if(dn<f[x]&&dn<v)v=dn;

		}

		if(v>=S/2)break;

		spfa(v);//更新f

	}

	int l=1,r=S/2,ans=-1;

	while(l<=r){

		int mid=(l+r)/2;

		if(check(mid)>=k+1)ans=mid,r=mid-1;//注意此处由于算入了0所以要与k+1相比

			else l=mid+1;

	}

	if(ans!=-1)return ans;

	l=1,r=S/2,k=(S-1)/2+1-k;

	while(l<=r){

		int mid=(l+r)/2;

		if(mid-check(mid)+2>=k+1)ans=mid,r=mid-1;//同样是由于算0

			else l=mid+1;

	}

	return S-ans;

}

signed main()

{

	int T;scanf("%lld",&T);

	while(T--)printf("%lld\n",solve());

	return 0;

}

后记：这个题折磨了我半个下午加半个晚上，不过也算是迄今为止做过的最难的题之一了，还是很有收获的。以及我真的很想吐槽一下，我函数里重复定义了 $d$ 调了快1个小时

巴特西

[AGC057D] Sum Avoidance

最新文章

热门文章