POJ 1011 Sticks

MayFlyyh | 搜索 | 2018-07-16
现在有n根木棍,然后需要把它们拼成同样长度的木棍,问满足这个条件的最短的长度是多少? 搜索一下,显然长度之和应该能整除木棍数量,用这个数去看木棍能不能达成 有几个剪枝,先用桶排序,然后每次算的时候从大向小装,记一下装到的长度l,如果没有拼好这个木棍就接着l开始,如果拼好了就开始新的木棍从最大的那个长度开始。(想一想觉得还是... [阅读全文]

POJ2785 4 Values whose Sum is 0

MayFlyyh | 二分答案 | 2018-07-16
题意:四列,每列找一个数,得到和为0的序列,有几种不同的方案 一开始想的是dfs。。。后来想的是前两列两两组合将和放入多重集multiset里然后后两列每次查询一下就可以,但还是T了。 原来是把前两列两两组合,后两列两两组合然后每次查询就可以。 看来是set常数太大了。 #include<cstdio> #include<iostream> #include<cstring... [阅读全文]

POJ 2784 Buy or Build

MayFlyyh | 最小生成树 | 2018-07-16
n个城市,告诉每个城市的坐标,还有q个联通块,现在要把这n个城市连起来,可以购买联通块(每个有一定的费用),或者新建一条边(费用为点之间的距离的平方),问最小费用是多少。 二进制枚举每个联通块的选择情况。 注意联通块的数量大小应该就可以判断出要枚举。然后每次都跑一边最小生成树算出最优的答案。。 #include<cstdio> #includ... [阅读全文]

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元钱。现在皮皮手中没有... [阅读全文]
Ɣ回顶部