Educational Codeforces Round 63
A
题目大意就不写了.
挺简单的,若果字符本来就单调不降,那么就不需要修改
否则找到第一次下降的位置和前面的换就好了.
#include<iostream>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 3e5 + 3;
char s[N];
int n;
int x,y;
inline bool check(){
int last = -1;
for(int i = 1;i <= n;++i){
if(last > s[i]) {
x = i - 1,y = i;
return false;
}
last = s[i];
}
return true;
}
int main(){
scanf("%d",&n);
scanf("%s",s + 1);
if(check()) printf("NO
");
else printf("YES
%d %d
",x,y);
return 0;
}
B
题目大意:给一个数字串,每个人可以轮流拿掉其中任何一个数字,串长为(11)(保证串长大于(11)且为奇数)时结束,这是如果开头为(8),则先手获胜,问先手是否有必胜策略
刚开始以为是个博弈论,推了(20)分钟,发现,我们设两人一共的操作次数为(k),能够影响答案的只有前(k + 1)个数,我们将(8)看作(1),非$8 $看作(0)
如果前(k)个数(1)比较多,那么先手必胜,因为后手拿不玩
反之如果(0)比较多,那么先手必败
如果一样多,则取决于第(k + 1)的数
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 3e5 + 3;
char s[N];
int n;
int main(){
scanf("%d",&n);
scanf("%s",s + 1);
bool flag = 1;
int need = (n - 11);
int sum1 = 0,sum2 = 0;
for(int i = 1;i <= need;++i)
if(s[i] == '8') sum1++;
else sum2++;
if(sum1 > sum2) printf("YES
");
else if(sum1 < sum2) printf("NO
");
else{
if(s[need + 1] == '8') printf("YES
");
else printf("NO
");
}
return 0;
}
C
题目大意:给定数组(x)与(y),问是否存在(y_i)和(b)将(x)中所有的数表示为(ky_i + b)的形式（(x)数组单调）
看样子自己的数学功底还是不行的
我们试想一下
对于(a_i)和(a_{i + 1}),如果存在(y_i)符合题意,那么一定有(a_{i + 1} - a_i = ky_i),也就是说
(y_i)要是所有数与其相邻的数差最大公约数的一个因子(这样才能用(ky_i)表示出所有的差).
而(b)的值,很明显选择(x_1)就好了
#include<cstdio>
#include<iostream>
#include<cmath>
#define LL long long
using namespace std;
const int N = 3e5 + 3;
LL a[N],b[N];
inline LL read(){
LL v = 0,c = 1;char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') c = -1;
ch = getchar();
}
while(isdigit(ch)){
v = v * 10 + ch - 48;
ch = getchar();
}
return v * c;
}
int n,m;
inline LL gcd(LL x,LL y){
return y == 0 ? x : gcd(y,x % y);
}
int main(){
n = read(),m = read();
for(int i = 1;i <= n;++i) a[i] = read();
for(int i = 1;i <= m;++i) b[i] = read();
LL g = a[2] - a[1];
for(int i = 3;i <= n;++i) g = gcd(g,a[i] - a[i - 1]);
LL ans = -1;
for(int i = 1;i <= m;++i) if(g % b[i] == 0){
ans = i;
break;
}
if(ans == -1) puts("NO");
else{
puts("YES");
cout << a[1] << " " << ans << endl;
}
return 0;
}
D
题目大意给定(x)和一个数组(a),你可以选择一个区间将其所有元素乘(x)(当然也可以不乘),求乘完之后的最大字段和.
这道题不会不应该.
但这也告诉了我一个技巧,当仅可以选择一个区间进项操作,然后求答案是,用(dp)将状态分为操作前,操作中和操作后进行考虑
那么转移方程很明显了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#define LL long long
using namespace std;
const int N = 3e5 + 3;
LL dp[N][3];
LL a[N];
int n;LL x;
int main(){
scanf("%d%I64d",&n,&x);
for(int i = 1;i <= n;++i) scanf("%I64d",&a[i]);
dp[1][0] = a[1],dp[1][1] = a[1] * x,dp[1][2] = a[1];
for(int i = 2;i <= n;++i){
dp[i][0] = max(a[i],dp[i - 1][0] + a[i]);
dp[i][1] = max(a[i] * x,max(dp[i - 1][1] + a[i] * x,dp[i - 1][0] + a[i] * x));
dp[i][2] = max(a[i],max(a[i] + dp[i - 1][2],a[i] + dp[i - 1][1]));
}
LL ans = 0;
for(int i = 1;i <= n;++i) ans = max(ans,max(dp[i][0],max(dp[i][1],dp[i][2])));
printf("%I64d
",ans);
return 0;
}