E - Lucky Numbers

传送门：

E - Lucky Numbers

题意：给你一个长为n-1的序列s，还有一个长为m的x序列，他们被称为幸运数字。

定义一个长为n的序列a满足下列条件那么这是一个好序列：

a[i]+a[i+1]=s[i]

构造一个好序列使得序列中有最多的数字是幸运数字。

分析：m<=10，考虑枚举，把每个a[i]=x[j]。容易发现确定a序列的一个值就能确定a序列，也就是可以说a序列的特征值是a[1]。假设最优解的序列是a[1],a[2],s[3]...，那么当且仅当a[i]=a[i]的时候这个序列出现一次，至此，可以将问题转化为 求出现最多的序列的次数。用map和特征值求解即可。

代码：

#include
using namespace std;
#define int long long
int sum[100005];
int ss[100005];
int x[15];
mapmp;signed main()
{int n,m;cin>>n>>m;for(int i=1;i<=n-1;i++){cin>>sum[i];}for(int i=2;i<=n;i++){ss[i]=sum[i-1]-ss[i-1];}for(int i=1;i<=m;i++){cin>>x[i];}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int now=x[j];int tmp;if(i%2) tmp=now-ss[i];else tmp=ss[i]-now;mp[tmp]++;}}int maxx=0;for(auto it:mp){maxx=max(maxx,it.second);}cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！