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

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 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 ≤ 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

if A_i > B_i, we also say that

as soon as A_i ≠ 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 ≤ 10⁶

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

s[i] represent

do a change, we have

use suffix maximum array is enough.

consider transform as swaping characters.

C++ CODE

F. Video Cards

it is easy to notice that A_i ≤ 2 × 10⁵

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 × 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 algorithm.

C++ CODE

Thanks for reading!