2024CSP-J模拟赛9————S12678

一，赛中得分

二，赛中概括  

T1T2较快过，T3T4骗了90分（意料之中，这么好骗分！！！）。

三，题目解析

涂格子(paint)

问题描述

现在有一个 n 行 m 列的网格纸，一开始每个格子都是白色的。

现在你可以任意挑选恰好 x 行和 y 列，将挑选的整行（整列）上的每一个格子涂成黑色， 问剩下多少个格子是白色的。

输入格式

第一行为 n,m,x,y，含义如上所示。

输出格式

一行一个整数表示答案。

样例输入

5

3

1

2

样例输出

4

数据分布

对于 60% 的数据:	1≤n,m≤100
对于 100% 的数据:	1≤n,m≤10^​9(1000000000)​​,1≤x≤n,1≤y≤m

较简单，一道数学题（不脑残就能过）

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("paint.in","r",stdin);
	freopen("paint.out","w",stdout);
	long long n,m,x,y;
	cin>>n>>m>>x>>y;
	cout<<n*m-n*y-x*(m-y);//算出结果
	return 0;
}

数串串(aba)

问题描述

给定一个长度为 n 的字符串，求有多少个长度为 3 的子序列满足形如 ABA 的格式，即子序列中的第一个字母等于第三个字母，但它们都不等于第二个字母。

由不同位置的相同字符构成的子序列被认为是不同的子序列，见样例解释。

一个序列被称为字符串 s 的子序列，当且仅当该序列能仅通过 s 删除一部分字符得到。

输入格式

第一行一个正整数 n 表示字符串的长度。

第二行一个长度为 n 的字符串，保证字符串仅由小写英文字母构成。

输出格式

一行一个整数表示答案。

样例输入

7

abacabc

样例输出

9

样例解释

满足条件的子序列有 aba,aba,aca,aca,bab,bab,bcb,cac,cbc 共 9 个。

数据分布

对于 10% 的数据满足 n≤300 ;

对于 60% 的数据满足 n≤5×10​^4(50000)​​ ;

对于 100% 的数据满足 1≤n≤10^​6(1000000)​​ 。

不会的人可以先参考一下两道题：

题目大意：

给定一个字符串，请计算ac作为字符串子序列出现的次数

注意：字符串子序列指的是从最初字符串通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列。例如，acf、bde、bcd都是abcdef的子序列，而cae并不是。

样例：

输入：

aaaccc

输出：

9

题目解析：

可以从前往后计算有多少个a，把每个c的地方出现了几个a加起来；也可以从后往前计算有多少个c，把每个a的地方出现了几个c加起来。

AC代码：

#include <bits/stdc++.h>
using namespace std;
int main() {
	//freopen("acok.in","r",stdin);
	//freopen("acok.out","w",stdout);
	string a;
	cin>>a;
	int b=a.size(),cnt=0,ans=0;
	int c[b]={0};
	for(int i=0;i<b;i++){
		if(a[i]=='a'){
			ans++;
			
		}
		c[i]=ans;
		if(a[i]=='c')cnt+=c[i];
	}
	cout<<cnt;
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

扩展：输入长度和字符串，求里面有多少个cow。

思路：用枚举，循环在字符串中正序查找O左边C的个数，用枚举，循环在字符串中倒序查找O右边W的个数，把他们相乘，最后相加。

样例：

输入：

6

coowww

输出：

6

AC代码：

#include<bits/stdc++.h>
using namespace std;
long long c[100005],d[100005];
int main(){
	int n;
	cin>>n;
	string a;
	cin>>a;
	long long cnt=0,b=a.size();
	long long ans=0;
	for(int i=0;i<b;i++){
		if(a[i]=='C')ans++;
		c[i]=ans;
	}
	ans=0;
	for(int i=b-1;i>=0;i--){
		if(a[i]=='W')ans++;
		d[i]=ans;
	}
	for(int i=0;i<b;i++){
		if(a[i]=='O'){
			cnt+=c[i]*d[i];
		}
	}
	cout<<cnt;
	return 0;
}

与上面两道题的思路一样

AC代码

#include<bits/stdc++.h>
using namespace std;
long long n,b[1000006],c[1000006],cntt=0;
int main(){
	freopen("aba.in","r",stdin);
	freopen("aba.out","w",stdout);
	string a;
	cin>>n>>a;
	for(char i='a';i<='z';i++){
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		long long ans=0,cnt=0,sum=0;
		for(int j=0;j<n;j++){
			if(a[j]==i)ans++;
			b[j]=ans;
		}
		for(int j=n-1;j>=0;j--){
			if(a[j]==i)cnt++;
			c[j]=cnt;
		}
		for(int j=0;j<n;j++){
			if(a[j]!=i){
				sum+=c[j]*b[j];
			}
		}
		cntt+=sum;
	}
	cout<<cntt;
	return 0;
}

取石子(pick)

问题描述

有 n 堆石头排成一行，第 i 堆中有 a​i​​ 颗石子，Alice 和 Bob 打算玩一个取石子的博弈游戏，他们为每堆石子赋予了一个权值 b​i​​，并规定一次操作为：选定一堆石子，从它本身和它前面的所有石子堆中各取走一颗。当前面有的石子堆中已经无石子的时候，不允许这样操作。对第 i 堆石子进行操作可以获得权值 b​i​​。每堆石子对应的操作只能做 11 次。

现在他们不想玩无趣的博弈游戏了，他们想知道如果他们不断进行这样的操作，直到没有任何操作可以进行，在最优情况下，一共能获得多少权值。

形式化来说：给定 n 长序列 a​1​​,a​2​​,⋯,a​n​​，一次操作为选定一个 x，使a​1​​,a​2​​,⋯,a​x​​ 均减少 1，但不允许选择会将某个 a​i​​ 减成负数的 x，操作完成之后获得权值 b​x​​，每种 x 最多只能被选定 1 次，求经过任意多次操作之后能获得的最大权值。

输入格式

第一行为石子堆数 n

第二行为 n 个整数 a​1​​,a​2​​,⋯,a​n​​

第三行为 n 个整数 b​1​​,b​2​​,⋯,b​n​​

输出格式

一行一个整数，可获得的最大权值和

样例输入

1. 5
2. 6 2 2 1 1
3. 1 3 2 4 5

样例输出

1. 9

样例解释

可以对第 1,2,5 堆石子分别进行一次操作，共获得权值 1+3+5=9，最后的石子堆情况为 3 0 1 0 0

数据分布

对于 100% 的数据，1≤n≤5000,1≤a​i​​≤10​^9(1000000000)​​,1≤b​i​​≤10^​5(100000)​​

对于 30% 的数据，有额外限制：1≤n≤20

对于另外 30% 的数据，有额外限制：对于所有的 i,b​i​​=1

动态规划

AC代码

#include<bits/stdc++.h>
using namespace std;
long long n,a[5005],b[5005],cnt=0,dp[5005][5005];
int main(){
	//freopen("pick.in","r",stdin);
	//freopen("pick.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		
	}
	for(int i=1;i<=n;i++){
		cin>>b[i];
	}
	memset(dp,-1,sizeof(dp));
	for(int i=0;i<=n;i++){
		dp[0][i]=0;
	}
	for(int i=1;i<=n;i++){
		for(long long j=0;j<=n;j++){
			dp[i][min(a[i],j)]=max(dp[i][min(a[i],j)],dp[i-1][j]);
			
		}
		if(a[i]>0){
			for(long long j=1;j<=n;j++){
				if(dp[i-1][j]!=-1)dp[i][min(a[i]-1,j-1)]=max(dp[i-1][j]+b[i],dp[i][min(a[i]-1,j-1)]);
			}
		}
		
	}
	for(int i=0;i<=n;i++){
		cnt=max(cnt,dp[n][i]);
		
	}
	cout<<cnt<<endl;
	return 0;
}

