7月 15 2018
Categories: 题解 Tags:

...

6月 29 2018
Categories: 题解 Tags: 2-SAT

题目描述 ...

5月 16 2018
Categories: 随笔 Tags: 日记

... ...

5月 15 2018
Categories: 随笔 Tags: 日记

结束了从来到... ...

4月 21 2018
Categories: 题解 Tags: FWT, 交互, 数学

Scape下载了好久终于下完了关于量子巧克力的游戏——Quantum break,准备邀请Mythological来享受在一起的时光。可是谁知道积劳... ...

4月 20 2018
Categories: 笔记 Tags: 数学

在求组合数的时候, 我们可能遇到模数是非质数的情况, 这时正常的Lucas可能无法解决问题。 所以我们要用到扩展Lucas定理 我... ...

4月 16 2018
Categories: 随笔 Tags: 日记

... ...

4月 13 2018
4月 12 2018
Categories: 题解 Tags: DP

题目描述 ...

4月 12 2018
4月 11 2018
Categories: 题解 Tags: DP

题目描述 ...

4月 11 2018
Categories: 题解 Tags: DP

题目描述 ...

3月 24 2018
3月 24 2018
3月 24 2018
Categories: 题解 Tags: 数论

...

3月 19 2018
Categories: 随笔 Tags: 日记

...

3月 19 2018
Categories: 题解 Tags: DP

...

3月 09 2018
Categories: 题解 Tags: 半平面交

题目描述 ...

3月 06 2018
Categories: 题解 Tags: 群论

...

3月 05 2018
Categories: 题解 Tags: 群论

...

3月 01 2018
Categories: 题解 Tags: FFT&NTT, 生成函数

在你的帮助下,跳蚤国王终于打开了最后一间房间的大门。然而,picks 博士和他的猴子们早已通过地道逃跑了。万幸的是,因为阿姆斯特朗回旋加速喷气式阿姆... ...

2月 28 2018
Categories: 题解 Tags: CDQ, FFT&NTT, 生成函数

著名核物理专家 Picks 最近发现了一种非常适合核裂变的元素叫囧元素。囧元素原子序数为 1024,囧-2333 如果被一个中子撞击后会分裂成 蒟-... ...

2月 26 2018
2月 26 2018
2月 26 2018
Categories: 题解 Tags: FFT&NTT, 生成函数

...

2月 26 2018
2月 25 2018
Categories: 题解 Tags: FFT&NTT

...

1月 18 2018
1月 18 2018
1月 16 2018
1月 16 2018
Categories: 笔记 Tags: 网络流

无源汇可行... ...

1月 01 2018
Categories: Tags:

...

12月 14 2017
11月 11 2017
Categories: 随笔 Tags: 日记

2017-11-9 明天就出发了,还有不少东西没有复习,心里好虚啊。觉得自己什么都不会, 不知道怎么办。很压... ...

10月 30 2017
Categories: 题解 Tags: 概率DP, 状压DP

转载自 Cooook ...

10月 29 2017
10月 28 2017
Categories: 题解 Tags: 树DP

题目描述 ...

10月 25 2017
Categories: 题解 Tags: CDQ

题目描述 ...

10月 21 2017
10月 21 2017
Categories: 题解 Tags: 状压DP

...

10月 10 2017
Categories: 题解 Tags: 模拟

概述 《猪国杀》是一种多猪牌类回合制游戏,一共有三种角色:主猪,忠猪,反猪。 每局游戏主猪有且只有一只,忠猪和反猪可以有多只,每只猪扮演一种角色。 ...

10月 01 2017
Categories: 随笔 Tags: 日记

2017 - 10 - 1 Day1 ...

9月 26 2017
Categories: 知识点 Tags: 后缀数组

后缀数组详解 请参见 IOI2009 国家集训队论文 ...

9月 24 2017
Categories: 题解 Tags: Treap

题目描述话说有一天doyouloveme和vfleaking到山里玩。谁知doyouloveme刚刚进山,所有的鸟儿竟被他的神犇气场给惊得全部飞走了。vfleaking顿时膜拜不已。这时鸟王用鸟语说道:“!@#$%……?”安抚了一下众鸟的情绪。鸟王生性好斗,作出了一个决定——要排鸟布阵把刚才吓到它们的人类赶出山去。 ...

9月 19 2017
Categories: 题解 Tags: 线段树

Description ...

9月 17 2017
Categories: 题解 Tags: DFS

题目描述贝希和她的闺密们在她们的牛棚中玩游戏。但是天不从人愿,突然,牛棚的电源跳闸了,所有的灯都被关闭了。贝希是一个很胆小的女生,在伸手不见拇指的无尽的黑暗中,她感到惊恐,痛苦与绝望。她希望您能够帮帮她,把所有的灯都给重新开起来!她才能继续快乐地跟她的闺密们继续玩游戏! ...

9月 17 2017
Categories: 题解 Tags: DFS

题目描述所谓虫食算,就是原先的算式中有一部分被虫子啃掉了,需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子: ...

9月 15 2017
Categories: 题解 Tags: DP

3.1 描述一棵k-超级树可按如下方法得到:取一棵深度为k的满二叉树,对每个节点,向它的所有祖先连边(如果这条边不存在的话)。例如,下图是一个4-超级树的例子: ...

8月 22 2017
Categories: 题解 Tags: 二分图匹配

题目描述  小Q是一个非常聪明的孩子,除了国际象棋,他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N*N黑白方阵进行(如同国际象棋一般,只是颜色是随意的)。每次可以对该矩阵进行两种操作:行交换操作:选择矩阵的任意两行,交换这两行(即交换对应格子的颜色)列交换操作:选择矩阵的任意行列,交换这两列(即交换对应格子的颜色) ...

8月 22 2017
Categories: 题解 Tags: Tarjan

