奇思妙想构造题 ARC145 D - Non Arithmetic Progression Set

Non Arithmetic Progression Set

大意：

给定m，n

要求构造一个序列：

长度=n，元素和=m，任意三个元素无法构成等差数列，|a[i]|<=1e7

思路：

一开始这个无法构成等差数列的条件我是怎么想都突破不了，果然还是见的太少了

官方题解提供了一个我认为极其巧妙的方法。

考虑用三进制来处理

如果一个数在三进制的表示下只有0/1的话，我们暂且叫它合法数。那么序列里全部放这种数肯定是优的。

下面我们给出证明：

现在假设序列里全部都是这种合法数

不妨想一想，一个合法数a的两倍在三进制表示下肯定只有0/2，那么如果它是等差数列的中间项的话，就意味着另外两个合法数b，c的所有三进制下含1的位置都是重合的，这样才能刚好凑出2，并且这些2的位置也要与2*a的位置重合，稍加思索，不难发现，

三个合法数能够组成等差数列，当且仅当a=b=c

要规避掉这种情况可就比原来的情况简单多了。

由此可见，只要满足序列里都是不相等的合法数，这个序列就一定满足“无等差数列”的性质 。

那么我们来讲讲如何构造出n个不相同的合法数

其实很简单，两个数不相同，当且仅当它们不满足在三进制下每一位都相同。所以我们可以枚举1-n（它们在二进制下时不相同的，且在二进制下只有0/1），再把对应的数字转换成三进制下拥有相同表示的数字即可

for(int i=1;i<=n;i++)
	{
		ll sum=0;
		ll t=1;
		for(int j=0;j<15;++j)
		{
			if((i>>j)&1) sum+=t;
			t*=3;//三进制向上枚举 
		}
		mas[++cnt]=sum;
		tot+=sum;
	}

所以我们不妨就先构造出n个合法数，设它们的和为sum

现在我们要做的工作是调整序列元素的值，使得sum=m

在这样的前提下，我们还发现，对序列的所有元素同时加上/减去相同的值，对序列的“无等差数列”性质并没有影响（废话，那么要让sum变成m，我们只要保证abs（sum-m）%n=0即可，这样就可以把差值均分到每一个元素的头上。

既然如此，我们不妨在构造时这n个合法数再做一些改变，把它们的三进制的第一位空出来，使得它们在加上1之后仍然是一个合法数（且不会与任何其它元素相等，因为大家都把第一位空出来了），这样只要把abs（sum-m）%n分到前几个元素头上（每个+1），就同时保证了序列全部都是合法数且abs（sum-m）%n=0，那么最后只要把差值均分就可以了

因此我们还得改变一下构造的方法，保证第一位=0，也就是保证数字的二进制表示是一个偶数

for(int i=2;i<=n*2;i+=2)
	{
		ll sum=0;
		ll t=1;
		for(int j=0;j<15;++j)
		{
			if((i>>j)&1) sum+=t;
			t*=3;//三进制向上枚举 
		}
		mas[++cnt]=sum;
		tot+=sum;
	}

调整一下枚举的数字即可 

妙哉~

#include
using namespace std;
#define ll long long
#define endl '\n'
const ll N=1e4+10;
ll n,m;
ll mas[N];
ll cnt=0;
ll tot=0;
int main()
{
	cin>>n>>m;
	for(int i=2;i<=n*2;i+=2)//构造n个合法数，且把第一位空出来
	{
		ll sum=0;
		ll t=1;
		for(int j=0;j<15;++j)
		{
			if((i>>j)&1) sum+=t;
			t*=3;//三进制向上枚举 
		}
		mas[++cnt]=sum;
		tot+=sum;
	}
	ll mod=((m-tot)%n+n)%n;//多余的部分分到前面的数去，每个+1
	tot+=mod;
	for(int i=1;i<=mod;++i) mas[i]++;
	ll oth=(tot-m)/n;//差值
	for(int i=1;i<=n;++i) cout<' ';
	return 0;
}