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\n");
    else printf("YES\n%d %d\n",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\n");
    else if(sum1 < sum2) printf("NO\n");
    else{
        if(s[need + 1] == '8') printf("YES\n");
        else printf("NO\n");    
    }
    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\n",ans);
    return 0;
}

Educational Codeforces Round 63部分题解

Educational Codeforces Round 63

A

B

C

D