题目描述煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。请写一个程序,用来计算至少需要设置几个救援出口,以及不同最少救援出口的设置方案总数。 ...

8月 22 2017
Categories: 题解 Tags: SPFA

题目描述为了得到书法大家的真传,小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图,节点标号为1..N,边标号为1..M。初始时小E同学在号节点1,隐士则住在号节点N。小E需要通过这一片魔法森林,才能够拜访到隐士。 ...

8月 21 2017
Categories: 随笔 Tags:

生日有感 ...

8月 15 2017
Categories: 题解 Tags: LCA

题目描述 ...

8月 15 2017
Categories: 题解 Tags: 乱搞, 模拟

题目描述 ...

8月 15 2017
Categories: 题解 Tags: DP

题目描述 ...

8月 15 2017
Categories: 题解 Tags: 并查集

题目描述给出一个R*C的棋盘.共有R行C列,R*C个格子.现要在每个格子都填一个非负整数.使得任意一个2*2的正方形区域都满足这样的性质:左上角的数字+右下角的数字=左下角的数字+右上角的数字.有些格子已经确定,你不能更改其中的数字.其他格子的数字由你决定.这是一个符合要求的3*3的棋盘: ...

8月 15 2017
Categories: 题解 Tags: 区间DP, 状压DP

题目描述有一个长度为 n 的 01 串,你可以每次将相邻的 k 个字符合并,得到一个新的字符并获得一定分数。得到的新字符和分数由这 k 个字符确定。你需要求出你能获得的最大分数。 ...

8月 14 2017
Categories: 题解 Tags: FFT

1.Why为什么我们信息学竞赛要用到FFT因为我们要优化卷积啊将n边为log是一个非常大的优化啊 ...

8月 14 2017
Categories: 题解 Tags: 莫比乌斯反演

Description有一张N×m的数表,其第i行第j列(1 < =i < =N,1 < =j < =m)的数值为能同时整除i和j的所有自然数之和。给定a,计算数表中不大于a的数之和。 ...

8月 13 2017
Categories: 题解 Tags: 莫比乌斯反演

【题目描述】给定n,m,k,计算 $\sum_{i=1}^{n}{\sum_{j=1}^{m}{gcd(i,j)^k}}$ 对1000000007取模的结果 ...

8月 13 2017
Categories: 题解 Tags: 数学

Description ...

8月 12 2017
Categories: 题解 Tags: 数学

Description给定一个nxm的网格,请计算三点都在格点上的三角形共有多少个。下图为4x4的网格上的一个三角形。注意三角形的三点不能共线。 ...

8月 12 2017
Categories: 题解 Tags: 乱搞

...

8月 12 2017
Categories: 题解 Tags: 组合

...

8月 12 2017
Categories: 题解 Tags: 乱搞

...

8月 10 2017
Categories: 题解 Tags: 二维SPFA

题目描述Alice和Bob现在要乘飞机旅行,他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务,设这些城市分别标记为0到n-1,一共有m种航线,每种航线连接两个城市,并且航线有一定的价格。 ...

8月 10 2017
Categories: 题解 Tags: 暴力

...

8月 10 2017
Categories: 题解 Tags: 分块

题目描述由于 Wulala 在上个问题中的精彩表现,公主认为 Wulala 是一个很棒的人,就把 Wulala 留在了 X 国。这时正好公主的一位传教士朋友来拜访公主,于是想找 wulala 帮忙X 国如同一条直线,其中有 n 个城市,从东向西分别编号为 1~n。而他的国家中有 m 种宗教,每个城市一定会有一种信仰的宗教。 ...

8月 10 2017
Categories: 题解 Tags: 树DP

题目描述繁华中学有一棵苹果树。苹果树有 n 个节点(也就是苹果),n − 1 条边(也就是树枝)。调皮的 Evensgn 爬到苹果树上。他发现这棵苹果树上的苹果有两种:一种是黑苹果,一种是红苹果。Evensgn 想要剪掉 k 条树枝,将整棵树分成 k + 1 个部分。他想要保证每个部分里面有且仅有一个黑苹果。请问他一共有多少种剪树枝的方案? ...

8月 09 2017
Categories: 题解 Tags: hash

题目描述蚯蚓幼儿园有nnn只蚯蚓。幼儿园园长神刀手为了管理方便,时常让这些蚯蚓们列队表演。 ...

8月 09 2017
Categories: 题解 Tags: 主席树

Description数集S的ForbiddenSum定义为无法用S的某个子集(可以为空)的和表示的最小的非负整数。例如,S={1,1,3,7},则它的子集和中包含0(S’=∅),1(S’={1}),2(S’={1,1}),3(S’={3}),4(S’={1,3}),5(S’ = {1, 1, 3}),但是它无法得到6。因此S的ForbiddenSum为6。给定一个序列A,你的任务是回答该数列的一些子区间所形成的数集的ForbiddenSum是多少。 ...

8月 09 2017
Categories: 题解 Tags: 乱搞

3.1 题目描述一个长度为n 的排列p[1..n]把排列的每个循环拿出来,写成标准循环,再做一次排序比如[4, 1, 6, 2, 5, 3],有3 个循环(421)(63)(5)其中第一个循环就是4 要到2 的位置,2 要到1 的位置,1 要到4 的位置 ...

8月 09 2017
Categories: 题解 Tags: 可持久化Trie树

2.1 题目描述Mavis 有一个序列(不必在乎这些细节),对于每个数都有一个在序列中的优美值,这个优美值的定义是:找到序列中最长的一段,满足包含这个数并且这个数是这一段的中位数(以数值为第一关键字,下标为第二关键字排序, 这样的话这一段的长度只有可能是奇数),那么这一 ...

8月 09 2017
Categories: 题解 Tags: 树状数组

