[contest:701]↵
↵
There is still no formal EDITORIAL for Codeforces Round #364 (Div. 2) yet ,so I write a informal one.↵
↵
Sorry for my poor English and poor format.↵
↵
↵
↵
↵
[problem:701A]↵
↵
You can calculate the sum (x) of a pair of cards.↵
↵
x=2*(a1+a2+...+an)/n↵
↵
For every card ai,find a card ak which ai+ak=x and k is not used.↵
↵
The n is small,so you can simplely write a o(n*n) solution(also there is a o(n) one,o(n*n) is enough).↵
↵
My o(n*n) solution:[submission:19328905]↵
↵
↵
[problem:701B]↵
↵
You can just record the number of rows and columns that is not under attack.↵
↵
If r rows and c columns is not under attack there is r*c cells that is not under attack.↵
↵
It's o(m).↵
↵
My o(m) solution:[submission:19330540]↵
↵
↵
[problem:701C]↵
↵
You can just use two pointers↵
↵
There are x types of Pokemon↵
↵
if [i,dp[i]-1] has x-1 types of Pokemon and [i,dp[i]] has x types of Pokemon↵
↵
dp[i+1]>=dp[i]↵
↵
so it's o(n)↵
↵
my o(xlogx+n) solution:[submission:19332828]↵
↵
↵
[problem:701D]↵
↵
It's a math problem.↵
↵
let d=ceil(n/k)↵
↵
Just look at the bus.↵
↵
it goes like that:↵
↵
>>>>>>>>>>>>↵
↵
___<<<<<<<<<↵
↵
___>>>>>>>>>>>>↵
↵
______<<<<<<<<<↵
↵
_____>>>>>>>>>>>>↵
↵
_>>>>>>>>>>>>↵
↵
____<<<<<<<<<↵
↵
____>>>>>>>>>>>>↵
↵
_______<<<<<<<<<↵
↵
_______>>>>>>>>>>>>↵
↵
__________<<<<<<<<<↵
↵
__________>>>>>>>>>>>>↵
↵
The '_' means empty(I cannot format it).↵
↵
The long lengths are the same(x) and goes to right.↵
↵
The short lengths are the same(y) and goes to left.↵
↵
It goes to right and put the old students down and does to left and welcome new students.↵
↵
so x+y:x-y=v2:v1↵
↵
it goes for d xs and (d-1) ys↵
↵
so:↵
↵
1:d*x-(d-1)*y=l↵
↵
2:x+y:x-y=v2:v1↵
↵
3:ans=(d*x+(d-1)*y)/v2↵
↵
so ans=l/v2*((d*2-1)*v2+v1)/(v2+(d*2-1)*v1)↵
↵
It's o(1).↵
↵
my o(1) solution:[submission:19334768]↵
↵
↵
[problem:701E]↵
↵
Let's take 1 as the root of the tree.↵
↵
Record the depth of every vertex(depth of 1 is 0).↵
↵
Record the number of schools of the subtree of every vertex.↵
↵
The sum of the depth of the lca of every pair of school should as small as possible.↵
↵
Consider 2x schools of the subtree of vertex y(may be 2x is not the number of all the schools of the subtree of vertex y)↵
↵
every depth of lca of the 2x schools is at least the depth of y .↵
↵
If a subtree of the son of y has k schools in the 2x schools(not in all the schools).↵
↵
1:if the k of every son is always mink<=x↵
↵
you can match the schools to make every lca y↵
↵
2:if for son z,mink>x↵
↵
match (2x-mink) schools of the subtree of z with the schools not in the subtree of z but in the subtree of y↵
↵
just look at z like look at y↵
↵
so,it's o(n)↵
↵
my o(n) solution:[submission:19344918]↵
↵
↵
[problem:701F]↵
↵
Any solution?↵
↵
[cut]↵
↵
Other solutions are welcomed.↵
↵
If you find any mistakes,tell me.↵
↵
[cut]↵
↵
Sorry I don't know how to use format.Can you tell me how to do that?
↵
There is still no formal EDITORIAL for Codeforces Round #364 (Div. 2) yet ,so I write a informal one.↵
↵
Sorry for my poor English and poor format.↵
↵
↵
↵
↵
[problem:701A]↵
↵
You can calculate the sum (x) of a pair of cards.↵
↵
x=2*(a1+a2+...+an)/n↵
↵
For every card ai,find a card ak which ai+ak=x and k is not used.↵
↵
The n is small,so you can simplely write a o(n*n) solution(also there is a o(n) one,o(n*n) is enough).↵
↵
My o(n*n) solution:[submission:19328905]↵
↵
↵
[problem:701B]↵
↵
You can just record the number of rows and columns that is not under attack.↵
↵
If r rows and c columns is not under attack there is r*c cells that is not under attack.↵
↵
It's o(m).↵
↵
My o(m) solution:[submission:19330540]↵
↵
↵
[problem:701C]↵
↵
You can just use two pointers↵
↵
There are x types of Pokemon↵
↵
if [i,dp[i]-1] has x-1 types of Pokemon and [i,dp[i]] has x types of Pokemon↵
↵
dp[i+1]>=dp[i]↵
↵
so it's o(n)↵
↵
my o(xlogx+n) solution:[submission:19332828]↵
↵
↵
[problem:701D]↵
↵
It's a math problem.↵
↵
let d=ceil(n/k)↵
↵
Just look at the bus.↵
↵
it goes like that:↵
↵
↵
___<<<<<<<<<↵
↵
___>>>>>>>>>>>>↵
↵
______<<<<<<<<<↵
↵
_____>>>>>>>>>>>>↵
↵
↵
____<<<<<<<<<↵
↵
____>>>>>>>>>>>>↵
↵
_______<<<<<<<<<↵
↵
_______>>>>>>>>>>>>↵
↵
__________<<<<<<<<<↵
↵
__________>>>>>>>>>>>>↵
↵
The '_' means empty(I cannot format it).↵
↵
The long lengths are the same(x) and goes to right.↵
↵
The short lengths are the same(y) and goes to left.↵
↵
It goes to right and put the old students down and does to left and welcome new students.↵
↵
so x+y:x-y=v2:v1↵
↵
it goes for d xs and (d-1) ys↵
↵
so:↵
↵
1:d*x-(d-1)*y=l↵
↵
2:x+y:x-y=v2:v1↵
↵
3:ans=(d*x+(d-1)*y)/v2↵
↵
so ans=l/v2*((d*2-1)*v2+v1)/(v2+(d*2-1)*v1)↵
↵
It's o(1).↵
↵
my o(1) solution:[submission:19334768]↵
↵
↵
[problem:701E]↵
↵
Let's take 1 as the root of the tree.↵
↵
Record the depth of every vertex(depth of 1 is 0).↵
↵
Record the number of schools of the subtree of every vertex.↵
↵
The sum of the depth of the lca of every pair of school should as small as possible.↵
↵
Consider 2x schools of the subtree of vertex y(may be 2x is not the number of all the schools of the subtree of vertex y)↵
↵
every depth of lca of the 2x schools is at least the depth of y .↵
↵
If a subtree of the son of y has k schools in the 2x schools(not in all the schools).↵
↵
1:if the k of every son is always mink<=x↵
↵
you can match the schools to make every lca y↵
↵
2:if for son z,mink>x↵
↵
match (2x-mink) schools of the subtree of z with the schools not in the subtree of z but in the subtree of y↵
↵
just look at z like look at y↵
↵
so,it's o(n)↵
↵
my o(n) solution:[submission:19344918]↵
↵
↵
[problem:701F]↵
↵
Any solution?↵
↵
[cut]↵
↵
Other solutions are welcomed.↵
↵
If you find any mistakes,tell me.↵
↵
[cut]↵
↵
Sorry I don't know how to use format.Can you tell me how to do that?
