数据结构 - Page 10

离大海最远点在哪里？
http://218.5.5.242:9014/problem.asp?id=1678题目描述遥远的海上有一座岛屿，这个岛屿的轮廓是一个凸多边形，把边视为岛屿的海岸线。当地的居民想要在岛屿上找一地点使其到大海的距离最远，这地点应在哪里？岛上居民们习惯地把岛上某个点到岛屿的各条海岸线（即各边）距离中最小者看成该点到大海的距离。如下图所示，点O到大海的距离为min{j,k,l,m,n}=j,其中j,k,l,m,n分别为O到AB，BC，CD，DE，EA的距离。现在，给您N...
02015年2月3日6,881STL,链表,二分法,半平面交

「fjWC2015」k个串 kstring
「题目描述」兔子们在玩k个串的游戏。首先，它们拿出了一个长度为n的数字序列，选出其中的一个连续子串，然后统计其子串中所有数字之和（注意这里重复出现的数字只被统计一次）。兔子们想知道，在这个数字序列所有连续的子串中，按照以上方式统计其所有数字之和，第k大的和是多少。「输入格式」第一行，两个整数n和k，分别表示长度为n的数字序列和想要统计的第k大的和接下里一行n个数a_i，表示这个数字序列「输出格式」一行一个整数...
42015年2月3日6,680STL,可持久化线段树
「fjWC2015」Screen
「题目描述」码农有一块超新星屏幕，它有N个像素点，每个像素点有亮度和灰度两个参数，记为I和H,范围都是0~32000.一天，码农突发奇想，想知道哪个点比较容易亮瞎眼睛。为此，他定义了一个瞎眼指数:瞎眼指数就是灰度和亮度均不大于该像素点的像素个数。现在，码农希望知道，瞎眼指数为0~N-1的像素点分别有多少个「输入格式」第一行一个数字N，代表有N个像素点。接下来N行，每行两个数字,代表该像素点的亮度和灰度。N个...
02015年2月3日2,637树状数组
「BZOJ3173」[TJOI2013] 最长上升子序列
Description给定一个序列，初始为空。现在我们将1到N的数字插入到序列中，每次将一个数字插入到一个特定的位置。每插入一个数字，我们都想知道此时最长上升子序列长度是多少？Input第一行一个整数N，表示我们要将1到N插入序列中，接下是N个数字，第k个数字Xk，表示我们将k插入到位置Xk（0<=Xk<=k-1,1<=k<=N）OutputN行，第i行表示i插入Xi位置后序列的最长上升子序列的长度是多少。SampleInput3002Samp...
62015年1月29日8,097递推与动规,treap
「BZOJ3162」独钓寒江雪
Description题解参照2007杨弋论文vfk的博客http://vfleaking.blog.163.com/blog/static/17480763420134452440444/太神了orzorzorz[crayon-6744728087585523532989/]
72015年1月28日4,758树形动规,哈希表
「BZOJ3772」精神污染
Description兵库县位于日本列岛的中央位置，北临日本海，南面濑户内海直通太平洋，中央部位是森林和山地，与拥有关西机场的大阪府比邻而居，是关西地区面积最大的县，是集经济和文化于一体的一大地区，是日本西部门户，海陆空交通设施发达。濑户内海沿岸气候温暖，多晴天，有日本少见的贸易良港神户港所在的神户市和曾是豪族城邑“城下町”的姬路市等大城市，还有以疗养地而闻名的六甲山地等。兵库县官方也大力发展旅游，为了方便...
02015年1月27日6,252dfs序,主席树
「vijos1459」车展
描述遥控车是在是太漂亮了，韵韵的好朋友都想来参观，所以游乐园决定举办m次车展。车库里共有n辆车，从左到右依次编号为1，2，…，n，每辆车都有一个展台。刚开始每个展台都有一个唯一的高度h[i]。主管已经列好一张单子：L1R1L2R2…LmRm单子上的(Li,Ri)表示第i次车展将要展出编号从Li到Ri的车。为了更加美观，展览时需要调整展台的高度，使参展所有展台的高度相等。展台的高度增加或减少1都需花费1秒时间。由于管理员只有...
02015年1月25日4,444treap
「BZOJ3813」奇数国
Description在一片美丽的大陆上有100000个国家，记为1到100000。这里经济发达，有数不尽的账房，并且每个国家有一个银行。某大公司的领袖在这100000个银行开户时都存了3大洋，他惜财如命，因此会不时地派小弟GFS清点一些银行的存款或者让GFS改变某个银行的存款。该村子在财产上的求和运算等同于我们的乘法运算，也就是说领袖开户时的存款总和为3100000。这里发行的软妹面额是最小的60个素数（p1=2,p2=3,…,p60=281），任何人...
02015年1月22日5,814线段树,筛法,欧拉函数,乘法逆元
「BZOJ2754」[SCOI2012] 喵星球上的点名
Descriptiona180285幸运地被选做了地球到喵星球的留学生。他发现喵星人在上课前的点名现象非常有趣。假设课堂上有N个喵星人，每个喵星人的名字由姓和名构成。喵星球上的老师会选择M个串来点名，每次读出一个串的时候，如果这个串是一个喵星人的姓或名的子串，那么这个喵星人就必须答到。然而，由于喵星人的字码过于古怪，以至于不能用ASCII码来表示。为了方便描述，a180285决定用数串来表示喵星人的名字。现在你能帮助a1...
52015年1月15日7,811STL,AC自动机
「POJ3693」Maximum repetition substring
DescriptionTherepetitionnumberofastringisdefinedasthemaximumnumberRsuchthatthestringcanbepartitionedintoRsameconsecutivesubstrings.Forexample,therepetitionnumberof"ababab"is3and"ababa"is1.Givenastringcontaininglowercaseletters,youaretofindasubstringofitwithmaximumrepetitionnumber.InputTheinputconsistsofmultipletestcases.Eachtestcasecontainsexactlyoneline,whichgivesanon-emptystringconsisti...
22015年1月14日6,336ST表,后缀数组
「点分治练习」boatherds
「问题描述」询问一颗树上距离为K的点对是否存在「输入格式」第一行两个整数n,m接下来n-1条边a,b,c描述a到b有一条长度为c的路径接下来m行每行询问一个K「输出格式」对于每个K每行输出一个答案存在输出”AYE”,否则输出”NYE”(不包含引号)「样例输入」2212112「样例输出」AYENYE「数据规模与约定」对于30%的数据,有1≤n≤100对于60%的数据,有1≤n≤10^31≤m≤50对于100%的数据,有1≤n≤10^4,1≤m≤100,1≤c≤1000,1...
12015年1月10日4,048STL,点分治
「BZOJ2151」种树
DescriptionA城市有一个巨大的圆形广场，为了绿化环境和净化空气，市政府决定沿圆形广场外圈种一圈树。园林部门得到指令后，初步规划出n个种树的位置，顺时针编号1到n。并且每个位置都有一个美观度Ai，如果在这里种树就可以得到这Ai的美观度。但由于A城市土壤肥力欠佳，两棵树决不能种在相邻的位置（i号位置和i+1号位置叫相邻位置。值得注意的是1号和n号也算相邻位置！）。最终市政府给园林部门提供了m棵树苗并要求全部种上，...
02015年1月9日7,215STL,贪心,堆