9.13总结

「爱情、让人受尽委屈。」 2023-08-17 15:35 32阅读 0赞

# 9.13总结 #

## 得分情况 ##

35+30+100=165 Rank2

第二题SPFA被卡了！！

## T1 ##

![1735240-20190913161415106-1691343142.png][]

![1735240-20190913161421491-1290057842.png][]

在DFS序上dp。

设f\[i\]\[j\]表示当前放了i个点，所在的位置x是DFS序最大的那一个，根到x走了j步。

于是有两种转移，就是x新增一个左儿子（此时j+1），或者是找一个dfs序最大，有左儿子但没有右儿子的节点添加一个右儿子(此时j-1)。这两种转移新增的节点的DFS序都一定是x的DFS序+1。

所以就从f\[i\]\[j\]转移到f\[i+1\]\[j-1\]或f\[i+1\]\[j+1\]

有x个叶子节点的时候，总节点数一定是2\*x-1，所以f\[2\*x-1\]\[0\]就是合法的答案。

## T2 ##

![1735240-20190913161443613-1287712626.png][]

![1735240-20190913161445960-353608203.png][]

推一下式子发现边权的变化每三次就会循环，即x->(1/(1-x))->((x-1)/x)。所以把一个点拆成三个，直接最短路就好了。

## T3 ##

![1735240-20190913161506709-1782669562.png][]

结论题

比赛的时候想分治去做，然后发现结论有问题，然后发现修正一下就好了

假设现在求区间\[l,r\]的长度为S的子序列的最大价值和最小价值（转移用），已经求出了\[l,mid\]和\[mid+1,r\]的答案。

假设左边选S1个，右边选S2个可以使答案最优。

现在我们要求长度为S+1的答案，假设左边选S1'个，右边选S2'个可以使答案最优。

发现S1'与S1;S2'与S2是有一些联系的。它们的差不超过3。

![1735240-20190913161513680-801873606.png][]

跑的最快

转载于:https://www.cnblogs.com/leason-lyx/p/11517066.html

[1735240-20190913161415106-1691343142.png]: /images/20230810/01c67410b4fa40f6a4b12456eaa8f92d.png
[1735240-20190913161421491-1290057842.png]: /images/20230810/8df551b7d4a049c9b187fd7c3007dce4.png
[1735240-20190913161443613-1287712626.png]: /images/20230810/533c9ba29b8c41bcbfd2bb2b062e4c6a.png
[1735240-20190913161445960-353608203.png]: /images/20230810/2be566bb529b4a95aa0e87cfb1b1dbd6.png
[1735240-20190913161506709-1782669562.png]: /images/20230810/91cc2cfea953497683da37f8a2749fda.png
[1735240-20190913161513680-801873606.png]: /images/20230810/0bc5fc941e294274926fc9aa014e6c52.png

发表评论取消回复

表情：

评论列表（有 0 条评论，32人围观）

还没有评论，来说两句吧...

相关阅读

相关 913 error Component name “home“ should always be multi-word vuemulti-word-component-names

新手在操作npm run serve 的时候会出现以下的报错，报错原因是希望组件名写成驼峰式或者链-先形式的，但是官方又明确单个单词组件命名是符合规定的，总结在编译的时候esl

今天药忘吃喽~/ 2023年09月30日 07:54/ 0 赞/ 36 阅读

相关排序不等式 AcWing 913. 排队打水

排序不等式 AcWing 913. 排队打水原题链接 [AcWing 913. 排队打水][AcWing 913.] 算法标签贪心排序不等式思路

蔚落/ 2023年09月28日 11:03/ 0 赞/ 133 阅读

相关【Leetcode 913】【Hard】Cat and Mouse 博弈论

描述 913. Cat and Mouse Hard A game on an undirected graph is played by two players

小咪咪/ 2023年06月03日 15:54/ 0 赞/ 37 阅读

相关 @codeforces - 913F@ Strongly Connected Tournament

目录 @description@ @solution@ @accepted code@ @details@ --------------------

谁借莪１个温暖的怀抱￠/ 2023年06月01日 12:59/ 0 赞/ 28 阅读

相关【Web技术】913- 谈谈你对前端路由的理解

![079731f66387e4af6a41f2a3b333798a.png][] > 来自：掘金 > > 作者：尼克陈 > > 链接：https://juejin.cn

朱雀/ 2022年11月15日 01:11/ 0 赞/ 163 阅读

相关总结(算不上总结的总结)

还有几天 2016年就要结束了，思来想去，还是觉得写点东西，总结自己过去这一年写博客的感受！回到2016年初，记得自己的博客访问量才一点点，虽然接触csdn

野性酷女/ 2022年07月13日 05:48/ 0 赞/ 387 阅读

相关总结

[总结][Link 1] 基本数据类型是放在栈中还是放在堆中，这取决于基本类型声明的位置。 -------------------- 一：在方法中声明的变量，

柔光的暖阳◎/ 2022年01月28日 11:53/ 0 赞/ 462 阅读

相关个人总结——学期总结

<table style="width:481px;"> <thead> <tr> <td> <p>这个作业属于哪个课程</p> </td> <td>

￡神魔★判官ぃ/ 2021年11月14日 14:34/ 0 赞/ 535 阅读

相关总结

一、作业简介 <table> <thead> <tr> <td> <p>这个作业属于哪个课程</p> </td> <td> <p>https:/

忘是亡心i/ 2021年11月05日 12:36/ 0 赞/ 581 阅读

相关【总结】年中总结

伴随着新年的鞭炮声和饺子香气，不知不觉，一年又过去了，今天都是大年初6了，明天又到了工作的日子了，去年的余味还没有散去，又得开始准备新一年的努力和拼搏了。

叁歲伎倆/ 2021年06月24日 15:58/ 0 赞/ 592 阅读