HihoCoder 1252 Kejin Game

By NodeKey in Graph on

网络流建图神题！！！ 同时也是2015年北京现场赛的金牌题，虽然我不可能去挑战金牌，但是也只有做这种神题，尽管不是自己想得，但A了之后仍然充满了满足。 题意： 给你一个DAG，表示一个游戏的技能树，也就是说某一些技能存在前置技能，但实际上这是为氪金大佬准备的游戏，有钱是真的可以为所欲为的，大佬们可以选择花钱直接无视所有前置技能直接习得某一个技能，也可以消除掉两个技能之间的依赖关系。 现在某个节俭的大佬想要学某一个技能，问最小花费。 思路： 说实话这道题一眼真的很容易想到图上DP，但是存在可以消除一个依赖的权利，使得DP存在后效性。 正解是最小割建模，这个最小割建模真的是非常巧妙： 1. 拆点建图，u -> u’ 的容量是直接氪金习得这一技能的花费 2. 如果u,v存在依赖关系 u -> v ，建边 u’ -> v ，容量为消除这个依赖的费用 3. 将源点与每一个技能连边，容量为按技能树学习的费用。 4. 将所要求的技能与汇点相连，容量为 inf 最后跑一遍最大流就是答案。 网上很多题解到这里就没了，也没有一个像样点的解释。 对于学习技能来说，…

HDU 5556 Land of Farms 附最大团最终模板

By NodeKey in Graph on

一眼以为是状压DP…… 但是仔细读题的话，会有一个致命条件是状压无法解决的。 偷看了一下薛昊的博客，回去路上还跟我说二分图不可能建出来，结果到头来却用HK写这题。 题意： 给你一张图，是矩阵的形式，在满足条件的情况下你要选择尽可能多的格子。 其条件如下 * 如果选中一个格子，这个格子是数字，则相同数字的格子立刻被选中。 * 每个被选中的格子不允许其四个相邻的格子中 存在被选中且与其不同的格子 思路： 实际上这道题的确很想状压，如果把题目中的第一个条件改成，与其选中格子联通且数字相同的格子立马被选中的话，状压可解。但事实并非如此。 其实可以把所有是数字且相同的格子作为一个点，每个 . 也作为一个点，再将其与四周连边，按题意来的话，略加思考，其实就是个最大独立集的裸题。 但是关键还是需要转化出来啊…… 坑点，答案最小为 1 。 AC Code #include #define each(i, n) for (int(i) = 0; (i) < (n); (i)++) #define reach(i,…

Dancing Link X 求精确覆盖与重复覆盖入门

By NodeKey in DLX on

DLX算法入门文……主要说一下我对这个算法的理解。 问题描述 精确覆盖问题： 以矩阵模型介绍，给你一个矩阵，其每个格子的权值范围是 [0,1] ，让你选出若干行，使得选出的行的 1 覆盖了一行的所有格子，且不能有重叠。 重复覆盖问题： 与精确覆盖问题基本相同，但是所选的行集合中，同一列的 1 允许重叠。 这个问题当然不可能让你输出可行方案，输出的应该是行数最小的方案。 算法理解 精确覆盖和重复覆盖都是NP问题，通常的，我们只能通过搜索去解决它。事实上DLX算法也是基于搜索算法。这里放上我的学习博客，里面讲的非常详细，一般人写的博客已然不会超过他。 所以我写这个个人理解其实主要是给自己看的。 首先最容易的当然是 ( 2^{row} ) 的最简单的裸搜，这谁都想得到……而且复杂度很高…… 其实当我们选中一行时，对于这一行的每一个 1 元素，含有与选中行同一列的 1 元素的行自然是不能选的，与此同时对于选中行每一个 1 元素，它所在的列其实我们也已经不再需要去考虑它们，因此，我们可以把这些元素删除，…

第一个Rails半成品的一些经验

By NodeKey in Rails on

简单说就是数据库课设，趁我现在保留着对整个程序的开发过程，这里简单阐述一些过程。 因为以前忘的多了，加上比赛啊，什么的，有点赶，还有两个功能没能实现，不过勉强还是能拿出手 主要学习来源 向作者ihower致敬 顺便在最前面展示一下成果主页 Rails 核心思想 众所周知，Rails 以开发速度闻名，我写完统计了一下代码量，所有代码应该不包含注释也不过 400 行多一点。 而其核心思想在于规定化，也可说是标准化。用一些内置函数去生成代码。 举个例子，在路由(Route)上，根据MVC规则，每一个网址都应该有一条路由与之相对应。rails则使用标准化的RESTful 而因为是函数，所以它的参数都必须与其相对应，所照成的缺陷也很显然，内置函数使用上限不足，完美自定义的网站仍需要自己去架构。为此Rails 也构造了更多的内置函数，为的是提高总体使用上限。当然所造成的结果会是有一些函数的作用重叠。但这并不影响，反而完全符合Ruby的哲学。 Rails 各目录简介 * app/assets 保存着各种样式文件 包括css，js，和一些图片…

