CSDN 第三十一期竞赛题解

第二次参加
总分77.5，主要是在最后一题数据有误，花费了巨量时间…
参加的另一次比赛最后一道题目也出现了一点问题，有点遗憾。

---

题解

T1：最优利润值

你在读的经营课程上，老师布置了一道作业。在一家公司的日常运营中，是会对一些商品的价格走势根据一些经验和数据进行预估，并据此进行决策。例如，假设某商品每天的价格都有可能变动，我们要做的就是低买高卖获得最高利润。比如假设我们预估该商品接下来七天内的价格走势如下： 4 1 2 3 6 4 8 那我们采取的最佳策略是在价格1块钱的时候买入，在价格8块钱的时候卖出。为了简化整个过程，我们限定在此周期内只能有一次买入一次卖出，且商品在没有购入前是无法卖出的，即该商品不是期货而是现货。 现要求你用程序来实现自动决策。输入一定天数的商品预估价格，自动计算出最优利润值。例如，上面的例子中，最优利润值为8-1=7。（简单起见，只考虑0-100000之间的整数价格）

最大值 - 最小值即可，注意卖出时间比进货时间晚。

Code(时间复杂度小)

#include<bits/stdc++.h>
using namespace std;
int a[8],ans,mn=1e9;
int main(){for(int i=1;i<=7;i++){scanf("%d",a+i);mn=min(mn,a[i]);ans=max(ans,a[i]-mn);}printf("%d",ans);return 0;
}

---

T2：开学趣闻之美食诱惑

小艺酱又开学了，可是在上学的路上总会又各种意想不到的美食诱惑让小艺酱迟到。 假设小艺酱家到学校是一个n*n的矩阵。 每个格子包含一个诱惑值p，诱惑着小艺，让她迟到。 小艺位于矩阵的左上角，学校在矩阵的右下角落。 小艺想知道自己到达学校所要经历的最小诱惑值是？

数字三角形 dp 板题。

Code

#include<bits/stdc++.h>
using namespace std;
int n,a[5005][5005],f[5005][5005];
int main(){scanf("%d",&n);for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]);f[1][1]=a[1][1];for(int i=1;i<=n;i++) f[i][0]=f[0][i]=1e9;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j&&i==1) continue;f[i][j]=min(f[i-1][j]+a[i][j],f[i][j-1]+a[i][j]);}}printf("%d",f[n][n]);return 0;
}

---

T3：小艺照镜子

回文串是一个正读和反读都一样的字符串，已知字符串str。 输出字符串str中最长回文串的长度

CSDN竞赛题目短的题能难吗？
和前两题比起来，能。

Manacher板题。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=110005;
int cnt,len,ans,p[N<<1];
char s[N<<1],S[N],ch;
inline void Rd(){ans=0;s[0]='~';s[1]='|';len=strlen(S);for(int i=0;i<len;i++) s[i*2+2]=S[i],s[i*2+3]='|';cnt=strlen(s);return ;
}
int main(){while (~scanf("%s",S)){Rd();for(int t=1,r=0,mid=0;t<=cnt;t++){if(t<=r) p[t]=min(p[(mid<<1)-t],r-t+1);while (s[t+p[t]]==s[t-p[t]]) p[t]++;if(t+p[t]>r) r=t+p[t]-1,mid=t;if(p[t]>ans) ans=p[t];}printf("%d\n",ans-1);}return 0;
}

---

T4：爱吃鬼
小艺酱每天都在吃和睡中浑浑噩噩的度过。 可是小肚子是有空间上限v的。 小艺酱有n包零食，每包零食占据小肚子空间##a_i##并会给小艺酱一个甜蜜值##b_i##。 小艺酱想知道自己在小肚子空间上限允许范围内最大能获得的甜蜜值是多少?

题目描述是01背包？
而看数据应该是完全背包？？
而交上去评测是？？？

别问我，我也不知道错哪儿了额。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL v,n,a[10005],b[10005],f[10000005];
int main(){scanf("%lld%lld",&v,&n);for(int i=1;i<=n;i++) scanf("%lld%lld",a+i,b+i);for(int i=1;i<=n;i++) for(int j=a[i];j<=v;j++) f[j]=max(f[j],f[j-a[i]]+b[i]);printf("%lld",f[v]);return 0;
}

找了一遍，最后一题的题解还是没有啊 @CSDN？