这道题还是比较容易能看得出是dp的。但是这个状态设计我不会，参考了大佬们的题解。这个状态的设计需要考虑到：由于每个格子的状态和前后都有关，所以，单纯一个维度是不足以准确表示状态然后进行状态转移的。俗话说得好：表达不准确？再来一维（我自己编的23333），我们可以考虑多维表示状态。因为想到：我们要确定一个格子的状态，我们还需要的就是前一个格子的信息，因此，前一个格子需要记录自己的信息。另外，这个格子的信息还和后一个格子有关，所以，还需要一个维度表示后对后一个一个格子的要求.自然的，格子本身的位置需要记录下，因此，我们考虑开这样一个三维数组，定义状态：dp[i][j][k]:i表示位置。若j==1...

看到这道题，发现不会最小生成树，遂昨晚熬夜补了prim算法，今天来写这道题。看到时间胶囊能回溯，因此确实可以想得到是最小生成树，其实就是最小生成树后求路径长度和最小的问题。这道唯一特别一点的地方就是只能从高处到低处，并且要保证能去的地方最多，所以贪心策略需要加一条：以边终点高的优先选择，保证高度高（能去地方最多）的情况下选择最短路径。之后，就是prim算法。这里我选择了堆优化。以1为起点，把和1相关的路径全部push进堆里，之后按照贪心策略取出，取到没有访问过的点就如法炮制丢路劲进来。 90分答案： #include <iostream> #include <map> ...

wa/tle了三页才写出来。。。菜鸡果然是菜鸡 主席树 这个昨晚刚看的数据结构，敲的时候敲错了n多次。。在树里，把数的版本号当作数组下标，树内记录每个区间内的数的出现次数，学过之后还是比较好理解的。 #include <iostream> #include <cstdio> using namespace std; const int maxn=1e5+10; struct node{ int l,r,sum; }tree[maxn*40]; int cnt,root[maxn]; int n,m; int a[maxn]; void insert(int l,int ...

这道题比赛的时候没有写出来。。没有写出来是想不出如何验证这个数是不是符合题目要求的，写不出check函数。参考大佬博客：https://blog.nowcoder.net/n/aa5ff9efa80440c897a9aaae4401a467卡住我的两个点：1、怎么分解出p的因数可以通过一个for和while的嵌套：for循环从2开始枚举，每次枚举令p除到不能再被i整除（不含因数i）的时候位置，因为一个合数肯定是由比它小的素数相乘的来的，因此，for循环枚举i的时候，枚举到合数的时候他是会自动跳过的，因为已经枚举过这个合数的质因数了，所以现在的p自然也就没办法被合数i整除了。 inline vo...

思路分析 看到每一道菜有选和不选两种决策，我们想到了01背包。但是，和普通的01背包相比有个区别，就是做每一个决策是具有后效性的：选了i道菜会影响i+k道菜的价值，也就是说，菜的价值会和选的顺序有关。因此，我们需要利用一个贪心确定一个选择的顺序，令按照这一顺序选择答案最优。通过证明我们可以得到可以按照的要求顺序排序。证明：设目前的时间为t，则，若顺序最优，则符合：化简后就能得到我们上面的结论。接下来就是普通的01背包了。这里还需要处理一个问题：因为结果可能是负数，我们需要将dp数组全部初始化为负无穷，然后将dp[0]设为0后再开始状态转移。这是需要学习的处理方式。 AC代码 #include ...

这道题写了好久，因为一个略傻缺的错误测了好久。。。这道题我们需要抓住到一点：前面的糖糖会不会被消灭，只和后面的糖糖有关，所以，我们获取信息的顺序应该是从后开始，然后让前面的和后面比较。由于我们只需要知道会不会被消灭，所以，我们要的是后面的糖糖种的、类似最大值的东西。那么，假设我们要比较两个糖糖i和j(i<j)，那么，我们确定i会不会被消灭的时候，我们比较的式子就是：b[i]+sum[j]-sum[i-1]<=>b[j]+c[j]我们变一下式，就变成：b[i]-sum[i-1]<=>b[j]+c[j]-sum[j]这时候，式子右边的就是我们要找的定值。那么，每次查询...