每日一题第六天(补)_jikelk的博客-爱代码爱编程
因为周赛打的实在不行emo了然后就🕊了qwq,就补卡了我3个多小时的这个题吧
题目是这一届的icpc河南省赛的原题f,为什么每次都没有想到呢。。。
题目意思:就是给你一个集合,让集合里面的数和其他数两两相加,形成一个新的集合(重复的元素只被看作一个集合)然后每个集合的元素都是大于等于0的。
首先n个数组成的集合的能够组成的
最多的情况为1,2,3,...n,为 n*(n+1)/2
最少的情况就是n+n-1(n*2-1),排列方式为(0,1,2,3,4,...,2(n-1)),有2n-1个数;
首先我们可以发现如果要组成的|A+A|的数的个数t是奇数的话,那么可以由|A|的n个数组成2
n-1反推原来的|A|需要(t+1)/2个数 ,然后从0开始到(t+1)/2(不包括)遍历输出即可。
如果是偶数的个数t,那么之比t+1的奇数的个数少了个1,可以由t+1的构造中移除一个一就在|A+A|中只去掉了一的这个数。
如:7是5时的构造时0,1,2,3,
0,1,2,3,4,5,6
那么我们找为6的构造时去掉5中的构造1即可形成6的构造.
0,2,3,4,5,6。
但是有两个例外2和4.
由可知n为1时最大和最小都为1,n为2时只能为3,n为3时范围为5-6,我们可以发现没有2或者4的构造的可能,所以只有2和4无能够组成的构造。
代码:
/**
* ┏┓ ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃ ┃
* ┃ ━ ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃ ┻ ┃
* ┃ ┃ + +
* ┗━┓ ┏━┛
* ┃ ┃ + + + +Code is far away from
* ┃ ┃ + bug with the animal protecting
* ┃ ┗━━━┓ 神兽保佑,代码无bug
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛ + + + +
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛+ + + +
*/
#include<cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include<vector>
#include<queue>
#include<map>
#define ll long long
using namespace std;
const int N=1000000+100;
int n ,m,h;
ll s[N];
int main()
{
cin>>n;
if(n%2!=0)
{
int x=(n+1)/2;
cout<<x<<endl;
for(int i =0;i<x;i++)
cout<<i<<" ";
}
else{
if(n==2||n==4)
cout<<"-1";
else {
int x=n/2;
cout<<x<<endl;
for(int i =0;i<=x;i++)
{
if(i!=1)
cout<<i<<" ";
}
}
}
cout<<endl;
return 0;
}