算法 - Page 20 - hzwer.com

「BZOJ3207」花神的嘲讽计划Ⅰ
Description背景花神是神，一大癖好就是嘲讽大J，举例如下： “哎你傻不傻的！「hqz：大笨J」” “这道题又被J屎过了！！” “J这程序怎么跑这么快！J要逆袭了！” ……描述这一天DJ在给吾等众蒟蒻讲题，花神在一边做题无聊，就跑到了一边跟吾等众蒟蒻一起听。以下是部分摘录： 1.“J你在讲什么！” “我在讲XXX！” “哎你傻不傻的！这么麻烦，直接XXX再XXX就好了！” “……” 2. “J你XXX讲...
22015年4月22日6,645可持久化线段树,哈希表

「BZOJ4008」[HNOI2015] 亚瑟王
Description小K不慎被LL邪教洗脑了，洗脑程度深到他甚至想要从亚瑟王邪教中脱坑。他决定，在脱坑之前，最后再来打一盘亚瑟王。既然是最后一战，就一定要打得漂亮。众所周知，亚瑟王是一个看脸的游戏，技能的发动都是看概率的。作为一个非洲人，同时作为一个前OIer，小K自然是希望最大化造成伤害的期望值。但他已经多年没写过代码，连Spaly都敲不对了，因此，希望你能帮帮小K，让他感受一下当欧洲人是怎样的体验。本题中我...
12015年4月22日7,505递推与动规,概率与期望
「BZOJ3996」[TJOI2015] 线性代数
Description给出一个N*N的矩阵B和一个1*N的矩阵C。求出一个1*N的01矩阵A.使得D=（A*B-C）*A^T最大。其中A^T为A的转置。输出DInput第一行输入一个整数N，接下来N行输入B矩阵，第i行第J个数字代表Bij.接下来一行输入N个整数，代表矩阵C。矩阵B和矩阵C中每个数字都是不超过1000的非负整数。Output输出最大的DSampleInput3121310123237SampleOutput2HINT 1<=N<=500题解倒腾下式子发现是...
02015年4月22日6,053最小割
「BZOJ3997」[TJOI2015] 组合数学
Description 给出一个网格图，其中某些格子有财宝，每次从左上角出发，只能向下或右走。问至少走多少次才能将财宝捡完。此对此问题变形，假设每个格子中有好多财宝，而每一次经过一个格子至多只能捡走一块财宝，至少走多少次才能把财宝全部捡完。Input 第一行为正整数T，代表数据组数。每组数据第一行为正整数N，M代表网格图有N行M列，接下来N行每行M个非负整数，表示此格子中财宝数量，0代表没有Output 输出一个整数...
22015年4月22日5,104递推与动规
「BZOJ3998」[TJOI2015] 弦论
Description对于一个给定长度为N的字符串，求它的第K小子串是什么。Input 第一行是一个仅由小写英文字母构成的字符串S第二行为两个整数T和K，T为0则表示不同位置的相同子串算作一个。T=1则表示不同位置的相同子串算作多个。K的意义如题所述。Output输出仅一行，为一个数字串，为第K小的子串。如果子串数目不足K个，则输出-1SampleInputaabc03SampleOutputaabHINT N<=5*10^5T<2K<=10^9题解日常o...
62015年4月22日7,240后缀自动机
「BZOJ3572」[HNOI2014] 世界树
Description 世界树是一棵无比巨大的树，它伸出的枝干构成了整个世界。在这里，生存着各种各样的种族和生灵，他们共同信奉着绝对公正公平的女神艾莉森，在他们的信条里，公平是使世界树能够生生不息、持续运转的根本基石。世界树的形态可以用一个数学模型来描述：世界树中有n个种族，种族的编号分别从1到n，分别生活在编号为1到n的聚居地上，种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相连，道路的长度为1。保...
22015年4月21日11,064虚树,树形动规
「BZOJ3573」[HNOI2014] 米特运输
Description米特是D星球上一种非常神秘的物质，蕴含着巨大的能量。在以米特为主要能源的D星上，这种米特能源的运输和储存一直是一个大问题。D星上有N个城市，我们将其顺序编号为1到N，1号城市为首都。这N个城市由N-1条单向高速通道连接起来，构成一棵以1号城市（首部）为根的树，高速通道的方向由树中的儿子指向父亲。树按深度分层：根结点深度为0，属于第1层；根结点的子节点深度为1，属于第2层；依此类推，深度为i的结点...
02015年4月21日4,213树形动规
「BZOJ2946」[POI2000] 公共串
Description 给出几个由小写字母构成的单词，求它们最长的公共子串的长度。任务：l 读入单词l 计算最长公共子串的长度l 输出结果Input文件的第一行是整数n，1<=n<=5，表示单词的数量。接下来n行每行一个单词，只由小写字母组成，单词的长度至少为1，最大为2000。Output仅一行，一个整数，最长公共子串的长度。SampleInput3abcbbcaacbcSampleOutput２题解后缀自动机...
12015年4月21日5,400后缀自动机
「BZOJ1095」[ZJOI2007] Hide 捉迷藏
Description捉迷藏Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特，由N个屋子和N-1条双向走廊组成，这N-1条走廊的分布使得任意两个屋子都互相可达。游戏是这样进行的，孩子们负责躲藏，Jiajia负责找，而Wind负责操纵这N个屋子的灯。在起初的时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激...
72015年4月20日25,047STL,线段树,点分治,最近公共祖先
「POJ1743」Musical Theme
DescriptionAmusicalmelodyisrepresentedasasequenceofN(1<=N<=20000)notesthatareintegersintherange1..88,eachrepresentingakeyonthepiano.Itisunfortunatebuttruethatthisrepresentationofmelodiesignoresthenotionofmusicaltiming;but,thisprogrammingtaskisaboutnotesandnottimings.Manycomposersstructuretheirmusicaroundarepeating&qout;theme&qout;,which,beingasubsequenceofanentiremelody,isasequ...
12015年4月20日6,372后缀数组,后缀自动机
「BZOJ3675」[Apio2014] 序列分割
Description小H最近迷上了一个分割序列的游戏。在这个游戏里，小H需要将一个长度为N的非负整数序列分割成k+l个非空的子序列。为了得到k+l个子序列，小H将重复进行七次以下的步骤：1．小H首先选择一个长度超过1的序列（一开始小H只有一个长度为n的序列一一也就是一开始得到的整个序列）；2．选择一个位置，并通过这个位置将这个序列分割成连续的两个非空的新序列。每次进行上述步骤之后，小H将会得到一定的分数。这个分数为...
42015年4月19日8,451斜率优化,决策单调性
UOJ Round #3
http://vfleaking.blog.uoj.ac/blog/43「UR#3」核聚变反应强度[crayon-67816637601d8860126773/]「UR#3」铀仓库[crayon-67816637601e1836643565/]「UR#3」链式反应题目都不敢看。。。
02015年4月19日2,890二分法,最大公约数与最小公倍数