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)

/ 注册

全部文章（共12篇）

2019牛客多校第一场

A Equivalent Prefixes 题意给两个序列a和b，找出最大一个位置p，使得两个序列1-p的子序列中，任意区间的最小值位置相同。分析最小值的位置考虑用单调栈预处理出每个数作为最小值的最左和最右的位置，然后从1开始枚举，对于某个位置i，如果\(a_i\)和\(b_i\)作为...

单调栈数学推导积分异或线性基 dp 线段树线段树优化dp 大数题解

2019-07-25

0 583

2019牛客多校第二场

A Eddy Walker 题意一个0到n-1的环，初始在0，每次随机前进或后退一格，当所有点都访问过就结束，问结束时站在k的概率是多少。(注意输出的是前缀积) 分析一开始站在0，最后显然不可能在0，剩下n-1格，随机数打表发现概率相同，都为\(\frac{1}{n-1}\) 代码 ...

题解概率打表 BM递推图论状压优先队列 dp 线段树矩阵暴力搜索单调栈

2019-07-25

0 591

2019牛客多校第四场

A meeting 题意给一棵树，以及树上的\(k\)个点，要求一个点使得这k个点到这个点的最大距离最小。分析简单的做法就是求出这\(k\)个点在树上的最远距离，类似于求树直径的做法，然后点肯定取在直径一半处。代码 #include <bits/stdc++.h> u...

题解字符串后缀数组回文树单调队列线段树 dfs 最短路分层图最短路 dp 树的直径

2019-07-27

0 491

2019牛客多校第七场

A String 题意给定一个01串，求最少的划分次数，使得每部分的01串都是循环字典序最小。分析从最长的整个串贪心，暴力判断是否是循环字典序最小，若是，直接输出前面的串，然后后面的串再进行新一轮判断。代码 #include <bits/stdc++.h> using...

题解贪心字符串模拟前缀和线段树思维权值线段树

2019-08-09

0 523

2019牛客多校第十场

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

题解思维分治数论线段树

2019-08-19

0 0

luoguP3588_[POI2015]PUS

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

题解线段树图论拓扑排序

2019-08-20

0 520

uoj218_火车管理

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

题解主席树线段树

2019-08-21

0 505

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

2018icpc宁夏邀请赛_L_Continuous Intervals

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

题解线段树单调栈

2019-09-06

0 421

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