redoCxz

分类

ACM练习赛(18) ACM练习题(418) BZOJ刷题(5) C++算法模板(20) codeforce(4) hdu(8) java(16) Java算法模板(24) kotlin(1) Leetcode(12) Lintcode(26) 剑指offer(1) 拓展欧几里德(1) 最小生成树(1) 未归档(70) 杂七杂八(41) 水题(1) 牛客网(2) 牛客网错题总结(1) 算法四(2) 题解(1)

/ 注册

全部文章（共388篇）

2018icpc宁夏邀请赛_L_Continuous Intervals

题意给定一个序列，定义连续区间为区间的数排序后，任意两个相邻的数之差不超过1。分析假设区间最大值为\(max\),最小值为\(min\)，不同数个数为\(cnt\)，那么问题转化为求满足\(max-min-cnt==1\)的区间个数。统计满足条件的区间个数可以考虑用线段树，主...

题解线段树单调栈

2019-09-06

0 421

2019icpc南京网络赛_F_Greedy Sequence

题意题意不明，队友告诉我对于每个\(i\)，所在下标\(p[i]\)，在\([p[i]-k,p[i]+k]\)中找到小于\(i\)的最大数\(x\)，然后\(ans[i]=ans[x]+1\)即可。分析第一种方法无脑主席树，求区间小于某个值的最大数。第二种方法是线段树，因为对...

题解主席树线段树

2019-09-01

0 430

luoguP3261_[JLOI2015]城池攻占

题意有一棵树\(n\)个节点，每个节点有一个防御值，以及两个属性，表示一个骑士占领该节点后攻击值是加还是乘，有\(m\)个骑士，有初始位置和初始攻击值，如果攻击值大于该节点的防御值，就能占领该节点，然后更新攻击值，走到父节点，如果攻击值小于防御值，骑士就会死在该节点。问每个骑士能占领多少个节...

题解左偏树可并堆 dfs

2019-09-01

0 367

poj3415_Common Substrings

题意给定两个字符串，求长度大于等于k的公共子串数。分析将两个字符串中间加个特殊字符拼接，跑后缀数组。将题目转化为对每一个后缀求\(\sum_{j=1}^{i-1}lcp(i,j)\)，且后缀\(i\)和\(j\)属于不同字符串。由于\(lcp\)只跟\(h\)数组的区间...

题解后缀数组单调栈字符串

2019-08-25

0 333

2019CCPC网络赛

hdu6703 array 题意给定一个1到\(n\)的全排列，两种操作，将\(a_{pos}\)修改为\(a_{pos}+1000000\)，询问第一个大于等于\(k\)的且不在\(a_1...a_r\)的数。分析由于\(k<=n\)，因此操作二询问的答案最大是\(n+1...

题解权值线段树后缀数组字符串主席树优先队列图论

2019-08-25

0 626

2018icpc宁夏邀请赛网络赛_G_Trouble of Tyrant

题意一列\(n\)个点，给定一个特殊的图，有两种边\(E(1,i)\)和\(E(i-1,i)\)，多个询问，每次给一个\(d\)，求所有路径长度加上\(d\)后1到\(n\)的最短路。分析首先这图很特殊，大胆猜测不是图论。 1到\(n\)的最短路包括\(p_i\)，即1直接到\...

题解单调栈凸包思维

2019-08-23

0 448

luoguP2444_[POI2000]病毒

题意给定多个01模式串，问是否存在一个无限长的字符串不包含任何一个模式串。分析好像数据有点水，网上一大堆题解连样例都没过？？？多模式串，先把AC自动机建出来再说。反向考虑，若存在一个无限长的字符串不包含任何一个模式串，那就说明这个字符串可以在AC自动机上无限匹配，所以我...

题解字符串 AC自动机 dfs

2019-08-22

0 458

uoj218_火车管理

题意 \(n\)个位置，每个位置一个栈，三种操作，询问区间栈顶的和，区间入栈某个数，单点出栈某个数。分析用一个线段树来维护栈顶的和，区间(单点)更新和区间询问。用一个主席树来维护每个位置最新一次入栈的时间，即主席树存的是时间，然后取出的时间也能作为主席树的下标来访问对应时间的版...

题解主席树线段树

2019-08-21

0 505

luoguP3588_[POI2015]PUS

题意有一个\(n\)个数的序列，已知其中的\(k\)个数，然后有\(m\)个信息，每个信息给出区间\([l,r]\)，和\(k\)个数，表示区间\([l,r]\)中这\(k\)个数大于剩下的\(r-l+1-k\)个数，求出一个方案。分析抄做的第一题线段树优化建图的题目，很巧妙。 ...

题解线段树图论拓扑排序

2019-08-20

0 520

2019牛客多校第十场

B Coffee Chicken 题意定义一个字符串的斐波那契数列，求从第k位开始的后面十个字符。分析把第n项求出来是不可能的。斐波那契数列的增长是很快的，而且由于题目保证\(k<=min(|S(n)|,10^{12})\)，且只输出十个字符，因此其实只有前几十项是有...

题解思维分治数论线段树

2019-08-19

0 0