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 $pos_{a}$ now and we wanna go to $pos_{b}$, there are two ways.↵
↵
1.clockwise, which cost $|pos_{a}-pos_{b}|$↵
↵
2.counter-clockwise, which cost $26-|pos_{a}-pos_{b}|$↵
↵
just choose the smaller one.↵
↵
[C++ CODE] [(http://mirror.codeforces.com/contest/731/submission/21476722])↵
↵
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 $a_{i}$ pizzas in that day↵
↵
but sometimes $a_{i}$ can't be divided by $2$↵
↵
so we need to buy option#2 : one pizza each day↵
↵
then $a_{i}-1$ can be divided by $2$↵
↵
but don't forget $a_{i+1}$ shoude decrease $1$↵
↵
why only one? beacause the main idea is to make smaller influence↵
↵
btw, when $a_{i}<0$ ( after decreasing ), stop and exit.↵
↵
[C++ CODE] [(http://mirror.codeforces.com/contest/731/submission/21478267])↵
↵
C. Socks↵
==================↵
↵
consider $l_{i},r_{i}$ 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 $O(n\alpha(n)+n\log n)$ algorithm.↵
↵
[C++ CODE] [(http://mirror.codeforces.com/contest/731/submission/21483617])↵
↵
D.80-th Level Archeology↵
==================↵
↵
imagine we need to sort an array $A$↵
↵
we want $A_{i}<A_{j}\;\;(j>i)$, we just need to make $A_{i}<A_{i+1}$↵
↵
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:$A\;and\;B(A\;is\;in\;front\;of\;B)$↵
↵
According to the notice, we know for each $i$ we need $A_{i}\leq B_{i}$↵
↵
let x represent the answer, consider two elements, $A_{i},B_{i}$↵
↵
if $A_{i}=B_{i}$, skip↵
↵
if $A_{i}<B_{i}$, absolutely $i\notin\begin{Bmatrix}C-B_{i}+1,C-A_{i}\end{Bmatrix}$↵
↵
if $A_{i}>B_{i}$, we also say that $i\notin\begin{Bmatrix}0,C-A_{i}\end{Bmatrix}\cup\begin{Bmatrix}C-B_{i}+1,C-1\end{Bmatrix}$↵
↵
as soon as $A_{i}\neq B_{i}$ is satisfie, we can skip the rest.↵
↵
how to solve these inequalities? just use Segment_Tree or Bit or Difference↵
↵
i recommend Difference because $C\leq 10^{6}$↵
↵
[C++ CODE] [(http://mirror.codeforces.com/contest/731/submission/21517946])↵
↵
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 $dp[i]=max\begin{Bmatrix}s[i]-dp[j]\end{Bmatrix}$↵
↵
$s[i]$ represent $\sum_{j=1}^{i}a[j]$↵
↵
do a change, we have $dp[i]=s[i]-max\begin{Bmatrix}dp[j]\end{Bmatrix}$↵
↵
use suffix maximum array is enough.↵
↵
consider transform as swaping characters.↵
↵
[C++ CODE] [(http://mirror.codeforces.com/contest/731/submission/21509197])↵
↵
F. Video Cards↵
==================↵
↵
it is easy to notice that $A_{i}\leq2\times10^{5}$↵
↵
so we use an array to count the number of $A_{i}$↵
↵
after that, we suppose $A_{i}$ is the base↵
↵
then we know all $P$ that $P=k\times A_{i}$, find how many times $P$ appears after modifying↵
↵
it is easy to solve by the array we created.↵
↵
because of this is harmonic progression, so it is an $O(n\log n)$ algorithm.↵
↵
[C++ CODE][(http://mirror.codeforces.com/contest/731/submission/21490349])↵
↵
↵
Thanks for reading!
==================↵
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 $pos_{a}$ now and we wanna go to $pos_{b}$, there are two ways.↵
↵
1.clockwise, which cost $|pos_{a}-pos_{b}|$↵
↵
2.counter-clockwise, which cost $26-|pos_{a}-pos_{b}|$↵
↵
just choose the smaller one.↵
↵
[C++ CODE]
↵
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 $a_{i}$ pizzas in that day↵
↵
but sometimes $a_{i}$ can't be divided by $2$↵
↵
so we need to buy option#2 : one pizza each day↵
↵
then $a_{i}-1$ can be divided by $2$↵
↵
but don't forget $a_{i+1}$ shoude decrease $1$↵
↵
why only one? beacause the main idea is to make smaller influence↵
↵
btw, when $a_{i}<0$ ( after decreasing ), stop and exit.↵
↵
[C++ CODE]
↵
C. Socks↵
==================↵
↵
consider $l_{i},r_{i}$ 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 $O(n\alpha(n)+n\log n)$ algorithm.↵
↵
[C++ CODE]
↵
D.80-th Level Archeology↵
==================↵
↵
imagine we need to sort an array $A$↵
↵
we want $A_{i}<A_{j}\;\;(j>i)$, we just need to make $A_{i}<A_{i+1}$↵
↵
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:$A\;and\;B(A\;is\;in\;front\;of\;B)$↵
↵
According to the notice, we know for each $i$ we need $A_{i}\leq B_{i}$↵
↵
let x represent the answer, consider two elements, $A_{i},B_{i}$↵
↵
if $A_{i}=B_{i}$, skip↵
↵
if $A_{i}<B_{i}$, absolutely $i\notin\begin{Bmatrix}C-B_{i}+1,C-A_{i}\end{Bmatrix}$↵
↵
if $A_{i}>B_{i}$, we also say that $i\notin\begin{Bmatrix}0,C-A_{i}\end{Bmatrix}\cup\begin{Bmatrix}C-B_{i}+1,C-1\end{Bmatrix}$↵
↵
as soon as $A_{i}\neq B_{i}$ is satisfie, we can skip the rest.↵
↵
how to solve these inequalities? just use Segment_Tree or Bit or Difference↵
↵
i recommend Difference because $C\leq 10^{6}$↵
↵
[C++ CODE]
↵
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 $dp[i]=max\begin{Bmatrix}s[i]-dp[j]\end{Bmatrix}$↵
↵
$s[i]$ represent $\sum_{j=1}^{i}a[j]$↵
↵
do a change, we have $dp[i]=s[i]-max\begin{Bmatrix}dp[j]\end{Bmatrix}$↵
↵
use suffix maximum array is enough.↵
↵
consider transform as swaping characters.↵
↵
[C++ CODE]
↵
F. Video Cards↵
==================↵
↵
it is easy to notice that $A_{i}\leq2\times10^{5}$↵
↵
so we use an array to count the number of $A_{i}$↵
↵
after that, we suppose $A_{i}$ is the base↵
↵
then we know all $P$ that $P=k\times A_{i}$, find how many times $P$ appears after modifying↵
↵
it is easy to solve by the array we created.↵
↵
because of this is harmonic progression, so it is an $O(n\log n)$ algorithm.↵
↵
[C++ CODE]
↵
↵
Thanks for reading!
