[AGC057D] Sum Avoidance

首先题意翻译:

给定一个正整数 (S) ,称一个正整数集合 (A) 是好的,当且仅当它满足以下条件:

考虑所有好的集合中元素数量最大且字典序最小的集合 (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-kx \mod d}+vk ]

一个数(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++){//&#x679A;&#x4E3E;x&#xFF0C;&#x5BB9;&#x6613;&#x53D1;&#x73B0;x&#x80AF;&#x5B9A;&#x4E0D;&#x662F;0" dn="0;" k="1;k<d;k++){//&#x679A;&#x4E3E;k&#xFF0C;&#x5BB9;&#x6613;&#x53D1;&#x73B0;k&#x53D6;0&#x80AF;&#x5B9A;&#x4E5F;&#x4E0D;&#x4F18;" lst="(S-x*k+d*d)%d;//&#x52A0;&#x4E0A;d*d&#x7528;&#x4E8E;&#x9632;&#x8D1F;&#x6570;" } if((dn+d-x)%d)dn+="d-(dn+d-x)%d;//&#x786E;&#x4FDD;&#x7B97;&#x51FA;&#x6765;&#x7684;&#x4E0B;&#x754C;mod" d="x" if(dn<f[x]&&dn<v)v="dn;" if(v>=S/2)break;
        spfa(v);//&#x66F4;&#x65B0;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;//&#x6CE8;&#x610F;&#x6B64;&#x5904;&#x7531;&#x4E8E;&#x7B97;&#x5165;&#x4E86;0&#x6240;&#x4EE5;&#x8981;&#x4E0E;k+1&#x76F8;&#x6BD4;
            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;//&#x540C;&#x6837;&#x662F;&#x7531;&#x4E8E;&#x7B97;0
            else l=mid+1;
    }
    return S-ans;
}
signed main()
{
    int T;scanf("%lld",&T);
    while(T--)printf("%lld\n",solve());
    return 0;
}

</=r){></=r){></d;i++)f[i]=1e18;></d;i++)q.push(i),in[i]=1;></int></d;i++)></int,int></bits>

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

Original: https://www.cnblogs.com/shight/p/16863844.html
Author: shight
Title: [AGC057D] Sum Avoidance

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/799221/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

  • python画花

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Python 2023年1月20日
    0102
  • 初遇 chatGPT

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Python 2023年2月4日
    0107
  • Pytest(3)fixture的使用

    Pytest的fixture相对于传统的xUnit的setup/teardown函数做了显著的改进: 命名方式灵活,不局限于 setup 和teardown 这几个命名 conft…

    Python 2023年9月14日
    035
  • python数据精度问题

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Python 2023年1月1日
    0106
  • python Web开发 flask轻量级Web框架实战项目–实现功能–账号密码登录界面(连接数据库Mysql)

    ps:各位好久不见,我回家了!终于有时间把之前的一些东西整理一下了(好吧,之前是我太懒了),今天分享一个功能简单的python web实战项目,后期功能可自行丰富。 由于好多朋友私…

    Python 2023年8月2日
    073
  • Django使用已有mysql数据库中的表生成models,遇到得一些坑和解决办法

    models使用过程中遇到一些问题,总结一下,以后自己忘记了可以借鉴一下 用已有mysql数据库创建models 准备工作:创建好project,app,注册app,更改setti…

    Python 2023年8月6日
    049
  • yolov5目标检测神经网络——损失函数计算原理

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Python 2023年1月24日
    0114
  • BiSeNet – 轻量级实时语义分割

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Python 2023年1月24日
    0105
  • matplotlib画三维图

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Python 2023年1月13日
    092
  • sklearn中的决策树(分类)

    本文在我的知乎上同步更新:sklearn中的决策树(分类) – 知乎 Sklearn库有很多机器学习模型,不同的模型有着不同的特点,针对不同的问题,选取对应的模型,可以…

    Python 2023年8月2日
    040
  • 用python写一个《飞机大战》

    欢迎加入我们卧虎藏龙的python讨论qq群:729683466 ● 导 语 ● 很久很久以前 公众号写过一个飞机大战 全部是方块组成的 太简单了 今天给大家分享一个新的飞机大战 …

    Python 2023年9月24日
    020
  • 爬虫案例—深圳租房数据的回归分析

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Python 2023年1月9日
    098
  • pytest快速入门(1)

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Python 2023年1月18日
    096
  • Numpy基础

    浅学了一点numpy,努力向机器学习方向学习!听了慕课老师的课总结一下,如有不对,请大佬指正! import numpy numpy.__version__ import nump…

    Python 2023年8月26日
    019
  • 《Python项目开发实战》PDF高清版下载

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Python 2022年9月3日
    0298
  • Python中如何使用matplotlib给柱状图添加数据标签(bar_label())

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Python 2023年1月13日
    0181
亲爱的 Coder【最近整理,可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球