Dispwnl

Crazy Up

[HEOI2015]最短不公共子串

题目题目描述在虐各种最长公共子串、子序列的题虐的不耐烦了之后，你决定反其道而行之。一个串的“子串”指的是它的连续的一段，例如bcd是abcdef的子串，但bde不是。一个串的“子序列”指的是它的可以不连续的一段，例如bde是abcdef的子串，但bdd不是。下面，给两个小写字母串A，B，请你计算： (1) A的一个最短的子串，它不是B的子串 (2) A的一个最短的子串，它...

Posted by Dispwnl on January 6, 2019

[SPOJ8093]Sevenk Love Oimaster

题目题目大意给定$n$个模板串和$m$个查询串，输出每个查询串在多少个模板串中出现过 Sample Input 3 3 abcabcabc aaa aafe abc a ca Sample Output 1 3 1 题解只想到了$SA$做法…… 先对于模板串拼成的大串建后缀数组，对于每个查询串，都可以二分找到$lcp$是ta自己的$rank$区间，然后问题就转换成了求一些区...

Posted by Dispwnl on January 5, 2019

[CF1097X]Hello 2019

上紫纪念 A　　Gennady and a Card Game 题目大意每个元素有两个值$a,b$，现在你有$5$个元素，问是否有一个元素与给定元素$a$相等或者$b$相等题解。代码 # include<bits/stdc++.h> using namespace std; int A,B; int a[5],b[5]; char s[5][10],qwq[1...

Posted by Dispwnl on January 4, 2019

[POI2007]树Drz

题目 Description CDQZ是一个偏远的小学校，FGD在学校里中了一排树。他却不喜欢这些树的顺序，因为他们高高矮矮显得那么参差不齐。FGD定义这些树的不整齐程度为相邻两树的高度差的和。设树高分别为h1,h2,h3,…,hn。那么不整齐程度定义为：$\vert h_1-h_2\vert+\vert h_2-h_3\vert +……+\vert h_{n-1}-h_n\vert$。...

Posted by Dispwnl on January 4, 2019

[BZOJ1396]识别子串

题目 Description Input 一行,一个由小写字母组成的字符串S,长度不超过10^5 Output L行,每行一个整数,第i行的数据表示关于S的第i个元素的最短识别子串有多长. Sample Input agoodcookcooksgoodfood Sample Output 1 2 3 3 2 2 3 3 2 2 3 3 2 1 2 3 3 2 1 2 3 4 题解有...

Posted by Dispwnl on January 3, 2019

[HEOI2016]字符串

题目题目描述佳媛姐姐过生日的时候，她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了一个长为n的字符串s，和m个问题。佳媛姐姐必须正确回答这m个问题，才能打开箱子拿到礼物，升职加薪，出任CEO，嫁给高富帅，走上人生巅峰。每个问题均有a,b,c,d四个参数，问你子串s[a..b]的所有子串和s[c..d]的最长公共前缀的长度的最大值是多少？佳媛姐姐并不擅长做这样...

Posted by Dispwnl on December 30, 2018

[SDOI2016]生成魔咒

题目题目描述魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 1、2 拼凑起来形成一个魔咒串 [1,2]。一个魔咒串 S 的非空字串被称为魔咒串 S 的生成魔咒。例如 S=[1,2,1] 时，它的生成魔咒有 [1]、[2]、[1,2]、[2,1]、[1,2,1] 五种。S=[1,1,1] 时，它的生成魔咒有 [1]、[1,1]、[1,1,1] 三种。最初 S...

Posted by Dispwnl on December 29, 2018

[WC2013]糖果公园

题目题目描述 Candyland 有一座糖果公园，公园里不仅有美丽的风景、好玩的游乐项目，还有许多免费糖果的发放点，这引来了许多贪吃的小朋友来糖果公园游玩。糖果公园的结构十分奇特，它由 $n$ 个游览点构成，每个游览点都有一个糖果发放处，我们可以依次将游览点编号为 $1$ 至 $n$。有 $n – 1$ 条双向道路连接着这些游览点，并且整个糖果公园都是连通的，即从任何一个游览点出发都可...

Posted by Dispwnl on December 13, 2018

[BZOJ3809]Gty的二逼妹子序列

题目 Description Autumn和Bakser又在研究Gty的妹子序列了！但他们遇到了一个难题。对于一段妹子们，他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。为了方便，我们规定妹子们的美丽度全都在[1,n]中。给定一个长度为n(1<=n<=100000)的正整数序列s(1<=si<=n)，对于m(1<=m<=100000...

Posted by Dispwnl on December 13, 2018

[CTSC2016]时空旅行

题目 Description 2045年，人类的技术突飞猛进，已经找到了进行时空旅行的方法。小R得到了一台时空旅行仪，他想用它调查不同时空中人类的发展状况。根据平行时空理论，宇宙中存在着很多独立的时空，每个时空在下一个时间点还会分化出若干个不同的时空。宇宙是一个三维空间，人类使用空间直角坐标系来描述空间中的一个位置，三维坐标分别是 x,y,z。我们假设在初始的时空（编号为 0）中，...

Posted by Dispwnl on December 10, 2018