当前位置：首页 > article >正文

CSDN 第三十九期竞赛题解

article 2025/2/22 16:52:36

题外

T2 死缠烂打都是 90 很遗憾
T3 缺乏生活经验在 10 pts卡了半小时 qw

感受到了 CSDN 比赛试题质量的增长，不过希望像 T3 这样需要实际经验的题目加一下类似 tips 之类的提醒，毕竟赛题考察点应重在思维力而非生存力（（ @CSDN

T1：圆小艺

最近小艺酱渐渐变成了一个圆滑的形状-球！！小艺酱开始变得喜欢上球！小艺酱得到n个同心圆。小艺酱对着n个同心圆进行染色。相邻的圆范围内不能有相同的颜色。相隔一层的圆颜色相同。小艺酱想知道两种颜色中最外层圆的那种颜色总共染了多少？

分析

~~小艺酱渐渐变成了一个球~~

首先排序。

圆的面积为
$S=\pi r^2$
相邻两个圆的面积差为
$\Delta S=\pi a_i^2-\pi a_{i-1}^2$
因为求最外层的颜色，所以可以从外往内做，时间复杂度 $O (N)$

为了保证精度，c++语言可以用系统函数 $a cos (- 1)$ 代表 $\pi$

样例一精度好像小了。

#include<bits/stdc++.h>
using namespace std;
const double Pi=acos(-1);
int n;
double ans,a[1005];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	for(int i=n;i>=1;i-=2) ans=(ans+Pi*(a[i]+a[i-1])*(a[i]-a[i-1]));//使用了平方差公式
	printf("%.3f",ans);
}

T2：近视的小张

小张和他的 M 个朋友来到了一个十分神奇的地方，在这里有 N 个柱子，对于每个 1 <= i <= N，第 i 个柱子都有两个属性 : H[i], P[i]。
H[i] 表示柱子 i 的高度，而 P[i] 则表示柱子 i 当前所处的位置，题目保证同一个位置不会有多个柱子。
在一个柱子 i 在另一个不比他低的柱子 j 的后面时 (P[i] > P[j] && H[i] <= H[j])，这个柱子会被遮挡住，也就不再能被清晰的看到。
小张和他的朋友们在位置 0 休息时，发现似乎朋友们能清晰看到的柱子数量并不相同，在他反复思考后，他认为这可能是近视度数导致的，于是他询问了每一个朋友的近视度数 A[i]。
为了方便计算，我们认为对于朋友 j 来说，对每一个柱子 i，如果有 P[i] > A[j]，那么第 i 个柱子无法被清晰看见。
请你计算出每个小张的朋友能清晰看到的最远一个柱子的位置, 如果那个朋友一个柱子都没有清晰看到，请输出 -1。 $1\leq N\leq 10^5$

分析

排序，按照近视度数依次处理，将时间复杂度由 $O (NM)$ 转为 $O (N + M)$
不断的调，从10pts 调到 50pts 再到 90pts，但是最终没拿满，缺憾。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+5;
int m,n;
struct qh{
	LL h,p;
	bool operator < (const qh &T){return p<T.p;}
}b[N];
struct A{
	LL a,pos,ans;
}a[N];
bool c1(A x,A y){return x.a<y.a;}
bool c2(A x,A y){return x.pos<y.pos;}
int main(){
	scanf("%lld%lld",&m,&n);
	for(int i=1;i<=n;i++) scanf("%lld",&b[i].h);
	sort(b+1,b+n+1);
	for(int i=1;i<=m;i++) scanf("%lld",&a[i].a),a[i].pos=i;
	sort(a+1,a+m+1,c1);
	LL j=1,mx=0;
	for(int i=1;i<=m;i++){
		a[i].ans=a[i-1].ans;
		while (b[j].p<=a[i].a&&j<=n){
			if(b[j].h>mx) a[i].ans=b[j].p,mx=b[j].h;
			j++;
		}
	}
	sort(a+1,a+m+1,c2);
	for(int i=1;i<=m;i++) printf("%lld\n",a[i].ans?a[i].ans:-1);
	return 0;
}

等待正解。

T3：小股炒股

已知n天后的股票行情，现在已有的本金是m，规定只能入手一次股票和抛售一次股票。最大收益（含本金）是？

分析

注意两点：

买的时候需保证 $m\ge s_i$ ，其中 $s_i$ 表示当天股价。
只能入手一次 不代表只能买一张股票。

时间复杂度 $O (N)$

#include<bits/stdc++.h>
using namespace std;
int a[1005],ans,n,m,mn=1e9;
int main(){
	scanf("%d%d",&n,&m);ans=m;
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
		mn=min(mn,a[i]);
		if(mn>m) continue;
		ans=max(ans,m/mn*a[i]+m%mn);
	}
	return 0;
}

T4：买铅笔

P老师需要去商店买n支铅笔作为小朋友们参加编程比赛的礼物。她发现商店一共有 3 种包装的铅笔，不同包装内的铅笔数量有可能不同，价格也有可能不同。为了公平起见，P老师决定只买同一种包装的铅笔。商店不允许将铅笔的包装拆开，因此P老师可能需要购买超过 n 支铅笔才够给小朋友们发礼物。现在P老师想知道，在商店每种包装的数量都足够的情况下，要买够至少 n 支铅笔最少需要花费多少钱。

分析

~~首先要认真审题~~

考场直接当背包dp打，实际贪心即可，时间复杂度 $O (1)$

#include<bits/stdc++.h>
using namespace std;
int n,ans=1e9,w[5],v[5],f[10005];
int main(){
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=3;i++) scanf("%d%d",v+i,w+i),ans=min(ans,((n-1)/v[i]+1)*w[i]);
	printf("%d",ans);
	return 0;
}