1.1 题目描述给定一个序列a,a 中任意两个元素都不等。如果i<j, 且a[i]<a[j],则我们称a[i],a[j] 为一个顺序对,这个顺序对的值是指a[i+1],a[i+2]…….a[j-1] 中比a[i] 大,且比a[j] 小的数的个数。求一个序列中所有顺序对的值的和。 ...

8月 08 2017
Categories: 题解 Tags: 乱搞

题目描述作为一名新世纪共产主义的接班人,你认识到了资本主义的软弱性与妥协性,决定全面根除资本主义,跑步迈入共产主义。但是当你即将跨入共产主义大门的时候,遇到了万恶的资本家留下的与非电路封印,经过千辛万苦的研究,你终于把复杂的破解转变成了以下问题: ...

8月 08 2017
Categories: 题解 Tags: 无旋Treap

题目描述一个排列,求出了 a 数组,其中 ai 表示第 i 个数左边有多少个数比它小 计算出原来的排列 ...

8月 08 2017
Categories: 题解 Tags: 乱搞

题目描述Evensgn 有一群好朋友,他们经常互相借钱。假如说有三个好朋友 A,B,C。 A 欠 B 20 元,B 欠 C 20 元,总债务规模为 20+20=40 元。Evensgn 是个追求简约 ...

8月 08 2017
Categories: 题解 Tags: 插头DP

先来一个最入门的HDU 1693 哈密顿回路 多回路 Problem DescriptionMost of us know that in the game called DotA(Defense of the Ancient), Pudge is a strong hero in the first period of the game. When the game goes to end however, Pudge is not a strong hero any more.So Pudge’s teammates give him a new assignment—Eat the Trees! ...

8月 08 2017
Categories: 题解 Tags: 概率DP

题目描述Hazel有n本书,编号1为n到 ,叠成一堆。当她每次抽出一本书的时候,上方的书会因重力而下落,这本被取出的书则会被放置在书堆顶。每次有pi的概率抽取编号为i的书。她每次抽书所消耗的体力与这本书在这堆中是第几本成正比。具体地,抽取堆顶的书所耗费体力值为1 ,抽取第二本耗费体力值为2 ,以此类推。 ...

8月 08 2017
Categories: 题解 Tags: 贪心

【背景描述】一排 N 个数, 第 i 个数是 Ai , 你要找出 K 个不相邻的数, 使得他们的和最大。请求出这个最大和。 ...

8月 08 2017
Categories: 题解 Tags: hash

题目描述你来到了一个庙前,庙牌上有一个仅包含小写字母的字符串 s。传说打开庙门的密码是这个字符串的一个子串 t,并且 t 既是 s 的前缀又是 s 的后缀并且还在 s 的中间位置出现过一次。 ...

8月 07 2017
Categories: 笔记 Tags: KD-Tree

维护K维的... ...

8月 06 2017
Categories: 知识点 Tags: 计算几何

1.什么是计算几何维基百科计算几何 计算几何是一门兴起于二十世纪七十年代末的计算机科学的一个分支,主要研究解决几何问题的算法。 ...

8月 06 2017
Categories: 题解 Tags: 状压DP

问题描述莫莉斯·乔是圣域里一个叱咤风云的人物,他凭借着自身超强的经济头脑,牢牢控制了圣域的石油市场。 圣域的地图可以看成是一个n*m的矩阵。每个整数坐标点(x , y)表示一座城市(1<=x<= n, 1<=y<=m)。两座城市间相邻的定义为:对于城市$(A_x, A_y)$和城市$(B_x, B_y)$,满足$(A_x - B_x)^2 + (A_y - B_y)^2 = 1$。由于圣域的石油贸易总量很大,莫莉斯意识到不能让每笔石油订购单都从同一个油库里发货。为了提高效率,莫莉斯·乔决定在其中一些城市里建造油库,最终使得每一个城市X都满足下列条件之一: ...

8月 06 2017
Categories: 题解 Tags: DP

【题目描述】一年一度的星哥选美又拉开了帷幕 N个人报名参加选拔,每个人都有着各自的相貌参数和身材参数(不大于 10000 的正整数)。你的任务是尽可能让更多人被星哥选中,而唯一要求就是,在这只队伍里面的每个人,都需满足以下不等式: ...

8月 06 2017
Categories: 题解 Tags: BFS

题目描述两头白天鹅生活在一个部分湖面结了冰的湖泊中,湖面的形状为一个长方形,并且被分割成R行C列的小方格,某些方格中结了冰,这样的方格称之为冰格,其余的方格称之为水格。冬天过去了,湖面上的冰渐渐开始溶解了,每一天与水相邻的冰格就将消融而转化为水格。所谓两个方格相邻是指它们在水平或垂直方向有公共边,两个呈对角的方格是不相邻的,下图给出样例数据的演化过程。 ...

8月 05 2017
Categories: 题解 Tags: 可持久化Trie树

DescriptionWelcome to ALO ( Arithmetic and Logistic Online)。这是一个VR MMORPG ,如名字所见,到处充满了数学的谜题。现在你拥有n颗宝石,每颗宝石有一个能量密度,记为ai,这些宝石的能量密度两两不同。现在你可以选取连续的一些宝石(必须多于一个)进行融合,设为 ai, ai+1, …, a j,则融合而成的宝石的能量密度为这些宝石中能量密度的次大值 ...

8月 05 2017
Categories: 题解 Tags: 矩阵乘

Description 农夫栋栋近年收入不景气,正在他发愁如何能多赚点钱时,他听到隔壁的小朋友在讨论兔子繁殖的问题。问题是这样的:第一个月初有一对刚出生的小兔子,经过两个月长大后,这对兔子从第三个月开始,每个月初生一对小兔子。新出生的小兔子生长两个月后又能每个月生出一对小兔子。问第n个月有多少只兔子? ...

8月 05 2017
Categories: 题解 Tags: 二分

