狗家onsite

少冰半糖谢谢 发表于 2018-11-28 16:50
emmmm 除去区间的概念和那个不等式 我觉得你其他说的都对。相当于对树进行了分割，选最优分割即可，就是 ...

那咱们先讨论区间的概念吧我觉得这是key， 也是我后面不等式的基础。我觉得区间需要是联通的，也就是说我确定区间和它的起始点我从起始点能把这个区间都占领了。 所以我定义的区间就是，如果以node a为分界，那么a为root的子树和以a的parent为起点的其它所有node构成两个区间。  还有我觉得我的不等式之间不互斥？ 比如m=n=k ?

补充内容 (2018-11-28 21:43):
也就是保证我选了这个点之后，不管你选我的左child或是右child或是parent， 我能保证我可以占据其它所有点，然后我都比你大。如过对手选的不是以上这三个点那对手能占的点数更少我还是能保证赢

lukuang 发表于 2018-11-28 21:41
那咱们先讨论区间的概念吧我觉得这是key， 也是我后面不等式的基础。我觉得区间需要是联通的，也就是说我 ...

赞同你的理解！但不等式那里我仍然不能苟同。我们就考虑你先选点的情况。一旦你选好了点，其实游戏结果已经出来了，这是因为你的对手会选一个最优解（你可以推断出你对手的move从而得到确定的游戏结果。因此，并不需要辅以不等式的判别来判定输赢。anyway，you get the idea！

少冰半糖谢谢 发表于 2018-11-29 02:26
赞同你的理解！但不等式那里我仍然不能苟同。我们就考虑你先选点的情况。一旦你选好了点，其实游戏结果已 ...

我觉得确实我选好点了游戏结果就定了因为对手会选最优的解。正因为如此，我们要判断对手的最优解还是比我能占的点少。。
比如说我选了点A， A的左子树有8个点， A的右子树有一个点，除去A这颗子树有5个点。 如果这时候我的对手选了我的左子树的root， 我就输了， 但是如果他选的我的右子树的顶点或着我的parent （也就是占所有非A子树的点）。那我就赢了。
这也是我的那个不等式的初衷。你能具体说说你的解法吗？你一开始好像说的是最大区间？那以root为起点就是最大区间因为除去root这个字数的点数为0？ 我可能还是没理解你的算法？

给少冰半糖小盆友 打call！！！

楼主 想问一下 第三题你是怎么做的

楼主真是牛人！

楼主，想请问下第四题第二问是怎么解决的？还是说就是要选一个尽量均分区间的点呢

同问第三题怎么做的，第三题generate的string长度怎么定呢，是看访问到的char如果后面没有可能的char就停止？