浙江龙网

  1. 首页 > 生活百科 > >

[AGC057D] Sum Avoidance

生活百科

Link
本篇题解大部分内容来自这篇文章
首先题意翻译:
给定一个正整数 \(S\)，称一个正整数集合 \(A\) 是好的，当且仅当它满足以下条件：

  1. \(A\)中元素在 \((0,S)\) 之间
  2. 不能用 \(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肯定不是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;}

推荐阅读


上一篇：简易版 纯css爱心代码-最近超级火的打火机与公主裙中的爱心代码

下一篇：day11-Servlet01