【问题描述】小 T 是一名质量监督员,最近负责检验一批矿产的质量。这批矿产共有n个矿石,从 1 到n逐一编号,每个矿石都有自己的重量$w_i$以及价值$v_i$。检验矿产的流程是: ...

8月 03 2017
Categories: 题解 Tags: 贪心

Description有n个人,每个人手里有一把手枪。一开始所有人都选定一个人瞄准(有可能瞄准自己)。然后他们按某个顺序开枪,且任意时刻只有一个人开枪。因此,对于不同的开枪顺序,最后死的人也不同。 ...

8月 03 2017
Categories: 题解 Tags: 暴力

DescriptionFarmer John knows that an intellectually satisfied cow is a happy cow who will give more milk. He has arranged a brainy activity for cows in which they manipulate an M x N grid (1 <= M <= 15; 1 <= N <= 15) of square tiles, each of which is colored black on one side and white on the other side. As one would guess, when a single white tile is flipped, it changes to black; ...

8月 03 2017
Categories: 题解 Tags: DP

DescriptionFJ打算好好修一下农场中某条凹凸不平的土路。按奶牛们的要求,修好后的路面高度应当单调上升或单调下降,也就是说,高度上升与高度下降的路段不能同时出现在修好的路中。 整条路被分成了N段,N个整数A_1, … , A_N (1 <= N <= 2,000)依次描述了每一段路的高度(0 <= A_i <= 1,000,000,000)。FJ希望找到一个恰好含N个元素的不上升或不下降序列B_1, … , B_N,作为修过的路中每个路段的高度。由于将每一段路垫高或挖低一个单位的花费相同,修路的总支出可以表示为:$ |A_1 - B_1| + |A_2 - B_2| + … + |A_N - B_N| $请你计算一下,FJ在这项工程上的最小支出是多少。FJ向你保证,这个支出不会超过2^31-1。 ...

8月 03 2017
Categories: 题解 Tags: 树贪心

DescriptionIn a village called Byteville, there are houses connected with N-1 roads. For each pair of houses, there is a unique way to get from one to another. The houses are numbered from 1 to . The house no. 1 belongs to the village administrator Byteasar. As part of enabling modern technologies for rural areas framework, computers have been delivered to Byteasar’s house. Every house is to be supplied with a computer, and it is Byteasar’s task to distribute them. The citizens of Byteville have already agreed to play the most recent version of FarmCraft (the game) as soon as they have their computers. ...

8月 03 2017
Categories: 题解 Tags: 概率DP

Description小Q同学现在沉迷炉石传说不能自拔。他发现一张名为克苏恩的牌很不公平。如果你不玩炉石传说,不必担心,小Q同学会告诉你所有相关的细节。炉石传说是这样的一个游戏,每个玩家拥有一个 30 点血量的英雄,并且可以用牌召唤至多 7 个随从帮助玩家攻击对手,其中每个随从也拥有自己的血量和攻击力。小Q同学有很多次游戏失败都是因为对手使用了克苏恩这张牌,所以他想找到一些方法来抵御克苏恩。他去求助职业炉石传说玩家椎名真白,真白 ...

8月 03 2017
Categories: 题解 Tags: DFS

Description牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的A到K加上大小王的共54张牌来进行的扑克牌游戏。在斗地主中,牌的大小关系根据牌的数码表示如下:3\<4\<5\<6\<7\<8\<9\<10\<J\<Q\<K\<A\<2\<小王\<大王,而花色并不对牌的大小产生影响。每一局游戏中,一副手牌由n张牌组成。游戏者每次可以根据规定的牌型进行出牌,首先打光自己的手牌一方取得游戏的胜利。现在,牛牛只想知道,对于自己的若干组手牌,分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。需要注意的是,本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。具体规则如下: ...

8月 03 2017
Categories: 题解 Tags: 可持久化, 线段树

Description给定一棵N个节点的树,每个点有一个权值,对于M个询问(u,v,k),你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案,初始为0,即第一个询问的u是明文。 ...

8月 03 2017
Categories: 题解 Tags: 欧拉定理, 矩阵乘

DescriptionRivest是密码学专家。近日他正在研究一种数列E = {E[1],E[2],……,E[n]},且E[1] = E[2] = p(p为一个质数),E[i] = E[i-2]*E[i-1] (若2<i<=n)。 ...

8月 03 2017
Categories: 题解 Tags: 可持久化, 线段树

Description给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1),并且,你可以改变一些a[i]的值,改变后,程序还能针对改变后的a继续回答上面的问题。 ...

8月 02 2017
Categories: 题解 Tags: Trie, 可持久化

简单题面求区间第k小 COGS 1534 == 930 找第k小的数本来是主席树或树套树的题然而 可持久化Trie树 可以过 ...

7月 30 2017
Categories: 题解 Tags: 博弈论

Problem Descriptiondingyeye loves play stone game with you. dingyeye has an n-point tree.The nodes are numbered from 0 to n−1,while the root is numbered 0.Initially,there are a[i] stones on the i-th node.The game is in turns.When one move,he can choose a node and move some(this number cannot be 0) of the stones on it to its father.One loses the game if he can’t do anything when he moves. ...

7月 30 2017
Categories: 题解 Tags: 博弈论

DescriptionGeorgia and Bob decide to play a self-invented game. They draw a row of grids on paper, number the grids from left to right by 1, 2, 3, …, and place N chessmen on different grids, as shown in the following figure for example: ...

7月 30 2017
Categories: 题解 Tags: 费用流

Description ...

7月 30 2017
Categories: 题解 Tags: 网络流

【问题描述】飞行大队有若干个来自各地的驾驶员,专门驾驶一种型号的飞机,这种飞机每架有两个驾驶员,需一个正驾驶员和一个副驾驶员。由于种种原因,例如相互配合的问题,有些驾驶员不能在同一架飞机上飞行,问如何搭配驾驶员才能使出航的飞机最多。 ...

