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)

/ 注册

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

2019CCPC网络赛

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

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

2019-08-25

0 628

poj3415_Common Substrings

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

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

2019-08-25

0 341

luoguP3261_[JLOI2015]城池攻占

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

题解左偏树可并堆 dfs

2019-09-01

0 370

2019icpc南京网络赛_F_Greedy Sequence

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

题解主席树线段树

2019-09-01

0 445

2018icpc宁夏邀请赛_L_Continuous Intervals

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

题解线段树单调栈

2019-09-06

0 433

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 418

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 530

2019icpc徐州网络赛_I_query

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

题解二位偏序树状数组

2019-09-10

0 449

bzoj2141_排队

题意给定\(n\)个数，每次交换两个数，输出交换后的逆序数。分析交换两个数只会影响到对应区间内的逆序数，具体为减少区间\([l+1,r-1]\)中比\(a[r]\)大的数的个数，增加比\(a[r]\)大的数的个数，减少比大的数的个数，\(a[l]\)增加比\(a[l]\)小的数的个...

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

2019-09-10

0 413

Codeforces1093E_Intersection of Permutations

题意给定两个排列a和b，两种操作，交换b_i和b_j，询问a[l_a...r_a]和b[l_b...r_b]有多少个数相同。分析由于给的是排列，保证b的每个数都有a的对应，构造数组c，c[i]表示b[i]在a数组中的位置。所以询问就变成询问c[l_b...r_b]中有多少个值...

题解树套树思维

2019-09-11

0 510