CodeForces 855 C Helga Hufflepuff's Cup

By NodeKey in DP on

前几天的上分场的树形DP 我敢说思路和我当时想得已经一模一样了，还有半个多小时的时候，gou bi 带鱼说把题目给他看一下，然后立马得出，树形DP解不了，肯定是树分治！ 当时我在一个子问题上走不出来，于是就信了，然后开始划水…… md 题意： 给你一棵树，要你给树上的每一个节点赋值，赋值存在范围，再给你一个特殊值，除开特殊值意外的数值赋值次数不限，但是特殊值的相邻节点的值不能是特殊值，也不能是比特殊值大的值。 问方案数。 思路： 首先值得注意的是，特殊值赋值次数不超过10，这是一个重要突破口，这使得树形DP的解法存在可能性。 简单说就是在每个节点都保存当前节点为根节点的子树分别含有 [ 0, 10 ] 个特殊值的方案数。 但这还不好决策转移，我们还需要对当前值的范围作为状态进行判断。 我在比赛中只用了，当前值为特殊值，和不是特殊值两个状态，但是现在看了其他人的代码，发现三个状态更容易。 当前节点赋值小于特殊值，大于特殊值，等于特殊值。这样就很好转移，不细说，看代码都能秒懂。 我在比赛时候被卡的子问题是这样的，对于计算当前子树的特殊值数量为 n 的时候…

Rails 使用 carrierwave 上传文件

By NodeKey in Rails on

……崩溃，找了很久的资料，最后找到一份template才解决问题。 carrierwave是一个rails 上传文件的 gem，然而用不来…… 作者在 github 上的文档真的很没有条理性 前言 偶然间看到这篇文章，希望读者也可以多思考一下。 现在框架发展这么迅速，各种api泛滥，我们在寻求解决一个问题的时候，往往会有点急功近利。如果你考虑了底层实现，那你才是真正学到了东西，并能广泛运用它。否则，你顶多只是积累了当前框架或者api的使用经验。换了一个框架你就完全不会了。 但我的确是看完了这篇文章，我也的确去思考了，但是还是不会用！！！ 因为网上很多文章和博客都忽略了一个非常重要的地方，下面我会说明。 这里详细介绍一下 carrierwave 的用法，并假设你已经开了上面那篇文章并思考过了。 安装 首先是安装，在gemfile中输入 gem 'carrierwave', '~> 1.0' 并执行 bundle install carrierwave 实际建立的是 model ，但这里便于区分并且生成的类同时也是 uploader ，输入命令…

计蒜客 Coin 附带矩阵加速模板

By NodeKey in DP on

大概是第5次写矩阵快速幂…… 这道题在DP还是矩阵上都是属于简单范畴……，但没想到用DP就很烦…… 感觉矩阵加速还是挺有必要学一下的…… 顺带学了一下什么叫分数取模用逆元 题意： 让你抛 k 次 硬币，求上面朝上的次数为偶数的概率。 单次正面朝上的概率为 ( \dfrac {q} {p} ) 思路： 令 dp [ n ] [ 0 ] 表示抛了 n 次后，朝上次数为偶数的概率，dp[ n ] [ 1 ] 则表示奇数的概率。 得转移方程 $ dp[n][0] = \dfrac {p-q} {p} \times dp[n-1][0] + \dfrac {q} {p} \times dp[n-1][1] $ $ dp[n][1] = \dfrac…

hihocoder 1513 小Hi的烦恼

By NodeKey in bitset on

别看了……bitset入门题…… bitset就是将32个01位操作整合成一个32位整数，一次位操作。 作为一个位运算的优化方法，可以省去 ( 2^5 )的时间复杂度。 有些大佬 sb 就故意让你 ( O ( n^2 ) )过不了，加个 bitset 优化就可以卡过去了。 不过也可以说是一个很巧妙的操作。 这题是今晚出去撸串的时候听其他三个沙雕吹的一道题，今晚补上。 题意： 给你一群学生每门功课的排名，总共 5 门学科，问你对于每个学生，所有成绩排名都比他高的学生数有多少。 不存在共列一个名次的数据。 思路： 很暴力…… 直接( n^2 ) + bitset 优化就可以卡过 但是不知道为什么，我的循环在 [ 1, n ] 就 T 了，[0, n ) 就 A 了…… #include…