2023-2024学年度第二学期 初一竞赛组期中考试 题解

A. 卡牌游戏（简单版）

题面

有 $n$ 张卡牌，每张卡牌有分数 $a_i$ 和得分倍率 $b_i$。

每次可以选择一张卡片 $x$，它在这次选择中贡献的得分是：所有未被选择卡片的分数之和乘 $x$ 的得分倍率，即 $b_x \times \sum_{卡片i未被选择} a_i$​。注意：卡片 $x$ 在当次计分时即被视为已选择。

请输出最大分数模 $998244353$ 的结果。

数据范围：$ 1 \le n \le 10^6, 1 \le a_i \le 10^5, 1 \le b_i \le 100 $。

分析

考点：顺序类贪心

考虑两张卡牌 $x,y$ 的选择顺序，记剩下其他卡牌的分数之和为 $S$。

如果先选 $x$，后选 $y$，则两次选择可以贡献得分 $S_1 = b_x \times (S+a_y) + b_y \times S$；如果先选 $y$，后选 $x$，则两次选择可以贡献得分 $S_2 = b_y \times (S+a_x) + b_x \times S$。

于是 $S_1 - S_2 = b_x \times a_y - b_y \times a_x$。

要使先选 $x$ 的贡献更大，则 $S_1 > S_2$，即 $b_x \times a_y > b_y \times a_x$，即 $\frac{a_x}{b_x} < \frac{a_y}{b_y}$。

于是我们得到贪心策略：对于每张卡牌 $p$，$\frac{a_p}{b_p}$ 越小就越先取。

代码

# include<iostream>
# include<algorithm>
using namespace std;

const int N=1e6+5;
const long long mod=998244353;

int n;
long long sum,ans;

struct card{
	long long a,b;
}p[N];

bool cmp(card x,card y){
	return x.a*y.b<x.b*y.a;
}

int main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>p[i].a>>p[i].b;
		sum+=p[i].a; 
	}
	sort(p+1,p+n+1,cmp);
	for(int i=1;i<=n;++i){
		sum-=p[i].a;
		ans=(ans+sum*p[i].b)%mod;
	}
	cout<<ans;
	return 0;
}

B. 半透明骨牌覆盖

题面

给定一个 $2 \times n$ 的数字矩阵，用 $n$ 个一半黑色一半透明的 $1 \times 2$ 骨牌将矩阵全部覆盖，骨牌不能有重叠，不能有数字不被覆盖。此时有 $n$ 个数被黑色盖住，另外 $n$ 个数可以看见。求可以看见的数字的和的最大值。

数据范围：对 $100\%$ 的数据，$3 \le n \le 3 \times 10^5$，矩阵中所有元素的值非负且不超过 $10^9$。

分析

考点：线性DP

代码

# include<iostream>
using namespace std;

const int N=3e5+5;
int n;
long long a[N][2],f[N];

long long f1(int x,int i){
	return max(a[x-1][i],a[x][i]);
}

long long f2(int x){
	return max(a[x][0],a[x][1]);
}

int main(){
	cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i][0];
	for(int i=1;i<=n;++i) cin>>a[i][1];
	for(int i=1;i<=n;++i){
		if(i==1)
			f[i]=f2(1);
		else
			f[i]=max(f1(i,0)+f1(i,1)+f[i-2],f2(i)+f[i-1]);
	}
	cout<<f[n];
	return 0;
}

C. 刷题

题面

分析

代码

D. 回文字串

题面

分析

代码