下一页 »Current position : 首页 >> 状压动规
「CF1242X」Codeforces Round #599 (Div. 1)
A.TilePainting对n做因式分解，如果n有超过一个质因数t，则答案是1，否则答案是t。因为两个质因数求gcd以后是1，则ax+by可以把所有格子染上。[crayon-6967270316bc0645900241/]B.0-1MST求补图的联通块个数，BZOJ1098原题。维护一个1-n的链表，表示有哪些点还没确定所在连通块。从1-n枚举点x，用bfs把与x同一连通块的点找出来，每次bfs只需要考虑还在链表里的点，这样每一条边要不然在原图中，要不然不在原图中使得某个点...
程序设计实习实验班2017作业(算法 作业19, 20, 21)
一些以前做过的就不再贴了AFunnyStoneGame发现每一堆的每个石子之间都是相互独立的[crayon-6967270317c76317672021/]nnimn阶nim和，在二进制下，每一位求和后对(n+1)取模[crayon-6967270317c81898113610/]一个水水的序列在建操作树的过程中就能顺便维护信息每次新加入节点的时候维护一下这个点的倍增数组，询问的时候直接向上倍增[crayon-6967270317c86506512014/]「poj1523」SPF求割点，并且求删去割点后的连通分量个数[cr...
「CF718X」Codeforces Round #373 (Div. 1)
A.EfimandStrangeGrade给一个长为n的小数，有t次操作，每次可以让小数点后的某一位向前四舍五入问能最终能得到的最大的数题解考虑找到最前的一个大等于5的数字，从其开始考虑四舍五入如果四舍五入到小数点，将小数点去掉最后再处理一下整数位的进位问题[crayon-6967270318333225833246/]C.SashaandArray给定一个长度为n的数列an，有两种操作1、将L到R的加上X2、询问\(\sum_{L\leqi\leqR}F(a_i)\)题解考虑在线段树的每...
「CF698X」Codeforces Round #363 (Div. 1)
A.Vacations题意：给出每天contest和gym的开关状态，不能连续俩天参加相同活动，问n天最少休息多少天用F(i,0-2)表示前i天，第i天的状态为（rest，contest，sport），最多能有多少天不休息简单dp一下[crayon-69672703188c1013836515/]B.FixaTree给出n个结点的父亲，问至少修改多少个能够使得其变成一棵树先用拓扑排序消去外向树，剩下的每个环要选出一个当根，然后再把所有的环连成树答案是环数-（是否存在自环）[crayon-6967...
「省选模拟赛」[BZOJ1556] 小奇走迷宫
![「省选模拟赛」[BZOJ1556] 小奇走迷宫](http://hzwer.com/wp-content/themes/ly/image/image_post/476EC26F-546E-4F63-95E5-CDF20937CB0C.png)
原题：「bzoj1556」墓地秘密「题目背景」小奇驾驶G-1500机器人探险时落入了一个有魔法的迷宫，一旁的木牌上写着：“你可以回头，但你永远无法离去。”「问题描述」木牌下方有一行小字：“撞击所有机关墙”。G-1500机器人每次可以朝着前方光速移动，质量、动能无穷大，可以选择自己在行进中停下来或者撞墙后停下来，移动时只有转向需要花费时间。真是个诡异的迷宫，不过，小奇的眼前已经出现了迷宫的地图，它想尽早离开这里，请你...
「CF317X」Codeforces Round #188 (Div. 1)
A.PerfectPair每次把小的那个变成两个的和，注意考虑负数[crayon-69672703194a7856466956/]B.Ants蚂蚁的活动范围不太大，所以依然是暴力QAQ[crayon-69672703194af143063744/]C.Balance每次从缺水的地方出发，找一条能送水过来的路径a->b，要保证a是路径上符合要求的第一个容器运送量\(d=min(b_b-a_b,a_a-b_a)\)，找n次若没有容量限制，每次从b到a扫，找当前水量超过d的往b方向运由于有容量限制，把d拆成d/2和d-d/2分两...
「CF293X」Croc Champ 2013 – Round 2
A.WeirdGame两个人都应该采取贪心策略根据规则，先取0而对方不取0则败，所以有1则取1，当然尽量取对方也是1的那些取0的时候同理，尽量取对方是1的那些我们模拟游戏进程得出两个人的最终序列比较即可[crayon-6967270319cf7948681956/]B.DistinctPaths容易发现，n+m-1>K时是无解的，那么有解的棋盘就很小了，状压使用的颜色+dfs然而这样的状态还是太多，我们发现dfs到一个格子的时候，所有未在棋盘上出现的颜色并无差别，所...
POJ训练记录5
3074.Sudoku数独。。dancinglink经典题[crayon-696727031a63a364270908/]3252.RoundNumbers简单数位dpf(i,j,x,y)表示最高的i位，0比1多j个，是否已小于n，高位是否有1然后转移显然。。。[crayon-696727031a64c444340707/]1665.Biker'sTripOdometer阅读题[crayon-696727031a652351398167/]1930.DeadFraction丧心病狂。。枚举循环节[crayon-696727031a656002056720/]1970.TheGame[crayon-696727031a65a607564831/]1185.炮兵...
CERC 2012 填坑计划(4 / 11)
A-Kingdoms把所有破产状态状压dp[crayon-696727031abf0773103298/]C-Chemist'svows无聊的抄表题。。。[crayon-696727031abfb379830605/]H-Darts模拟题[crayon-696727031ac00914662395/]J-Conservation怀疑数据是不是有问题。。。贪心+拓扑排序[crayon-696727031ac04049590142/] ...
POJ训练记录3
1379.RunAway模拟退火裸题[crayon-696727031b12e479777070/]2758.CheckingtheText暴力+哈希[crayon-696727031b138514146348/]poj3156.Interconnect由于状态是满足拓扑序的，所以直接dp上，再用个hash记忆化[crayon-696727031b13e977989045/]1837.Balancef(i,j)前i个力矩为j的方案,dp[crayon-696727031b144085931233/]3609.ResetSequence状压+bfs初始集合是0-n-1每个指令会使得集合中的一些元素消失，目标状态是只有一个0[c...
CERC 2014 填坑计划(9 / 12)
又是一个深不见底的大坑9/12A.Parades树形dp，dp[x]=∑dp[son]可能还有从一个子树出发，到达另一个子树的路径在每个结点记录在这棵树最优解的情况下去掉覆盖的路径树根能到达的点，这个每次暴力合并每个结点用状压dp配对子树得出最优解[crayon-696727033023d852407536/]C.Sum我傻逼了。。。枚举答案后二分（其实可以直接算）不合法的情况似乎是2的幂[crayon-696727033024c118773665/]D.Wheels模拟[crayon-696727033025116171...
「JoyOI」五月有奖赛 暨Loi 55 Round #1 Day2
抱枕被抢走了QAQ为何ZJ神犇要来虐蒟蒻控油刚捡肥皂[crayon-69672703309ff616571410/]dC和俄罗斯方块我yy了一个奇怪的dp，高精模板太傻了就写了python[crayon-6967270330a0c044689983/]Loi_M的YoGiOh计划（byLoi_imcy）[crayon-6967270330a13409147577/] ...
近期评论