Dispwnl

Crazy Up

[SHOI2012]信用卡凸包

题目题目背景 SHOI2012D1T2 题目描述信用卡是一个矩形，唯四个角作了圆滑处理，使它们都是与矩形的两边相切的 1/4 圆，如下图所示。现在平面上有一些规格相同的信用卡，试求其凸包的周长。注意凸包未必是多边形，因为它可能包含若干段圆弧。输入输出格式输入格式：输入的第一行是一个正整数 n，表示信用卡的张数。第二行包含三个实数 a, b, r，分别表示信用卡（圆...

Posted by Dispwnl on January 18, 2019

[HEOI2014]大工程

题目题目描述国家有一个大工程，要给一个非常大的交通网络里建一些新的通道。我们这个国家位置非常特殊，可以看成是一个单位边权的树，城市位于顶点上。在 2 个国家 a,b 之间建一条新通道需要的代价为树上 a,b 的最短路径。现在国家有很多个计划，每个计划都是这样，我们选中了 k 个点，然后在它们两两之间新建 C(k,2)条新通道。现在对于每个计划，我们想知道： 1.这些...

Posted by Dispwnl on January 18, 2019

[CF613D]Kingdom and its Cities

题目题目大意给定一颗$n$个点的树，每次询问选择$k$个关键点，问至少选多少个非关键点才能使关键点两两不连通 Examples input 4 1 3 2 3 4 3 4 2 1 2 3 2 3 4 3 1 2 4 4 1 2 3 4 output 1 -1 1 -1 input 7 1 2 2 3 3 4 1 5 5 6 5 7 1 4 2 4 6 7 out...

Posted by Dispwnl on January 18, 2019

[BZOJ4372]烁烁的游戏

题目 Description 背景：烁烁很喜欢爬树，这吓坏了树上的皮皮鼠。题意：给定一颗n个节点的树，边权均为1，初始树上没有皮皮鼠。烁烁他每次会跳到一个节点u，把周围与他距离不超过d的节点各吸引出w只皮皮鼠。皮皮鼠会被烁烁吸引，所以会一直待在节点上不动。烁烁很好奇，在当前时刻，节点u有多少个他的好朋友—皮皮鼠。大意：给一颗n个节点的树，边权均为1，初始点权均为0...

Posted by Dispwnl on January 18, 2019

[BZOJ3879]SvT

题目 Description (我并不想告诉你题目名字是什么鬼) 有一个长度为n的仅包含小写字母的字符串S,下标范围为[1,n]. 现在有若干组询问,对于每一个询问,我们给出若干个后缀(以其在S中出现的起始位置来表示),求这些后缀两两之间的LCP(Longest Common Prefix)的长度之和.一对后缀之间的LCP长度仅统计一遍. Input 第一行两个正整数n,m,分别...

Posted by Dispwnl on January 18, 2019

[ZJOI2015]幻想乡战略游戏

题目题目描述傲娇少女幽香正在玩一个非常有趣的战略类游戏，本来这个游戏的地图其实还不算太大，幽香还能管得过来，但是不知道为什么现在的网游厂商把游戏的地图越做越大，以至于幽香一眼根本看不过来，更别说和别人打仗了。在打仗之前，幽香现在面临一个非常基本的管理问题需要解决。整个地图是一个树结构，一共有n块空地，这些空地被n-1条带权边连接起来，使得每两个点之间有一条唯一的路径将它们连接起...

Posted by Dispwnl on January 17, 2019

[BZOJ3730]震波

题目 Description 在一片土地上有N个城市，通过N-1条无向边互相连接，形成一棵树的结构，相邻两个城市的距离为1，其中第i个城市的价值为value[i]。不幸的是，这片土地常常发生地震，并且随着时代的发展，城市的价值也往往会发生变动。接下来你需要在线处理M次操作： 0 x k 表示发生了一次地震，震中城市为x，影响范围为k，所有与x距离不超过k的城市都将受到影响...

Posted by Dispwnl on January 17, 2019

[HNOI2014]世界树

题目题目描述世界树是一棵无比巨大的树，它伸出的枝干构成了整个世界。在这里，生存着各种各样的种族和生灵，他们共同信奉着绝对公正公平的女神艾莉森，在他们的信条里，公平是使世界树能够生生不息、持续运转的根本基石。世界树的形态可以用一个数学模型来描述：世界树中有 $n$ 个种族，种族的编号分别从 $1$ 到 $n$，分别生活在编号为 $1$ 到 $n$ 的聚居地上，种族的编号与其聚居地...

Posted by Dispwnl on January 16, 2019

[CF914E]Palindromes in a Tree

题目题目大意给定一棵树，每个点有一个在a和t之间的小写字母，定义回文路径指这条路径上所有字符能组成回文串，求经过每个点的回文路径数量 Examples input 5 1 2 2 3 3 4 3 5 abcbb output 1 3 4 3 3 input 7 6 2 4 3 3 7 5 2 7 2 1 4 afefdfs output 1 4 1 1 2 ...

Posted by Dispwnl on January 16, 2019

[LOJ6401]字符串

题目题目描述有一个只包含小写字母，长度为 $n$ 的字符串 $S$ 。有一些字母是好的，剩下的是坏的。定义一个子串 $S_{l\ldots r}$ 是好的，当且仅当这个子串包含不超过 $k$ 个坏的字母。求有多少个不同的满足以下要求的字符串 $T$ ： $T$ 作为 $S$ 的子串出现过。存在一个 $T$ 出现的位置 $[l,r]$ ，满足 $S_{l\ldot...

Posted by Dispwnl on January 15, 2019