Codeforces Round#372 Div.2

A. Crazy Computer

ZS the Coder is coding on a crazy computer. If you don't type in a word for a c consecutive seconds, everything you typed disappear!

More formally, if you typed a word at second a and then the next word at second b, then if b - a ≤ c, just the new word is appended to other words on the screen. If b - a > c, then everything on the screen disappears and after that the word you have typed appears on the screen.

For example, if c = 5 and you typed words at seconds 1, 3, 8, 14, 19, 20 then at the second 8 there will be 3 words on the screen. After that, everything disappears at the second 13 because nothing was typed. At the seconds 14 and 19 another two words are typed, and finally, at the second 20, one more word is typed, and a total of 3 words remain on the screen.

You're given the times when ZS the Coder typed the words. Determine how many words remain on the screen after he finished typing everything.

Solution

题意:给定一个序列,在第A_{i}秒写一个数,如果有个时刻之差大于C则清空之前所有的数,问最后剩余的数

SB题,1Y


B. Complete the Word

ZS the Coder loves to read the dictionary. He thinks that a word is nice if there exists a substring (contiguous segment of letters) of it of length 26 where each letter of English alphabet appears exactly once. In particular, if the string has length strictly less than 26, no such substring exists and thus it is not nice.

Now, ZS the Coder tells you a word, where some of its letters are missing as he forgot them. He wants to determine if it is possible to fill in the missing letters so that the resulting word is nice. If it is possible, he needs you to find an example of such a word as well. Can you help him?

Solution

题意:问是否可以通过修改通配符使得存在一长度为26的子串满足恰好包含26个字母

SB题,1Y,直接暴力枚举,不偷懒不会WA


C. Plus and Square Root

ZS the Coder is playing a game. There is a number displayed on the screen and there are two buttons, ' + ' (plus) and '' (square root). Initially, the number 2 is displayed on the screen. There are n + 1 levels in the game and ZS the Coder start at the level 1.

When ZS the Coder is at level k, he can :

  1. Press the ' + ' button. This increases the number on the screen by exactly k. So, if the number on the screen was x, it becomes x + k.
  2. Press the '' button. Let the number on the screen be x. After pressing this button, the number becomes . After that, ZS the Coder levels up, so his current level becomes k + 1. This button can only be pressed when x is a perfect square, i.e. x = m2 for some positive integer m.

Additionally, after each move, if ZS the Coder is at level k, and the number on the screen is m, then m must be a multiple of k. Note that this condition is only checked after performing the press. For example, if ZS the Coder is at level 4 and current number is 100, he presses the '' button and the number turns into 10. Note that at this moment, 10 is not divisible by 4, but this press is still valid, because after it, ZS the Coder is at level 5, and 10 is divisible by 5.

ZS the Coder needs your help in beating the game — he wants to reach level n + 1. In other words, he needs to press the '' button ntimes. Help him determine the number of times he should press the ' + ' button before pressing the '' button at each level.

Please note that ZS the Coder wants to find just any sequence of presses allowing him to reach level n + 1, but not necessarily a sequence minimizing the number of presses.

Solution

题目大意:有两种操作,加1,开根号,开根号以后如果剩余的数能被当前的等级+1整除这个操作就是合法的,然后会level up,问若要达到等级n+1,需要在每级按多少次+1

考虑构造,当前的等级为k的话,只需要把变成由k\times(k-1)加到(k\times(k+1))^{2}即可,因为在下一个阶段会轮换回来,注意不要爆long long


D. Complete The Graph

ZS the Coder has drawn an undirected graph of n vertices numbered from 0 to n - 1 and m edges between them. Each edge of the graph is weighted, each weight is a positive integer.

The next day, ZS the Coder realized that some of the weights were erased! So he wants to reassign positive integer weight to each of the edges which weights were erased, so that the length of the shortest path between vertices s and t in the resulting graph is exactly L. Can you help him?

Solution

题目大意:给一张无向图,让你给被删掉权的边赋值,使得ST的最短路恰好为L

先跑一次堆优化dij,如果当前最短路<L,就GG

如果当前最短路==L,就结束了

然后枚举关键边,再跑最短路,如果最短路<L,就结束了

如果还是没有成功,就GG

时间复杂度O(NM\log N)

 

发表评论