- 博客(158)
- 收藏
- 关注
RSS订阅
原创 高中数学必备知识
∑i=1n\huge\sum_{i=1}^ni=1∑n即int ans=0;for(int i=1;i<=n;i++)ans+=i;∏i=1n\Huge\prod_{i=1}^ni=1∏n即int ans=0;for(int i=1;i<=n;i++)ans*=i;x∣y x整除y,即...
2019-04-19 19:53:02
412
4
原创 BSGS & EXBSGS 算法略解
BSGSBSGSBSGS要解决的问题:给定整数a,b,pa,b,pa,b,p，其中a,pa,pa,p互质，求一个非负整数xxx,使得ax≡b(mod p)a^x \equiv b(mod~p)ax≡b(mod p)首先我们先可以了解一下,欧拉定理aφ(n)≡b(mod n)a^{\varphi(n)}\equiv b(mod~n)aφ(n)≡b(mod&nbs...
2019-04-18 15:09:48
483
4
原创 陨石的秘密
设fi,a,b,cf_{i,a,b,c}fi,a,b,c表示当前深度小于等于iii并且有aaa对{ }\{~\}{ },bbb对[ ][~][ ]，ccc对( )(~)( )的方案数，根据优先级，将fi,a,b,cf_{i,a,b,c}fi,a,b,c分成左串，以及右串，现在假设是左串往外套一层括号({ }\{~\}{&nb...
2019-10-24 10:44:00
1356
原创 后缀数组练习题
POJ1743思路由于可能转调，现设匹配长度lenlenlen，A[i∼i+len−1]=A[j∼j+len−1]−w(j>i+len−1)A[i\sim i+len-1]=A[j\sim j+len-1]-w(j>i+len-1)A[i∼i+len−1]=A[j∼j+len−1]−w(j>i+len−1)，w就是转调值，但这样并不好处理。由于是区间加上(...
2019-08-21 08:48:54
239
原创 AC自动机练习题
caioj1465【题意】给出有一个L∗CL*CL∗C的字符地图，地图的行与列都从000开始编号然后给出一些字符串，求出这些字符串在字符地图上的位置。（数据保证有唯一解）输出字符串第一个字母的坐标和字符串的方向字符串的方向是指字符串的走向A表示正北，B表示东北，C表示正东，D表示东南，E表示正南，F表示西南，G表示正西，H表示西北且保证字符串的方向是固定的【输入格式】第一行输入L...
2019-08-20 14:31:43
323
原创 EXKMP练习题
caioj1462【题意】给出26个字母所代表的权值和一个字符串，要求把字符串分成两段（每一段长度至少为1，也就是必须要有字符），假如这一段子串是一个回文串，那么加上该串所有字符权值之和，求最大的权值和。【输入格式】输入一个整数T，表示数据组数每组数据第一行输入26个数，表示26个字母的权值，第二行输入一个字符串（保证字符串内全是小写字母,2<=字符串长度<=500000）...
2019-08-19 15:23:27
275
原创 KMP练习题
这里放一些KMP的题解。caioj1457【题意】我们定义两个字符串aaa和bbb$的乘法： a∗ba*ba∗b ，就是把它们连接起来。比如： aaa = “abcabcabc” ，bbb= "def"def"def" ，那么 a∗*∗b = “abcdef”.由此推广，字符串的幂运算: a0a^0a0 = “” (空字符串)a(n+1)=a∗(an)...
2019-08-19 10:15:01
226
原创 字符串学习笔记
在这里放一些浅显易懂的证明吧。kmp\operatorname{kmp}kmp证明:next[i]next[i]next[i]表示“以i结尾的非前缀子串“与”前缀子串”能够匹配的最长长度，即:next[i]=max{j},j<i,A[1∼j]=A[i−j+1∼i]next[i]=max\begin{Bmatrix}j\end{Bmatrix},j<i,A[1\s...
2019-08-15 14:32:16
247
1
原创 lb摸鱼系列1
题目描述传送门思路就是一道火星人的升级版。其实核心思想就是康托，但5e5的全排列受不鸟，考虑优化康托。其实康托个数就是排列个数，根据n！=n∗(n−1)∗(n−2)∗⋯∗1n！=n*(n-1)*(n-2)*\cdots*1n！=n∗(n−1)∗(n−2)∗⋯∗1因此第一个位置可以有n种选择，由于第一个数被选了，第二个数只有(n-1)种选择，以此类推，恰好为n！n！n！，正好对应进制数，...
2019-08-14 09:36:08
143
原创 主席树学习笔记
前置知识权值线段树权值线段树之所以会带上“权值”二字，是因为它是记录权值的线段树。因此需要用到离散化操作来处理a[1-n]。记录权值指的是，每个点上存的是区间内的数字出现的总次数。因此，叶子节点存的就是单个值的次数咯。学完这个之后呢，我们就差不多理解了权值线段树了，并没有什么卵用。离散化就不讲了。初次尝试什么？你要我求区间第k大值，那好，我每插入一个值，我就建多一颗线段树。时间...
2019-08-09 21:05:58
185
原创 [SHOI2002]滑雪
题面描述我真的不会记忆化搜索思路记忆化搜索琪琪乖乖的。状态挺好想的，记忆化搜索自己想不起来了，看了题解才恍然大悟。AC code#include<cstdio>#include<algorithm>#include<cstdlib>#include<cstring>#include<cmath>using name...
2019-08-09 16:16:15
106
原创 [BZOJ3779]重组病毒
题面描述穷哭了思路难吗?难码.首先观察一下操作一，就是一个access，但是要改变子树啊，LCT不缁瓷，所以线段树稍微维护一下。怎么维护是一个大难点啊。是要分类讨论的。先找出实右子树在原数上的根xxx。情况rt=xrt=xrt=x，直接修改整颗树。rtrtrt在子树中，令y=rty=rty=rt，跳到xxx的儿子上，由于xxx的整颗子树，都不用经过x就可以到达yyy，即可证明...
2019-08-08 20:32:44
174
原创 [SDOI2011]染色
题面描述滑稽思路初看不可做，再看不可做。之后过了几天之后，才想起来有这道题。铁头娃LCT\operatorname{LCT}LCT来了。由于是统计不同的颜色段数，那么一个颜色段与另一颜色段接壤的地方，也就是左端点的col\operatorname{col}col，以及右端点的col\operatorname{col}col。转化成LCT\operatorname{LCT}LC...
2019-08-08 20:13:10
231
原创 [BJOI2014]大融合
题面描述题面不可描述思路貌似LCT\operatorname{LCT}LCT瞎搞维护一下虚儿子就行了。但细节比较多啊。通过瞎搞的规律，我们可以发现，答案貌似就是(xxx的儿子数+1+1+1)∗*∗(yyy的儿子数+1+1+1)。经过询问操作的一系列操作，其实就等价于虚儿子+1+1+1∗*∗虚儿子+1+1+1好了，就这么简单。记得linklinklink的时候，将yyy调到所在辅助...
2019-08-08 19:56:45
116
原创 [SDOI2017]树点涂色
题面描述传送门思路代码居然出奇的短想都不想LCT\operatorname{LCT}LCT首先观察一下opt=1opt=1opt=1，这不就是一个奇奇怪怪♂ 的accessaccessaccess吗？想想accessaccessaccess的操作，实际上就是实虚边的切换。由于建树时是全部虚边，恰好就对应每个点的颜色不一样，那么每个点到根节点的权值就恰好是它的深度(dep[rt]=1d...
2019-08-07 08:31:08
133
原创 [HDOJ4699]Editor
题面描述传送门思路大概就是两个栈不断出栈入栈，一个主栈，一个辅助栈，辅助栈用来存储当前光标以后的所有值。AC code#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define ll long longusing namespace std...
2019-08-03 08:55:23
163
原创 [BZOJ2759]一个动态树好题
题面描述传送门思路思考一下不难发现应该至少有一个环(没环貌似不能求解)，也就是下面这样一个同余方程组{x1≡k1∗x2+b1(mod10007)x2≡k2∗x3+b2(mod10007)x3≡k3∗x4+b3(mod10007)⋯⋯xn≡kn∗x1+bn(mod10007)\begin{cases}x_1\equiv k_1*x_2+b_1(\operatorname{mod} 1...
2019-08-02 11:01:26
187
原创 Qtree LCT系列
Qtree1,2,3暂缺Qtree4思路总是有机房大佬问我怎么做(抄题解不就好了吗？)，那我就讲一讲我紊乱的思路吧。应该不难想到边权下放到子节点，有了这个基础，我们对细节的处理就不用那么模糊了。先上定义：lslsls为当前辅助树以中序遍历形成的链(在原树上也是一条链)，严格以链的开头为起点，往深度递增方向拓展，找到白节点则返回值，找不到返回负无穷。rsrsrs为当前链的结尾，往深度递减...
2019-07-19 21:19:55
217
原创 史上最菜的splay讲解
先了解一下什么是平衡树吧。之后进行各种玄学操作，但都离不开平衡树的基本性质:满足根存在一性质，大于左子树的同一性质，小于右子树的同一性质请记住这句话。定义结构体(以普通平衡树为例):struct node{int d,n,c,f,son[2];}t[N];int len,root;//son[0]为左，son[1]为右先讲讲五个基本操作吧。updateupdateupdate操作(...
2019-07-10 11:05:33
145
原创 [CH5202]自然数拆分Lunatic版
题面描述传送门思路好题，适宜考前看。仔细分析题意，实际上就是一道完全背包，111~NNN这NNN个自然数构成NNN种物品，每种物品都可以使用无数次，背包容积也是NNN。AC code#include<cstdio>#include<cstring>#include<cstdlib>#include<cmath>#include&l...
2019-07-06 16:31:16
179
原创 [CH5105]Cookies
题面描述传送门思路这么一道无序的题目，怎么弄出来的DP！经过lydlydlyd的玄学引导，详见蓝书。可以尝试将gig_igi从大到小排序，因为贪婪值较大的，拥有的饼干越多，对答案的贡献就越小。排序之后，第iii个孩子的饼干只有两种情况:饼干数小于第i−1i-1i−1个孩子拥有的饼干数，即ai=i−1a_i=i-1ai=i−1饼干数等于第i−1i-1i−1个孩子拥有的饼干数，...
2019-07-06 09:41:51
182
原创 动态规划经典例题
把一个序列AAA变成非严格单调递增的(单调不下降的)，至少需要修改多少个数。序列AAA的总长度减去AAA的最长不下降子序列长度即为答案。证明:对于最长不下降子序列中相邻两数Ai,AjA_i,A_jAi,Aj，之间有Aj+1,Aj+2,⋯ ,Ai−1A_{j+1},A_{j+2},\cdots,A_{i-1}Aj+1,Aj+2,⋯,Ai−1，需要改变这...
2019-07-05 08:39:26
780
原创 [USACO08FEB]修路Making the Grade
题面描述传送门思路(以下引理借鉴lydlydlyd)引理:在满足SSS最小化的前提下，一定存在一种构造序列BBB的方案，使得BBB中的数值都在AAA中出现过下面给出以递增为例的证明:(递减是类似的)证明:命题在N=1N=1N=1时显然成立。设引理在N=k−1N=k-1N=k−1时成立，序列为B1B_1B1~Bk−1B_{k-1}Bk−1。当N=kN=kN=k时，Bk−1≤A...
2019-07-05 08:17:05
231
原创 [SDOI2016]征途
题面描述传送门思路方差s2=1k∑i=1k(vi−vˉ)2s^2=\frac{1}{k}\sum_{i=1}^k(v_i-\bar{v})^2s2=k1i=1∑k(vi−vˉ)2vˉ=1k∑i=1kvi\bar{v}=\frac{1}{k}\sum_{i=1}^k v_ivˉ=k1i=1∑kvis2=1k∑i=1k(1k∑j=1kvj−vˉ)2s^2=\frac{1}{k}...
2019-07-05 07:13:42
185
原创 [HDU2829]Lawrence
题面描述传送门思考状态转移方程:Fi,p=min(Fj,p−1+∑x=j+1i∑y=x+1iax∗ay)F_{i,p}=\min(F_{j,p-1}+\sum_{x=j+1}^i\sum_{y=x+1}^ia_x*a_y)Fi,p=min(Fj,p−1+x=j+1∑iy=x+1∑iax∗ay)∑x=j+1i∑y=x+1iax∗ay=∑x=j+1iax∑y=x+1iay=∑x...
2019-07-03 15:35:19
82
原创 [HDU3480]Division
题面描述传送门思路排序之后显而易见的状态转移方程Fi,p=min(Fj,p−1+(ai−aj+1)2)F_{i,p}=\min(F_{j,p-1}+(a_i-a_{j+1})^2)Fi,p=min(Fj,p−1+(ai−aj+1)2)决策单调性自己证明。踢队头Fk,p+(ai−ak+1)2≤Fj,p+(ai−aj+1)2F_{k,p}+(a_i-a_{k+1})^2\le...
2019-07-03 11:55:37
89
原创 [HDU3045]Picnic Cows
题面描述传送门思路这道题看一看，貌似就是小的跟小的混，大的跟大的混嘛简单来说就是从小到大排序。状态转移方程sss为前缀和Fi=min(Fj−(i−j)∗aj+1+si−sj)F_i=\min(F_j-(i-j)*a_{j+1}+s_i-s_j)Fi=min(Fj−(i−j)∗aj+1+si−sj)决策单调性设Fj−(i−j)∗aj+1+si−sj≥Fk−(i−k)...
2019-07-03 10:42:14
156
原创 [NOI2005]瑰丽华尔兹
题面描述传送门思路这个代码真是又臭又长思想很简单，相信大家做单调队列应该深有感受了。就不讲了。AC code#include<cstdio>#include<cstring>#include<cstdlib>#include<cmath>#include<algorithm>#define gc getchar()...
2019-07-02 18:53:10
142
原创 [CEOI2004]锯木厂选址
题面描述传送门思路状态转移方程tottottot为所有树都运到山下锯木厂的费用，disdisdis为到山下锯木厂的距离，sss为树的重量前缀和。Fi=min(tot−disj∗sj−disi∗(si−sj))(j<i)F_i=\min(tot-dis_j*s_j-dis_i*(s_i-s_j))(j<i)Fi=min(tot−disj∗sj−disi...
2019-07-02 15:24:53
134
原创 [APIO2014]序列分割
题面描述传送门思路对于同一种分割方式，顺序不会影响最终结果。分析样例(4,1,3,4,0,2,3)(4,1,3,4,0,2,3)(4,1,3,4,0,2,3)，如果先切555,则(4+1+3+4+0)∗(2+3)=60(4+1+3+4+0)*(2+3)=60(4+1+3+4+0)∗(2+3)=60再切333,则(4+1+3)∗(4+0)=32(4+1+3)*(4+0)=32(4+1+3...
2019-07-02 12:24:06
240
原创 [HDU2993]MAX Average Problem
题面描述传送门思路状态转移方程Fi=max(Fj,sumi−sumji−j)F_i=\max(F_j,\frac{sum_i-sum_j}{i-j})Fi=max(Fj,i−jsumi−sumj)决策单调性设有j<k≤i−mj<k\le i-mj<k≤i−mmax(Fk,sumi−sumki−k)≥max(Fj,sumi−sumji−...
2019-07-02 10:17:38
194
原创 [HDU3507]Print Article
题面描述传送门思路状态转移方程:(sss为前缀和)Fi=min(Fj+(si−sj)2+m)F_i=\min(F_j+(s_i-s_j)^2+m)Fi=min(Fj+(si−sj)2+m)决策单调性Fj+(si−sj)2+m≥Fk+(si−sj)2+mF_j+(s_i-s_j)^2+m\ge F_k+(s_i-s_j)^2+mFj+(si−sj)2+m≥Fk+(si...
2019-07-01 21:21:59
177
原创 [APIO2010]特别行动队
题面描述传送门思路状态转移方程应该很好想:设sss为战斗力前缀和，那么有Fi=max(Fj+a∗(si−sj)2+b∗(si−sj)+c)F_i=\max(F_j+a*(s_i-s_j)^2+b*(s_i-s_j)+c)Fi=max(Fj+a∗(si−sj)2+b∗(si−sj)+c)决策单调性设有Fk+a∗(si−sk)2+b∗(si−sk)+c≥Fj+a∗(si...
2019-07-01 20:34:11
126
原创 [USACO08MAR]土地征用Land Acquisition
题面描述传送门思路瞎扯乍一看，貌似找不到什么有序的东西。先排序吧(第一关键字为xxx坐标，第二关键字为yyy坐标，都以从小到大排序)。类似下图发现相邻的两块土地(排序后)i,i+1i,i+1i,i+1,如果yi<yi+1y_i<y_{i+1}yi<yi+1，那么买第i+1i+1i+1块土地，顺便可以带上第iii块土地(岂不美哉！，买一送一啊！)...
2019-07-01 16:18:48
141
原创 [ZJOI2007]仓库建设
题面描述传送门思路决策单调性其实很容易想到方程，Fi=min(Fj+ciF_i=\min(F_j+c_iFi=min(Fj+ci+++[j+1,i−1][j+1,i-1][j+1,i−1]的物品运到iii的花费)关键在于如何快速求到[j+1,i−1][j+1,i-1][j+1,i−1]的物品运到iii的花费运用前缀和思想，我们将[j+1,i−1][j+1,i-1][j+1,i...
2019-07-01 13:05:02
174
原创 [HNOI2008]玩具装箱TOY
题面描述传送门思路理解题意之后，发现斜率优化真是一个大坑FiF_iFi为最近一个箱子装到第iii件物品的花费首先我们来看看状态转移方程(sumsumsum为前缀和)Fi=min(Fi,Fj+(sumi−sumj+(i−(j+1))−L)2)F_i=\min(F_i,F_j+(sum_i-sum_j+(i-(j+1))-L)^2)Fi=min(Fi,Fj+(sumi−su...
2019-06-30 19:49:50
111
原创 [LuoguP1714]切蛋糕
题面描述传送门思路太水了，看看就好。AC code#include<cstdio>#include<algorithm>#include<cstring>#include<cstdlib>#include<cmath>#define gc getchar()#define ll long long using na...
2019-06-28 15:59:29
138
原创 [SCOI2010]股票交易
题面描述传送门思路这道题DP的很明显啊(可惜我就是不会写啊)提前声明:这里的nnn为TTT,mmm为MaxPMaxPMaxP,t为WWW,a为APiAP_iAPi,c为BPiBP_iBPi,b为ASiAS_iASi,d为BSiBS_iBSi状态转移方程:Fi,j={Fi−1,j−a∗j(j≤b)Fi−t,k−a∗j+a∗k(0≤k≤j−1&j−k≤d)Fi−t...
2019-06-28 14:34:26
117
原创 [SCOI2009]生日礼物
题面描述传送门思考本来想用二分的，读完数据之后，又发现不用了。然而需要开多一个数组ppp记录颜色最近出现的位置，以便进行玄学操作当达成目标(now==endnow==endnow==end)时,if(now==end){ while(l<i&&p[a[l].col]!=a[l].p)++l;//不影响，而且更短 ans=min(ans,(ll)a[i].p...
2019-06-28 11:33:07
99
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人