<> subject

Problem description

Given a 1~N Arrangement of a[i], Add two adjacent numbers at a time , Get a new sequence , Repeat this operation for the new sequence , Obviously, the length of the sequence obtained each time is less than that of the last time 1, Finally, there is only one number left .
   for example :
  3 1 2 4
  4 3 6
  7 9
Now if you know N And the final number sum, Request initial sequence a[i], by 1~N An arrangement of . If there are multiple answers , The one with the smallest dictionary order is output . The data is guaranteed to be solved .
Input format

The first 1 Line two positive integers n,sum
Output format

One 1~N An arrangement of

sample input

4 16

sample output

3 1 2 4

Data scale and agreement


I feel this topic is not standardized :n and N All appeared , We should unify the letters ; Also used sum Declared as a variable , stay python in sum Is a function , Avoid using function names as variable names , No final figures were given s Value range of … In addition, we should also distinguish between the topics “ One 1~N Arrangement of ”,“1~N An arrangement of ”,“ One 1~N An arrangement of ” Meaning of , Because I understand the wrong topic , I also asked for help in the Q & A area , Woo woo , Many words are tears …

<> analysis

Let's take a look at the topic , His general meaning is to give a number n, adopt 1 ~
n Various permutations of ( hypothesis n yes 5, So it's 1,2,3,4,5 Various permutations of ) Continue to add in pairs to get a number , If this number is equal to the sum , Then return to this arrangement , When there are multiple sequences, the sequence with the smallest dictionary order is returned .([2,1,3],[1,3,2],[3,1,2] The sequence with the smallest dictionary order is [1,3,2]).

The easiest way to think of is to enumerate each sequence from low to high in dictionary order , Let each sequence sum and add continuously , Finally get a number , Compare this number with the target value to see if it is equal , If equal , The sequence is returned directly , Otherwise, continue to add the next sequence , Until a qualified sequence is encountered . This method can be obtained 70 branch , Students who don't want to waste too much time on this question , That's enough .

Enumerate each sequence , Generally, it is used DFS To find . as far as I'm concerned , I have tried many methods to optimize the above algorithm, but they have failed ,(AC It's not easy to take it !!) Even if it is added in the process of traversal search, such as when the added value of the sequence is greater than the target value , Conditions for early termination of recursion , Or only one 70 branch . It shows that this problem still needs to find out the law in order to further optimize this algorithm .

This question is similar to Yang Hui's triangle , Is a number whose value is equal to the sum of its left and right shoulder values , If you look at the example of this problem , Combined with Yang Hui triangle , You can find out the law .

It doesn't matter if you can't read the words clearly , Can you see the picture clearly ? I can see clearly. I'm about to say it . Cough ,ab The sum of the corresponding elements multiplied by each row in the figure is equal . The conditions are quite equal good, With it , No more middlemen will make the difference , Directly in one step .

<> thinking

After learning that this topic is closely related to Yanghui triangle , We can optimize the search algorithm through Yang Hui triangle .

Because we are exhausting the last line of sequence , That's it n Elements , So we also need to get the third chapter of Yang Hui triangle n All elements of the row . because n Little value , We can directly pass the relationship that the value of a number is equal to the sum of the values of its two numbers , Continuous line by line launch n All elements of the row .

Then let each length be n The sequence of is multiplied by the corresponding element of the row, summed and compared with the target value , If equal , Then print the sequence and terminate the recursion , Otherwise, continue the search . Come here , The efficiency of the optimized algorithm is significantly improved , Submit the algorithm of this idea to you 90 branch , It's already very good .

Still bad 10 branch , this 10 The difference is that there is no pruning . We should not let the length of the exhaustive sequence be n The sequence and Yang Hui triangle are multiplied and summed, and the result is consistent with the target value s compare . Instead, it should match the target value in the process of its generation s Compared to , If the length during generation is less than n The sum of the sequence multiplied by Yang Hui triangle has been greater than the target value , Then the complete sequence must be greater than the target value , Recursion can be terminated in advance .

<> code

Deep first search is to start trial and error search from low to high in dictionary order , When the first qualified sequence is found , You can return directly , Because this sequence must be the sequence with the smallest dictionary order .
# Yanghui triangle def triangle(): # Store each line of Yang Hui triangle lines = [[1], [1, 1]] if n <= 2: #
When n Less than or equal to 2 Time , Directly return to the corresponding line , Because the subscript from 0 start , So it's n-1 return lines[n-1] #
Traverse from the third line , Because there are already two ready-made , So you can traverse two lines less , so n-2 for i in range(n - 2): temp = [] #
ergodic lines In order to remove the element of the next line for j in range(len(lines[-1]) - 1): # The value of a number is equal to the sum of the values of its two numbers
val= lines[-1][j] + lines[-1][j + 1] temp.append(val) # Then the two special cases 1 Put it inside lines.
append([1] + temp + [1]) # Return to the last line of Yang Hui triangle , The length of the row element is equal to the length of the sequence element return lines[-1] # Depth first search
temp Save the generated sequence cnt Represents the sum of the generated sequence elements multiplied by the corresponding elements of Yang Hui triangle ind Subscript representing the last sequence def search(temp, cnt, ind)
: # Early termination conditions not met , Realize pruning if cnt > s: return False if len(temp) == n: #
When the length is n And cnt When equal to the target value , Print all elements of the sequence if cnt == s: for i in temp: print(i, end=" ") #
Element returned found True, No need to continue recursive search return True # If not, return False Keep looking return False #
Ergodic base sequence ,i Represents the index ,j Represents the value under the corresponding index for i, j in enumerate(nums): #
If this number is used , That is, the number already exists in the generated sequence , The following statement is not executed # If this number is not used , Then run the following program if not used[i]: #
Mark unused numbers as used used[i] = True # Add this number to the generation sequence temp.append(j) #
Calculate the sum of the product of the value of this position of the generated sequence and the value of the corresponding position of Yang Hui triangle val = temp[ind] * yanghui[ind] # Add it to the sum cnt += val
# Move to next element location ind += 1 # Continue backtracking to add numbers to the generated sequence , If a qualified sequence has been found, it is returned directly Ture End this recursion if search(temp
, cnt, ind): return True # Status reset , This is a feature of depth first search , If no matching sequence is found , You need to deselect the last selected number to select another number
used[i] = False temp.pop() cnt -= val ind -= 1 n, s = map(int, input().split())
# nums Is the foundation of all sequences , Contains all the elements that appear in the sequence nums = [i for i in range(1, n + 1)] #
used Tag array , Has the tag number been used ,used Array fit nums Use with arrays , Used to mark the second 1~ The first n Have the numbers been used used = [False for i in
range(n)] # Call Yang Hui trigonometric function , Get all elements in the last row yanghui = triangle() # Start depth first search search([], 0,

©2019-2020 Toolsou All rights reserved,
evo Tool usage problems ——Degenerate covariance rank, Umeyama alignment is not possible Experiment 4 Automated test tools - software test mysql Export data sql sentence _mysql according to sql Query statement export data Create a thread ——— Javaweb (3) Data structure experiment ( three )—— Stacks and queues TS stay vue2 Writing in the project web Front end signature plug-in _signature_pad Plug in implements electronic signature function docker Where is the image stored Qt Getting Started tutorial 【 Basic controls 】QCalendarWidget calendar control springboot How to get reality in ip address