ACM

Atcoder - Flip and Rectangles(图形递推)

Atcoder - Flip and Rectangles(图形递推)
题意:给你两行相等长度的字符串,你有R\G\B三种颜色可选,颜色可以涂一个1*2的矩形,要么横要么竖,不能存在两个相邻矩形颜色相同,给出的字符串代表的是矩形可以摆放的方向。求最多有多少种涂色的方法。题解:这个要在草稿纸上画一画自己分类讨论一下才能好理解,比赛的时候画是画了,但是由于代码写的太low导致出了bug,赛后补了。要注意特判前面第一个对后面的影响,到了后面就都是规律了。代码:#includ... 继续阅读 »
ACM

Atcoder - Fennec VS. Snuke(DFS)

Atcoder - Fennec VS. Snuke(DFS)
题意:Fennec和Snuke玩一个游戏,F在第一个点并且第一个点为黑色,S在第N个点并且第N个点为白色,然后给出一些点的相连,两个人轮流选择自己自己的颜色旁边相连并且没有上色的点进行涂色,谁最先没有色可以涂谁就输。问最后谁赢谁输。题解:先dfs找到1到N这条链中间中间的下一个点并且保存位置为p,然后从第1个点开始再次dfs,如果遇到p点则停止dfs返回0,然后求dfs到点的和sum,如果sum&... 继续阅读 »
ACM

Atcoder - Built?(预处理+最小生成树)

Atcoder - Built?(预处理+最小生成树)
题意:给出n个点的坐标,连接每两个点之间的的花费是min(|x1-x2|, |y1-y2|)。求将这些点连接起来的最小花费。题解:要是数据给的小的话,这题就是最小生成树的模板题了,但是这里给出的点的大小是10^5,并且还给出了两个点之间的最小花费是min(|x1-x2|, |y1-y2|),那么可以先将x坐标排序,这样两个点之间的最小距离就是他们相邻两个点的x轴的距离了,我们push一个u->... 继续阅读 »
ACM

Atcoder - Widespread(二分答案)

Atcoder - Widespread(二分答案)
题意:你遇到了N个怪兽,你可以选择其中一头怪兽进行攻击,它将会受到a点伤害值,其他怪兽获得b点伤害值(b<a)。当一个怪兽的hp为0时他将会消失,求攻击的最少次数。题解:选择最大的进行攻击肯定不是最优,这题可以用二分答案来解。假设当前攻击次数为mid,那么每头怪兽收到的攻击就是mid*b,剩下要是还有值则选用a的伤害值来攻击,看最后是否能够把每头怪兽消灭掉,如果能消灭那么就将右区间减少,否则... 继续阅读 »
ACM

Atcoder - Chocolate Bar(简单几何)

Atcoder - Chocolate Bar(简单几何)
题意:给出一个由很多格子组成的矩形的宽高(2≤H,W≤105),然后将其分成三个矩形,求最大的矩形和最小的矩形最小的差值。题解:分成三个矩形只有四种情况,三份横着切,三份竖着切;一份横,两份竖着,一份竖着,两份横着。但是我们要是将宽高转换一下其实就两种情况。然后需要注意的就是一二开的情况,直接取中间剖分有可能不能得到最小的差值,还要往左右挪一挪才能得到最优解。代码:#include &l... 继续阅读 »
ACM

Atcoder - 3N Numbers(优先队列)

Atcoder - 3N Numbers(优先队列)
题意:给出3N个点,删除其中N个点,将剩下的2N个数分成两份,求前面部分的和减去后面部分的和的最大值。题解:设前面部分为Na,后面部分为Nb,要使Na-Nb最大。我们可以先假设这删除的N个全都是从N+1到3N中删除的。那么Na最大的就是前面N个的和,我们用最小优先队列来维护这N个的值,然后把接下来的第N+1个数push 进去,删除其中最小的这样就得到了在前N+1个中删除一个的前面的最大值了,依次类... 继续阅读 »
ACM

POJ - 3621 Sightseeing Cows (最优比率生成环)

POJ - 3621 Sightseeing Cows (最优比率生成环)
给出一个有L个点P条边的**有向图(有向图记得了,判成无向图一直跑不出数据气死)**,每个点上的点权为F,每条边上的边权为T。请计算存在一个回路使得∑Fi/∑Ti最大。同样进行二分建图,跑spfa判断是否存在环,由于是正环,所以取反就相当于判负环了。只不过这题目数据有点水啊(不如说题目描述不够准确),网上很多人从1开始跑环的,但是也有人说是从哪个点都可以,仔细看了一下题目是从起始地点开始,也终于起... 继续阅读 »
ACM

POJ - 2728 Desert King (最优比率生成树)

POJ - 2728 Desert King (最优比率生成树)
题目大意是给你n个点的完全图,对于每两个点之间的边有两个权值,cost和len,求一个生成树,使得∑cost/∑len最小。每条边cost的计算是这条边两端点的权值之差的绝对值。len的计算是两个点之间的距离。01分数规划传送门:http://woodcoding.com/?id=172我们可以先根据给出的数据求出每条边的cost和len,然后把每条边的权值设为cost-x*len跑生成树求和,最... 继续阅读 »
ACM

POJ 2976 - Dropping tests(基础01分数规划)

POJ 2976 - Dropping tests(基础01分数规划)
题目的意思是你现在有n场测试,每场测试的成绩总共有b个题目,你对了a个题目,然后你可以选择放弃k个测试,选择剩下的所有测试来作为你的总分数,总分数定义为∑ai/∑bi。请计算你能获得的最大分数。明显的01分数规划模板题,我们令∑ai/∑bi>=x,所以有∑ai-x*∑bi>=0;对每场测试进行计算然后排序选择除掉k个之后剩下的和然后不断判断就好了。01分数规划不会?不如看看之前文章的分... 继续阅读 »
ACM

01分数规划

01分数规划
个人对01分数规划的理解是:01分数规划是利用二分的思想,不断地对答案进行二分验证,使得答案趋近于正确值,最后在精度允许的情况下得到最终的正确答案。先来举个例子,假设有一堆物品,价值为分别为v_i(v_i\geq0)vi(vi≥0),代价分别为w_i(w_i\geq0)wi(wi≥0)。每种物品只有选和不选,请选出一些物品,使他们的收益和最大(为了体现出01规划中01的思想,我们规定这里的w>... 继续阅读 »