codeforces1045B Space Isaac 【manacher】【差分】
2024-08-20 14:56:42
题目大意:
题目是将$[0,m)$的数划成了两个集合,其中一个集合的元素个数不超过$n$。问在第一个集合中选出的数加上第二个集合中选出的数的和中没有出现的数有哪些。
题目分析:
很有意思的一道题。方便起见,接下来的所有表述在模意义下进行。选出的数集合用$a_1 \sim a_n$表示
考虑给出的集合,$k$无法由两个集合中任选一个数的和表示等价于对于给出的集合元素$a_i$,$k-a_i$也在给出的集合之中。
这样来看答案不会超过$n$。也就是你对选出的集合中最小的数考虑,它与另一个选出的数配对。且每个选出的数都能这样配对。
假设你现在让$a_1$与$a_i$配对,那么$a_2 \sim a_{i-1}$必然首尾配对。且$a_{i+1}$一定与$a_n$配对,否则$a_n$找不到配对对象。
这样我们将问题化为了两个环。内部要与最外层答案一致意味着从左到右增加了$k$,那么从右到左也要减少$k$,换句话说它的差分数组是回文的。
所以manacher判回文就行了。
代码:
#include<bits/stdc++.h>
using namespace std; const int maxn = ; int n,m;
int a[maxn],x[maxn],ans[maxn],num; int ss[maxn*],f[maxn*],ct,rr; void read(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
} void manacher(){
for(int i=;i<=n;i++) ss[i*] = x[i];
for(int i=;i<=n;i++) ss[i*-] = -; // to replace '$'
ss[*n+] = -; f[] = ,rr = ,ct = ;
for(int i=;i<=*n+;i++){
if(rr < i) f[i] = ; else f[i] = min(rr-i+,f[*ct-i]);
while(i+f[i]<=*n+&&i-f[i]>=&&ss[i+f[i]]==ss[i-f[i]])f[i]++;
if(i+f[i]- > rr) ct = i,rr = i+f[i]-;
}
} int chk(int l,int r){
if(l >= r) return ;
int cent = l+r;
int ll = cent-f[cent]+,rr = cent+f[cent]-;
if(ll <= *l && rr >= *r) return ;
else return ;
} void work(){
for(int i=;i<=n;i++) x[i] = a[i] - a[i-];
if(n == ){printf("1\n%d",(a[]+a[])%m);return;}
manacher();
for(int i=;i<n;i++){
if((a[] + a[i])%m == (a[i+] + a[n])%m){
if(chk(,i)&&chk(i+,n)){
ans[++num] = (a[]+a[i])%m;
}
}else continue;
}
if(chk(,n)){ans[++num] = (a[]+a[n])%m;}
sort(ans+,ans+num+);
printf("%d\n",num);
for(int i=;i<=num;i++){
printf("%d ",ans[i]);
}
} int main(){
read();
work();
return ;
}
最新文章
- TODO:Go语言同名Go字体发布
- [LeetCode] Maximum Product of Word Lengths 单词长度的最大积
- libnode 0.4.0 发布,C++ 语言版的 Node.js
- 通过ADO方式连接数据库
- Java 生成验证码
- Java基础之在窗口中绘图——利用多态性使用鼠标自由绘图(Sketcher 7 with a crosshair cursor)
- @synthesize vs. @dynamic
- jQuery过滤选择器
- javascriipt类型转换
- Mac打造python2 python3开发环境
- StickyListHeaders的使用
- 专访 | 新浪架构师:0-5年Java工程师的职业规划如何做?
- ASP.NET Core 企业开发架构概述
- .Net并行编程(一)-TPL之数据并行
- 使用Nginx转发TCP/UDP数据
- Java集合&;Spring源码浅读
- Laravel中pluck的使用——返回指定的字段值信息列表
- Linux配置示例:配置java环境变量
- Python-Numpy的tile函数用法
- 使用Array.prototype.indexOf()的几点注意
热门文章
- 2017湘潭大学邀请赛E题(贪心)
- Ubuntu 14.04 安装caffe
- org.apache.ibatis.binding.BindingException: Invalid bound statement (not found): com.bw.mapper.BillMapper.getBillList 	at org.apache.ibatis.binding.MapperMethod$SqlCommand.<;init>;(MapperMethod.java:225
- 搭建私服-docker registry
- CopyOnWriteArrayList源码分析
- html js 表单提交前检测数据
- gethostbyname用法
- MySQL根据某个字段查询重复的数据
- 理解ORM的前提:数据库中的范式和约束
- 2 Servlet 细节