[7.16] code source - [array division] [disassembly] [select 2] [maximum common divisor]

#665. Array partition

The question ： Given $n(n\le 100)$ It's an integer , Divide it into just $k(k\le 100)$ Subarray , Find the maximum value of sum operation after summing each sub array .

Answer key ：( Dynamic programming ) Code source daily question Div1 Array partition

Ideas ： At first I defined $dp(i,j)$ For the former $i$ Each element is divided into $j$ The maximum value of the block , The transfer equation is $dp(i,j)=\max (dp(k,j-1)\&(sum(k+1,i)))$ , But that doesn't work . Tell me in detail why not .

First , Each state is essentially a set , Each element in the set corresponds to a weight , According to the topic, we usually require the upper bound or lower bound of the weight of the set （ That is what is usually said $\max -\min$ ）, That is, the attributes of the set . If we adopt DP Find this attribute recursively , We must ensure that the attributes of the subsequent state and the attributes of the precursor state are monotonous . How do you understand that ？

We define an independent variable $x$ , Its definition domain is the weight value domain of the precursor node （ Of course, there are upper and lower bounds ）. According to the recursive equation , Weight value range of subsequent nodes $y=f(x)$ . Only when $f(x)$ It is incremental within the definition field , Only by maintaining the upper bound of the precursor （ Lower bound ）, To get the upper bound of the subsequent range （ Lower bound ）. If monotonic increase is not satisfied , Then the extreme value of the subsequent state does not necessarily lie on the upper bound of the precursor state （ Lower bound ） obtain . This recursive monotone property of dynamic programming is also important .

Back to the question , Because it's a bit operation , Increasing the value of the predecessor node does not necessarily increase the value of the successor node , Then this method will not work .

The solution to this problem is ： Enumerate the binary bits of the answer from the high order , Then judge whether the sequence is divided k The scheme of parts makes the sum greater than or equal to ans, Then decide whether to keep the bit 1 The decision .DP Existence , $y\ge x$ If and only if $(y\&x)==x$ , If there is a segmentation scheme , Every paragraph must meet $su{m}_i\&x==x$ , Definition $dp(i,j)$ Before presentation i Divided into k Whether there is a scheme to make the sum greater than or equal to x,DP The existence of transfer .

AC Code ：http://oj.daimayuan.top/submission/290489

---

#611. Dismantle

The question ： Multiple sets of data . Each group is given two numbers X,Y, Ask how many lengths are Y The product of the integer sequence of is X. $T\le 10^5,X,Y\le 10^6$ .

Ideas ： Split the prime factor and allocate it .

Optimization of the method of splitting qualitative factors （$O(a\sim b)$ Indicates that the pretreatment time is $a$, The query time is $b$）：

1. Preprocess to get all primes , Then use only prime numbers to sift , Time complexity $O(n\sim \frac{\sqrt{n}}{\ln \sqrt{n}})$
2. Pretreat all numbers with an Ehrlich sieve , Get the prime factor of each number （ The series is $\log n$）, The time complexity is $O(n\times \log n\sim \log n)$

This problem uses the second optimization . We store all the prime factor preprocessing of a number , Then use it directly .

vector<int> primes[M];

for(int i = 2; i < M; i ++ ){
    
	if(primes[i].size()) continue;
	for(int j = i; j < M; j += i){
    
		int t = j, cnt = 0;
		while(t % i == 0) cnt ++ , t /= i;
		primes[j].push_back(cnt);
	}
}

AC Code ：http://oj.daimayuan.top/submission/291303

---

#618. Selection 2

The question ：

Answer key ：( greedy ) Code source daily question Div1 Selection 2

Ideas ： First of all find out $m$ . If there is one, the length is $m$ The subsequence of satisfies the meaning of the question , Then there must be a length of $m$ The subinterval of satisfies the meaning of the question , Because we fix the right endpoint , Move other numbers to the right , The average will only get bigger . In this way, we can find $m$ .

Find out $m$ after , For each substring that meets the meaning of the topic , Only move the left endpoint to the left , This ensures that the left endpoint moves as far to the left as possible . Still two points .

AC Code ：http://oj.daimayuan.top/submission/290739

---

#131. greatest common divisor

The question ： You have a ring , It's on the ring $n$ A positive integer . You can cut the ring into sections , Each paragraph contains one or more numbers .

For a segmentation scheme , The degree of beauty is the maximum common divisor of each number and , You want to maximize the beauty of the segmentation program , about $k=1,2,\cdots ,n$ Output the answer .

Answer key ：( mathematics / enumeration / Problems on the ring ) Code source daily question Div1 greatest common divisor

Ideas ： We divide the rings into $k$ Share , that $gcd|s_i,i\in [1,k]$ , namely $gcd|{\sum }_{i=1}^k{s}_i=sum$ . Let's enumerate $sum$ The factor of is $gcd$ . The order of magnitude of the factor can be considered as expectation $\log n$ , The worst $\sqrt{n}$ Of .

about $gcd$ , We can find out how many segments can be divided at most , Because segments can be merged , The suffix and the maximum are enough . If it is a normal sequence , Then directly find how many numbers in the prefix sum are $\mathrm{mod}gcd$ In the sense of $0$ . If it's a ring , We ask how many numbers are in the prefix and $\mathrm{mod}gcd$ In the sense of equal .

AC Code ：http://oj.daimayuan.top/submission/290873