题目1（dp60分->双向dp口胡）
题目描述
一个矩阵数组，从左上角走到右下角，每一步可向右or向下，走完之后的总价值为通过的位置的数的乘积，（每个数的范围是-8到8，矩阵数组15*15），求最大总价值，答案mod 1e9+7。
解题思路
- 原始版本：全是正数，经典模型，保留dp[i][j]为最大值，dp[i][j] = max(dp[i-1][j], dp[i][j-1])*value[i][j]。
- 正数和复数都有：如果value[i][j]为负，取max反而得到最小的value，而最大的value由之前的最小值得到。因此保留每一步转移的最大值和最小值。dp_max[i][j], dp_min[i][j]。
dp_max[i][j] = max(dp_max[i-1][j], dp_max[i][j-1])*value[i][j], dp_min[i][j] = min(dp_min[i-1][j], dp_min[i][j-1])*value[i][j]
if value[i][j]< 0:
swap(dp_max[i][j], dp_min[i][j]);
- 正数和复数都有：如果value[i][j]为负，取max反而得到最小的value，而最大的value由之前的最小值得到。因此保留每一步转移的最大值和最小值。dp_max[i][j], dp_min[i][j]。
- （赛后发现）上一步得到了60分。赛后发现，数据范围8=2^3，则8^15大于long long，需要过程中取模，而过程中的取模会导致dp方程转移失败。但8^8就不会大于long long，不需要过程取模，因此，把单项dp递推，改为从左上角和右下角分别双向递推，应该就能拿满分。（赛后才想明白，没办法）。。
题目2（高精度？0分）
题目描述
计算一个带有开立方+取模+高精度的公式，答案也是高精度的科学表示法。解题思路
没想明白。
目前想到的是，把题目中出现的10^-15和10^-20往上乘一些量级避免精度太高的浮点数运算，且sum这个部分可以用前缀和。但精度仍然不够高，或许需要数学层面的优化。
开立方：pow(x,1.0/3.0)，感觉上误差应该不小？题目3（dp100分）
题目描述
一排m个盒子，n个颜色的数量无限的小球，要求每个盒子一个小球，最多有连续两个盒子里球的颜色相同。求方法数。解题思路
无脑的dp。dp[i][2]，dp[i][1]代表当前颜色和上一个相同的方案数，dp[i][0]代表当前颜色和上一个不同的方案数。
dp[i][0] = (dp[i-1][0]+dp[i-1][1])*(n-1);
dp[i][1] = dp[i-1][0];
（写成这个样子的dp，是不是能压成一维？反正没必要）
唯一一道100分的，第一次还因为取模次数太多得了95分，相当于卡常。题目4（递归30分->有新思路）
题目描述
一串n个数的集合，每个数的大小在0-2n范围内，每次根据数组的最大值和最小值的平均值（取地板—）把数划成两个子集。求所有子集的元素和的和。解题思路
对于集合中任意一个元素，他被计算的次数等于参与划分的次数。即一个数被一直划分，每次加一个它的值，直到他无法被划分成两个子集。
子集划分停止条件：1.集合中只有一个元素。2.集合中所有数大于或小于(min+max/2)。即所有数的大小相等。
然后就可以直接模拟+递归了，复杂度理论上是nlogn就能解决。
如果能划分，找到划分元素的位置。我就是因为找划分元素套了一个二分查找多了logn的复杂度超时。没有注意题目是元素范围是0-2n，直接遍历数组记录0-2n的划分位置下标就没这回事了，当时过于着急，二分查找是又难写又超时T T。题目5 （map和set0分，没做完）
题目描述
n个文档，分别k个字符。每个文档中每个字符的重要度定义为(本文档中字符出现次数/多少个文档出现了这个字符)。每个文档的重要度定义为它最重要的字符的重要度。依次输出重要度。解题思路
map<string, long long>mp0记录所有出现过的字符以及出现的文档。value我想的是bool二进制编码。数据范围大的话可能要再嵌套一个set。
map<string, int>mp1[n]记录各个文档各个字符出现次数。
然后map遍历。不知道有没有坑以及时间复杂度，大约是这样吧。
没有拿到模板的情况下，遍历map一直报错，没改明白。
- （赛后发现）上一步得到了60分。赛后发现，数据范围8=2^3，则8^15大于long long，需要过程中取模，而过程中的取模会导致dp方程转移失败。但8^8就不会大于long long，不需要过程取模，因此，把单项dp递推，改为从左上角和右下角分别双向递推，应该就能拿满分。（赛后才想明白，没办法）。。