【题解】山东财经大学新生赛暨天梯赛选拔赛
A 骆驼拼写法
嘟噜噜，这个题目很简单啊用getchar()一个一个的读入字符
第一个单词都小写后面的单词都首字母大写
空格过滤掉输出答案就可以啦
B 流浪地球
这个题目要看图片
图片里一个v速度的小星体绕一个u速度的星体速度变成了2u+v
题目中 一个超级大球向右运动 有n个小球向左运动 其中每个小球的质量都远小于其左边的球
问的是 需要进行图片中的加速多少次 会产生一个达到光速百分之一的小星体
答案就是 进行图片里那个式子的过程 记录一下加速了多少次就可以啦
C Retina
很简单的模拟题
主要注意好最后 山的一横 后面没有空格就好啦
D 流星雨
简单dp题
这个题目就是给我们好多段线段让我们求最长段
开一个一维dp 设dp[i]是末尾为i的连续段的最长长度
从前面往后面跑一遍 到i的时候 用从i开始的线段接到i的后面更新一下后面的dp值
因为我们走到i的时候 可以保证到达i的之前的线段都更新过 所以dp[i]就是那个i为末尾的最优值
再扫一遍dp[I]找到最大长度就可以了
E 旅行商问题
一个树 从根开始走过所有点的最短距离长度 有的边要走2次 有的边要走1次
走一次的边就是从根开始的一个简单路径
我们把所有的边权求个和再乘2 减去距离树根最远距离就可以出答案啦
F 简单排序
实际上就是求这个序列的最长上升子序列的长度。 简略证明:
假设最长上升子序列长度为 K’，则其中任意两辆个数不会进入同一个队列，因此 K≥K’。至 于 K=K’可由数学归纳法详细证明。
用二分法或树状数组(线段树)优化 DP，时间复杂度 O(NlogN)。
假设最长上升子序列长度为 K’，则其中任意两辆个数不会进入同一个队列，因此 K≥K’。至 于 K=K’可由数学归纳法详细证明。
用二分法或树状数组(线段树)优化 DP，时间复杂度 O(NlogN)。
G 武林秘籍
dfs序的模板题，先差分，求点到根的路径和，再计算每个修改的贡献。对于单点修改可以转化为子树加，将链求和转化为在链的底端单点求和。
对于节点u的子树修改w，对u的子结点v的贡献为w*dep(v-u)，可以转化为 w*dep v-w*dep u，其中后一项是不随查询节点的变化而改变的，
对于节点u的子树修改w，对u的子结点v的贡献为w*dep(v-u)，可以转化为 w*dep v-w*dep u，其中后一项是不随查询节点的变化而改变的，
可以理解为w节点的权值不是增加了w而是增加了w*dep u，这样就可以存储在上一问的树状数组里。
同时新增一个树状数组存储w*dep v的w，在每次查询时计算w*depv，复杂度O(nlogn)
std
- A :https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40432663
- B: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40432664
- C: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40432665
- D: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40432677
- E: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40432674
- F: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40432675
- G: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40432676
