SSL-OI Summer Camp 2020.08.21 Group A

I spent a lot of money on keyboards and keycaps these two days, because I drank too much? The F60 actually removed the Bluetooth module (although I don't use it much normally), the pink F60 paired with pure white keycaps still looks okay. Today I tried to get partial scores, it wasn't very smooth, but it was still a decent attempt.

A Decisive Battle

A small easy problem, but I still didn't think of the correct solution and went for partial scores.

Problem Statement

Given a graph with $n$ vertices and $m$ edges, ask: which vertex to delete so that the remaining graph becomes a tree. It is guaranteed that at least one vertex can be the answer.

Story

I chose a partial score for $m=n-1$ and a partial score for $m=n$, and in the end only the tree case was solved, 20pts.

Solution

First, the deleted vertex must not be a cut vertex, which can be found using tarjan. For a non-cut vertex $x$, if deleting this vertex leaves a tree, then we must have $m-Due_x=n-2$. $Due$ represents the degree of this vertex.

However, I don't know strongly connected components, so I can't judge the graph either

B The End

C Interpretation

Obviously this is a greedy problem, but I got the greedy wrong. As expected, people who don't usually do greedy problems won't do them in exams either.

Problem Statement

Given an array $a$ of length $n$, merge two numbers in the form $a_i+2\times a_i$. There are $q$ queries, each query asks for the maximum value after merging in the interval $[l,r]$.

$n,q\leq10^5$, the answer is modulo $10^9+7$.

Story

Obviously, since we need the maximum and also modulo, it can only be greedy. In the exam, I wrote an interval DP for the first subtask $n\leq10$, and tried to write an $n^2$ brute force (but it was wrong).

Correct Solution

By intuitively understanding the solution, we can find that if for a given subsegment $b$ we have $f(b)<0$,

It is easy to see that this problem is about multiplying each value by a coefficient $2^k$ and then summing. If it is a continuous segment (from back to front) merged, the exponent $k$ of the coefficients in the segment is increasing. For example: $$a_{i}^{2^0}+a_{i+1}^{2^1}+a_{i+2}^{2^2}+a_{i+3}^{2^3}$$

To merge two consecutive segments, let the sums of the two segments be $s_1$ and $s_2$ respectively, after merging we have $s=s_1+2\times s_2$. (as in the problem)

Consider the case $l=1$ (Sub5). Obviously, the coefficient of $a_1$ is $1$, and the coefficients of other numbers are at least $2$. (They will be merged with $a_1$ at least once) If the added value is less than $0$, we want its exponent to be as small as possible, so we set the exponent to $2$. If the added value is greater than $0$, it will definitely make a positive contribution, so we set its coefficient exponent to the coefficient exponent of the previous one $+1$. (Merge into the previous block) For example: $$(a_i\geq0)$$