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) 杂七杂八(41) 水题(1) 牛客网(2) 牛客网错题总结(1) 算法四(2) 题解(1)

/ 注册

全部文章 / 未归档（共70篇）

2019icpc徐州网络赛_I_query

题意给定一个序列，多次询问区间\([l,r]\)中满足\(min(a[i],a[j])==gcd(a[i],a[j])\)的数对\((i,j)\)数。分析其实就是求区间有倍数关系的数对数。由于序列是全排列，所有有倍数关系的数对数只有\(nlogn\)个，因此可以暴力求出所有数...

题解二位偏序树状数组

2019-09-10

0 442

2019icpc南昌网络赛_I_Yukino With Subinterval

题意给定一个序列，两种操作，单点修改，询问区间\([l,r]\)值域在\([x,y]\)范围内的连续段个数。分析原数组为\(a\)，构造一个新的数组\(b\)，\(b[i]=(a[i]==a[i-1])?0:a[i]\)，这样将连续段转化为左端点的一个数来表示。询问就可以转化...

题解树套树树状数组权值线段树思维

2019-09-10

0 511

2019icpc徐州网络赛

A Who is better? 题意 excrt+斐波那契博弈分析 Java的BigInteger对象默认为null，不能直接比较。代码 import java.math.BigInteger; import java.util.Scanner; public class Mai...

题解数论博弈并查集思维暴力 KMP 字符串回文树线段树树形dp 枚举

2019-09-07

0 415

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