有哪位大神帮忙来看道题啊
BZOJ 2654 tree_noip吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：18,535贴子：
有哪位大神帮忙来看道题啊
BZOJ 2654 tree收藏
据说是陈立杰留下的！
全国首家青少儿编程机构,专注于教授8岁~18岁孩子专业编程技能.C/C++,noip竞赛,游戏开发等独创课程,培养兴趣,全面提升能力,超越同龄小伙伴.
在网上 题解一搜一片 全是二分！！！！可是 二分总感觉怪怪的！因为有很多时候会遇到权值相同的情况！！
Description　　给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。　　题目保证有解。
二分没什么不对啊
先选白边啊 如果当前mid的答案大于就左移答案，小于就右移答案，如果说上一个状态的答案大于k下一个的答案小于k就选择可以卡在k的那个，如果硬要说矛盾的话一定有黑边白边权值相同的情况，那么白边够了的话全部视为黑边就好啦
谢邀题解：显然可以发现随着白边权值的增大。最小生成树中白边的个数不增。然后根据这个性质我们就可以二分一个值，然后每次给白边加上这个值。看一下最小生成树中白边的个数。最后答案再把它减去。看起来思路非常简单，但是有一个很重要的细节。如果在你的二分过程中如果给白边加上mid,你得到的白边数比need大。给白边加上mid+1,你得到的白边比need小。这种情况看似没法处理。但是考虑一下克鲁斯卡尔的加边顺序。可以发现如果出现这种情况，一定是有很多相等的白边和黑边。因为数据保证合法。所以我们可以把一些白边替换成黑边。所以我们要在白边数&=need的时候跟新答案。具体用ans=ans-mid*即可。转自cnblog
@我作甚？ 二分不是很靠谱吗？相同权值优先选白边就是了
沉了吧！ 谢大家！！
7L已得正解！
登录百度帐号推荐应用
为兴趣而生，贴吧更懂你。或直流电桥法测电阻！3.4题做出来一个就行！跪求大神！_大学物理吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：22,939贴子：
直流电桥法测电阻！3.4题做出来一个就行！跪求大神！收藏
登录百度帐号推荐应用
为兴趣而生，贴吧更懂你。或求大神帮忙解决两道题_推理吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0可签7级以上的吧50个
本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：853,218贴子：
求大神帮忙解决两道题
1.有5个海盗分100个金币,规则如下:第一人提出一个方案有半数或以上的人同意就按方案分,否则把他杀掉,剩下的人依此类推,海盗们都很聪明,都想让自己获得最大利益,问:最后金币怎么分的?2.一村有50户人家,家家都狗,有一部分狗得了狂犬病,需要杀掉,但毎个人白天只能看出别人的狗得了病,看不出自己的狗,并且还不能告诉他人他的狗得了病,也不能去杀别人的狗,只能杀自己的,他们不想误杀,就这样第一天......第二天......第三天夜里只听一阵枪响......问:死了几只狗?
缺牙要及时修复，揭秘种植牙如何做到几十年不掉？
人生的道路也是细一点才有趣哦。
我懒得打字了，直接=-=给你答案海贼分金问题　　海贼，就是海盗，大家听说过吧。这是一帮亡命之徒，在海上抢人钱财，夺人性命，干的是刀头上舔血的营生。在我们的印象中，他们一般都瞎一只眼，用条黑布或者讲究点的用个黑皮眼罩把坏眼遮上。他们还有在地下埋宝的好习惯，而且总要画上一张藏宝图，以方便后人掘取。不过大家是否知道，他们是世界上最民主的团体。参加海贼的都是桀骜不驯的汉子，是不愿听人命令的，船上平时一切事都由投票解决。船长的唯一特权，是有自己的一套餐具——可是在他不用时，其他海贼是可以借来用的。船上的唯一惩罚，就是被丢到海里去喂鱼。　　现在船上有若干个海贼，要分抢来的若干枚金币。自然，这样的问题他们是由投票来解决的。投票的规则如下：先由最凶猛的海贼来提出分配方案，然后大家一人一票表决，如果有50%或以上的海贼同意这个方案，那么就以此方案分配，如果少于50%的海贼同意，那么这个提出方案的海贼就将被丢到海里去喂鱼，然后由剩下的海贼中最凶猛的那个海贼提出方案，依此类推。　　我们先要对海贼们作一些假设。　　1) 每个海贼的凶猛性都不同，而且所有海贼都知道别人的凶猛性，也就是说，每个海贼都知道自己和别人在这个提出方案的序列中的位置。另外，每个海贼的数学和逻辑都很好，而且很理智。最后，海贼间私底下的交易是不存在的，因为海贼除了自己谁都不相信。　　2) 一枚金币是不能被分割的，不可以你半枚我半枚。　　3) 每个海贼当然不愿意自己被丢到海里去喂鱼，这是最重要的。　　4) 每个海贼当然希望自己能得到尽可能多的金币。　　5) 每个海贼都是现实主义者，如果在一个方案中他得到了1枚金币，而下一个方案中，他有两种可能，一种得到许多金币，一种得不到金币，他会同意目前这个方案，而不会有侥幸心理。总而言之，他们相信二鸟在林，不如一鸟在手。　　6) 最后，每个海贼都很喜欢其他海贼被丢到海里去喂鱼。在不损害自己利益的前提下，他会尽可能投票让自己的同伴喂鱼。　　现在，如果有10个海贼要分100枚金币，将会怎样？　　要解决这类问题，我们总是从最后的情形向前推，这样我们就知道在最后这一步中什么是好的和坏的决定。然后运用这个知识，我们就可以得到最后第二步应该作怎样的决定，等等等等。要是直接就从开始入手解决问题，我们就很容易被这样的问题挡住去路：“要是我作这样的决定，下面一个海贼会怎么做？”　　以这个思路，先考虑只有2个海贼的情况（所有其他的海贼都已经被丢到海里去喂鱼了）。记他们为P1和P2，其中P2比较凶猛。P2的最佳方案当然是：他自己得100枚金币，P1得0枚。投票时他自己的一票就足够50%了。　　往前推一步。现在加一个更凶猛的海贼P3。P1知道——P3知道他知道——如果P3的方案被否决了，游戏就会只由P1和P2来继续，而P1就一枚金币也得不到。所以P3知道，只要给P1一点点甜头，P1就会同意他的方案（当然，如果不给P1一点甜头，反正什么也得不到，P1宁可投票让P3去喂鱼）。所以P3的最佳方案是：P1得1枚，P2什么也得不到，P3得99枚。　　P4的情况差不多。他只要得两票就可以了，给P2一枚金币就可以让他投票赞同这个方案，因为在接下来P3的方案中P2什么也得不到。P5也是相同的推理方法只不过他要说服他的两个同伴，于是他给每一个在P4方案中什么也得不到的P1和P3一枚金币，自己留下98枚。　　依此类推，P10的最佳方案是：他自己得96枚，给每一个在P9方案中什么也得不到的P2，P4，P6和P8一枚金币。　　下面是以上推理的一个表（Y表示同意，N表示反对）：　　（P1）（P2）　　（0
）（100）　　（N ）（Y ）　　（P1） （P2） （P3）　　（1
） （99 ）　　（Y
）　　（P1） （P2） （P3） （P4）　　（0
） （99 ）　　（N
）　　（P1） （P2） （P3） （P4） （P5）　　（1
） （98 ）　　（Y
）　　…………………………　　（P1） （P2） （P3） （P4） （P5） （P6） （P7） （P8） （P9） （P10）　　（0
） （96 ）　　（N
）　　问题推广　　现在我们将海盗分金问题推广：　　1) 改变一下规则，投票中方案必须得到超过50%的票数（只得到50%票数的方案的提出者也会被丢到海里去喂鱼），那么如何解决10个海贼分100枚金币的问题？　　2) 不改变规则，如果让500个海贼分100枚金币，会发生什么？　　3) 如果每个海贼都有1枚金币的储蓄，他可以把这枚金币用在分配方案中，如果他被丢到海里去喂鱼，那么他的储蓄将被并在要分配的金币堆中，这时候又怎样？　　通过对规则的细小改变，海贼分金问题可以有许多变化，但是最有趣的大概是1)和2)（规则仍为50%票数即可）的情况，本帖只对这两种情况进行讨论。　　首先考虑　　1) 现在只有P1和P2的情形变得对P2其糟无比：1票是不够的，可是就算他把100枚金币都给P1，P1也照样会把他丢到海里去。可是P2很关键，因为如果P3进行分配方案的话，即使他一枚金币也不给P2，P2也会同意，这样一来P3就有P2这张铁票！P3的最佳方案就是：独吞100枚金币。　　P4要3张票，而P3是一定反对他的，而如果不给P2一点甜头，P2也会反对，因为P2可以在P3的方案中得救，目前为什么不把P4丢到海里呢？所以要分别给P1和P2一枚金币，这样P4就有包括他自己1票的3票。P4的方案为：P1，P2每人1枚金币，他自己98枚。　　P5的情况要复杂点，他也要3票。P4是会反对他的，所以不用给，给P3一枚金币就能使他支持自己的方案，因为在接下来的P4方案中他什么也得不到。问题是P1和P2：只要其中有一个支持就可以了。可是只给1枚金币是不行的，P4方案中他们一定有1枚金币可得，所以只要在他们中随便选一个，给2枚金币，另一个就对不起了，不给。这样P5的方案是：自己97枚，P3得1枚，P1或P2得2枚。　　P6的方案建立在P5的上面，只要给每个P5方案中不得益的海贼1枚金币。要注意的是，P1和P2都应该看作在P5方案中不得益的：他们可能得2枚，可是也可能1枚不得，所以只要P6给他们1枚金币，根据“二鸟在林，不如一鸟在手“的原则，就可以让他们支持P6的方案。所以P6的方案是唯一的：P1，P2，P4每人1枚金币，P6自己拿97枚。　　这样继续下去，P9的方案是：P3，P5，P7每人1枚金币，然后在P1，P2，P4，P6中任选一人给2枚金币，P9自己得95枚。最后，P10的方案是唯一的：P1，P2，P4，P6，P8每人1枚金币，P10自己得95枚。　　2) 是最有趣的（提醒：我们回到50%票即可的规则）。原题解中的推理过程直到200个海贼都是成立的：P200给每个偶数号的海贼1枚金币，包括他自己，其他海贼什么也得不到。从P201开始，继续推理就变得有点困难了：P201为了不被丢到海里去，必须什么也不留给自己，而给从P1到P199中所有奇数号海贼每人1枚金币，从而争取到100票，加上他自己1票，逃过一劫。P202也什么都得不到，他必须用这100枚金币买通100个从P201的方案中什么也得不到的海贼，要注意到现在这个方案不是唯一的：P201的方案中得不到金币的海贼是所有偶数号的海贼，有101个（包括P201），所以有101种方案。　　P203必须得到102票，除了自己的1票外，他只有100枚金币，所以只能买到100票，所以可怜的家伙就被丢到海里喂鱼了。但是，P203是个很重要的角色，因为P204知道如果自己的方案不被通过，P203也一样会完蛋，所以他有P203的一张铁票。所以P204可以大出一口气：他自己一票，加上P203一票，然后加上用100枚金币买的确100票，他就得救了！100个有幸得到1枚金币的海贼，可以是P1到P202中任何100个：因为其中的偶数号的从P2　　02的方案中什么也得不到，如果P204给他们中某个海贼1枚金币，这个海贼一定会赞同这个方案；而编号为偶数的海贼呢，只是有可能从P202的方案中得益罢了（可能性为100/101），所以根据“二鸟在林，不如一鸟在手“的原则，如果能得到1枚金币，他也会赞同这个方案。　　接下去P205是不能把希望放在P203和P204这两张票上的，因为就算他被丢到海里去，P203和P204还可以通过P204的方案机会活下来。P206虽然可以靠P205的铁票，加上自己1票和100枚金币搞到的100票，只有102票，所以他也被丢到海里喂鱼。P207好不了多少，他需要104票，而他自己以及P205和P206的铁票加上100枚金币搞到的100票只有103票——只好下海。　　P208运气比较好，他同样也要104票，可是P205，P206，P207都会投票赞成他的方案！加上他自己的1票和买来的100票，他终于逃脱了做鱼食的命运。　　这样我们就有了一种可以一直推下去的新逻辑。海贼可以什么也不留给自己，买上100票，然后依靠一部分一定会被丢下海的海贼的铁票，从而让自己的方案通过。有这样运气的海贼分别是P201，P202，P204，P208，P216，P232，P264，P328和P456……我们看到这样的号码是200加上一个2的次幂。　　哪些海贼是受益者呢，显然铁票是不用（不能）给金币的。所以只有上一个幸运号码及他以前的那些海贼才有可能得到1枚金币。于是我们得到500海贼分100枚金币的结论是：前44个最凶猛的海贼被丢进海里，然后P456给P1到P328中的100个海贼每人1枚金币。　　就这样，最凶猛的海贼被丢进海里，而比较凶猛的什么也得不到，而只有最温柔的那些海贼，才有可能得到1枚金币。正如《马太福音》所说：“温柔的人有福了，因为他们必承受地土！“　　1
都是争议过多的题目
推理过程是这样的：从后向前推，如果1至3号强盗都喂了，只剩4号和5号的话，5号一定投反对票让4号喂鲨鱼，以独吞全部金币。所以，4号惟有支持3号才能保命。3号知道这一点，就会提出“100，0，0”的分配方案，对4号、5号一毛不拔而将全部金币归为已有，因为他知道4号一无所获但还是会投赞成票，再加上自己一票，他的方案即可通过。不过，2号推知3号的方案，就会提出“98，0，1，1”的方案，即放弃3号，而给予4号和5号各一枚金币。由于该方案对于4号和5号来说比在3号分配时更为有利，他们将支持他而不希望他出局而由3号来分配。这样，2号将拿走98枚金币。同样，2号的方案也会被1号所洞悉，1号并将提出（97，0，1，2，0）或（97，0，1，0，2）的方案，即放弃2号，而给3号一枚金币，同时给4号（或5号）2枚金币。由于1号的这一方案对于3号和4号（或5号）来说，相比2号分配时更优，他们将投1号的赞成票，再加上1号自己的票，1号的方案可获通过，97枚金币可轻松落入囊中。这无疑是1号能够获取最大收益的方案了！答案是：1号强盗分给3号1枚金币，分给4号或5号强盗2枚，自己独得97枚。分配方案可写成（97，0，1，2，0）或（97，0，1，0，2）。企业中的一把手，在搞时，经常是抛开二号人物，而与会计和们打得火热，就是因为公司里的小人物好收买。1号看起来最有可能喂，但他牢牢地把握住先发优势，结果不但消除了死亡威胁，还收益最大。这不正是全球化过程中先进国家的先发优势吗？而5号，看起来最安全，没有死亡的威胁，甚至还能坐收渔人之利，却因不得不看别人脸色行事而只能分得一小杯羹。不过，模型任意改变一个假设条件，最终结果都不一样。而现实世界远比模型复杂。首先，现实中肯定不会是人人都“绝对理性”。回到“海盗分金”的模型中，只要3号、4号或5号中有一个人偏离了绝对聪明的假设，海盗1号无论怎么分都可能会被扔到海里去了。所以，1号首先要考虑的就是他的海盗兄弟们的聪明和理性究竟靠得住靠不住，否则先分者倒霉。如果某人偏好看同伙被扔进海里喂。果真如此，1号自以为得意的方案岂不成了自掘坟墓！再就是俗话所说的“人心隔肚皮”。由于信息不对称，谎言和虚假承诺就大有用武之地，而阴谋也会像杂草般疯长，并借机获益。如果2号对3、4、5号大放烟幕弹，宣称对于1号所提出任何分配方案，他一定会再多加上一个金币给他们。这样，结果又当如何？通常，现实中人人都有自认的公平标准，因而时常会嘟嚷：“谁动了我的奶酪？”可以料想，一旦1号所提方案和其所想的不符，就会有人大闹……当大家都闹起来的时候，1号能拿着97枚金币毫发无损、镇定自若地走出去吗？最大的可能就是，海盗们会要求修改规则，然后重新分配。想一想二战前的希特勒德国吧！而假如由一次博弈变成重复博弈呢？比如，大家讲清楚下次再得100枚金币时，先由2号海盗来分……然后是3号……最可怕的是其他四人形成一个反1号的大联盟并制定出新规则：四人平分金币，将1号扔进大海……这就是阿Q式的革命理想：高举平均主义的旗帜，将富人扔进死亡深渊……制度规范行为，理性战胜愚昧！如果假设变为，是10人分100枚金币，投票50%或以上才能通过，否则他将被扔入大海喂，依此类推。50%是问题的关键，海盗可以投自己的票。因此如果剩下两个人，无论什么方案都会被通过，即100，0。往上推一步，3个人时，倒数第三个人知道只剩两个人时的分配情况，因此它会团结最后一个人，给他一个金币“往前推一步。当前加一个更凶猛的海盗P3。P1知道———P3知道他知道———如果P3的方案被否决了，游戏就会只由P1和P2来继续，而P1就一枚金币也得不到。所以P3知道，只要给P1一枚金币，P1就会同意他的方案（当然，如果不给P1一枚金币，P1反正什么也得不到，宁可投票让P3去喂鱼）。所以P3的最佳策略是：P1得1枚，P2什么也得不到，P3得99枚。P4的情况差不多。他只要得一票就可以了，给P2一枚金币就可以让他投票赞同这个方案，因为在接下来P3的方案中P2什么也得不到。P5也是相同的推理方法只不过他要说服他的两个同伴，于是他给在P4方案中什么也得不到的P1和P3一枚金币，自己留下98枚。依此类推，最终P10的最佳方案是：他自己得96枚，给每一个在P9方案中什么也得不到的P2、P4、P6和P8一枚金币。结果结果，“海盗分金”最后的结果是P1、P2、P3、P4、P5、P6、P7、P8、P9、P10各可以获得0、1、0、1、0、1、0、1、0、96枚金币。在“海盗分金”中，任何“分配者”想让自己的方案获得通过的关键是，事先考虑清楚“挑战者”的分配方案是什么，并用最小的代价获取最大收益，拉拢“挑战者”分配方案中最不得意的人们。真地是难以置信。P10看起来最有可能喂，但他牢牢地把握住先发优势，结果不但消除了死亡威胁，还获得了最大收益。而P1，看起来最安全，没有死亡的威胁，甚至还能坐收渔人之利，但却因不得不看别人脸色行事，结果连一小杯羹都无法分到，却只能够保住性命而已。这答案。。。。你慢慢看吧=-=
这些题很不适合这个吧。-- 真正的完美犯罪，依靠的永远是思想和大局观，而不是高端的科技手段。
有人说我是来混经验的，我转身就是一巴掌，“ 你特么不是废话嘛！”
98 0 1 0 1 第二个没看懂
网狐 专业棋牌游戏开发
回复楼主关于海盗的问题我是海盗我会最后一个回答问题的因为第一个提出答案的一定会死因为大家都一样第二个也是如此到我了就只有两个了我就可以杀了她然后一个人拥有所有的东西
=-=无聊忽悠。。。人
第一个海盗提出他和其他分得金币最多且相等时其必然得到2个人的支持
第二道题狗全死了
第一题应该是98，0，1，0，1。画表逆推就好了。5号最安全，他的方案是前面全部人都死了：0，0，0，0，100但是，这是不可能的，因为：假设4号前面的都死了，4号只需给自己投一票就可以通过：0,0，0，100,05号什么也得不到所以3号只要给5号一个金币，5号就会赞成，否则就什么也没了，即：0,0,99,0,1所以2号只需给4号一个金币，即可通过，即：0,99,0,1,0所以1号的方案是：98,0,1,0,1第二题应该是3只假设只有一只狗感染，那它当天就会死，因为那家人知道别的狗都没事。可是第一天没事发生，说明至少有两只。假设有两只狗感染，由于第一天没事发生，他们主人又只知道其他人有一只感染，所以第二天他们就知道自己的狗有感染。以此类推，可知第三天死了三只狗。
海贼问题:答案是否成立。要看海贼是否把自己的性命考虑进去了。
漫画端脑中有第一题答案
在这个吧混了这么久还没人敢对我发滑稽
贴吧热议榜
使用签名档&&
保存至快速回贴