企业官网建设流程全解析

3970

如果不限制k的话，本质上就是求最短路

如果限制k的话，好的算法还没想到

如果是朴素的dijs算法的话，无法得知给定最短路上是否会超过k

DFS超时解

先用dfs，记录当前所有字母的出现次数，

但对于这个数量级，应该是必定会超的

又或者先由k这个条件对原labels做一下筛选，得到一系列可能的路径，然后再用上边权去求最短的

但这样筛选的效果可能并不是很好

DEBUG

关键误解

vis会漏掉可行解

AI解

原来Dijkstra算法是有一个优先队列，里面放的是距离最近的节点

然后每次从中取来一个，将其固定，并更新新邻居

n个节点，dp[n]

疑问1

现在是说再扩展一个状态，表示每次取出节点固定时，当前这个固定节点的连续次数吗？

那遍历过程是否发生变化？即原来是不断从优先队列当中取最小值，现在也还是不断取最小值，但原来是取n次，固定n次，那现在是取多少次呢？也还是取n次吗？

怎么理解优先队列里放的是{节点，连续的长度}?如果取出一个节点，就表示此时从起点到这个节点的最短距离就固定下来了，那么相对应其邻居的更新也对应下来了；

如果说是一维的话，固定的是只有一维的状态，即从起点到终点；现在是二维，还多了一个状态，就是到当前节点时，当前节点所连续的次数；如果说是只有一维的话，那么dp[i]=max(dp[i][j])，而现在二维，每次所固定的就只是其中的某一个节点

疑问1.1

对于<int,pair<int,int>>结构的优先队列，如何构造其排序规则？

现在是“取多少次、固定多少次”？

所以那就是说，优先队列保留的是两个状态{目标，目标连续次数}，取节点的时候，依然还是看距离，但是更新状态的时候，则是更新两个状态；

最终结束，就是先到n-1节点上

DEBUG

错误5

错误5就是说，pq可能在早期插入了一些代价较大的方案，但是后续松弛更新时有更好的方案

但是因为循环条件是!pq.empty()，所以早期的那些大代价方案依然会被拿出来处理

但是代价小的方案会被先采纳，所以此时w+dist一定比不过此时dp记录的数值

所以应当直接continue掉

即dist>dp[][]时就该直接continue

但注意也不能取等

就是说在上一层while的时候，可能是刚从INT_MAX更新到dp有效值，然后下次pq取出来处理的时候，可能就会因为这个等于而continue掉

所以应当是只有>

只有已经从INT_MAX取到dp有效值，且这个有效值已经处理过一次后，这个取等才有意义，即避免相同值的重复处理，但判断不出来这个值到底是第一次遇到，还是多次遇到了，所以就不写取等了

DE完后自解

AIcode

当目的是n-1的时候，第一次遇到就可以提前结束，因为是从优先队列里取出来的，所以此时一定是代价最小的；

不过此时考虑过一些小优化，出了问题，即既然目的是n-1那就可以直接return了

那dp或许不需要n-1这一行

但这样在判断邻居时，会出现数组越界的情况

所以判断会因为这个逻辑，而被提前到当前节点判断邻居这一步上，即不再是从优先队列当中取出了

但这样就会出问题，因为如果提前的话，就意味着是目的地第一次是n-1的时候就直接return，但此时可能并不是最优解，即最终答案是dist+w,当前第一次遇到，只能说明此时dist最小，但无法说明dist+w最小；可能pq后面的节点也能到n-1，虽然dist大一点，但w更小，使dist+w更小，所以放到pq里后会更早被取出

所以提前判断以及省掉dp[n-1]这一行不可取

复杂度

又一构造子序列

就是给定len的长度，看能否构造出n个yyc子序列

考虑len当中有a个y，b个c，那么就是去求它们所能组成的最多可能性

是yycyyc的类型排列可能性最多，还是yyycccc的类型排列可能性最多？还是单纯数学运算？

如果是后者，或许应该是(a-1)*b种可能

那对于a+b=len,那么是个二次项为负的二次函数，先增后减

当b在len/2的时候取最大值

不过整个分析建立在yyyccc类型排列可能性最多下，如何证明？

理解错题意了，是要有n个yyc序列，然后自定义要输出的长度

那这样的话，yyyccc类型排列的二次函数，不一定涵盖所有的整数值，所以就需要一些特殊的排序方式

判断上限的话，或许是通过yyccc类型的来计算

即对于输入N,先判断是否超过1e5长度时的最大值，

然后就考虑如何构造

但如何选择对应的构造方式？

如果有a个y,b个c，那么每增长一个c，就会增长a个可能性每增长一个y，就会增长b个可能

AI题解

核心原理

就是说对于每个c，要在前面选择2个y来组成组合，所以就是(a,2)

固定 a 个 y、b 个 c 时，最大是多少？

就是说为了求最大值，因为是要对每个c去选择y然后求和，所以肯定是希望每个c的选择越多越好；那么如果所有的y都在所有的c前面，那么每个c的选择都最多，所以整体最大值就最多

不过题目要求的是排列的yyc数量恰好是n，即整体最大值恰好是n，所以还需要构造

构造方法

疑问1

后半部分，把r拆成若干个三角数之和，是怎么拆的？什么是三角数？

疑问2

如果最大的a满足(a,2)<=n，那么q=n/t不是必然为1？

疑问3——关键疑问

拆分方法是知道了，但是如何构造字符串呢？即使是拆，两部分也不是独立的啊，思路就是针对当前还所需的组合数len不断找最大的a，然后更新len，假设此时找到的那一块字符串是x，那么后续再继续找的时候构造出字符串y的时候，x和y并非完全独立的，即如果x放在y前面，那么y在构造的时候，就无法独立地从0开始遍历三角数，因为前面x里已经包含了一定数量的y；所以后续再继续缩减的时候，必须在x的基础上开始，那么y必然不能在x后面；

那么y只能在x前面，但这样在构造x的时候又会影响已经确定好的x，因为会让x部分中的每个c的前置y数量增加

就是说在拆分的时候，确定好每个c该有ki个y，这应该也就说明了该有i个c（特殊考虑ki==2的情况）

那么对于ki从小到达排序，那就是不断输出ki个y，记录已输出的y的数量cnt

输出完一段ki后，如果cnt刚好等于2，那就是输出两个c,否则就输出一个c

然后继续输出下一段ki，此时输出的下一段ki是建立在cnt基础上的，所以是要输出ki-cnt个y

实现

就是不断拆

不断寻找最大的k，来逼近当前值，然后取余

组合数表示