[AGC057D] Sum Avoidance( 二 ) _生活百科

接下来就可以还原 \(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肯定不是0int 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 = xif(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;//同样是由于算0else l=mid+1;	}	return S-ans;}signed main(){	int T;scanf("%lld",&T);	while(T--)printf("%lld\n",solve());	return 0;}

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