hdu多校总链接

• 置换群
• 排列组合
• 计算几何
• 线段树
• LIS
• LDS

B. Beautiful Now

for each permutation of digits, the minimum number of swaps equals to n minus the number of disjoint cycles in the permutation. We can solve the problem by enumerating all the n-permutations. That is, for each permutation, we just check if it can be reached within k swaps (because swapping the same digit is permitted) and then update the answer. Time complexity is expected to be O(n!) while algorithms in time complexity O(n!n) may get TLE verdict (but who knows?). In order to achieve the excepted time complexoty, we may need to maintain some information about chains and cycles effciently during the process of searching and backtracking.

E. Everything Has Changed

Note that the cutting areas do not intersect and the different areas do not affect each other. Just enumerate every cutting area intersecting the disk and then count the lengths of their circumferences covered by each other.

If there are two operations covering the same interval, we can just keep the maximum one. For each operation(l,r,v),let d be 」log2(r-l+1)」, replace this operation by two operations (l,l+2^d-1,v) and (r-2^d+1,r,v). After that, the length of the interval that each operations covers is a power of 2, which means the lengths are only O(logn) types. The remaining part is just to enumerate operations in length decreasing order and split each operation into two operations of equal length until the length is one. Time complexity is O(m+nlogn) and space complexity is O(nlogn).

H. Hills And Valleys

dp方程我们的设计思路是

$dp[i][j]=max(dp[i-1][j]+(a[i]==b[j]),dp[i][j-1])$

2018.08.11晚

2018.08.12 早

2018.08.12 晚