[BZOJ 4523][Cqoi2016]路由表 Trie树 单调栈

Description路由表查找是路由器在转发IP报文时的重要环节。通常路由表中的表项由目的地址、掩码、下一跳(Next Hop)地址和其他辅助信息组成。例如:当路由器收到一个IP报文时,会将报文中的目的IP地址与路由表中的表项逐条进行比较,选择匹配且最明确的表项,将报文转发给该表项中指定的下一跳。     阅读全文
WildRage's avatar
WildRage 6月 13, 2017

[COGS 2051] 王者之剑 题解 网络流最大权闭合子图

【题目描述】这是在阿尔托利亚·潘德拉贡成为英灵前的事情,她正要去拔出石中剑成为亚瑟王,在这之前她要去收集一些宝石。宝石排列在一个n*m的网格中,每个网格中有一块价值为v(i,j)的宝石,阿尔托利亚·潘德拉贡可以选择自己的起点。开始时刻为0秒。以下操作,每秒按顺序执行1.在第i秒开始的时候,阿尔托利亚·潘德拉贡在方格(x,y)上,她可以拿走(x,y)中的宝石。2.在偶数秒,阿尔托利亚·潘德拉贡周围四格的宝石会消失3.若阿尔托利亚·潘德拉贡第i秒开始时在方格(x,y)上,则在第i+1秒可以立即移动到(x+1,y),(x,y+1),(x-1,y)或(x,y-1)上,也可以停留在(x,y)上。求阿尔托利亚·潘德拉贡最多可以获得多少价值的宝石     阅读全文
WildRage's avatar
WildRage 6月 13, 2017

图库

    阅读全文
WildRage's avatar
WildRage 6月 13, 2017

[BZOJ 1954] The xor-longest Path Trie树 贪心

Description给定一棵n个点的带权树,求树上最长的异或和路径     阅读全文
WildRage's avatar
WildRage 6月 13, 2017

[NOI2000] 单词查找树

[题目描述]在进行文法分析的时候,通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度,通常都要画出与单词列表所对应的单词查找树,其特点如下:     阅读全文
WildRage's avatar
WildRage 6月 13, 2017

POJ 2406 Power Strings 题解 KMP 适配函数

DescriptionGiven two strings a and b we define ab to be their concatenation. For example, if a = “abc” and b = “def” then ab = “abcdef” . If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = “” (the empty string) and a^(n+1) = a*(a^n) .     阅读全文
WildRage's avatar
WildRage 6月 13, 2017

[POJ3461] 乌力波 MP 题解 板子

【题目描述】法国作家乔治·佩雷克(Georges Perec,1936-1982)曾经写过一本书,《敏感字母》(La disparition),全篇没有一个字母‘e’。他是乌力波小组(Oulipo Group)的一员。下面是他书中的一段话:     阅读全文
WildRage's avatar
WildRage 6月 13, 2017

网络流笔记

网络流 是指在一个每条边都有容量(capacity)的有向图分配流,使一条边的流量不会超过它的容量。 最大流DinicDinic算法(又称Dinitz算法)是一个在网络流中计算最大流的强多项式复杂度的算法,设想由以色列(前苏联)的计算机科学家Yefim (Chaim) A. Dinitz在1970年提出。     阅读全文
WildRage's avatar
WildRage 6月 13, 2017