- 博客(279)
- 收藏
- 关注
RSS订阅
原创 NOI2019 退役记落幕记
刚刚考完NOI，忙着打游戏，就一直咕了，本来计划着一天通一个章节，五天就能通关，结果才通了三个章节，就突然莫名其妙收到通知开学时间提前了，变成了明天。既然已经正式成为了一名高三生，我觉得我还是要清理一下还咕咕咕着的事情，比如说写这篇游记。Not all stories can end on a happy noteNOI前去广二培训，然后就是天天被广二神仙吊打，怀疑人生，怀疑自己，哦哦哦哦...
2019-07-24 16:34:17
3638
2
原创 洛谷P5210/loj2570 [ZJOI2017]线段树 处理广义线段树的一类方法
题目分析处理广义线段树的一类套路方法。首先，定义原来的线段树为原树，并且将其改造一下，使得它能够管理的区间为[0,n+1][0,n+1][0,n+1]。定义左偏树（跟一种可并堆重名了2333）为一棵将原树上，所有是左儿子的点提取出来，构成的一棵树，每个点的父亲，是代表在其左边，与其代表区间相邻的区间，且深度比它浅的节点。画出来是这样的：定义右偏树为提取右儿子们，与在它右边深度比它浅的第一...
2019-06-26 15:55:18
1230
原创 codeforces 917D Stranger Trees 矩阵树定理+拉格朗日插值
题目分析把原树连成完全图，在原树中的边边权为xxx，否则为111。假设一棵生成树的权值是该生成树中所有边的权值之积，若我们将所有生成树权值相加，那么xkx^kxk的系数就是含有kkk条原树边的树的个数。现在我们假设边权代表这条边有多少重边，那么总生成树个数就是原来定义的生成树权值之和。总生成树个树可以用矩阵树定理求。设x=1,2,3...nx=1,2,3...nx=1,2,3...n，代入后...
2019-06-19 18:51:38
573
原创 CodeChef TREDEG Trees and Degrees NTT+生成函数
题目分析题目地址->here这是一道二合一题，对于50%的数据，有∑n≤105\sum n \leq 10^5∑n≤105，对于50%的数据有∑n≤2∗106,K=1\sum n \leq 2*10^6,K=1∑n≤2∗106,K=1。显然prufer编码，出现iii次的点度数为i+1i+1i+1。设f(i,j)f(i,j)f(i,j)表示考虑到第iii个点，此时的prufer序列长度...
2019-06-19 18:50:59
424
原创 洛谷P5333/bzoj5528/loj3102 [JSOI2019]神经网络 树形DP+生成函数
题目分析链划分显然，一条欧拉路是在一棵树上走一条链，然后跳到另一棵树上走一条链，再跳……可以利用DP求出，每棵树有多少种链划分方式（注意一条链“从这头走到那头”和“从那头走到这头”算两种不同的划分方式）DP方法：设f(x,i,0/1/2)f(x,i,0/1/2)f(x,i,0/1/2)表示以xxx为根的子树，xxx所在的链往子树里伸入的有0/1/2根，一共划分为iii条链的方案数。然后用那...
2019-06-03 20:16:32
654
原创 codeforces 1149E Election Promises Nim游戏
题目分析这题好喵啊。如果没有“任意修改相邻城市的税收”这个操作，就是个美滋滋的Nim游戏。接下来的思路就很巧妙了，将城市分组。所有出度为0的点为第0组，其他点为第mex(其可达节点的组编号)组。这个有两个性质：同一组不存在一对节点xxx,yyy，满足存在边(x,y)(x,y)(x,y)。对于第ttt组中的任意一个点，它可以到达第000到第ttt组，每一组中的至少一点。若每一组的...
2019-05-30 15:45:14
372
原创 loj2550/洛谷P4558/bzoj5318 「JSOI2018」机器人 性质分析＋DP
题目分析首先，同一根对角线上的行为决策必须一样（要么都往右要么都往下）。行走是循环的，走到最右就变成最左，走到最左就变成最右了，所以“一根对角线”的意义也是循环的，比如说下图每一种颜色的点都属于同一根对角线。假设有一根对角线，对于它上面的每一个点(x,y)(x,y)(x,y)，x+y=kx+y=kx+y=k。当(x,y)(x,y)(x,y)出了边界后，为了使它拥有合法的意义，需要（x+=...
2019-05-28 10:45:39
355
原创 bzoj3636 教义问答手册 分治
题目分析分块一种虽然过不了但是很喵的做法。设f[l,r]f[l,r]f[l,r]表示区间[l,r][l,r][l,r]的答案。bib_ibi表示区间[i−L+1,i][i-L+1,i][i−L+1,i]的权值和。则有f[l,r]=max(f[l,r−1],f[l,r−L]+br)f[l,r]=max(f[l,r-1],f[l,r-L]+b_r)f[l,r]=max(f[l,r−1],...
2019-05-23 11:03:00
396
原创 二次离线莫队
例题：洛谷 P5047题面图上的妹子好可爱啊(ˉ﹃ˉ)多组询问，求一个区间内的逆序对数，离线，n≤105n \leq 10^5n≤105，时限0.3s，空间限制32MB （好，不愧是lxl）二次离线莫队如果直接用莫队做这道题的话，每次移动都要来一遍树状数组，复杂度就是O(nnlogn)O(n \sqrt{n} \log n)O(nnlogn)的了。记([l1,r1],[l2,r2])...
2019-05-22 08:46:59
1952
原创 《从Unknown谈一类支持末尾插入删除的区间信息维护方法》学习笔记+UOJ #191代码（及HACK5原理，雾）
笔记做带末尾插入删除的区间信息维护）的数据结构题的方法：分块思路：每次插删操作暴力重构最后一块。支持插删操作，支持区间查询，支持在线二进制分组思路：若每次添加一个元素进数据结构里的复杂度比较高，则每次将这个元素单独放在最后一组，若最后一组与上一组的大小相同，就将这两组合并为同一组，不难发现最后得到的每个组大小都是2的次幂，并且互不相同，复杂度会是log\loglog级的。不支持删除...
2019-05-21 20:04:53
429
原创 洛谷P4707 重返现世 kMAX-MIN反演＋DP
题目分析kMAX-MIN反演设kMAX-MIN反演有反演系数函数f(∣S∣)f(|S|)f(∣S∣)，使得kMAX(S)=∑T≠∅,T⊂Sf(∣T∣)MIN(T)kMAX(S)=\sum_{T =\not \emptyset,T \subset S} f(|T|)MIN(T)kMAX(S)=T≠∅,T⊂S∑f(∣T∣)MIN(T)假设SSS集合里有nnn个数，分别是a1,a2......
2019-05-20 14:42:28
277
原创 UOJ #390 【UNR #3】百鸽笼 容斥＋DP
题目分析算法0每个管理员选哪一列，将构成一个长度为N−1N-1N−1的序列，序列的种数可以通过经典的将aaa个相同元素插入到一个没有该元素的长度为bbb的序列里问题，轻松求出。若一列iii要求有空笼，则标号iii只出现ai−1a_i-1ai−1次，然后算出每种序列的种数，按种数分配概率。期望得分：0算法1分析一下算法0错在哪——每种序列的出现概率并不是相等的，因为每一个管理员选择列的时...
2019-05-17 13:21:20
539
原创 洛谷P3553/bzoj3414 [POI2013]Inspector 二分答案+贪心
题目分析首先二分答案，就可以只判断这几条可不可行了。根据每个人的称述，我们先可以给这些人确定一个大致的“必须存在的区间”，而那些没有称述的人，根据boshi命名法，称其为“幽灵”。假设当前检查的时刻iii，必须存在的人数为sis_isi。nows：由于“必须存在的区间”，而导致当前时刻至少有多少人存在。people：当前已经被“使用”了的人数。ghost：当前使用了，且其所在区间还在...
2019-05-13 20:02:41
349
原创 bzoj2616 SPOJ PERIODNI 笛卡尔树+DP
题目分析建立出小根堆性质的笛卡尔树，于是每个节点可以代表一个矩形，其宽度为子树大小，高度为该节点记录的那一列高度-父节点那一列高度。设f(x,i)f(x,i)f(x,i)表示以xxx为跟的子树中放了iii个棋子的方案数。初始值：f(0,0)=1f(0,0)=1f(0,0)=1首先求出不在xxx的矩形中放棋子的方案数：f(x,i)=∑j=0if(ls(x),j)f(rs(x),i−j)f(x...
2019-05-13 15:54:53
292
1
原创 loj3042/bzoj5600/洛谷P5279 [ZJOI2019]麻将 DP+麻将自动机
题外话我这种辣鸡放到浙江分分钟暴毙啊。题目分析牌是两两不同的，相同大小的牌也是不同的假设现在有一个手头的牌的状态，则它可以表示为第iii个位置为第iii种牌取了多少张的字符串。现在我要判断我手头能不能组成一组胡牌。情况1：有七个对子，这个很好判断（设对子数为cntcntcnt，则要求cnt≥7cnt \geq 7cnt≥7）。情况2：可以拆成三面子一对子。这个有点难判断，所以在字符...
2019-05-07 21:30:53
540
原创 loj3059/bzoj5494/洛谷P5294 [HNOI2019]序列 单调栈+主席树
题目分析若a单调不升，如图，b全部相等显然比b不相等要优。那么∑i=1m(ai−b)2\sum_{i=1}^m (a_i-b)^2∑i=1m(ai−b)2，求导得∑ai2−2b(∑ai)+mb2\sum a_i^2-2b(\sum a_i)+mb^2∑ai2−2b(∑ai)+mb2，当导函数等于0时取到最小值，此时b=∑aimb=\frac{\sum a_i}{m}b=m∑ai也...
2019-05-04 15:38:16
367
原创 洛谷P5286/bzoj5489/loj3054 [HNOI2019]鱼 计算几何
题目分析不难发现需要枚举D和A，然后鱼头鱼尾分别处理。对于鱼尾，其实就是对着A的半平面内两条到D距离相等的线段组成的，枚举D后，将其他点极角排序，然后扫描线即可解决。对于鱼头，也就是BC这条线段要垂直于AD，且BC的中点在AD上。则预处理枚举每个BC，将这个点对存入它的垂直平分线的vector中，按照中点排序。然后枚举AD，找到AD所在直线的vector，二分查找vector中中点在AD上的...
2019-05-03 21:46:29
304
原创 bzoj5493/洛谷P5293/loj3058 [HNOI2019]白兔之舞 单位根反演+MTT+矩阵快速幂
题目分析设AAA为给定的矩阵。余数为ttt时的答案为：∑i=0LCLiAi[i mod k=t]\sum_{i=0}^LC_L^iA^i[i \bmod{k}=t]i=0∑LCLiAi[imodk=t]已知单位根反演的式子1k∑i=0k−1ωkin=[k∣n]\frac{1}{k} \sum_{i=0}^{k-1}...
2019-05-01 16:48:32
273
原创 loj3057/bzoj5492/洛谷P5292 [HNOI2019]校园旅行 性质分析优化建图+bfs
题目分析30分做法：初始，所有(x,x)(x,x)(x,x)和所有满足x,yx,yx,y同色且中间有边的(x,y)(x,y)(x,y)之间都有回文路径。将所有点对放入队列中，从两个端点开始往周围各找一个同色的点，就可以扩展出新点对，满足存在回文路径。复杂度O(m2)O(m^2)O(m2)。优化建图是这样的，首先只连上那些连接同色点的边，原图构成了若干连通块。一个回文串，例如11100111，...
2019-05-01 14:29:03
255
原创 洛谷P1721/bzoj4654/loj2087/uoj223 [NOI2016]国王饮水记 斜率优化
题目分析性质：所有积水高度小于等于1号点的点可以直接丢掉。所以，将留下来的水的高度都改成其原本的高度-1号点高度，最后答案再加上1号点的高度。假如被要求进行两次合并，有两杯水h1<h2h _ 1<h _ 2h1<h2，则一定先合并低的，再合并高的。证明：先合并低的：12(12h1+h2)=14h1+12h2\frac{1}{2}(\frac{1}{...
2019-04-30 16:30:51
474
原创 loj3056/洛谷P5288 [HNOI2019]多边形
题目分析容易发现，一条边将多边形分成了“面对n点”的一侧和“背对n点”的一侧。在“背对n点的一侧”，可以找到这条边旋转后，代码#include<bits/stdc++.h>using namespace std;#define RI register intint read() { int q=0;char ch=' '; while(ch<'0'||...
2019-04-28 19:04:09
260
原创 HNOI2019 头铁记爆肝记
Day0省选前的模拟考试连环爆炸，说是爆炸，其实也不算，因为出来的分基本上都和预估分差不多，至于为啥考那么点分，原因就一条——我菜。我还真没犯多少傻逼错误，真的就是单纯地做不出来而已。结果弄得心态挺爆炸的。不过一想，我去年也打过Ag了，至于集训队真是想都不敢想的事情，于是我就只有两种结果：若是进了省队，那很大可能不会有新收获，要多浪费学文化课的时间，然后还要大夏天地清早起床坐公交车跑到雅礼...
2019-04-14 13:48:35
1179
4
原创 洛谷P4516/loj2546/bzoj5314 [JSOI2018]潜入行动 树形DP复杂度证明
题目分析设f(x,i,0/1,0/1)f(x,i,0/1,0/1)f(x,i,0/1,0/1)表示以节点xxx为根的子树，用掉iii个窃听器，xxx上是否有窃听器，xxx是否被窃听的方案数。转移的话枚举xxx的儿子的子树中用了多少窃听器。注意到假设我DP过程中考虑过了xxx子树中sz(x)sz(x)sz(x)个点，那么它们上面放的窃听器不会超过sz(x)sz(x)sz(x)个，利用szszsz...
2019-03-27 20:01:00
593
原创 loj 523 「LibreOJ β Round #3」绯色 IOI（悬念） 霍尔定理+基环树+线段树
题目分析神仙题（确信）首先，j−aij-a _ ij−ai和ai−ja _ i-jai−j互为相反数，若其中最小值为bib _ ibi，则一个为bib _ ibi一个为m−bim-b _ im−bi。（以下运算均在模mmm意义下进行）j−ai=bij-a _ i = b _ ij−ai=bi即j=ai+bij= a _ i + b _ ij=ai+biai−j=bia _...
2019-03-20 20:08:19
534
原创 二分图匹配相关结论及方案构造法
最小点覆盖=匹配数方案：从左侧所有未匹配点出发，交错走非匹配边和匹配边模拟匹配，未走到的所有左侧点和走到的所有右侧点即为方案。（用网络流做的：和源点不相连的左侧点与和源点相连的右侧点）最大点独立集=总点数-匹配数方案：将最小点覆盖取反。最小路径覆盖：将每个点一拆为2，若原图存在一条边(x,y)，在新图中连边(x,y’)，原图点数-新图匹配数方案：新图中每一对匹配代表的边在原图中为某条路径...
2019-03-17 19:23:29
556
原创 codeforces1063F String Journey SAM+DP+dfs序+线段树
题目分析实际上，分出来的所有ttt的长度应该是连续的，因为如果不连续的话，删掉过长的ttt首尾几个字符即可。于是可知，ti+1t_{i+1}ti+1应该是tit_iti删掉首字母或者尾字母形成的字符串。将原串反过来，前缀就变成了后缀。设dp(i)dp(i)dp(i)表示以字符iii结尾划分为最后一个字符串，可以划分的最大长度。由于以iii结尾的字符串和以i−1i-1i−1结尾的字符串，...
2019-03-15 08:07:53
376
原创 codeforces1019E Raining season 边分治+闵可夫斯基和+凸包
题目分析假设你准备把所有“可能”成为最长路径的路径都提取出来，显然是用树分治啦，这题中，边分治比点分治更方便。边分治教学->here边分治的套路，第一步将多叉树转为二叉树，对于新增加出来的边，它的aaa和bbb都是0。然后集中处理经过某一条边的路径，一条边将整棵树分为两个部分，这条路径由在这两个部分里的部分组成，于是我们要合并两个部分的信息。什么是可能成为最长路径的路径？将每条路径看...
2019-03-14 14:50:32
748
原创 模拟费用流模型总结
基础模型你在玩一款益智推箱子游戏。数轴上有nnn个箱子和mmm个传送点，第iii个箱子在xix_ixi，第iii个传送点在yiy_iyi。当箱子放在传送点上时可以传送走，每个传送点可以最多送走一个箱子，传送走所有箱子视为通关。你可以做的唯一操作是将一个箱子向左推一个单位，耗费代价1，过程中允许有多个箱子在同一位置或者箱子在传送点位置但没被送走，问你通关的最小代价。只要从左到右依次考...
2019-03-11 22:04:35
4802
4
原创 洛谷P3676 小清新数据结构题 动态点分治
题目分析设整棵树的点权和为WWW，sis_isi表示以iii为根的子树的点权和，则无论哪个点为根，∑i=1nsi(W−si)=P\sum_{i=1}^n s_i(W-s_i) =P∑i=1nsi(W−si)=P都是个定值。这是因为可以看做当两个点i,ji,ji,j分别在以某个点为根的子树内外时，PPP加上vivjv_iv_jvivj的贡献，也就是说P=∑i=1n∑j=1ndist(...
2019-03-06 10:22:12
302
原创 bzoj3512 DZY Loves Math IV 欧拉函数+杜教筛
题目分析好难不会QAQ。设S(n,m)=∑i=1mϕ(im)S(n,m)=\sum_{i=1}^m \phi(im)S(n,m)=∑i=1mϕ(im)设www为nnn的所有质因子的（一次方）乘积，v=nwv=\frac{n}{w}v=wn，d=gcd(w,i)d=gcd(w,i)d=gcd(w,i)，根据欧拉函数的性质，则有：S(n,m)=v∑i=1mϕ(iw)=v∑i=1mϕ(i)ϕ...
2019-03-04 17:17:52
323
原创 51nod 1965 奇怪的式子 min_25筛（扩埃筛）
题目分析首先式子可以写成∏i=1nσ0(i)i∏i=1nσ0(i)μ(i)\prod_{i=1}^n \sigma_0(i)^i \prod_{i=1}^n \sigma_0(i)^{\mu(i)}∏i=1nσ0(i)i∏i=1nσ0(i)μ(i)，然后分成两部分分别计算。第一部分也就是∏i=1nσ0(i)i\prod_{i=1}^n \sigma_0(i)^i∏i=1nσ0(i...
2019-03-02 13:51:51
206
原创 51nod 1847 奇怪的数学题 莫比乌斯反演+min_25筛+杜教筛
题目分析莫比乌斯反演所谓的sgcd(i,j)sgcd(i,j)sgcd(i,j)，就是gcd(i,j)gcd(i,j)gcd(i,j)除以其最小的一个质因子。我们记g(x)=(xminpri(x))Kg(x)=(\frac{x}{minpri(x)})^Kg(x)=(minpri(x)x)K，答案就是求∑i=1n∑j=1ng(gcd(i,j))\sum_{i=1}^n \sum_{j=1}^...
2019-03-02 08:34:52
343
原创 与扩展埃氏筛（min_25筛？）玩耍
这篇博客是一年前写的……那时这东西好像还是个Cai佬偷偷教我们的黑科技但现在似乎已经人尽皆知了……Cai佬说这东西叫做扩展埃氏筛，但似乎它和min25筛是一个东西？与素数玩耍例题： loj6235 区间素数个数设sum(x)sum(x)sum(x)表示小于等于x的素数个数。假设我很蠢（这件事根本不用假设好吗)，连10以内的素数有哪些都不知道，只知道1不是素数。那么我就会令sum(x)=x...
2019-03-01 15:49:45
762
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人