POJ 1324 Holedox Moving

MayFlyyh | 搜索 | 2018-07-16
题意:给出蛇头和蛇身(蛇身分为若干节,用坐标连起来,当然蛇头也是一个坐标) 给出终点坐标,障碍物坐标,问蛇能不能到达终点(蛇头到达) 本题可以用状态压缩,表示蛇头在x,y,蛇身的状态。蛇身的状态可以用该部分和上一部分的相对位置来表示,分别有四种状态就是在它的上下左右,分别记为0,1,2,3,二进制位是00,01,10,11。蛇身长共7节... [阅读全文]

POJ 2420 A Star not a Tree

MayFlyyh | 随机算法 | 2018-07-16
给定一个平面和平面上n个点求出一点到所有点的距离和最小输出该最小距离; 很想JS省选吊打XXX 答案是模拟退火,思路明白了以后,重点是每次重新选点的随机方式一定要好。这个一定要多做几道模拟退火领会一下思路。因为我发现不按照题解那样写还真不行。。。 #include<iostream> #include<cstdio> #include<cstdlib> #include&... [阅读全文]

POJ 2976 Dropping tests

MayFlyyh | 二分答案 | 2018-07-16
给定n个二元组(a,b),扔掉k个二元组,使得剩下的a元素之和与b元素之和的比率最大。题目求的是 max(∑a[i] * x[i] / (b[i] * x[i])) 其中a,b都是一一对应的。 x[i]取0,1 并且 ∑x[i] = n - k。 看到除法,应该是分数规划吧。每次二分以后计算出一串数字对答案的贡献大小,从小到大排序选前n-k个。如果都大于0就说明还可以选择一个更好的分数。注... [阅读全文]

POJ 3279 Fliptile

MayFlyyh | 搜索 | 2018-07-16
> 给一个N行M列的矩阵,值分别为0和1,每次你可以选择将一个变成相反状态,同时,它周围的四个数也会变为相反状态。 问:最少翻转多少次,可以将所有值都变成0 多个解,输出翻转次数最少的(若有次数相同解,输出字典序小的) 若无解,输出”IMPOSSIBLE” 显然一个数字只能翻转一次,那就按照字典序枚举第一行的所有可能,记录下答案最小的一个... [阅读全文]

POJ 1239-Increasing Sequences

MayFlyyh | DP | 2018-07-15
有一串数字,在它们之间加逗号来分隔,使之成为一个上升序列。 要求最后一个数尽可能的小,如果有多个满足要求,则使第一个数尽可能大;如果还有多个,则使第二个最大,依此类推。 感觉这是一道很经典的线性DP题(因为做的太少了)。 思路就是首先保证后一个数尽量大于前一个数,一旦满足条件就去找下一个数。 然后就找到了能满足条件的而且最... [阅读全文]

BZOJ 1079[SCOI2008]着色方案

MayFlyyh | DP | 2018-07-12
1079: [SCOI2008]着色方案 Time Limit: 10 Sec Memory Limit: 162 MB Description   有n个木块排成一行,从左到右依次编号为1~n。你有k种颜色的油漆,其中第i种颜色的油漆足够涂ci个木块。 所有油漆刚好足够涂满所有木块,即c1+c2+...+ck=n。相邻两个木块涂相同色显得很难看,所以你希望统计任意两 个相邻木块颜色不同的着色方案... [阅读全文]

BZOJ1426 收集邮票

MayFlyyh | DP, 期望 | 2018-07-12
1426: 收集邮票 Time Limit: 1 Sec Memory Limit: 162 MB Description 有n种不同的邮票,皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买,每次只能买一张,并且 买到的邮票究竟是n种邮票中的哪一种是等概率的,概率均为1/n。但是由于凡凡也很喜欢邮票,所以皮皮购买第k 张邮票需要支付k元钱。现在皮皮手中没有... [阅读全文]

BZOJ1076 [SCOI2008]奖励关

MayFlyyh | DP, 期望 | 2018-07-12
BZOJ 1076: [SCOI2008]奖励关 Time Limit: 10 Sec Memory Limit: 128 MB Description   你正在玩你最喜欢的电子游戏,并且刚刚进入一个奖励关。在这个奖励关里,系统将依次随机抛出k次宝物, 每次你都可以选择吃或者不吃(必须在抛出下一个宝物之前做出选择,且现在决定不吃的宝物以后也不能再吃)。 宝物一共有n种,系统每次抛... [阅读全文]

BZOJ1415 [Noi2005]聪聪和可可

MayFlyyh | DP, 期望 | 2018-07-12
BZOJ1415 [Noi2005]聪聪和可可
BZOJ1415 [Noi2005]聪聪和可可 首先要预处理处当前聪聪在i点,可可在j点的时候聪聪下一步要走到哪里(这我都没想出来。。。 然后就比较简单了,根据套路,这个聪聪在x节点的期望应该是可可在j节点走到各种地方后,聪聪跟上的期望,当然也要算出可可留在原地,聪聪跑两步的期望。最后一加就好了。 一开始是这么想的,可害怕转移的东西互相依赖就没... [阅读全文]

【网络流24题】软件补丁问题

MayFlyyh | 网络流 | 2018-06-29
【网络流24题】软件补丁问题 T 公司发现其研制的一个软件中有 n 个错误,随即为该软件发放了一批共 m 个补丁程序。每一个补丁程序都有其特定的适用环境,某个补丁只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用。一个补丁在排除某些错误的同时,往往会加入另一些错误。 换句话说,对于每一个补丁 i,都有 2 个与之相应的错误... [阅读全文]
Ɣ回顶部