Something need to say
first of all, this is my first tutorial of one whole round, so there must be some places that i need to improve, if you find bug, just comment it and i will be pleasure to update.
Secondly, this round i got rk 151 in div2. it's too stupid that i came up with a wrong idea which made me waste lots of time, but after the competition, i finish them, it seems the offical tutorial still not okay. Therefore, i published this one.
Third, i wanna say thanks to my friends: samzhang[15120] & quailty[quailty]
A. Night at the Museum
We know if we are
Unable to parse markup [type=CF_TEX]
now and we wanna go toUnable to parse markup [type=CF_TEX]
, there are two ways.1.clockwise, which cost
Unable to parse markup [type=CF_TEX]
2.counter-clockwise, which cost
Unable to parse markup [type=CF_TEX]
just choose the smaller one.
B.Coupons and Discounts
there are two ways to buy pizzas:
1.one day, two pizzas.
2.two day, one pizza each day.
We know it is always better if we can buy exactly ai pizzas in that day
but sometimes ai can't be divided by 2
so we need to buy option#2 : one pizza each day
then
Unable to parse markup [type=CF_TEX]
can be divided by 2but don't forget ai + 1 shoude decrease 1
why only one? beacause the main idea is to make smaller influence
btw, when
Unable to parse markup [type=CF_TEX]
( after decreasing ), stop and exit.C. Socks
consider
Unable to parse markup [type=CF_TEX]
as a non-directed edge.so the question changes into: there are some conected components, one component must be the same color, query the minimum times to modify one vector's color.
it's easy to solve with dsu , first of all, we use dsu to get all conected components. For each conected component, we use the color which has the most frequency to colour this connected component.
so we get an
Unable to parse markup [type=CF_TEX]
algorithm.D.80-th Level Archeology
imagine we need to sort an array A
we want
Unable to parse markup [type=CF_TEX]
, we just need to makeUnable to parse markup [type=CF_TEX]
this problem is the same way, if we want all words are sorted, we just need to compare each pair of adjacent words.
consider about the following two words:
Unable to parse markup [type=CF_TEX]
According to the notice, we know for each i we need
Unable to parse markup [type=CF_TEX]
let x represent the answer, consider two elements,
Unable to parse markup [type=CF_TEX]
if
Unable to parse markup [type=CF_TEX]
, skipif
Unable to parse markup [type=CF_TEX]
, absolutelyUnable to parse markup [type=CF_TEX]
if
Unable to parse markup [type=CF_TEX]
, we also say thatUnable to parse markup [type=CF_TEX]
as soon as
Unable to parse markup [type=CF_TEX]
is satisfie, we can skip the rest.how to solve these inequalities? just use Segment_Tree or Bit or Difference
i recommend Difference because
Unable to parse markup [type=CF_TEX]
E. Funny Game
let dp[i] represent the maximum difference when Petya is first,and he got prefix [1, i]
it's easy to see that
Unable to parse markup [type=CF_TEX]
s[i] represent
Unable to parse markup [type=CF_TEX]
do a change, we have
Unable to parse markup [type=CF_TEX]
use suffix maximum array is enough.
consider transform as swaping characters.
F. Video Cards
it is easy to notice that
Unable to parse markup [type=CF_TEX]
so we use an array to count the number of Ai
after that, we suppose Ai is the base
then we know all P that
Unable to parse markup [type=CF_TEX]
, find how many times P appears after modifyingit is easy to solve by the array we created.
because of this is harmonic progression, so it is an algorithm.
Thanks for reading!