图论

[BJWC2012]冻结

题目描述

“我要成为魔法少女!” “那么,以灵魂为代价,你希望得到什么?” “我要将有关魔法和奇迹的一切,封印于卡片之中„„” 在这个愿望被实现以后的世界里,人们享受着魔法卡片(SpellCard,又名符卡)带来的便捷。 现在,不需要立下契约也可以使用魔法了!你还不来试一试? 比如,我们在魔法百科全书(Encyclopedia of Spells)里用“freeze”作为关键字来查询,会有很多有趣的结果。 例如,我们熟知的Cirno,她的冰冻魔法当然会有对应的 SpellCard 了。 当然,更加令人惊讶的是,居然有冻结时间的魔法,Cirno 的冻青蛙比起这些来真是小巫见大巫了。 这说明之前的世界中有很多魔法少女曾许下控制时间的愿望,比如 Akemi Homura、Sakuya Izayoi、„„ 当然,在本题中我们并不是要来研究历史的,而是研究魔法的应用。 (更多…)

DefFrancis
动态规划

WJMZBMR打osu! / Easy

题目描述

某一天WJMZBMR在打osu~~~但是他太弱逼了,有些地方完全靠运气:( 我们来简化一下这个游戏的规则有 次点击要做,成功了就是o,失败了就是x,分数是按combo计算的,连续 个combo就有 分,combo就是极大的连续o。 Sevenkplus闲的慌就看他打了一盘,有些地方跟运气无关要么是o要么是x,有些地方o或者x各有50%的可能性,用?号来表示。 比如oo?xx就是一个可能的输入。 那么WJMZBMR这场osu的期望得分是多少呢? 比如oo?xx的话,?o的话就是oooxx => 9,是x的话就是ooxxx => 4 期望自然就是 (更多…)

DefFrancis

[国家集训队]聪聪可可

题目描述

聪聪和可可是兄弟俩,他们俩经常为了一些琐事打起来,例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑(可是他们家只有一台电脑)……遇到这种问题,一般情况下石头剪刀布就好了,可是他们已经玩儿腻了这种低智商的游戏。 他们的爸爸快被他们的争吵烦死了,所以他发明了一个新游戏:由爸爸在纸上画n个“点”,并用n-1条“边”把这n个“点”恰好连通(其实这就是一棵树)。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点(当然他们选点时是看不到这棵树的),如果两个点之间所有边上数的和加起来恰好是3的倍数,则判聪聪赢,否则可可赢。 聪聪非常爱思考问题,在每次游戏后都会仔细研究这棵树,希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。 (更多…)

DefFrancis
图论

航空路线问题

题目描述

给定一张航空图,图中顶点代表城市,边代表 2 城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。 (1)从最西端城市出发,单向从西向东途经若干城市到达最东端城市,然后再单向从东向西飞回起点(可途经若干城市)。 (2)除起点城市外,任何城市只能访问 1 次。 对于给定的航空图,试设计一个算法找出一条满足要求的最佳航空旅行路线。 (更多…)

DefFrancis
图论

太空飞行计划问题

题目描述

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E1,E2,…,Em},和进行这些实验需要使用的全部仪器的集合I={I1,I2,…In}。实验Ej需要用到的仪器是I的子集RjÍI。配置仪器Ik的费用为ck美元。实验Ej的赞助商已同意为该实验结果支付pj美元。W教授的任务是找出一个有效算法,确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。 对于给定的实验和仪器配置情况,编程找出净收益最大的试验计划。 (更多…)

DefFrancis
图论

[APIO2009]抢掠计划

题目描述

Siruseri 城中的道路都是单向的。不同的道路由路口连接。按照法律的规定, 在每个路口都设立了一个 Siruseri 银行的 ATM 取款机。令人奇怪的是,Siruseri 的酒吧也都设在路口,虽然并不是每个路口都设有酒吧。 Banditji 计划实施 Siruseri 有史以来最惊天动地的 ATM 抢劫。他将从市中心 出发,沿着单向道路行驶,抢劫所有他途径的 ATM 机,最终他将在一个酒吧庆 祝他的胜利。 (更多…)

DefFrancis