POJ 3156 Interconnect

MayFlyyh | Hash, 期望 | 2018-08-11
> 现在有n个点,给你m条边,每次随机选2个点连边(可能选已经连过的)并且花费1个代价,求使n点联通的期望最小代价。 --- 本题关心每个联通块的规模,但不关心每个联通块具体的点。 然后根据规模记忆化搜索,因为规模无法正常表示成值,所以每次hash一下当前dp的状态,然后记忆化搜索看是否已经算过并返回答案。 对于每个联通块,有两种情况,... [阅读全文]

POJ 1201 Intervals

MayFlyyh | 最短路 | 2018-08-11
> 题意:给m个区间li,ri,再给一个ci,要求在每个区间li-ri种至少选ci个数,求满足条件最小选的数字。 > 数字值域:0~50000,m=c,从l-1到r连一条权值为c的边 然后隐藏条件:0 [阅读全文]

POJ 3417 Network

MayFlyyh | LCA | 2018-08-11
> 题意:给你一颗N个节点树,再给你M条新边(保证不与树边重复)。现在求剪短一条树边和任意M边中的一条边,能将树分成两个联通块的方案 >N (1 ≤ N ≤ 100 000), M (1 ≤ M ≤ 100 000) --- 一开始想的:暴力,N*M然后检验。。 然后想到树形DP,能不能按照每个节点剪掉它与它父亲节点的树边思考 剪掉这条树边,树边部分肯定不与大树相连接 ... [阅读全文]

POJ 1475 Pushing Boxes

MayFlyyh | 搜索 | 2018-07-16
> 想象您正站在一个二维的迷宫中,迷宫由是正方形的方格组成,这些方格可能被岩石阻塞,也可能没有。您可以向北,南,东或西一步移到下一个方格。这些移动被称为行走(walk)。 > 在一个空方格中放置了一个箱子,您可以挨着箱子站着,然后按这个方向推动这个箱子,这个箱子就可以被移动到一个临近的位置。这样的一个移动被称为推(push)。除了推以... [阅读全文]

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 #include #include #include #include #inc... [阅读全文]

POJ 2784 Buy or Build

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

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 #include #include #include #include using namespace std; ... [阅读全文]

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就说明还可以选择一个更好的分数... [阅读全文]
Ɣ回顶部