[Top]CTSC&APIO前集训日记

...     阅读全文
WildRage's avatar
WildRage 4月 16, 2018

BZOJ 1426 收集邮票

Description有n种不同的邮票,皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买,每次只能买一张,并且买到的邮票究竟是n种邮票中的哪一种是等概率的,概率均为1/n。但是由于凡凡也很喜欢邮票,所以皮皮购买第k张邮票需要支付k元钱。 现在皮皮手中没有邮票,皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。     阅读全文
WildRage's avatar
WildRage 6月 14, 2017

网络流24题 太空飞行计划

【问题描述】W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E1,E2,…,Em},和进行这些实验需要使用的全部仪器的集合I={ I1, I2,…,In }。实验Ej 需要用到的仪器是I的子集Rj∈I。配置仪器Ik 的费用为ck 美元。实验Ej 的赞助商已同意为该实验结果支付pj 美元。W教授的任务是找出一个有效算法,确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。     阅读全文
WildRage's avatar
WildRage 6月 14, 2017

[COGS 2248] 情书 AC自动机模板

【题目描述】John平静的生活最近有了波澜:他已经连续n天受到陌生人的情书了。小小的心中充满了憧憬,但是某些人觉得有乐子可以找,决定伪造情书。John总结出了那个陌生人写信的习惯,也就是某些关键的字符串。如果一封信中这若干个关键字符串都出现,他就认为这是那个陌生人写的,否则就是他同学的恶作剧。注意,John可能收到多封情书。     阅读全文
WildRage's avatar
WildRage 6月 13, 2017

[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