Codeforces Round#369 Div.2

A. Bus to Udayland

ZS the Coder and Chris the Baboon are travelling to Udayland! To get there, they have to get on the special IOI bus. The IOI bus has nrows of seats. There are 4 seats in each row, and the seats are separated into pairs by a walkway. When ZS and Chris came, some places in the bus was already occupied.

ZS and Chris are good friends. They insist to get a pair of neighbouring empty seats. Two seats are considered neighbouring if they are in the same row and in the same pair. Given the configuration of the bus, can you help ZS and Chris determine where they should sit?

Solution

思博题,考场上我用了清缓存还用puts导致wa on 1若干次。。。


B. Chris and Magic Square

ZS the Coder and Chris the Baboon arrived at the entrance of Udayland. There is a n × n magic grid on the entrance which is filled with integers. Chris noticed that exactly one of the cells in the grid is empty, and to enter Udayland, they need to fill a positive integer into the empty cell.

Chris tried filling in random numbers but it didn't work. ZS the Coder realizes that they need to fill in a positive integer such that the numbers in the grid form a magic square. This means that he has to fill in a positive integer so that the sum of the numbers in each row of the grid (), each column of the grid (), and the two long diagonals of the grid (the main diagonal — and the secondary diagonal — ) are equal.

Chris doesn't know what number to fill in. Can you help Chris find the correct positive integer to fill in or determine that it is impossible?

Solution

水题,只要确定一个已知的列的和,然后作差求出空位,再验证即可


C. Coloring Trees

ZS the Coder and Chris the Baboon has arrived at Udayland! They walked in the park where n trees grow. They decided to be naughty and color the trees in the park. The trees are numbered with integers from 1 to n from left to right.

Initially, tree i has color ci. ZS the Coder and Chris the Baboon recognizes only m different colors, so 0 ≤ ci ≤ m, where ci = 0 means that tree i is uncolored.

ZS the Coder and Chris the Baboon decides to color only the uncolored trees, i.e. the trees with ci = 0. They can color each of them them in any of the m colors from 1 to m. Coloring the i-th tree with color j requires exactly pi, j litres of paint.

The two friends define the beauty of a coloring of the trees as the minimum number of contiguous groups (each group contains some subsegment of trees) you can split all the n trees into so that each group contains trees of the same color. For example, if the colors of the trees from left to right are 2, 1, 1, 1, 3, 2, 2, 3, 1, 3, the beauty of the coloring is 7, since we can partition the trees into 7contiguous groups of the same color : {2}, {1, 1, 1}, {3}, {2, 2}, {3}, {1}, {3}.

ZS the Coder and Chris the Baboon wants to color all uncolored trees so that the beauty of the coloring is exactly k. They need your help to determine the minimum amount of paint (in litres) needed to finish the job.

Please note that the friends can't color the trees that are already colored.

Solution

水题,设dp[i,j,k]表示前i个点美丽值为j,上一个点的染色为k所用的最少的颜料

然后暴力n\times m\times k\times m转移即可,CF速度快怎么跑都能过

事实上对dp数组维护一个前缀后缀最小值可以做到O(nmk)


D. Directed Roads

ZS the Coder and Chris the Baboon has explored Udayland for quite some time. They realize that it consists of n towns numbered from 1to n.

There are n directed roads in the Udayland. i-th of them goes from town i to some other town ai (ai ≠ i). ZS the Coder can flip the direction of any road in Udayland, i.e. if it goes from town A to town B before the flip, it will go from town B to town A after.

ZS the Coder considers the roads in the Udayland confusing, if there is a sequence of distinct towns A1, A2, ..., Ak (k > 1) such that for every 1 ≤ i < k there is a road from town Ai to town Ai + 1 and another road from town Ak to town A1. In other words, the roads are confusing if some of them form a directed cycle of some towns.

Now ZS the Coder wonders how many sets of roads (there are 2n variants) in initial configuration can he choose to flip such that after flipping each road in the set exactly once, the resulting network will not be confusing.

Note that it is allowed that after the flipping there are more than one directed road from some town and possibly some towns with no roads leading out of it, or multiple roads between any pair of cities.

Solution

水题,对于每个环的贡献为2^{m}-2,每条链的贡献为2^{k},其中m,k分别为环的大小和链的长度,然后直接tarjan即可,当然dfs也不会爆


E. ZS and The Birthday Paradox

ZS the Coder has recently found an interesting concept called the Birthday Paradox. It states that given a random set of 23 people, there is around 50% chance that some two of them share the same birthday. ZS the Coder finds this very interesting, and decides to test this with the inhabitants of Udayland.

In Udayland, there are 2n days in a year. ZS the Coder wants to interview k people from Udayland, each of them has birthday in one of2n days (each day with equal probability). He is interested in the probability of at least two of them have the birthday at the same day.

ZS the Coder knows that the answer can be written as an irreducible fraction . He wants to find the values of A and B (he does not like to deal with floating point numbers). Can you help him?

Solution

考虑固定法,固定第一个人,那么第二个人与第一个人不同的概率是\frac{2^{n}-1}{2^{n}}

以此类推,得出最终的每个人均不同的概率是P=\frac{\prod_{i=1}^{k-1}(2^{n}-i)}{(2^{n})^{k-1}}

答案就是1-P

怎么求P呢,很容易发现为了化简这个式子,分子和分母会不断地约掉2

2^{n}显然是偶数,所以只需要考虑i的情况

[1,k-1]的2次幂数可以利用勒让德公式进行算出,即

num=\sum_{i=1}^{k-1}\frac{k-1}{2^{i}}

而由gcd(2,Mod)=1知,如果分子出现了Mod的倍数那么最终的分子一定是0

于是对于分子的乘积直接用暴力算出来即可

最终除的时候需要使用乘法逆元,因为1000003是质数,它的欧拉函数\phi(Mod)=1000002

于是直接利用费马小定理求出乘法逆元即可

总的时间复杂度为O(Mod+\log k)

 

发表评论