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;
}
