根据上排的数填写下排的数,并满足要求.根据上排给出十个数,在其下排填出对应的十个数,要求下排每个数都是上排对应位置的数在下排出现的次数.上排的数：0,1,2,3,4,5,6,7,8,9.

Question

根据上排的数填写下排的数,并满足要求.
根据上排给出十个数,在其下排填出对应的十个数,要求下排每个数都是上排对应位置的数在下排出现的次数.上排的数：0,1,2,3,4,5,6,7,8,9.

Answer 1

解题思路：关键是理解“要求下排每个数都是先前上排那十个数在下排出现的次数”.
做以下分析：设总共有n个数,上排a[0...n-1],下排b[0...n-1],.
1）下排n个数的累加和为n,即b[0]+b[1]+...+b[n-1] = n
2）ai*bi的累加和也为n,即a[0]*b[0]+a[1]*b[1]+...+a[n-1]*b[n-1] = n
3）对于b中任意一个元素b[j],都存在i,a[i] = b[j].
4）对于b中任意一个元素b[j],都有b[j] >= 0
5）如果a中存在负数.其在b中出现的次数一定为0.如果a中数值大于n,则其出现次数也为0.
6）a中至少有两个非0数值在b中出现的次数非0
a：由1）n > n*b[i],其中b[i]为最小值,则a b中一定均有数值0,否则无解.设a[0] = 0,b[0]为a[0]在b中出现次数.
b：由于b中一定存在0,则0的出现次数一定大于0,因此b[0]>0 且b[0] < n,b[1...n-1]中至少一个值为0.非0元素出现的次数一共是n-b[0].
c：有2）和6）对任意a[i],a[i]*b[i] < n,即b[i] < n/a[i],对所有a[i]>=n/2的元素中,在b中出现的次数必须最多只有1个出现次数不为0,且为1.其余出现次数均为0,即[1,n/2）范围内最多只有n/2-1个元素,故0出现的次数必不小于n/2,[n/2,n）范围内的元素必有一个出现次数为1.因此a数列中也必须有1,否则无解.
d：有c得在数值范围为（0,n/2)中（假设有x这样的数）出现的次数和s为n - b[0]或n-b[0]-1.其中1出现的次数至少为1（由c得）.又如果1出现的次数为1,则1出现的次数已经为2,故1出现的次数必大于1.设为x,则x出现的次数至少为1,而x>1,如果x出现的次数大于1,那么必须要有其他数出现的次数为x,这样无法收敛.故x出现的次数只能为1,1出现的次数只能为2.
结论：
0出现的次数为n-4,1出现的次数为2.2出现的次数为1.n-4出现的次数为1.如果数列中无则四个数,无解.