# 2019-4-23-div2 又一次codeforces的日常

## A. Reverse a Substring

You are given a string  s

">s

consisting of  n

">n

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  3

">33

and ends in position  6

">66

), but "a" or "d" aren't substrings of this string. So the substring of the string  s

">ss

from position  l

">ll

to position  r

">rr

is  s[l;r]=slsl+1…sr

">s[l;r]=s(l+1)slsr

.

You have to choose exactly one of the substrings of the given string and reverse it (i. e. make  s[l;r]=srsr−1…sl

">s[l;r]=srsr1sls[l;r]=srsr−1…sl

) 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.

String  x

">xx

is lexicographically less than string  y

">y

, if either  x

">xx

is a prefix of  y

">y

(and  x≠y

">xy

), or there exists such  i

">ii

( 1≤i≤min(|x|,|y|)

">1imin(|x|,|y|)1≤i≤min(|x|,|y|)

), that  xi<yi

">xi<yi

, and for any  j

">j

( 1≤j<i

">1j<i

xj=yj

">xj=yj

. Here  |a|

">|a||a|

denotes the length of the string  a

">a

. The lexicographic comparison of strings is implemented by operator < in modern programming languages​​.

A题的话其实我最初并没有看懂题，有大佬讲解一波才理解，简单来说就是找到两个相连的字符if(c[i] > c[i + 1])的话就满足情况然后输出这种情况即可，一道纯暴力的题

## B. Game with Telephone Numbers

A telephone number is a sequence of exactly  11

">1111

digits such that its first digit is 8.

Vasya and Petya are playing a game. Initially they have a string  s

">s

of length  n

">n

( n

">n

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 112111 or 121. The game ends when the length of string  s

">s

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).

B题的话就是相当于一个简单的分析，有题目直接可以看到电话号码是以8开头的11位数。

## 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  i

">i

-th of them will start during the  xi

">xi

-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  x1,x2,…,xn

">x1,x2,,xn,

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  y

">yy

) and the interval between two consecutive signals (let's denote it by  p

">pp

). After the clock is set, it will ring during minutes  y,y+p,y+2p,y+3p

">y,y+p,y+2p,y+3py

and so on.

Ivan can choose any minute as the first one, but he cannot choose any arbitrary value of  p

">pp

. He has to pick it among the given values  p1,p2,…,pm

">p1,p2,,pm

(his phone does not support any other options for this setting).

So Ivan has to choose the first minute  y

">y

when the alarm clock should start ringing and the interval between two consecutive signals  pj

">pjpj

in such a way that it will ring during all given minutes  x1,x2,…,xn

">x1,x2,,xn

(and it does not matter if his alarm clock will ring in any other minutes).

Your task is to tell the first minute  y

">yy

and the index  j

">j

such that if Ivan sets his alarm clock with properties  y

">

and  pj

">pj

it will ring during all given minutes  x1,x2,…,xn

">x1,x2,,xn

or say that it is impossible to choose such values of the given properties. If there are multiple answers, you can print any.

c题其实就是就去一下x序列的最大公约数gcd看看p序列里有没有gcd的约数有的话直接输出第i个如果都没有的话就直接输出NO

## D. Beautiful Array

You are given an array  a

">a

consisting of  n

">n

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  a

">a

and multiply all values contained in this subarray by  x

">xx

. You want to maximize the beauty of array after applying at most one such operation.

d题就是一个dp问题先不管那个乘x的情况如果只考虑一个区间和最大的情况易得

dp[i] = max(dp[i - 1], 0ll) + a[i]

dp[i][1] = max(dp[i][0], dp[i][1], 0ll) + a[i] * x;

dp[i][2] = max(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]) + a[i];

res = max(res, dp[i][0], dp[i][1], dp[i][2]);

## E. Guess the Root

Jury picked a polynomial  f(x)=a0+a1⋅x+a2⋅x2+⋯+ak⋅xk

">f(x)=a0+a1x+a2x2++akxkf(x)=a0+a1⋅x+a2⋅x2+⋯+ak⋅xk

k≤10

">k10k≤10

and all  ai

">aiai

are integer numbers and  0≤ai<106+3

">0ai<106+30≤ai<106+3

. It's guaranteed that there is at least one  i

">ii

such that  ai>0

">ai>0ai>0

.

Now jury wants you to find such an integer  x0

">x0x0

that  f(x0)≡0mod(106+3)

">f(x0)0mod(106+3)f(x0)≡0mod(106+3)

or report that there is not such  x0

">x0x0

.

You can ask no more than  50

">5050

queries: you ask value  xq

">xqxq

and jury tells you value  f(xq)mod(106+3)

">f(xq)mod(106+3)f(xq)mod(106+3)

.

Note that printing the answer doesn't count as a query.