A. Reverse a Substring
You are given a string
lowercase Latin letters.
Let's define a substring as a contiguous subsegment of a string. For example, "acab" is a substring of "abacaba" (it starts in position
and ends in position
), but "a" or "d" aren't substrings of this string. So the substring of the string
You have to choose exactly one of the substrings of the given string and reverse it (i. e. make
) to obtain a string that is less lexicographically. Note that it is not necessary to obtain the minimum possible string.
If it is impossible to reverse some substring of the given string to obtain a string that is less, print "NO". Otherwise print "YES" and anysuitable substring.
is lexicographically less than string
, if either
is a prefix of
), or there exists such
, and for any
denotes the length of the string
. The lexicographic comparison of strings is implemented by operator < in modern programming languages.
if(c[i] > c[i + 1])的话就满足情况然后输出这种情况即可，一道纯暴力的题
B. Game with Telephone Numbers
A telephone number is a sequence of exactly
digits such that its first digit is 8.
Vasya and Petya are playing a game. Initially they have a string
is odd) consisting of digits. Vasya makes the first move, then players alternate turns. In one move the player must choose a character and erase it from the current string. For example, if the current string 1121, after the player's move it may be 112, 111 or 121. The game ends when the length of string
becomes 11. If the resulting string is a telephone number, Vasya wins, otherwise Petya wins.
You have to determine if Vasya has a winning strategy (that is, if Vasya can win the game no matter which characters Petya chooses during his moves).
经分析易得，一共会删除n-10(n - 11 + 1)个数字，若是想要Vasya失败的话首先 Petya会尽可能的从前面删除8，如果能将8删完那么Petya肯定会胜利的，所以输出NO即可如果前n-10个8是大于(n - 11) /2(Petya删除的次数)那样就输出YES即可，一共简单的分析题。
C. Alarm Clocks Everywhere
Ivan is going to sleep now and wants to set his alarm clock. There will be many necessary events tomorrow, the
-th of them will start during the
-th minute. Ivan doesn't want to skip any of the events, so he has to set his alarm clock in such a way that it rings during minutes
so he will be awake during each of these minutes (note that it does not matter if his alarm clock will ring during any other minute).
Ivan can choose two properties for the alarm clock — the first minute it will ring (let's denote it as
) and the interval between two consecutive signals (let's denote it by
). After the clock is set, it will ring during minutes
and so on.
Ivan can choose any minute as the first one, but he cannot choose any arbitrary value of
. He has to pick it among the given values
(his phone does not support any other options for this setting).
So Ivan has to choose the first minute
when the alarm clock should start ringing and the interval between two consecutive signals
in such a way that it will ring during all given minutes
(and it does not matter if his alarm clock will ring in any other minutes).
Your task is to tell the first minute
and the index
such that if Ivan sets his alarm clock with properties
it will ring during all given minutes
or say that it is impossible to choose such values of the given properties. If there are multiple answers, you can print any.
D. Beautiful Array
You are given an array
integers. Beauty of array is the maximum sum of some consecutive subarray of this array (this subarray may be empty). For example, the beauty of the array [10, -5, 10, -4, 1] is 15, and the beauty of the array [-3, -5, -1] is 0.
You may choose at most one consecutive subarray of
and multiply all values contained in this subarray by
. You want to maximize the beauty of array after applying at most one such operation.
dp[i] = max(dp[i - 1], 0ll) + a[i]
dp[i - 1] + a[i]合起来就是包括前面的区间，一个是自建单独开一个区间就是
0ll + a[i] 然后最后答案就是
res = max(res, dp[i]);这个是显而易见的。
我想用一个二维的数组来记录 dp[i]就是之前说的那个一维数组那么我用dp[i] 表示当前值乘x再加上上一个区间的最优解就是
dp[i] = max(dp[i], dp[i], 0ll) + a[i] * x;
dp[i] = max(dp[i - 1], dp[i - 1], dp[i - 1]) + a[i];
res = max(res, dp[i], dp[i], dp[i]);
E. Guess the Root
Jury picked a polynomial
are integer numbers and
. It's guaranteed that there is at least one
Now jury wants you to find such an integer
or report that there is not such
You can ask no more than
queries: you ask value
and jury tells you value
Note that printing the answer doesn't count as a query.
可以通过交互的道关于f(x)的n组解，然后通过预处理分数得到分数的逆元然后去枚举所有的k(就是x0)若能发现f(k)≡0(mod 1e6 + 3)