Straightforward implementation with exhaustive enumeration.
The main idea is binary search, since if v is a reasonable result, then any v' > v also serves as a reasonable answer. Moreover, we can calculate kp in previous, and it is sufficient to consider p up to 40, since the problem guarantees that the maximum value of n is 109. Do not worry that kp will lead to overflow, as we will never use the value which exceeds v. The left work is to adopt binary search to find the minimum value of v.
165C - Another Problem on Strings
We can solve this problem based on two cases.
1) k = 0: we find out all the consecutive intervals [l, r] that only 0s are included. This interval contributes 
to the final answer, where t = r - l + 1.
2) k > 0: we find out each interval [l, r] that exactly k 1s are included and integers with indices l and r are also 1s. Then, we move from position l to the left and find out the first index l' that a[l'] = 0 while a[l' - 1] = 1. Similarly, we find the index r' so that a[r'] = 0 while a[r' + 1] = 1. Then, this interval contributes (r' - r) × (l - l') to the final answer.
The total complexity is O(N) according to amortized analysis.
At first, we should realize that the whole graph is either a single link, or a tree that there exists a unique root node so that after deleting this node, the tree is decomposed into several independent single links.
We can build a segment tree to deal with the modification of the color of some edge, and the query of the distance between two nodes. In order to do this, we have to assign new indices to each edge. Without loss of generality, we start from the root and adopt dfs for each of the “single link”. For each link, we assign both the edges and nodes with indices 1,2,3,... until all the nodes have been visited. After these operations, we can find that for each single link, the indices of edges and nodes belonging to it have consecutive numbers. As for the segment tree, each node contains its managing range, i.e., the edges that it covers, and the number of white edges belonging to this range.
When the color of some edge is changed, it is equivalent to modifying a single element in the segment tree. For instance, when an edge becomes white, we increase one for each node that covers this edge in the segment tree. When we are asked to output the distance between two nodes a and b, we should consider two cases based on whether they belong to the same single link or not, which can be conveniently obtained by using disjoint set union. Besides, for each node, we should also compute the distance to the root node, as dis[a], in previous. If they belong to the same single link, we can directly query the segment tree to check whether there exists at least one white edge between them, since they have consecutive indices in the segment tree, and the answer is |dis[a] - dis[b]|. If they belong to different single links, we should check whether there is at least one white edge from node a the root node, and from b to the root node, independently. To achieve this, we should find the index of the child node that belongs to the same single link as node a (or b), and query this range in the segment tree. The answer is dis[a] + dis[b].
I read tutorials and found that the solution is based on dp.
We start with a simple example. Suppose that we are asked to find an integer x that reaults in zero after XOR with 6. We write 6 in binary form as (00...0110), where the total number of digits is 22 (note that 4 * 106 = 4 * (103)2 < 4 * 10242 = 222, and thus 22 digits are enough to represent all the integers required by this problem). We can see that (11...111001) can serve as a potential answer. However, we can find many more reasonable sequences, such as (11....110001), (11...110000) and so on. One can check that the correct sequences must have zeros at the second and third positions, counted from right to left, while the values at the other positions never matter.
We define that a sequence can be reduced to another sequence, by converting some single 1 to 0. For instance, for (01110), it can be reduced to (01100), (01010), (00110). Thus, given an integer x, we represent it in a binary form and inverse every binary digit (0 to 1 and 1 to 0), obtaining a new integer x'. Then, it is sufficient to check whether x' can be reduced to some integer that can be found in the given array.
We can use bit-mask based dp algorithm to calculate for each integer that, whether it can be reduced to some other one that has appeared in the given sequence.
Comments (0)
