Educational Codeforces Round 63 (Rated for Div. 2)题解
A. Reverse a Substring
给出一个字符串，现在可以对这个字符串进行一次翻转，问是否存在一种方案，可以使得翻转后字符串的字典序可以变小。
这个很简单，贪心下就行了。
代码如下：
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
int n;
char s[N] ;
int main() {
cin >> n;
scanf("%s",s + 1) ;
int pos1, pos2 = -1;
int mx = 0;
for(int i = 1; i <= n; i++) {
if(s[i] - 'a' + 1 >= mx) {
mx = s[i] - 'a' + 1;
pos1 = i;
} else {
pos2 = i;
break ;
}
}
if(pos2 == -1) puts("No") ;
else {
puts("YES") ;
cout << pos1 << ' ' << pos2 ;
}
return 0;
}
B. Game with Telephone Numbers
给出一个数字序列，长度为n，满足\(13\leq n\leq 10^5\)，并且保证长度为偶数。并且给出电话号码的定义：长度为11并且首位为8。
现在两个人，每个人选择一个数删去。现在问先手是否有必胜策略。
因为保证了\(n\)为偶数，所以我们可以知道每个人的操作次数，假设每个人可以操作\(k\)次。那么我们就只需要看前\(2*k+1\)个字符就行了，统计一下8的数量就ok了。
具体见代码吧：
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
int n;
char s[N] ;
int main() {
cin >> n;
scanf("%s",s + 1) ;
int remain = (n - 11) / 2;
int cnt1 = 0, cnt2 = 0;
for(int i = 1; i <= 2 * remain; i++) {
if(s[i] == '8') cnt1++ ;
else cnt2++;
}
if(cnt1 > remain) puts("YES") ;
else if(cnt1 == remain && s[2 * remain + 1] == '8') puts("YES") ;
else puts("NO") ;
return 0;
}
C. Alarm Clocks Everywhere
给出\(n\)个数的位置，每个数的位置为\(x_i\)，\(m\)个间隔，分别为\(p_i\)。现在问是否可以从这些间隔里面选出一个\(p_i\)出来，现在还随意选出一个起点，问这样是否可以遍历所有的位置。
比如选择了一个起点\(s\)，假设间隔为\(v\)，那么就会遍历\(s,s+v,\cdots,s+v*k\)。
求出所有间隔的gcd就行了，最后依次枚举每个间隔，判断一下就行了。
代码如下:
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
ll a[N];
int n, m;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
ll d = 0;
for(int i = 1; i <= n; i++) {
cin >> a[i] ;
if(i != 1) d = __gcd(d, a[i] - a[i - 1]) ;
}
ll x;
int ans = -1;
for(int i = 1; i <= m; i++) {
cin >> x;
if(d % x == 0) {
ans = i;
}
}
if(ans == -1) cout << "NO" ;
else {
cout << "YES" << '\n';
cout << a[1] << ' ' << ans ;
}
return 0;
}
D. Beautiful Array
给出\(n\)个数，每个数为\(a_i\)，满足\(1\leq n\leq 3*10^5,-10^9\leq a_i\leq 10^9\)。同时给出一个数\(x\)，满足\(-100\leq x\leq 100\)。
现在可以选出一个区间\([l,r]\)，之后对这个区间中的每一个数都乘以一个\(x\)。
询问在至多执行了一次操作过后，这\(n\)个数的最大连续子段和为多少。
额，这个题我一开始以为就是贪心...结果贪遭了，大部分时间就搭进去了。最后发现其实一个简单dp(?)就行了。。。反正我看过题解之后感觉挺简单的。
因为只能最多执行一次操作，所以最后整个区间会被分为三段或者一段。定义\(dp(i,j)\)表示当前第\(i\)个数，且处于第\(j\)段中时，前\(i\)个数的最大连续子段和，这里\(0\leq j\leq 2\)。这里中间那段就是被改变的区间，前面、后面都是没有改变的。之后根据这个来转移就行了。
因为我的转移中只有新开一段和延续之前这两种情况，所以最后还需要枚举一下来维护答案。因为最后的答案不一定会延续到最后一位。
详细见代码吧：
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
int n ;
ll x;
ll a[N] ;
ll dp[N][3] ;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> x;
for(int i = 1; i <= n; i++) cin >> a[i] ;
for(int i = 1; i <= n; i++) {
dp[i][0] = max({a[i], dp[i - 1][0] + a[i]}) ;
dp[i][1] = max({dp[i - 1][0] + a[i] * x, dp[i - 1][1] + a[i] * x, a[i] * x}) ;
dp[i][2] = max({dp[i - 1][1] + a[i], dp[i - 1][2] + a[i], a[i]});
}
ll ans = 0;
for(int i = 1; i <= n; i++)
ans = max({ans, dp[i][0], dp[i][1], dp[i][2]}) ;
cout << ans ;
return 0;
}
E. Guess the Root
这是一个交互题。
给出一个函数\(f(x)=a_0+a_1*x+a_2*x^2+\cdots+a_k*x^k\)，其中\(0\leq a<10^6+3,k\leq 10\)。
之后你最多有50次询问，给出一个\(x_0\)，最后会给出回答\(f(x_0)\mod 10^6+3\)。之后要求你输出一个\(x_0\)，满足\(f(x0)\mod 10^6+3\)。
由于这里的\(k\)很小，所以我们可以直接询问11次，然后就会有11个方程，因为题目保证有解，所以直接高斯消元就好啦，可以直接把\(a_0,a_1,\cdots,a_k\)给求出来。
之后枚举\(x\)从\(0\)到\(10^6+2\)就行了，为啥不往后面枚举呢，因为有取余，往后面枚举是没必要的。如果满足条件就直接输出，最后发现没有满足条件的数，直接输出\(-1\)就好了。
代码如下：
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 15, MOD = 1e6 + 3;
ll a[N][N], b[N];
ll qp(ll A, ll B) {
ll ans = 1;
while(B) {
if(B & 1) ans = ans * A % MOD;
A = A * A % MOD;
B >>= 1;
}
return ans ;
}
void gauss() {
for(int i = 0; i < 11; i++) {
ll t = qp(a[i][i], MOD - 2) ;
for(int j = 0; j < 12; j++)
a[i][j] = a[i][j] * t % MOD;
for(int j = 0; j < 11; j++) {
ll c = a[j][i] ;
if(i != j && a[j][i])
for(int k = 0; k < 12; k++)
a[j][k] = ((a[j][k] - a[i][k] * c % MOD) % MOD + MOD ) % MOD;
}
}
}
ll f(ll x) {
ll ans = 0;
for(int i = 10; i >= 0; i--) {
ans = (ans * x + b[i]) % MOD ;
}
return ans ;
}
int main() {
for(int i = 0; i < 11; i++)
for(int j = 0; j < 11; j++)
a[i][j] = qp(i, j) ;
for(int i = 0; i < 11; i++) {
printf("? %d\n", i);
fflush(stdout) ;
scanf("%d", &a[i][11]) ;
}
gauss() ;
for(int i = 0; i < 11; i++) b[i] = a[i][11] ;
for(int i = 0; i < MOD; i++) {
if(f(i) == 0) {
printf("! %d",i) ;
return 0;
}
}
printf("! -1") ;
return 0 ;
}