Educational Codeforces Round 63 (Rated for Div. 2)

A. Reverse a Substring

time limit per test2 seconds memory limit per test256 megabytes

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 “aa” or “d” aren’t substrings of this string. So the substring of the string 𝑠s from position 𝑙l to position 𝑟r is 𝑠[𝑙;𝑟]=𝑠𝑙𝑠𝑙+1…𝑠𝑟s[l;r]=slsl+1…sr.

You have to choose exactly one of the substrings of the given string and reverse it (i. e. make 𝑠[𝑙;𝑟]=𝑠𝑟𝑠𝑟−1…𝑠𝑙s[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 is lexicographically less than string 𝑦y, if either 𝑥x is a prefix of 𝑦y (and 𝑥≠𝑦x≠y), or there exists such 𝑖i (1≤𝑖≤𝑚𝑖𝑛(|𝑥|,|𝑦|)1≤i≤min(|x|,|y|)), that 𝑥𝑖<𝑦𝑖xi<yi, and for any 𝑗j (1≤𝑗<𝑖1≤j<i) 𝑥𝑗=𝑦𝑗xj=yj. Here |𝑎||a| denotes the length of the string 𝑎a. The lexicographic comparison of strings is implemented by operator < in modern programming languages​​.Input

The first line of the input contains one integer 𝑛n (2≤𝑛≤3⋅1052≤n≤3⋅105) — the length of 𝑠s.

The second line of the input contains the string 𝑠s of length 𝑛n consisting only of lowercase Latin letters.Output

If it is impossible to reverse some substring of the given string to obtain a string which is lexicographically less, print “NO”. Otherwise print “YES” and two indices 𝑙l and 𝑟r (1≤𝑙<𝑟≤𝑛1≤l<r≤n) denoting the substring you have to reverse. If there are multiple answers, you can print any.
Examplesinput

7
abacaba

output

YES
2 5

input

6
aabcfg

output

NO

Note

In the first testcase the resulting string is “aacabba”.

辣鸡签到题,题意没读清楚浪费了15分钟,只要找到一对l,r使得新的字符串字典序变小就好了,而不是找最小的

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int INF=0x3f3f3f3f;
int main(){
	int n;cin>>n;
    string s;cin>>s;
    int l=0,r=0;
    char maxx='a';
    rep(i,0,n-1){
        if(s[i]>maxx) maxx=s[i],l=i;
        if(s[i]<maxx) {r=i;break;}
    }
    if(r==0) puts("NO");
    else {
        puts("YES"); printf("%d %d\n",l+1,r+1);
    }
}


B. Game with Telephone Numbers

time limit per test1 second memory limit per test256 megabytes

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 112, 111 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).Input

The first line contains one integer 𝑛n (13≤𝑛<10513≤n<105, 𝑛n is odd) — the length of string 𝑠s.

The second line contains the string 𝑠s (|𝑠|=𝑛|s|=n) consisting only of decimal digits.Output

If Vasya has a strategy that guarantees him victory, print YES.

Otherwise print NO.
Examplesinput

13
8380011223344

output

YES

input

15
807345619350641

output

NO

Note

In the first example Vasya needs to erase the second character. Then Petya cannot erase a character from the remaining string 880011223344 so that it does not become a telephone number.

In the second example after Vasya’s turn Petya can erase one character character 8. The resulting string can’t be a telephone number, because there is no digit 8 at all.

辣鸡博弈题,显然对于自己,最优的策略是删掉从前开始的非8数字,而对于对手来说,最优策略是删除前面的8,那么直接扫一遍就好了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const int INF=0x3f3f3f3f;
int main(){
    int n;cin>>n;
    string s;cin>>s;
    int c=(n-11)/2;
    int num8=0,b=0;
    rep(i,0,n-1){
        if(s[i]=='8') num8++;
        else b++;
        if(num8>c) break;
    }
    if(num8<=c) {puts("NO");exit(0);}
    if(b<=c) puts("YES");
    else puts("NO");
}


C. Alarm Clocks Everywhere

time limit per test3 seconds memory limit per test256 megabytes

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 𝑥1,𝑥2,…,𝑥𝑛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) and the interval between two consecutive signals (let’s denote it by 𝑝p). After the clock is set, it will ring during minutes 𝑦,𝑦+𝑝,𝑦+2𝑝,𝑦+3𝑝y,y+p,y+2p,y+3p and so on.

