The following are all intranet
Matrix game
http://hzoj.com/contest/60/problem/2
Just started I thought that as long as there is a 1 in each row and each column, it is a feasible solution,
and found that it can Simple data hacked by yxm:
1 1 1 1
0 0 0 1
0 0 0 1
0 0 0 1 span>
The positive solution is a bipartite graph.
rows and columns are two distinct sets of nodes,
If there is a 1, you can connect edges between its rows and columns,
If the maximum number of matches is n, the graph has a feasible solution.
It is easy to think that the number of 1s on the same row and column will not change,< /p>
Because it is required to be on the diagonal, if a 1 is used, its row and column cannot be exchanged to exist At the position of 1, these 1s are abolished,
So it is feasible to use bipartite graphs.
I love running every day< /span>
http://hzoj.com/contest/60/problem/7< /span>
This question has no idea at the beginning, only 45 points of violence.
Although I know it is the difference on the tree, I can’t think of maintaining anything.
xuefeng reminded me and reminded me of maintaining a constant amount through variables Look for this invariant in the existing information.
The path of a point pair is $x->lca->y$, let d be Depth, len is the point-to-point distance, w(a) is the observation time at point a.
in $x ->lca$ Path segment, point a can be observed if and only if $w(a)=d(x) -d(a) \Leftrightarrow w(a)+d(a)=d(x)$,
In the path segment of $lca->y$, click a to observe Until and only if $w(a)=len-(d(y)-d(a)) \Leftrightarrow w(a)-d(a )=d(x)-2*d(lca)$.
Maintain the two invariants on the right side of the equal sign.
This question reminds me of the tail of a rainy day. In that question, maintenance is required The maximum value of the interval,
The maintenance method used is to merge the line segment trees, but in this question Medium complexity may be very high.
This question allows us to maintain a single-point value and satisfy this value Reducibility.
As long as a global array is maintained, the current value is recorded when dfs enters, and after the recursion ends Count the current value, the latter minus the former is the contribution of its subtree to it.
Journeys
http://hzoj.com/contest/60/problem/11
About interval building:
$O(n^2m)$’s violence is not mentioned, a kind of $O(nm)$The method is:
For each interval edge, create a new node, create a one-way edge with a weight of 0 between each point of interval a and this node, and establish a one-way edge with a weight of 0 between this node and interval b. Click to create a one-way edge with a weight of 1,
to meet our requirements.
the better one is the oneThe method of $O(mlogn^2)$ is:
Create two line segment trees, namely the in-side line-segment tree and the out-side line-segment tree.
We put each node on two line segment trees, let them be the line segment tree Leaf node,
So we can support one interval to build an edge to another interval.
Combining the two methods, you can get $O(mlogn)$ method.
Tree
http://hzoj.com/contest/60/problem/4
wqs two points< /span>
Add a weight to each white edge, and divide the size of this weight in half.
Obviously for the additional weight change, the obtained minimum number of white edges selected in the spanning tree It is monotonous.
When we just get the required number of white borders, we get the most solvable one.
But for many cases where the weights are the same, we can’t get exactly k.
Analyze the requirements in the question, and we can update the answer when it is greater than k.