Educational Codeforces Round 59

题目连接

Educational Codeforces Round 59

A

思路

直接拆成2部分，第一部分一个数，第二个部分n个数，考虑相等的情况输入NO，其他为YES

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
string s;
int main(){
	int q;
	scanf("%d",&q);
	while(q--){
		int n;
		scanf("%d",&n);
		cin>>s;
		if(n==2&&s[0]>=s[1])printf("NO\n");
		else {
			printf("YES\n2\n"); 
		printf("%c ",s[0]);
		for(int i=1;i<n;i++)printf("%c",s[i]);
		printf("\n");
		}
	}
}

B

思路

随便写两个数后发现输出（k-1）*9+n即可

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
	int n;
	scanf("%d",&n);
	while(n--){
		ll k,x;
		scanf("%lld %lld",&k,&x);
		printf("%lld\n",(k-1)*9+x);
	}
}

C

思路

当连续的超过k个，取这一段最大的k个即可，维护当前连续的个数，然后当大于k的时候就排序加起来即可

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5+10;
char s[N];
int b[N];
int cmp(int a,int b){
	return a>b;
}
int main(){
	int n,k;
	scanf("%d %d",&n,&k);
	for(int i=0;i<n;i++)scanf("%d",&b[i]);
	scanf("%s",s);
	int ce = 1;
	int l=0;
	ll ans = 0;
	for(int i=1;i<n;i++){
	   if(s[i]==s[i-1])ce++;
	   else {
	   	if(ce>=k){
	   	sort(b+l,b+l+ce,cmp);
		for(int j=l;j<l+k;j++)ans+=b[j];	
		}
		else{
			for(int j=l;j<l+ce;j++)ans+=b[j];
		}
	   	ce=1;
	   	l=i;
	   }
	}
	if(ce>=k){
	   	sort(b+l,b+l+ce,cmp);
		for(int j=l;j<l+k;j++)ans+=b[j];	
		}
		else{
			for(int j=l;j<l+ce;j++)ans+=b[j];
		}
	printf("%lld\n",ans);
}

D

思路

二维前缀和O(1)查询，O(n^2)的时间复杂度预处理一下，然后就可以查询每个方块，从大到小枚举n的因子，然后再check是否符合，只要符合就输出答案。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5210;
string str[16]={"0000","0001","0010","0011","0100","0101","0110","0111","1000","1001","1010","1011","1100","1101","1110","1111"};
char s[N][N];
bool martix[N][N];
int pre[N][N];
int n;
int getnum(char c){
	if(c>='0'&&c<='9')return c-'0';
	else return c-'A'+10;
}
int judge(int x1,int y1,int x2,int y2){
	return pre[x2][y2]+pre[x1-1][y1-1]-pre[x1-1][y2]-pre[x2][y1-1];
}
bool check(int k){
	for(int i=1;i<=n;i+=k){
		if(i+k-1>n)break;
		for(int j=1;j<=n;j+=k){
			if(j+k-1>n)break;
			if(judge(i,j,i+k-1,j+k-1)!=k*k&&judge(i,j,i+k-1,j+k-1)!=0)return false;
		}
	}
	return true;	
}
int main(){
   scanf("%d",&n);
   for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
   int ans = 1;
   for(int i=1;i<=n;i++){
   	 for(int j=1;j<=n;j++){
   	 	int l = ceil(1.0*j/4);
   	 	int pos = getnum(s[i][l]);
   	 	martix[i][j]=str[pos][j%4==0?3:j%4-1]-'0';
		}
	}
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=n;j++){
    		pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+martix[i][j];
		}
	}
	int sn =sqrt(n)+1;
	for(int i=n;i>=2;i--){
		if(n%i==0&&check(i)){
			ans=i;
			break;
		}
	}
	printf("%d\n",ans);
   }