健身计划(gym)

问题描述

Setsuna 想要运动！

于是她安排了 n 天内的作息，作息用一个 01 字符串 s 表示，若 s​i​​ 为 0 则表示这天休息，为 11 则表示这天要去健身房运动。

但是连续 x 天的运动会积累 ​​x(x+1)/2​​ 点疲劳值，也就是说字符串中每段长度为 x 的极长连续 1 会带来 ​​x(x+1)/2​​ 点疲劳值。

例如，若她的安排为 11101011 ，那疲劳值为 ​2​​3(3+1)​​+​2​​1(1+1)​​+​2​​2(2+1)​​=10 点。

现在她可以把任意天运动日改成休息日，问最少需要改几天才能使得疲劳值小于等于 k。

输入格式

第一行包含两个整数 n,k 。

第二行包含一个长度为 n 的 01 串 s。

输出格式

输出一个整数，表示答案。

样例输入1

1. 7 4
2. 1110111

样例输出1

1. 2

样例输入2

1. 3 1
2. 111

样例输出2

1. 2

数据分布

对于 15% 的数据满足 n≤15 ;

对于 40% 的数据满足 n≤300 ;

对于 60% 的数据满足 n≤2000 ;

对于 100% 的数据满足 1≤n≤10​^5(100000)​​,0≤k≤​2​​n(n+1)​​ 。

优先队列

AC代码

#include<bits/stdc++.h>
using namespace std;
long long n,m,cnt=0,t=0;
long long pilao(long long x){
	return x*(x+1)/2;
}
long long cal(long long l,long long k){
	if(l<=k)return 0;
	l-=k;
	k++;
	return l%k*pilao(l/k+1)+(k-l%k)*pilao(l/k);
}
struct node{
	int len,k;
	node(int lenn=0,int kk=0){
		len=lenn;
		k=kk;
	}
	bool operator<(const node& p) const {
		long long x=cal(len,k)-cal(len,k+1);
		long long y=cal(p.len,p.k)-cal(p.len,p.k+1);
		return x<y;
	}
};
priority_queue<node> q;
int main(){


	//freopen("gym.in","r",stdin);
	//freopen("gym.out","w",stdout);
	int now=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int x;
		scanf("%1d",&x);
		if(x)cnt++;
		if(!x||i==n){
			if(cnt){
				q.push(node(cnt,0));
				now+=pilao(cnt);
			}
			cnt=0;
		}
	}
	long long ans=0;
	while(now>m){
		ans++;
		node tmp=q.top();
		q.pop();
		now-=cal(tmp.len,tmp.k)-cal(tmp.len,tmp.k+1);
		q.push(node(tmp.len,tmp.k+1));
	}
	cout<<ans;
	return 0;
}