7月 30 2017
Categories: 题解 Tags: 费用流

【问题描述】 一个餐厅在相继的N天里,第i天需要Ri块餐巾(i=l,2,…,N)。餐厅可以从三种途径获得餐巾。 购买新的餐巾,每块需p分; 把用过的餐巾送到快洗部,洗一块需m天,费用需f分(f<p)。如m=l时,第一天送到快洗部的餐巾第二天就可以使用了,送慢洗的情况也如此。 ...

7月 30 2017
Categories: 题解 Tags:

题目描述Czy找到宝藏获得屠龙宝刀和神秘秘籍!现在他要去找经常ntr他的Jmars报仇…… Czy学会了一招“堕天一击”,他对一个地点发动堕天一击,地面上就会留下一个很大的圆坑。圆坑的周围一圈能量太过庞大,因此无法通过。所以每次czy发动技能都会把地面分割。Jmars拥有好大好大的土地,几十眼都望不到头,所以可以假设土地的大小是无限大。现在czy对他发动了猛烈的攻击,他想知道在泽宇攻击之后他的土地被切成几份了? ...

7月 30 2017
Categories: 题解 Tags: 最小生成树

题目描述Czy爬上黑红树,到达了一个奇怪的地方…… Czy发现了一张奇怪的藏宝图。图上有n个点,m条无向边。已经标出了图中两两之间距离dist。但是czy知道,只有当图刚好又是一颗树的时候,这张藏宝图才是真的。如果藏宝图是真的,那么经过点x的边的边权平均数最大的那个x是藏着宝物的地方。请计算这是不是真的藏宝图,如果是真的藏宝之处在哪里。 ...

7月 30 2017
Categories: 题解 Tags: 概率DP

题目描述Mz们在czy的生日送他一个黑红树种子……czy种下种子,结果种子很快就长得飞快,它的枝干伸入空中看不见了…… Czy发现黑红树具有一些独特的性质。 这是二叉树,除根节点外每个节点都有红与黑之间的一种颜色。 每个节点的两个儿子节点都被染成恰好一个红色一个黑色。 这棵树你是望不到头的(树的深度可以到无限大) ...

7月 27 2017
Categories: 题解 Tags: DP, 矩阵乘

Description有M个球,一开始每个球均有一个初始标号,标号范围为1~N且为整数,标号为i的球有ai个,并保证Σai = M。每次操作等概率取出一个球(即取出每个球的概率均为1/M),若这个球标号为k(k < N),则将它重新标号为k + 1;若这个球标号为N,则将其重标号为1。(取出球后并不将其丢弃)现在你需要求出,经过K次这样的操作后,每个标号的球的期望个数。 ...

7月 27 2017
Categories: 题解 Tags: BFS

【问题描述】Mayan puzzle 是最近流行起来的一个游戏。游戏界面是一个7 行5 列的棋盘,上面堆放着一些方块,方块不能悬空堆放,即方块必须放在最下面一行,或者放在其他方块之上。游戏通关是指在规定的步数内消除所有的方块,消除方块的规则如下: ...

7月 27 2017
Categories: 题解 Tags: DP, 权值树状数组

Description给出N个正整数a[1..N],再给出K个关系符号(>、<或=)s[1..k]。选出一个长度为L的子序列(不要求连续),要求这个子序列的第i项和第i+1项的的大小关系为s[(i-1)mod K+1]。求出L的最大值。 ...

7月 27 2017
Categories: 题解 Tags: Tarjan

Description一位冷血的杀手潜入 Na-wiat,并假装成平民。警察希望能在 N 个人里面,查出谁是杀手。警察能够对每一个人进行查证,假如查证的对象是平民,他会告诉警察,他认识的人, 谁是杀手, 谁是平民。 假如查证的对象是杀手, 杀手将会把警察干掉。现在警察掌握了每一个人认识谁。每一个人都有可能是杀手,可看作他们是杀手的概率是相同的。问:根据最优的情况,保证警察自身安全并知道谁是杀手的概率最大是多少? ...

7月 26 2017
Categories: 题解 Tags: CDQ

【题目描述】摩尔瓦多的移动电话公司摩基亚(Mokia)设计出了一种新的用户定位系统。和其他的定位系统一样,它能够迅速回答任何形如“用户C的位置在哪?”的问题,精确到毫米。但其真正高科技之处在于,它能够回答形如“给定区域内有多少名用户?”的问题。 ...

7月 26 2017
Categories: 题解 Tags: 贪心

【题目描述】在焦作太行路上,有一家烤鸡翅的生意火爆。因为好吃,所以卖的特别好。排队的人就特别多,经常有很多人买不到鸡翅。鸡翅会在每分钟烤出Xi个,每分钟也只会卖给一个客人,第i个客人需要买Yi个。因为生意火爆,老板可以选择在这分钟不卖给这个客人鸡翅,或者卖给这个顾客他需要的鸡翅, 如果现在剩余的鸡翅不够,那就肯定不能卖给这个客人。无论这个客人能否买到鸡翅,他必须离开队伍。现在给定N分钟,且已经知道每分钟烤出的鸡翅个数Xi,也知道每个客人需要鸡翅的Yi个数,现在老板想知道,如何合理安排卖给与拒绝,最多可以满足多少人 ...

7月 26 2017
Categories: 题解 Tags: 位运算, 其他

