【CSDN竞赛】第十一期解题报告

这应该是站内相对详细的解题报告吧。
转载思路请@本人。

感想

关于自己

这一次时间改善了一点点，不过还是不够 快 。
前面3题做完后没有什么收获（毕竟挺简单的）。
本人认为题目不能只考做法，还要考思维。
下次努力吧，争取得奖。

关于平台

第一题 （难度：简单）

题目描述

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

100分做法

考虑容斥原理，将与外层距离为奇数的面积加上，距离为偶数的面积减去。其中距离为按照半径从小到大排序后间隔的圆的个数。

注意一个问题：圆周率取的越精准越好。
$C++$代码如下：

#include<bits/stdc++.h>
using namespace std;
double r[1005]={};
double pi=3.14159265358979;
int n;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lf",&r[i]);
	}
	sort(r+1,r+n+1);
	double f=1;
	double ans=0;
	for(int i=n;i>=1;i--)
	{
		ans=ans+r[i]*r[i]*pi*f;
		f=-f;
	}
	printf("%.3lf\n",ans);
	return 0;
}

第二题 （难度：入门）

题目描述

存在$n$个节点，目标节点在$m$。 每个节点有自己的权值$a$。 在权值$k$内（含$k$值）选择一个权值非$0$节点且与目标节点距离最近。 节点i与节点j的距离为$abs(i-j)$。

100分做法

这一题直接按照题意模拟即可。

$C++$代码如下：

#include<bits/stdc++.h>
using namespace std;
int a[100005]={};
int n,m,k,ans=1000;
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]!=0&&a[i]<=k)ans=min(ans,abs(i-m));
	}
	printf("%d\n",ans);
	return 0;
}

第三题 （难度：简单+）

题目描述

已知存在$n$个宝物，每个宝物都有自己的质量$m$和价值$v$，在考虑选择宝物时只能选择总质量小于等于$M$的方案，请问在最方案下选择宝物，能获取到最大价值$V$是多少？

100分做法

01背包问题模板，只要学过动态规划都能做对的一道题。
设$d{p}_{i,j}$表示前$i$个物品，背包大小为$j$的最大价值，
则$d{p}_{i,j}=max(d{p}_{i,j},d{p}_{i-1,j-m_i}+v_i)$。
直接按照模板打上去即可。

$C++$代码如下：

#include<bits/stdc++.h>
using namespace std;
int m[100005]={},v[100005]={},dp[1005]={};//滚动数组
int n,M;
int main()
{
	scanf("%d%d",&n,&M);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&m[i],&v[i]);
		for(int j=M;j>=m[i];j--)
		{
			dp[j]=max(dp[j],dp[j-m[i]]+v[i]);//将第一维滚动掉
		}
	}
	printf("%d\n",dp[M]);
	return 0;
}

第四题（难度：中等+）

题目描述

有$N$个客人与足够多张的圆桌。主人安排每位客人坐在一个圆桌边，但是每位客人希望自己左右边上分别有一些空座位，不然会觉得害羞。注意，如果一个客人所在的圆桌只有他一个人，那么他左边的空座位数量就是他右边的空座位数量。 试问主人需要准备多少个座位，才能让每个客人舒适的坐下。

100分做法（证明找其他大佬）

贪心算法。考场上乱推代码莫名对了。
这也是为什么我用的是$C$语言，因为我怕我打的$C++$修改后不能撤回来了。
将$l$和$r$分别从小到大排序，然后一一匹配求最大值，相加后加上人数就是答案。

$C$代码如下：

#include<stdio.h>
#include<math.h>
long long a[100005]={},b[100005]={},c[100005]={};
int n;
long long max(long long x,long long y){return x>y?x:y;}
void msort(int l,int r)
{
	if(l>=r)return;
	int mid=(l+r)>>1;msort(l,mid);msort(mid+1,r);
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r)
	{
		if(a[i]<a[j])c[k++]=a[i++];
		else c[k++]=a[j++];
	}
	while(i<=mid)c[k++]=a[i++];
	while(j<=r)c[k++]=a[j++];
	for(k=l;k<=r;k++)a[k]=c[k];
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&a[i],&b[i]);
	}
	msort(1,n);
	for(int i=1;i<=n;i++)
	{
		long long t=a[i];a[i]=b[i];b[i]=t;
	}
	msort(1,n);
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		ans+=max(a[i],b[i]);
	}
	printf("%lld\n",ans+n);
	return 0;
}