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

题目连接: cf

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位数。

经分析易得,一共会删除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 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]

这句话就是对于第i个元素有两种选择一种是和前面的序列dp[i - 1] + a[i]合起来就是包括前面的区间,一个是自建单独开一个区间就是 0ll + a[i] 然后最后答案就是 res = max(res, dp[i]);这个是显而易见的。

不过题目中求的是对于某一个区间选择性的乘上x(只能乘一个)然后再看区间和最大是什么所以此时

我想用一个二维的数组来记录 dp[i][0]就是之前说的那个一维数组那么我用dp[i][2] 表示当前值乘x再加上上一个区间的最优解就是

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

这个就是选择性的对于每个区间乘上x,因为每个区间显然都是独立,只有一个,但是他最后要的不一定是也乘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.

这道题就是一个纯板子题+一个交互处理

可以通过交互的道关于f(x)的n组解,然后通过预处理分数得到分数的逆元然后去枚举所有的k(就是x0)若能发现f(k)≡0(mod 1e6 + 3)

总结: 不会写啊!!!!

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注