连续串之和.txt

ACM资料大集合

#include <iostream>
#include <stdio.h>
using namespace std;
//连续串之和
/*
输入
8
4

输出
0
1
2
1
0
-1
0
1

问题转述：
给出一个具有性质A的串集P和一个具有性质B的串集Q，试判断P Q是否是空集。若不是，试给出其中的一个元素。
分析：
这一题目显然无法把所有可能的串都搜索出来然后一一判断，所以应当根据具体的性质进行剪枝，排除不可能的串；或更直接的，构造出答案。
考虑一个长度为n的连续串a，我们把它的元素从左端开始标号为1、2、…、n，并用ai表示第i（1 i n）个元素。由于连续串的性质是用相邻两整数之差定义的，故直接考虑元素的性质比较麻烦，我们再定义一个串b，为串a的性质串，其中有bi=ai+1-ai（1  i  n-1）。这样，我们可知这个串中所有元素之和  。这里bi只有-1和1两种选择。因为用负数计算还是比较麻烦，所以我们设ci=bi+1，这样就有 。这里ci的取值为0或2，这时问题就转化成了一个不完全的不等进位制问题。为了完善这个表达，我们再设dn-i=ci/2。可知 ，也就是 。由于di的取值只有0和1，故该问题已经完全的转化成了一个不等进位制问题。
我们可以知道0到 之间的整数均可以用 表示出来 ，而 的最大值为 ，最小值为0，并且又是整数。故我们得到了一个判定有解的方法。对于一个有解的问题，我们可以用如下的算法求出d的值：
1.	k←n-1；
2.	如果T  k，那么T←T-k，dk←1，否则dk←0；
3.	k←k-1；
4.	如果k=0则退出，否则转2。█
由于算法开始时 ，这样如果T k，则 ；否则 。所以无论算法开始时T的值如何（当然，需要符合条件），执行一次后均有 。故在最后一次执行后 。又由于T在算法执行过程中非负，所以T=0。故算法必然正确。
最后，根据求出的di值代回求出ai就可以了。
总结：
为了在问题的特殊性质中挖掘可用的信息，通常都需要一些数学方面的技巧。在这一题的解题过程中，我们就可以看到数学技巧是如何应用的。

*/
#define NMAX 20
int x[NMAX];
int yuan[NMAX];
int temp[NMAX];

void cal(int num,int s1)
{
	int s2,sum,i;
	s2=num*(num-1)/2;
	sum=(s1+s2)/2;
	cout<<sum<<endl;
	for(i=num-1;i>0;i--)
	{
		if(sum>=i)
		{
			sum-=i;
			x[i]=1;
		}
		else x[i]=0;
		temp[num-i]=2*x[i]-1;
	}
	yuan[0]=0;
	for(i=1;i<num;i++)
		yuan[i]=yuan[i-1]+temp[i];

}

void print(int num)
{
	int i;
	for(i=0;i<num;i++)
		cout<<yuan[i]<<" ";
	cout<<endl;
}
int main()
{
	int num,sum;
	scanf("%d%d",&num,&sum);
	if(num%2==1) cout<<"NO SUCH STRING"<<endl;
	else
	{
		cal(num,sum);
		print(num);
	}
	return 0;
}