« 上一页下一页 »Current position : 首页 >> 图论 >> 第3页
FJ2016集训 day7
题目来自coolinging（orz）Problem1挑选子序列(sequence.cpp/c/pas)题目来源：原创考察要点：搜索与剪枝、dancinglinks、二分、排序涉及要点：动态规划、随机化算法、贪心解题报告：题目可以理解为在串t中选取m个字母，每个字母覆盖串s1和串s2的部分位置，使串s1和串s2被完全覆盖，求满足如上条件时距离的最小值。对于数据点1，n<=10，T<=10，可以直接枚举选取哪m个字母，简单计算即可。由此可知，对于本题来说，判定比求解...
FJ2016集训 day5
打了个酱油，身败名裂0。01冷战1.1题目大意给定一副N个点的图。动态的往图中加边，并且询问某两个点最早什么时候联通。1.2题解考虑并查集。并查集实际上维护了一棵树。那么假如我们按秩合并，这棵树的深度是O(logn)的。我们将一个点连向其父亲的边权设为这条边加入的时间，那么每次询问时，暴力查询树上从u到v所经过边权的最大值即可。时间复杂度为O(nlogn)，常数较小。假如写了常数较大的可以得到80分。[crayon-67a335cac57121...
「CF685X」Codeforces Round #360 (Div. 1)
A.NP-HardProblem二分图染色[crayon-67a335cac5ea7951710933/]B.RemaindersGame将K分解为a1^p1*a2^p2...an^pn则ai^pi要被c中的某个数整除[crayon-67a335cac5eb1544633710/]C.TheValuesYouCanMake用f(i,j)表示容量i和j的背包能不能同时取得若f(x,K-x)则可以用K中的物品凑出X[crayon-67a335cac5eb6298986032/] ...
2014PKU计算概论入学测试
poj1961Periodkmp求出fail数组后，前i个的重复子串就是i-fail(i)[crayon-67a335cac6347020652006/]poj1276 CashMachine用f(i,j)表示前i种面值，达到j的面值和，所需要的第i种钞票的最少数量[crayon-67a335cac6351628755847/]poj1702 Eva'sBalance先把n转为3进制，若p位为2，就在左盘放3^p，进位若p位为1，就在右盘放3^p[crayon-67a335cac6357156901955/]poj1273 DrainageDitches大名鼎鼎的草地排水，网络流模板[crayon-6...
「NOI考前欢乐赛」[BZOJ3648] 小奇泛舟
「题目背景」微露点滴沾衿落袖丽日绰约轻解莲舟蒹葭荣茂燕雀啁啾白石溪畔斜阳逐流——《白石溪》「问题描述」小奇喜欢在斜阳下的白石溪上泛舟。白石溪风光奇美，名花异石甚多，小奇在地图上标记了n处景观（标号从1到n），有些景观通过溪流连接，这样的溪流有m段。小奇想知道，有多少种泛舟的路径，经过的景观数大于等于K呢？（小奇不喜欢一次泛舟重复经过一个景观）「输入格式」第一行包括3个整数，n，m，K。接下来m行，每行2个整...
树上问题入门
结点、叶结点、分支结点、儿子结点有根树，无根树子孙、祖先、兄弟结点结点的度，结点的层次，树的度，树的深度森林，仙人掌，沙漠树的存储树的遍历结点的父亲，树的深度，树上距离，树的子树大小，树的最大子树，子树的最长链（以子树的根为一个端点，叶为另一个端点），子树最大权，次长链公共祖先，最近公共祖先链的长度树的直径树的重心[crayon-67a335cac754e545676838/] ...
二叉搜索树 / set入门
仅列出纲要二叉树 结点，叶结点，分支结点，结点的度左右孩子 树的深度，大小二叉树类型 满二叉树 完全二叉树 平衡二叉树二叉搜索树性质1.前驱后继2.如何查找？构建1.对已经排序的数快速构建二叉搜索树2.如何顺序插入？效率讨论STL-set顾名思义的操作什么是Iterator？如何遍历set？用法示例[crayon-67a335cae4f9b549166467/] 替罪羊树阅读http://pan.baidu.com/share/link?shareid=318543&a...
「小奇模拟赛2」小奇的危机
「题目背景」小奇驾驶飞船来到了一个奇怪的星球，这个星球的所以城市都在地下，而且由于环境不断恶化，星球上发生了可怕的生化危机。「问题描述」星球上有n个城市，标号为1-n，用n-1条双向通道连接，保证任意两个城市能互相到达。生化危机爆发了！但由于政府安全能力有限，安全区只包括在标号l到r的城市，小奇现在在城市x，它想知道最近的安全城市的距离。「输入格式」第一行有1个整数n。接下来n-1行，每行3个整数u，v，l，表示u，...
「小奇模拟赛2」[BZOJ3784] 小奇的树
![「小奇模拟赛2」[BZOJ3784] 小奇的树](http://hzwer.com/wp-content/themes/ly/image/image_post/2014-12-10_11-24-06.jpg)
「题目背景」小奇在研究树时，遇到了一个难题。「问题描述」给定一棵n个节点的树，求前m条最长路径的长度。「输入格式」第1行2个整数n，m。接下来n-1行，每行3个整数u，v，l，表示u，v之间有一条长度为l的边。「输出格式」m行如题，从大到小输出。「样例输入」42121132143「样例输出」54「数据范围」序号nm数据类型1103暴力223323333暴力32000300000暴力42000300000暴力5500001随机生成6779817798随机生成7779827798随机生成877983...
「CF623X」AIM Tech Round (Div. 1)
A.GraphandString题意n个点，每个点有a,b,c其中一种颜色，若两个点颜色的字母相邻则它们之间连边。给出图的连边情况，求一种可行的染色方案。题解如果有一个点和其它点都有连边，将其标号b。然后选择一个未被标号的点，标号为a，二分图染色。最后验证一下即可。[crayon-67a335cae5f69479901502/]B.ArrayGCD题意给定长为n的数列和两个操作，每个操作用一次1.移除数列的一个子串，代价是长度*a2.对于一些数字+1或者-1，每个数...
「省选模拟赛」小奇的花园
原题：「泉七培训-刘定峰」花园「题目背景」小奇在家中的花园漫步时，总是会思考一些奇怪的问题。「问题描述」小奇的花园有n个温室，标号为1到n，温室以及以及温室间的双向道路形成一棵树。每个温室都种植着一种花，随着季节的变换，温室里的花的种类也在不断发生着变化。小奇想知道从温室x走到温室y的路径中(包括两个端点),第t种花出现的次数。「输入格式」第一行为两个整数n，q，表示温室的数目和操作的数目。第二行有n个整数T1...
「省选模拟赛」[BZOJ1556] 小奇走迷宫
![「省选模拟赛」[BZOJ1556] 小奇走迷宫](http://hzwer.com/wp-content/themes/ly/image/image_post/2014-12-10_13-21-49.jpg)
原题：「bzoj1556」墓地秘密「题目背景」小奇驾驶G-1500机器人探险时落入了一个有魔法的迷宫，一旁的木牌上写着：“你可以回头，但你永远无法离去。”「问题描述」木牌下方有一行小字：“撞击所有机关墙”。G-1500机器人每次可以朝着前方光速移动，质量、动能无穷大，可以选择自己在行进中停下来或者撞墙后停下来，移动时只有转向需要花费时间。真是个诡异的迷宫，不过，小奇的眼前已经出现了迷宫的地图，它想尽早离开这里，请你...
OI 课件=>
近期评论