Description21 世纪,许多人得了一种奇怪的病:起床困难综合症,其临床表现为:起床难,起床后精神不佳。作为一名青春阳光好少年,atm 一直坚持与起床困难综合症作斗争。通过研究相关文献,他找到了该病的发病原因:在深邃的太平洋海底中,出现了一条名为 drd 的巨龙,它掌握着睡眠之精髓,能随意延长大家的睡眠时间。正是由于 drd 的活动,起床困难综合症愈演愈烈,以惊人的速度在世界上传播。为了彻底消灭这种病,atm 决定前往海底,消灭这条恶龙。历经千辛万苦,atm 终于来到了 drd 所在的地方,准备与其展开艰苦卓绝的战斗。drd 有着十分特殊的技能,他的防御战线能够使用一定的运算来改变他受到的伤害。具体说来,drd 的防御战线由 n扇防御门组成。每扇防御门包括一个运算op和一个参数t,其中运算一定是OR,XOR,AND中的一种,参数则一定为非负整数。如果还未通过防御门时攻击力为x,则其通过这扇防御门后攻击力将变为x op t。最终drd 受到的伤害为对方初始攻击力x依次经过所有n扇防御门后转变得到的攻击力。由于atm水平有限,他的初始攻击力只能为0到m之间的一个整数(即他的初始攻击力只能在0,1,…,m中任选,但在通过防御门之后的攻击力不受 m的限制)。为了节省体力,他希望通过选择合适的初始攻击力使得他的攻击能让 drd 受到最大的伤害,请你帮他计算一下,他的一次攻击最多能使 drd 受到多少伤害。 ...

7月 26 2017
Categories: 题解 Tags: Treap, 其他

【题目描述】Treap是一种平衡二叉搜索树,除二叉搜索树的基本性质外,Treap还满足一个性质:每个节点都有一个确定的优先级,且每个节点的优先级都比它的两个儿子小(即它的优先级满足堆性质)。不难证明在节点的优先级都事先给定且互不相同时,对应的Treap有且仅有一个。现在,给定n个数和每个数对应的优先级,求出对应的以数的大小作为二叉搜索树比较依据的Treap的先序遍历结果。对先序遍历的定义是:先访问根节点,再访问左子树,最后访问右子树。 ...

7月 26 2017
Categories: 题解 Tags: 莫比乌斯反演

Description给定整数N,求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对. Input一个整数N Output如题 ...

7月 15 2017
Categories: 题解 Tags: Treap

【问题描述】题目链接BZOJ COGS ...

7月 13 2017
Categories: 题解 Tags: DP, 矩阵乘

Made by WZZDescriptionHH有个一成不变的习惯,喜欢饭后百步走。所谓百步走,就是散步,就是在一定的时间 内,走过一定的距离。 但是同时HH又是个喜欢变化的人,所以他不会立刻沿着刚刚走来的路走回。 又因为HH是个喜欢变化的人,所以他每天走过的路径都不完全一样,他想知道他究竟有多 少种散步的方法。 现在给你学校的地图(假设每条路的长度都是一样的都是1),问长度为t,从给定地 点A走到给定地点B共有多少条符合条件的路径 ...

7月 13 2017
Categories: 题解 Tags: 线段树

DescriptionXLk觉得《上帝造题的七分钟》不太过瘾,于是有了第二部。“第一分钟,X说,要有数列,于是便给定了一个正整数数列。第二分钟,L说,要能修改,于是便有了对一段数中每个数都开平方(下取整)的操作。第三分钟,k说,要能查询,于是便有了求一段数的和的操作。第四分钟,彩虹喵说,要是noip难度,于是便有了数据范围。第五分钟,诗人说,要有韵律,于是便有了时间限制和内存限制。第六分钟,和雪说,要省点事,于是便有了保证运算过程中及最终结果均不超过64位有符号整数类型的表示范围的限制。第七分钟,这道题终于造完了,然而,造题的神牛们再也不想写这道题的程序了。”——《上帝造题的七分钟·第二部》所以这个神圣的任务就交给你了。 ...

7月 11 2017
Categories: 题解 Tags: STL

描述硬盘中里面有n个文件,文件从1到n标号,每个文件可以用若干个数字序列来表示,而且每个文件存在一个重要值。现在请你完成一个搜索系统,有m个搜索的操作,如果一个文件中有以这个数字序列为前缀的数字序列,那么这个文件会被搜索到,现在我们想知道会有多少个文件被搜索到,以及这些文件中重要值前k小的是哪些。 ...

7月 10 2017
Categories: 笔记 Tags: 数学

组合数$$ ... ...

7月 09 2017
Categories: 题解 Tags: 分块

题目描述墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令: 1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求,你知道你需要干什么了吗? ...

7月 09 2017
Categories: 题解 Tags: 分块

题目描述 ...

7月 06 2017
Categories: 题解 Tags: 分块

题目描述某天,Lostmonkey发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏。游戏一开始,Lostmonkey在地上沿着一条直线摆上n个装置,每个装置设定初始弹力系数ki,当绵羊达到第i个装置时,它会往后弹ki步,达到第i+ki个装置,若不存在第i+ki个装置,则绵羊被弹飞。绵羊想知道当它从第i个装置起步时,被弹几次后会被弹飞。为了使得游戏更有趣,Lostmonkey可以修改某个弹力装置的弹力系数,任何时候弹力系数均为正整数。 ...

7月 03 2017
Categories: 题解 Tags: 分块

题目描述C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段,所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动,可能增加或减少若干人手,但这些都逃不过C国的监视。 ...

7月 03 2017
Categories: 题解 Tags: 二分答案, 状压DP

题目描述Vladik在回家的路上无聊,决定玩下面的游戏:他拿了n张牌在他面前排成一个序列,每张牌上都有一个不超过8的正整数,他决定找到满足以下条件的牌的最长子序列: 在这个序列中,[1,8]每个数字出现的次数之差的绝对值不超过1; 相同的数字必须连续,输出最长子序列的长度。例如,子序列[1, 1, 2, 2]满足第2个条件,但是子序列 [1, 2, 2, 1]就不满足(注意,子序列[1, 1, 2, 2]不满足第一个条件)。 ...

