下一页 »Current position : 首页 >> 广度搜索
程序设计实习实验班2017作业（算法 作业1,5）
【Bailian4115】鸣人和佐助bfs的时候多一维记录查克拉[crayon-5972a0ee9d2e0543201440/]【poj1190】生日蛋糕/泰国佛塔从下往上一层一层搜索，每一层枚举半径和高度（注意范围）根据每一层半径和高度严格递减，进行一些剪枝：1、剩下的若干层都放最小的圆柱，体积也不够2、剩下的若干层都放最小的圆柱，得出的表面积比当前最优解劣3、剩下的体积所需的最小表面积加上当前表面积比当前最优解劣[crayon-5972a0ee9d2f1958379101/]【B...
2015程序设计实习实验班免修考试(校内）
【poj1037】decorativefence用f(i,j)表示长度为i，开头为j，开头为上升的序列用g(i,j)表示长度为i，开头为j，开头为下降的序列考虑在序列的第二位放一个数字，改变上升/下降预处理完之后，一位位枚举贪心[crayon-5972a0ee9eec9892545059/]【poj1011】Sticks经典的搜索剪枝1.长度取值范围是木棍的最长长度到长度总和之间。2.长度总和一定可以整除原来的长度。3.从大到小排序搜索。4.某次组合时，如果不能加入某根木棍，同种长度的木...
【cf718X】Codeforces Round #373 (Div. 1)
A.EfimandStrangeGrade给一个长为n的小数，有t次操作，每次可以让小数点后的某一位向前四舍五入问能最终能得到的最大的数题解考虑找到最前的一个大等于5的数字，从其开始考虑四舍五入如果四舍五入到小数点，将小数点去掉最后再处理一下整数位的进位问题[crayon-5972a0ee9f64d007736732/]C.SashaandArray给定一个长度为n的数列an，有两种操作1、将L到R的加上X2、询问\(\sum_{L\leqi\leqR}F(a_i)\)题解考虑在线段树的每...
【NOI考前欢乐赛】小奇画画
【题目背景】红莲清泪两行欲吐半点却无如初是你杳然若绯雾还在水榭畔画楼处是谁衣白衫如初谁红裳如故——《忆红莲》【问题描述】小奇想画几朵红莲，可惜它刚开始学画画，只能从画圆开始。小奇画了n个圆，它们的圆心都在x轴上，且两两不相交（可以相切）。现在小奇想知道，它画的圆把画纸分割成了多少块？（假设画纸无限大）【输入格式】第一行包括1个整数n。接下来n行，每行两个整数x，r，表示小奇画了圆心在（x，0），半径为r的一...
【tyvj1520】树的直径
描述Description树的直径，即这棵树中距离最远的两个结点的距离。每两个相邻的结点的距离为1，即父亲结点与儿子结点或儿子结点与父子结点之间的距离为1.有趣的是，从树的任意一个结点a出发，走到距离最远的结点b，再从结点b出发，能够走的最远距离，就是树的直径。树中相邻两个结点的距离为1。你的任务是：给定一棵树，求这棵树中距离最远的两个结点的距离。输入格式InputFormat输入共n行第一行是一个正整数n，表示这棵树的结点...
【codevs1004】四子连棋
题目描述 Description在一个4*4的棋盘上摆放了14颗棋子，其中有7颗白色棋子，7颗黑色棋子，有两个空白地带，任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格，这叫行棋一步，黑白双方交替走棋，任意一方可以先走，如果某个时刻使得任意一种颜色的棋子形成四个一线（包括斜线），这样的状态为目标棋局。●○●○●○●●○●○○●○ 输入描述 InputDescription[crayon-5972a0eea08ff711130178/]输出描述 Ou...
【cf666X】 Codeforces Round #349 (Div. 1)
A.ReberlandLinguistics此题最重要的是理解题意！！！英语渣伤不起给定一个字符串，先去掉一个长度至少为5的前缀，要求把剩下的字符串划分成长度为2或3的串，这些串相邻之间不能完全相同，问可能有哪些长度为2或3的串看错题意就写了个哈希+搜索一直wa，后来领悟了就没另起炉灶，改成了牵强的记搜大概和dp差不多意思，f[i][0/1]表示前i个字符，最后一个串长度为2/3是否可行，转移显然。。。[crayon-5972a0eea0d9b022653301/]B.W...
【省选模拟赛】小奇挖矿 3
原题：【泉七培训-刘定峰】物流【题目背景】小奇在喵星系使用了无限非概率驱动的采矿机，以至于在所有星球上都采出了一些矿石，现在它准备建一些矿石仓库并把矿石运到各个仓库里。【问题描述】喵星系有n个星球，标号为1到n，星球以及星球间的航线形成一棵树。所有星球间的双向航线的长度都为1。小奇要在若干个星球建矿石仓库，设立每个仓库的费用为K。对于未设立矿石仓库的星球，设其到一个仓库的距离为i，则将矿石运回的费用为D...
【cf235X】Codeforces Round #146 (Div. 1)
A.LCMChallenge显然是在接近n数内找三个两两互质的，由于懒得推公式所以可以小范围暴力一下[crayon-5972a0eea162a712079725/]B.Let'sPlayOsu!计算出到每个位置的期望连续长度就可以得到如果该位置正确的期望得分，就可以dp辣[crayon-5972a0eea1632584722872/]C.CyclicalQuest一道很正经的后缀自动机建出s串的后缀自动机把xi复制一遍接在后面，然后在s串上匹配，就可以得出后缀自动机上贡献答案的结点[crayon-5972a0eea...
pkusc 2013 #2
A:TheSettlersofCatan枚举起点dfs[crayon-5972a0eea1c21197738373/]B:Nim傻逼记忆化搜索我竟然清空错数组QAQ[crayon-5972a0eea1c2b260483112/]C:TraditionalBINGO纯阅读题[crayon-5972a0eea1c30081978486/]D:TraditionalBINGO排序后广搜更新每个点能到达的最高点。。。一通乱搞感觉并查集也可以就是很麻烦？[crayon-5972a0eea1c35153756470/] ...
poj训练记录3
1379.RunAway模拟退火裸题[crayon-5972a0eeb7356162399592/]2758.CheckingtheText暴力+哈希[crayon-5972a0eeb7366299689502/]poj3156.Interconnect由于状态是满足拓扑序的，所以直接dp上，再用个hash记忆化[crayon-5972a0eeb736c622230114/]1837.Balancef(i,j)前i个力矩为j的方案,dp[crayon-5972a0eeb7372976860317/]3609.ResetSequence状压+bfs初始集合是0-n-1每个指令会使得集合中的一些元素消失，目标状态是只有一个0[c...
【cf507X】Codeforces Round #287 (Div. 2)
A.AmrandMusic排序贪心[crayon-5972a0eeb7df7733085675/]B.AmrandPins算出距离除以直径[crayon-5972a0eeb7e07354438574/]C.GuessYourWayOut!按位考虑[crayon-5972a0eeb7e0e149252669/]D.TheMathsLecture从后往前dpf(i,j,k)表示后i位，当前模为j，是否有后缀被K整除[crayon-5972a0eeb7e15800959866/]E.BreakingGood广搜，选可用边最多的路径[crayon-5972a0eeb7e21530225787/] ...
【cf543X】Codeforces Round #302 (Div. 1)
本场血崩A.WritingCode显然的n^3dp，滚动数组[crayon-5972a0eeb8474157400143/]B.DestroyingRoadsn个结点,m条边的无向图(边权全为1),问最多能删掉多少条边使得s1到t1距离不超过l1,s2到t2距离不超过l2。\(1\leqn\leq500,1\leqm\leqn(n-1)/2\)题解其实就是问，至少需要多少条边，才能使得s1到t1距离不超过l1,s2到t2距离不超过l2。如果这两条路径不相交，那么答案为dis(s1,t1)+dis(s2,t2)。如果相交部分为(p1,p2)，答案为p1,p2的...
近期评论