Educational Codeforces Round 63部分题解

时间：2021-08-13 23:34:32

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;

}

相关文章