7月 03 2017
Categories: 题解 Tags: KMP

DescriptionEvery morning when they are milked, the Farmer John’s cows form a rectangular grid that is R (1 <= R <= 10,000) rows by C (1 <= C <= 75) columns. As we all know, Farmer John is quite the expert on cow behavior, and is currently writing a book about feeding behavior in cows. He notices that if each cow is labeled with an uppercase letter indicating its breed, the two-dimensional pattern formed by his cows during milking sometimes seems to be made from smaller repeating rectangular patterns. ...

6月 25 2017
Categories: 题解 Tags: 概率DP

Description对于刚上大学的牛牛来说,他面临的第一个问题是如何根据实际情况申请合适的课程。在可以选择的课程中,有2n节课程安排在n个时间段上。在第i(1≤i≤n)个时间段上,两节内容相同的课程同时在不同的地点进行,其中,牛牛预先被安排在教室ci上课,而另一节课程在教室di进行。在不提交任何申请的情况下,学生们需要按时间段的顺序依次完成所有的n节安排好的课程。如果学生想更换第i节课程的教室,则需要提出申请。若申请通过,学生就可以在第i个 ...

6月 24 2017
Categories: 题解 Tags: 概率DP

Description 你正在玩你最喜欢的电子游戏,并且刚刚进入一个奖励关。在这个奖励关里,系统将依次随机抛出k次宝物,每次你都可以选择吃或者不吃(必须在抛出下一个宝物之前做出选择,且现在决定不吃的宝物以后也不能再吃)。 宝物一共有n种,系统每次抛出这n种宝物的概率都相同且相互独立。也就是说,即使前k-1次系统都抛出宝物1(这种情况是有可能出现的,尽管概率非常小),第k次抛出各个宝物的概率依然均为1/n。 获取第i种宝物将得到Pi分,但并不是每种宝物都是可以随意获取的。第i种宝物有一个前提宝物集合Si。只有当Si中所有宝物都至少吃过 ...

6月 22 2017
Categories: 题解 Tags: 概率DP, 高斯消元

Description ...

6月 21 2017
Categories: 笔记 Tags: 莫比乌斯反演

莫比乌斯反演已知$$ F(n)=\sum_{d|n}{f(d)} $$则$$ f(n)=\sum_{d|n}{\mu(d)F(\frac {n}{d})} $$ ...

6月 21 2017
Categories: 题解 Tags: 概率DP

Description Input数据的第1行为两个整数N和E,以空格分隔,分别表示森林中的景点数和连接相邻景点的路的条数。 第2行包含两个整数C和M,以空格分隔,分别表示初始时聪聪和可可所在的景点的编号。 接下来E行,每行两个整数,第i+2行的两个整数Ai和Bi表示景点Ai和景点Bi之间有一条路。 所有的路都是无向的,即:如果能从A走到B,就可以从B走到A。 输入保证任何两个景点之间不会有多于一条路直接相连,且聪聪和可可之间必有路直接或间接的相连。 ...

6月 21 2017
Categories: 题解 Tags: 概率DP, 高斯消元

Description一个无向连通图,顶点从1编号到N,边从1编号到M。小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束,总分为所有获得的分数之和。现在,请你对这M条边进行编号,使得小Z获得的总分的期望值最小。 ...

6月 19 2017
Categories: 题解 Tags: 概率DP, 高斯消元

Description奶牛们建立了一个随机化的臭气炸弹来驱逐猪猡。猪猡的文明包含1到N (2 <= N <= 300)一共N个猪城。这些城市由M (1 <= M <= 44,850)条由两个不同端点A_j和B_j (1 <= A_j<= N; 1 <= B_j <= N)表示的双向道路连接。保证城市1至少连接一个其它的城市。一开始臭气弹会被放在城市1。每个小时(包括第一个小时),它有P/Q (1 <= P <=1,000,000; 1 <= Q <= 1,000,000)的概率污染它所在的城市。如果这个小时内它没有污染它所在的城市,那麽它随机地选择一条道路,在这个小时内沿着这条道路走到一个新的城市。可以离开这个城市的所有道路被选择的概率均等。因为这个臭气弹的随机的性质, ...

6月 19 2017
Categories: 题解 Tags: 高斯消元

Description 有一个球形空间产生器能够在n维空间中产生一个坚硬的球体。现在,你被困在了这个n维球体中,你只知道球面上n+1个点的坐标,你需要以最快的速度确定这个n维球体的球心坐标,以便于摧毁这个球形空间产生器。 ...

6月 19 2017
Categories: 题解 Tags: 高斯消元

【问题描述】已知 n 元线性一次方程组。$$ a_{1,1}x_1+a_{1,2}x_2+…+a_{1,n}x_n=b_1 $$$$ a_{2,1}x_1+a_{2,2}x_2+…+a_{2,n}x_n=b_2 $$$$…………$$$$ a_{n,1}x_1+a_{n,2}x_2+…+a_{n,n}x_n=b_n $$其中: n<=50.系数是整数,绝对值<=100 , bi的值都是正整数且<300。编程任务:根据输入的数据,编程输出方程组的解的情况。 ...

6月 18 2017
Categories: 题解 Tags: dfs, 二分答案, 贪心