Ivan can choose any minute as the first one, but he cannot choose any arbitrary value of 𝑝p. He has to pick it among the given values 𝑝1,𝑝2,…,𝑝𝑚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 𝑝𝑗pj in such a way that it will ring during all given minutes 𝑥1,𝑥2,…,𝑥𝑛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 and the index 𝑗j such that if Ivan sets his alarm clock with properties 𝑦y and 𝑝𝑗pj it will ring during all given minutes 𝑥1,𝑥2,…,𝑥𝑛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.Input

The first line of the input contains two integers 𝑛n and 𝑚m (2≤𝑛≤3⋅105,1≤𝑚≤3⋅1052≤n≤3⋅105,1≤m≤3⋅105) — the number of events and the number of possible settings for the interval between signals.

The second line of the input contains 𝑛n integers 𝑥1,𝑥2,…,𝑥𝑛x1,x2,…,xn (1≤𝑥𝑖≤10181≤xi≤1018), where 𝑥𝑖xi is the minute when 𝑖i-th event starts. It is guaranteed that all 𝑥𝑖xi are given in increasing order (i. e. the condition 𝑥1<𝑥2<⋯<𝑥𝑛x1<x2<⋯<xn holds).

The third line of the input contains 𝑚m integers 𝑝1,𝑝2,…,𝑝𝑚p1,p2,…,pm (1≤𝑝𝑗≤10181≤pj≤1018), where 𝑝𝑗pj is the 𝑗j-th option for the interval between two consecutive signals.Output

If it’s impossible to choose such values 𝑦y and 𝑗j so all constraints are satisfied, print “NO” in the first line.

Otherwise print “YES” in the first line. Then print two integers 𝑦y (1≤𝑦≤10181≤y≤1018) and 𝑗j (1≤𝑗≤𝑚1≤j≤m) in the second line, where 𝑦y is the first minute Ivan’s alarm clock should start ringing and 𝑗j is the index of the option for the interval between two consecutive signals (options are numbered from 11 to 𝑚m in the order they are given input). These values should be chosen in such a way that the alarm clock will ring during all given minutes 𝑥1,𝑥2,…,𝑥𝑛x1,x2,…,xn. If there are multiple answers, you can print any.
Examplesinput

3 5
3 12 18
2 6 5 3 3

output

YES
3 4

input

4 2
1 5 17 19
4 5

output

NO

input

4 2
1 5 17 19
2 1

output

YES
1 1

显然答案的开始时间是第一个节点,间隔时间是所有节点时间差的gcd,那么扫一遍就好了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)3e5+100;
const ll INF=(int)(1<<63);
int n,m;
ll x[maxn];
ll minx=INF;
ll g=0;
ll gcd(ll x,ll y){
    if(!y)return x;
    return gcd(y,x%y);
}
int main(){
	cin>>n>>m;
    rep(i,1,n){
        scanf("%lld",&x[i]);
        if(i==1) g=x[1];
        if(i==2) g=x[2]-x[1];
        if(i>2) g=gcd(g,x[i]-x[i-1]);
        if(i>1) minx=min(minx,x[i]-x[i-1]);
    }
    rep(i,1,m){
        ll tem;scanf("%lld",&tem);
        if(tem>=minx&&g%tem==0){
            printf("YES\n%lld %d\n",x[1],i);
            exit(0);
        }
    }
    puts("NO");
}


D. Beautiful Array

time limit per test2 seconds memory limit per test256 megabytes

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 𝑥x. You want to maximize the beauty of array after applying at most one such operation.Input

The first line contains two integers 𝑛n and 𝑥x (1≤𝑛≤3⋅105,−100≤𝑥≤1001≤n≤3⋅105,−100≤x≤100) — the length of array 𝑎a and the integer 𝑥x respectively.

The second line contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (−109≤𝑎𝑖≤109−109≤ai≤109) — the array 𝑎a.Output

Print one integer — the maximum possible beauty of array 𝑎a after multiplying all values belonging to some consecutive subarray 𝑥x.
Examplesinput

5 -2
-3 8 -2 1 -6

output

22

input

12 -3
1 3 3 7 1 3 3 7 1 3 3 7

output

42

input

5 10
-1 -2 -3 -4 -5

output

0

Note

In the first test case we need to multiply the subarray [-2, 1, -6], and the array becomes [-3, 8, 4, -2, 12] with beauty 22([-3, 8, 4, -2, 12]).

In the second test case we don’t need to multiply any subarray at all.

In the third test case no matter which subarray we multiply, the beauty of array will be equal to 0.

