文章目录

• 感想
• • • 关于自己
    • 关于平台
• 第一题 小艺读书（难度：入门）
• • • 题目描述
    • 100分做法
• 第二题 鬼画符门之宗门大比（难度：简单）
• • • 题目描述
    • 100分做法1
    • 100分做法2
• 第三题 硬币划分（难度：中等）
• • • 题目描述
    • 100分做法
• 第四题 饿龙咆哮-逃离城堡（难度：简单~中等）
• • • 题目描述
    • 100分做法

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

感想

关于自己

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

关于平台

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

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

题目描述

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

100分做法

按照题意模拟即可。可以先处理一周读不完的情况，使其变成一周内读完。
C++C++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;}}
}

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

题目描述

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

100分做法1

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

100分做法2

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

C++C++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);
}

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

题目描述

有111分，222分，555分，101010分四种硬币，每种硬币数量无限，给定nnn分钱(n≤105)(n\leq10^5)(n≤105)，有多少中组合可以组成nnn分钱？(((答案modmodmod 109+7)10^9+7)109+7)

100分做法

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

C++C++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]);
}

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

题目描述

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

100分做法

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

C++C++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(sdouble 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);
}