【CSDN竞赛】第九期解题报告

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

感想

关于自己

这一次排名第三，原因是第四题的某个变量打错，调了几分钟，浪费了时间。
可能是我做的比较快（也可能是其他原因），我并没有遇到提交不上题目的问题。
下一次比赛是在下一个周日，争取前三。

关于平台

还是那句话：难度安排需要注意。
不过这次题目考察的算法确实广了一点。
听说一些人在代码界面无法提交，一直显示加载还是什么。
还有一些人代码一直运行却没提示时间超限，也无法保存。
考试结束给出的测评报告排名不准，可能是刚出成绩就出了测评报告导致的（这个问题出现了很多次，一直没说）。
不过总体也有所进步，希望$CSDN$能越做越好。

第一题 小艺读书（难度：入门）

题目描述

书是人类进步的阶梯。 小艺每周因为工作的原因会选择性的每天多读几页或者少读几页。 小艺想知道一本$n$页的书她会在周几读完。

100分做法

按照题意模拟即可。可以先处理一周读不完的情况，使其变成一周内读完。
$C++$代码如下：

#include
using namespace std;
int main()
{
	int n,a[8]={};
	scanf("%d",&n);
	for(int i=1;i<=7;i++)
	{
		scanf("%d",&a[i]);
		a[0]+=a[i];
	}
	n%=a[0];
	for(int i=1;i<=7;i++)
	{
		n-=a[i];
		if(n<=0)
		{
			printf("%d\n",i);
			return 0;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

第二题 鬼画符门之宗门大比（难度：简单）

题目描述

给定整数序列A。求在整数序列$A$中连续权值最大的子序列的权值。

100分做法1

发现数据范围很小，所以考虑先算出前缀和，然后枚举两个端点，求最大值。

100分做法2

我们记$1$~$i$的和为$s_i$，则区间$[i,j]$的和可以表示为$s_i-s_{j-1}$。
要求最大子序列的和，就是求对于每个$s_i$，$s_i-s_x$的最大值。
要想让$s_i-s_x$最大化，就得让$s_x$最小，所以记录$1$~$i-1$中最小的$s_x$，然后求出的$s_i-s_x$就是当前最大值。
把所有的当前最大值取$max$即为答案。

$C++$代码如下：

#include
using namespace std;
long long a[100005],mx=-1e9,ls=0;
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		a[i]+=a[i-1];
		mx=max(mx,a[i]-ls);
		ls=min(ls,a[i]);
	}
	printf("%lld\n",mx);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

第三题 硬币划分（难度：中等）

题目描述

有$1$分，$2$分，$5$分，$10$分四种硬币，每种硬币数量无限，给定$n$分钱$(n\le 10^5)$，有多少中组合可以组成$n$分钱？$($答案$mod$ $10^9+7)$

100分做法

动态规划经典题。
类比完全背包，这四种硬币就相当于物品，钱相当于背包容量。
我们将完全背包中的取$max$操作改成加就变成了求方案数。
相信大家都会完全背包。

$C++$代码如下：

#include
using namespace std;
int a[5]={0,1,2,5,10},dp[100005]={};
int n;
int main()
{
	scanf("%d",&n);
	dp[0]=1;
	for(int i=1;i<=4;i++)
	{
		for(int j=a[i];j<=n;j++)
		{
			dp[j]+=dp[j-a[i]];
			dp[j]%=1000000007;
		}
	}
	printf("%d\n",dp[n]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

第四题 饿龙咆哮-逃离城堡（难度：简单~中等）

题目描述

小艺酱误入龙族结界，被恶龙带回城堡，小艺酱决定逃离城堡，逃离龙族结界.。
总路程为$c$， 小艺酱的速度是$vp$，饿龙速度为$vd$。饿龙会在$t$小时后发现小艺酱出逃。小艺酱担心自己跑不出去，准备了好多珍宝。 每当饿龙追上自己的时候小艺酱就会丢下一个珍宝，饿龙捡到珍宝会返回自己的城堡进行研究，研究f小时后，再出城堡追赶小艺。小艺想知道自己至少需要丢多少珍宝才能让自己安全逃出结界。

100分做法

题目比较长，大概就是一种追及问题，可以用贪心算法解决（就是模拟）。
其实也可以打动态规划，不过没必要。
注意小艺的速度和饿龙的速度，如果$vq\le vp$且$t>0$，答案为$0$。
计算中会出现小数，所以用浮点型存。

$C++$代码如下：

#include
using namespace std;
double c,vp,vd,t,f;
int main()
{
	scanf("%lf%lf%lf%lf%lf",&vp,&vd,&t,&f,&c);
	double s=vp*t;
	int ans=0;
	if(vp>=vd)
	{
		printf("0\n");
		return 0;
	}
	while(s<c)
	{
		double tt=s/(vd-vp);
		s+=vp*tt;
		if(s>=c)
		{
			printf("%d\n",ans);
			return 0;
		}
		ans++;
		s+=vp*tt;
		s+=vp*f;
	}
	printf("%d\n",ans);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28