DescriptionFarmer John为了保持奶牛们的健康,让可怜的奶牛们不停在牧场之间 的小路上奔跑。这些奶牛的路径集合可以被表示成一个点集和一些连接 两个顶点的双向路,使得每对点之间恰好有一条简单路径。简单的说来, 这些点的布局就是一棵树,且每条边等长,都为1。 对于给定的一个奶牛路径集合,精明的奶牛们会计算出任意点对路径的最大值, 我们称之为这个路径集合的直径。如果直径太大,奶牛们就会拒绝锻炼。 Farmer John把每个点标记为1..V (2 <= V <= 100,000)。为了获得更加短 的直径,他可以选择封锁一些已经存在的道路,这样就可以得到更多的路径集合, 从而减小一些路径集合的直径。 我们从一棵树开始,FJ可以选择封锁S (1 <= S <= V-1)条双向路,从而获得 S+1个路径集合。你要做的是计算出最佳的封锁方案,使得他得到的所有路径集合 直径的最大值尽可能小。 Farmer John告诉你所有V-1条双向道路,每条表述为:顶点A_i (1 <= A_i <= V) 和 B_i (1 <= B_i <= V; A_i!= B_i)连接。 我们来看看如下的例子:线性的路径集合(7个顶点的树) 1—2—3—4—5—6—7 如果FJ可以封锁两条道路,他可能的选择如下: 1—2 | 3—4 | 5—6—7 这样最长的直径是2,即是最优答案(当然不是唯一的)。 ...

6月 18 2017
Categories: 题解 Tags: hash

Description几乎所有操作系统的命令行界面(CLI)中都支持文件名的通配符匹配以方便用户。最常见的通配符有两个,一个是星号(“”’),可以匹配0个及以上的任意字符:另一个是问号(“?”),可以匹配恰好一个任意字符。现在需要你编写一个程序,对于给定的文件名列表和一个包含通配符的字符串,判断哪些文件可以被匹配。 ...

6月 17 2017
Categories: 题解 Tags: dfs, 贪心

Description很久很久之前,森林里住着一群兔子。有一天,兔子们突然决定要去看樱花。兔子们所在森林里的樱花树很特殊。樱花树由n个树枝分叉点组成,编号从0到n-1,这n个分叉点由n-1个树枝连接,我们可以把它看成一个有根树结构,其中0号节点是根节点。这个树的每个节点上都会有一些樱花,其中第i个节点有c_i朵樱花。樱花树的每一个节点都有最大的载重m,对于每一个节点i,它的儿子节点的个数和i节点上樱花个数之和不能超过m,即son(i) + c_i <= m,其中son(i)表示i的儿子的个数,如果i为叶子节点,则son(i) = 0现在兔子们觉得樱花树上节点太多,希望去掉一些节点。当一个节点被去掉之后,这个节点上的樱花和它的儿子节点都被连到删掉节点的父节点上。如果父节点也被删除,那么就会继续向上连接,直到第一个没有被删除的节点为止。 ...

6月 14 2017
Categories: 题解 Tags: fail树

Description某人读论文,一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次,现在想知道每个单词分别在论文中出现多少次。 ...

6月 14 2017
Categories: 题解 Tags: 网络流

DescriptionKiana最近喜欢到一家非常美味的寿司餐厅用餐。每天晚上,这家餐厅都会按顺序提供n种寿司,第i种寿司有一个代号ai和美味度di,i,不同种类的寿司有可能使用相同的代号。每种寿司的份数都是无限的,Kiana也可以无限次取寿司来吃,但每种寿司每次只能取一份,且每次取走的寿司必须是按餐厅提供寿司的顺序连续的一段,即Kiana可以一次取走第1,2种寿司各一份,也可以一次取走第2,3种寿司各一份,但不可以一次取走第1,3种寿司。由于餐厅提供的寿司种类繁多,而不同种类的寿司之间相互会有影响:三文鱼寿司和鱿鱼寿司一起吃或许会很棒,但和水 ...

6月 14 2017
Categories: 题解 Tags: Treap, 树套树

Description给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1),并且,你可以改变一些a[i]的值,改变后,程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序,从输入文件中读入序列a,然后读入一系列的指令,包括询问指令和修改指令。对于每一个询问指令,你必须输出正确的回答。 第一行有两个正整数n(1≤n≤10000),m(1≤m≤10000)。分别表示序列的长度和指令的个数。第二行有n个数,表示a[1],a[2]……a[n],这些数都小于10^9。接下来的m行描述每条指令,每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t Q i j k (i,j,k是数字,1≤i≤j≤n, 1≤k≤j-i+1)表示询问指令,询问a[i],a[i+1]……a[j]中第k小的数。C i t (1≤i≤n,0≤t≤10^9)表示把a[i]改变成为t。 ...

6月 14 2017
Categories: 题解 Tags: 概率DP

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

6月 14 2017
Categories: 题解 Tags: 概率DP

Descriptionosu 是一款群众喜闻乐见的休闲软件。我们可以把osu的规则简化与改编成以下的样子:一共有n次操作,每次操作只有成功与失败之分,成功对应1,失败对应0,n次操作对应为1个长度为n的01串。在这个串中连续的 X个1可以贡献X^3 的分数,这x个1不能被其他连续的1所包含(也就是极长的一串1,具体见样例解释)现在给出n,以及每个操作的成功率,请你输出期望分数,输出四舍五入后保留1位小数。 ...

6月 14 2017
Categories: 题解 Tags: 网络流

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

6月 13 2017
Categories: 题解 Tags: AC自动机

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

6月 13 2017
Categories: 题解 Tags: Trie

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

6月 13 2017
Categories: 题解 Tags: 网络流

【题目描述】这是在阿尔托利亚·潘德拉贡成为英灵前的事情,她正要去拔出石中剑成为亚瑟王,在这之前她要去收集一些宝石。宝石排列在一个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)上。求阿尔托利亚·潘德拉贡最多可以获得多少价值的宝石 ...

6月 13 2017
Categories: 图库 Tags: 图库

...

6月 13 2017
Categories: 题解 Tags: Trie, 贪心

Description给定一棵n个点的带权树,求树上最长的异或和路径 ...

6月 13 2017
Categories: 题解 Tags: Trie

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

6月 13 2017
Categories: 题解 Tags: 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) . ...

6月 13 2017
Categories: 题解 Tags: KMP

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

6月 13 2017
Categories: 笔记 Tags: 网络流

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