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

## A. Reverse a Substring

You are given a string s consisting of 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 33and ends in position 66), but "a" or "d" aren't substrings of this string. So the substring of the string ss from position ll to position rr is 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]=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 xx is lexicographically less than string y, if either xx is a prefix of y (and xy), or there exists such ii (1imin(|x|,|y|)1≤i≤min(|x|,|y|)), that xi<yi, and for any j (1j<ixj=yj. Here |a||a| denotes the length of the string 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 1111 digits such that its first digit is 8.

Vasya and Petya are playing a game. Initially they have a string s of length 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 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-th of them will start during the 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, 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 yy) and the interval between two consecutive signals (let's denote it by pp). After the clock is set, it will ring during minutes 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 pp. He has to pick it among the given values p1,p2,,pm (his phone does not support any other options for this setting).

So Ivan has to choose the first minute y when the alarm clock should start ringing and the interval between two consecutive signals pjpj in such a way that it will ring during all given minutes 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 yy and the index j such that if Ivan sets his alarm clock with properties and pj it will ring during all given minutes 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 consisting of 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 and multiply all values contained in this subarray by 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+a1x+a2x2++akxkf(x)=a0+a1⋅x+a2⋅x2+⋯+ak⋅xkk10k≤10 and all aiai are integer numbers and 0ai<106+30≤ai<106+3. It's guaranteed that there is at least one ii such that ai>0ai>0.

Now jury wants you to find such an integer x0x0 that f(x0)0mod(106+3)f(x0)≡0mod(106+3) or report that there is not such x0x0.

You can ask no more than 5050 queries: you ask value xqxq and jury tells you value f(xq)mod(106+3)f(xq)mod(106+3).

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