有点像区间dp
dp[i][0]表示当前在第i位时,前面没有乘过x并且现在也不乘的最大答案;
dp[i][1]表示当前在第i位时,上一位乘过x或者之前都没有乘x,并且当前位要乘x时的最大答案;
dp[i][2]表示当前在第i位时,之前已经有乘过x并且这一位不乘x时的最大值;
转移方程如下:
dp[i][0]=max(dp[i-1][0]+t,(ll)0)
dp[i][1]=max(max(dp[i-1][0],dp[i-1][1])+t*x,(ll)0)
dp[i][2]=max(max(dp[i-1][1],dp[i-1][2])+t,(ll)0)

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)3e5+100;
const ll INF=(int)(1<<63);
int n;
ll dp[maxn][3],x;
int main(){
	cin>>n>>x;
    ll ans=0;
    rep(i,1,n){
        ll t;scanf("%lld",&t);
        dp[i][0]=max(dp[i-1][0]+t,(ll)0);
        dp[i][1]=max(max(dp[i-1][0],dp[i-1][1])+t*x,(ll)0);
        dp[i][2]=max(max(dp[i-1][1],dp[i-1][2])+t,(ll)0);
        ans=max(max(max(dp[i][0],dp[i][1]),dp[i][2]),ans);
    }
    printf("%lld",ans);
}


E. Guess the Root

time limit per test2 seconds memory limit per test256 megabytes

Jury picked a polynomial 𝑓(𝑥)=𝑎0+𝑎1⋅𝑥+𝑎2⋅𝑥2+⋯+𝑎𝑘⋅𝑥𝑘f(x)=a0+a1⋅x+a2⋅x2+⋯+ak⋅xk. 𝑘≤10k≤10 and all 𝑎𝑖ai are integer numbers and 0≤𝑎𝑖<106+30≤ai<106+3. It’s guaranteed that there is at least one 𝑖i such that 𝑎𝑖>0ai>0.

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

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

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

To ask a question, print “? 𝑥𝑞xq” (0≤𝑥𝑞<106+3)(0≤xq<106+3). The judge will respond with a single integer 𝑓(𝑥𝑞)mod(106+3)f(xq)mod(106+3). If you ever get a result of −1−1 (because you printed an invalid query), exit immediately to avoid getting other verdicts.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • see documentation for other languages.

When you are ready to answer, print “! 𝑥0x0” where 𝑥0x0 is the answer or −1−1 if there is no such 𝑥0x0.

You can ask at most 5050 questions per test case.

Hack Format

To hack, use the following format.

The only line should contain 1111 integers 𝑎0,𝑎1,…,𝑎10a0,a1,…,a10 (0≤𝑎𝑖<106+30≤ai<106+3, max0≤𝑖≤10𝑎𝑖>0max0≤i≤10ai>0) — corresponding coefficients of the polynomial.
Examplesinput

 
1000002

0

output

? 0

? 1

! 1

input

 
5

2

1

output

? 2

? 1

? 0

! -1

Note

The polynomial in the first sample is 1000002+x2.

The polynomial in the second sample is 1+x2.

询问11个x就可以得到11个方程,高斯消元求出所有的a[i],然后再暴力枚举

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int INF=0x3f3f3f3f;
const int mod=(int)1e6+3;
ll a[20][20],x[20];
int query(int x){
    printf("? %d\n",x);
    fflush(stdout);
    int ans;scanf("%d",&ans);return ans;
}
ll qpow(ll base,ll n){
    ll res=1;
    while(n){
        if(n&1) res=(res*base)%mod;
        base=(base*base)%mod;
        n>>=1;
    }
    return res%mod;
}
ll inv(ll a){return qpow(a,mod-2)%mod;}
void gauss(){
    rep(i,1,11)
        rep(j,1,11)
            if(i!=j){
                ll tem=(a[i][i]*inv(a[j][i]))%mod;
                rep(k,1,12) a[j][k]=(a[i][k]-a[j][k]*tem%mod)%mod,a[j][k]=(a[j][k]+mod)%mod;
            }
    rep(i,1,11) x[i]=(a[i][12]*inv(a[i][i]))%mod;
}
int main(){
	rep(i,1,11){
        a[i][1]=1; a[i][12]=query(i);
        rep(j,2,11) a[i][j]=a[i][j-1]*1ll*i%mod;
    } gauss();
    rep(i,0,mod-1){
        ll tem=0;
        rep(j,1,11) tem=(tem+x[j]*qpow(i,j-1))%mod;
        if(tem==0){
            printf("! %d\n",i); exit(0);
        }
    }
    printf("! -1\n");
    return 0;
}

 

发表评论,支持MarkDown语法