- 博客(85)
- 资源 (1)
- 收藏
- 关注
RSS订阅
原创 DTOJ4837 数组对
有两个长度为nnn的数组a1,a2,⋯ ,ana_1,a_2,\cdots,a_na1,a2,⋯,an和b1,b2,⋯ ,bnb_1,b_2,\cdots,b_nb1,b2,⋯,bn，请同时维护这两个数组，支持三种操作：对于三种操作均有d∈{0,1},1⩽l⩽r⩽nd\in\{0,1\},1\leqslant l\leqslant r\leqslant nd∈{0,1},1⩽l⩽r⩽n。第一行两个整数n,mn,mn,m，表示数组长度和操作个数。第二行nnn个整数a1,a2,⋯ ,ana_1,a
2022-10-24 22:11:41
253
原创 洛谷P7916 [CSP-S 2021]交通规划
洛谷P7916 [CSP-S 2021]交通规划Part1 k⩽2k\leqslant 2k⩽2的情况Step1 分析Step2 计算分界线上边权之和如果你没有学习过对偶图等知识，那么对你来说其他题解可能有点难理解，但这篇题解不会！在阅读这篇题解之前，你不需要掌握任何高深的知识，就可以学会这道题的做法Part1 k⩽2k\leqslant 2k⩽2的情况Step1 分析首先，k=1k=1k=1的情况非常简单，你只需要把所有点染成相同颜色即可，这时候答案为000，显然是最小的而对于k=2k=2k=2
2021-11-15 22:39:01
1192
1
原创 浅谈快速傅里叶变换FFT
浅谈快速傅里叶变换FFT前置知识FFT的思想前置知识在学习快速傅里叶变换前，你需要先了解一下快速傅里叶变换吧快速傅里叶变换 (fast Fourier transform), 即利用计算机计算离散傅里叶变换（DFT)的高效、快速计算方法的统称，简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。——百度百科额，好像还是不知道啥是快速傅里叶变换啊……
2021-02-08 21:34:56
337
原创 洛谷P4609 [FJOI2016]建筑师
题目题目描述小Z是一个很有名的建筑师，有一天他接到了一个很奇怪的任务：在数轴上建 nnn 个建筑，每个建筑的高度是111到nnn之间的一个整数小Z有很严重的强迫症，他不喜欢有两个建筑的高度相同另外小Z觉得如果从最左边（所有建筑都在右边）看能看到AAA个建筑，从最右边（所有建筑都在左边）看能看到BBB个建筑，这样的建筑群有着独特的美感现在，小Z想知道满足上述所有条件的建筑方案有多少种如果建筑iii的左(右)边没有任何建造比它高，则建筑iii可以从左(右)边看到两种方案不同，当且仅当存在某个建筑在
2021-01-18 22:21:26
127
原创 洛谷P5395 第二类斯特林数·行
题目题目描述第二类斯特林数{nm}\begin{Bmatrix} n \\m \end{Bmatrix}{nm}表示把nnn个不同元素划分成mmm个相同的集合中（不能有空集）的方案数给定nnn，对于所有的整数i∈[0,n]i\in[0,n]i∈[0,n]，你要求出{ni}\begin{Bmatrix} n \\i \end{Bmatrix}{ni}由于答案会非常大，所以你的输出需要对167772161167772161167772161（225×5+12^{25}\times 5+1225×5+
2021-01-18 22:11:22
141
原创 变、不变——NOIP2020游记
前言（Day0）2020年，的确是一个不平凡的年，疫情、洪水、贸易战……不仅对于国家，对于我，也是不平凡的此时此刻，我正坐在去往福州的动车上，想半年前，初二的我跟一群高中的神仙，坐着同样的动车，到同样的福州师大附中考试不变的人、不变的地方、不变的电脑……这一切，都没有变变的是什么，我问自己？许久后，我得到了答案：变的，是目标半年前的省选，就是一次划水，去考试的路上，我还不慌不忙地写着生物中考练习，一趟就做了半本，最后考试也抱了一个鸭蛋回家但是，这一次不同，这一次，是决定我的暑假行程的一次重要考试
2021-01-18 22:01:53
209
1
原创 DTOJ5021 最近公共祖先
DTOJ5021 最近公共祖先题目题目描述输入格式输出格式样例样例输入样例输出数据范围与提示题解题目注：本题来源于2020牛客暑期多校训练营（第六场）D题data structure题目描述作为此次 NOIP 模拟的最后一道题，宫水三叶决定把题意说得简单一点给一棵大小为nnn的以rtrtrt为根的树有mmm组询问，每次询问 l,r,xl,r,xl,r,x，你要回答有多少l⩽a<b⩽rl \leqslant a < b \leqslant rl⩽a<b⩽r，满足a,ba,ba,b
2020-09-21 22:49:29
159
1
原创 基础组合计数常用的概念和方法总结
组合计数方法总结一、组合中的基本概念与性质1、排列定义性质2、组合定义性质二、组合计数中的一些常用技巧1、容斥原理定义公式2、捆绑与插空法一、组合中的基本概念与性质1、排列定义一般地，从n个不同元素中取出m(m⩽n)m(m\leqslant n)m(m⩽n)个元素，按照一定的顺序排成一列，叫做从nnn个元素中取出mmm个元素的一个排列特别地，当m=nm=nm=n时，这个排列被称作全排列，...
2020-09-19 22:02:21
2260
原创 组合数的常见计算方法
1、组合数低级版方法概述直接用组合数性质中的③式递推即可程序实现int mod,c[2010][2010];int C(int n){ for(int i=0;i<=n;i++) c[i][0]=1; c[1][1]=1; for(int i=2;i<=n;i++) for(int j=1;j<=i;j++) c[i][j]=(c[i-1][...
2020-09-19 21:29:21
866
2
原创 初中生都看得懂的快速上手斯特林数指南——从盒放球问题说起
初中生都看得懂的快速上手斯特林数指南——从盒放球问题说起盒放球球相同，盒不同，不允许为空球相同，盒不同，允许为空球相同，盒相同，不允许/允许为空球不同，盒不同，允许为空球不同，盒相同，不允许为空第二类斯特林数定义通项特殊值计算第二类斯特林数自然数幂和快速幂？解决自然数幂和问题第一类斯特林数定义特殊值快速幂？斯特林反演第一次当标题党好方，但好像也没啥问题，因为我就是一个初中的菜鸡盒放球盒放球问题可以描述为：有nnn个相同/不同的球，kkk个相同/不同的盒子，把nnn个球放到盒子里，盒子允许/不允许为
2020-08-18 23:02:43
563
3
原创 网络流算法总结1——网络流最大流概述
网络流最大流概述网络流中的一些概念网络流中的一些概念边（弧）：在网络流问题中基本上所有的边都为有向边，所以在不加说明的情况下，文中出现的所有边都为有向边，有向边也成为弧，记为有序对(a,b)(a,b)(a,b)图：一堆点加上一堆边就是一张图，也就是说，图是边集加上点集，用G=⟨V,E⟩G=\langle V,E\rangleG=⟨V,E⟩路径：图中的一条路径就是一串相连的点，一条路径v1,v2,⋯⋯ ,vnv_1,v_2,\cdots\cdots,v_nv1,v2,⋯⋯,vn满足∀i∈[1,
2020-08-18 21:35:52
387
原创 HDU6753&DTOJ4963 2020 Multi-University Training Contest 1 cookies（看星）
题目原题题目描述Elsa’s elder brother Eric has got nnn cookies in his icebox and each cookie has a special number written on it. Let’s denote the number written on the ithi^{th}ith cookie by fif_ifi. fif_ifi is defined as followsHere, divmed(x)divmed(x)divme
2020-08-11 15:17:25
330
原创 树链剖分之重链剖分详解
树链剖分之重链剖分详解一些概念一些概念在学习重链剖分前，首先要明白以下几个概念：中二重儿子：就是一个节点的儿子中最“重”的那个，“重”表示的是子树大小最大，如果都一样大，就随便选一个就好了（用sonsonson数组存储）亲轻儿子：除了重儿子外其他的儿子重边：重儿子和父亲之间的边轻边：轻儿子和父亲之间的边重链：重边连在一起形成的链轻链：轻边连在一起形成的链（貌似没啥用）重链顶点：一条重链中，深度最小的点（用toptoptop数组记录）为了方便大家理解，这里我画了一张图，来表示重链剖分后
2020-07-28 11:32:53
1377
原创 编程中的较高端的数论知识总结1——莫比乌斯反演
前言之前写过一篇名叫基础数论总结的博客，自己认为写得不是很好，当时刚开始用CSDN写博客，LaTeX公式写得不是很熟练，花了快3个月才写完，而且写得比较杂，有的地方也写得不够全，后来也没去改过这次疫情期间，学校老师让我写一篇数论总结的博客，让我回学校后和其他同学分享，于是就有了这一系列博客对于以前那篇，如果有不懂的可以自行在百度上查询，我也不会再去更改了
2020-07-10 22:42:06
522
原创 FJOI2020游记
前言作为一名初二的蒟蒻，能参加省选我感到很荣幸，但是我有一个大问题，就是我模板背不熟！！！所以……总之就是准备赶紧去背模板吧这是我第一次参加省选，大佬勿喷同时，这也是我真正意义上的第一次自己去外地（以前有去过集训，但是都是家长带着去的……）Day-1（2020.6.23）今天是上文化课的最后一天了，因为明天请假，不用上了，所以就作了语文和英语，数学就不做了开电脑后惊奇地发现洛谷的省选联考数据居然有了，赶紧去康了康，发现不会正解，只会暴力……（我还是太菜了结果第一题暴力LOJ直接过了，洛谷开了O
2020-07-10 19:37:24
443
1
原创 DTOJ3681 购物（shopping）
DTOJ3681 购物（shopping）题解题解显然，这是一个DP我们假设fif_ifi表示前iii个的最大值（如果有的区间[l,r][l,r][l,r]满足l⩽i<rl\leqslant i<rl⩽i<r，那么就去除(i,r](i,r](i,r]的部分）我们需要先计算出两个值，一个是RiR_iRi，表示包含iii的rrr最大的区间，即maxj∈[1,n],i∈[lj,rj]rj\max \limits_{j \in [1,n],i\in [l_j,r_j]}r_jj∈[1
2020-05-16 12:56:03
280
原创 DTOJ2351 情报传递（message）
DTOJ2351 情报传递（message）题解题解首先，题目相当于要求我们回答两个问题：两个点之间的链的长度两个点之间的链上有多少个数大于ccc第一个问题极其简单，直接计算depx+depy−2×deplca(x,y)+1dep_x+dep_y-2\times dep_{lca(x,y)}+1depx+depy−2×deplca(x,y)+1就可以了对于第二个问题，我们可以...
2020-05-08 08:54:47
200
原创 DTOJ2548 翻转硬币
DTOJ2548 翻转硬币题解题解因为每次翻转改变的是相邻硬币相对的状态所以我们用did_idi表示相邻硬币相对的状态，即000表示状态相同，111表示状态不同现在，假设我们翻转[x+1,x+ai)[x+1,x+a_i)[x+1,x+ai)，那么，我们只会影响dxd_xdx和bx+aib_{x+a_i}bx+ai，有三种情况：dx=dx+ai=0d_{x}=d_{x+a_i}...
2020-05-07 21:56:32
204
原创 DTOJ2549 有没有wifi
DTOJ2549 有没有wifi题解题解一个极其暴力的暴力……（居然第一题A了那么多人，第三题只有我A了……）看到这道题，第一眼的思路就是二分那么我们就看怎么判断是否所有地方都被覆盖了如果一个矩形，如果它的四个角都被同一个圆覆盖了，那么显然，这整个矩形都被圆覆盖了；如果它的四个角都没有被任何一个圆覆盖，那么显然，这个矩形就完全没有被覆盖；除了上面这两种情况以外的其他情况，我们可以直接暴力...
2020-05-07 21:20:03
153
原创 DTOJ3702 月读（tsukuyomi）
DTOJ3702 月读（tsukuyomi）题解题解如果重新排列能形成一个回文序列的话，那么满足出现的次数是奇数的数字最多只能有一个所以我们可以对每一种边权进行哈希赋值，和000一起存入哈希表中接着，我们记XoriXor_iXori为根到iii点的边权异或和那么，如果询问的点为x,yx,yx,y，只要fx∧fyf_x\land f_yfx∧fy在哈希表里出现过，回答就是YesYes...
2020-05-06 09:32:48
177
原创 DTOJ3629 染色游戏（paint）
DTOJ3629 染色游戏（paint）题解题解首先，我们先不考虑“对于任意两个画了图案的格子l<rl<rl<r，有al⩽ara_l \leqslant a_ral⩽ar”这个条件，正常的进行DP我们用fif_ifi表示只画前iii个并且一定画第iii时最大的美观度我们先写出转移方程：fi=maxj<i{fj+ai−(i−j−1)(i−j)2}f_i=...
2020-05-06 09:19:12
295
原创 DTOJ3312 行走
DTOJ**** 行走题解题解因为我不知道qqq的范围，所以，我还是尽量让时间复杂度变小了太怂了所以我进行了两个优化：边权是111的边就不操作了当两个点的距离⩾62\geqslant 62⩾62时，答案一定是000（因为c⩽1018⩽2305843009213693952=261⩽c\leqslant 10^{18}\leqslant 2305843009213693952=2^{61...
2020-05-05 21:25:14
248
原创 DTOJ3305 环（circle）
DTOJ3305 环（circle）题解题解显然，答案是∑i=1nai\sum \limits_{i=1}^na_ii=1∑nai的约数所以我们可以枚举∑i=1nai\sum \limits_{i=1}^na_ii=1∑nai的每一个约数，对于每一个约数ddd，计算最多能切成几段，使得这几段gcdgcdgcd起来是ddd现在的问题就是到底能分成几段这个非常简单我们统计前缀和su...
2020-05-05 16:51:49
142
原创 DTOJ3701 天照
DTOJ3701 天照题解题解对于答案的第kkk位（从大到小考虑），大于kkk的位都是没啥用，把AAA和xxx数组大于kkk的位都去掉首先，我们先考虑xi=0x_i=0xi=0的情况如果xi=0x_i=0xi=0，那第iii位是111的数只能是(100⋯0)2∼(111⋯1)2(100\cdots 0)_2\sim (111\cdots 1)_2(100⋯0)2∼(111⋯1)2之...
2020-05-02 13:21:14
168
原创 DTOJ3342 工业题
DTOJ3342 工业题题解题解刚看到题目，就让我想到了以前的一道题：DTOJ3603 table这道题也是一样的道理，只需要计算边界点到这个点的路径条数，再乘以aaa的次方，bbb的次方唯一要注意的点是：边界上是不满足递推式的，所以第一步的方向是确定的通过计算，我们可以得出递推式：fi,0f_{i,0}fi,0的贡献是：fi,0×(m−1n+m−1−i)×am×bn−if_{i,0...
2020-05-02 08:30:38
107
原创 DTOJ3704 威士忌（whiskey）
DTOJ3704 威士忌（whiskey）题解题解首先，我们先将这些粉丝按aia_iai的大小来排序，然后我们枚举a0a_0a0的大小，有两种情况：如果ai>a0a_i>a_0ai>a0，那我们就要要求b>bib>b_ib>bi并且c>cic>c_ic>ci，为了方便，我们可以先预处理求出maxbimaxb_imaxbi和...
2020-04-30 21:40:07
175
原创 DTOJ3489 可怜与超市（supermarket）
DTOJ3489 可怜与超市（supermarket）题解题解这道题主要的难点在于处理“使用第iii张优惠券时必须先使用第xix_ixi张优惠券”这个问题这非常容易让我们联想到树，我们把iii向xix_ixi连一条边，就可以构成一棵树然后就很容易想到可以使用树形DP了我们用fi,j,kf_{i,j,k}fi,j,k表示第iii个节点，买了jjj个，用(k=1k=1k=1)还是没用(...
2020-04-30 21:21:55
793
原创 DTOJ3123 最大割cut
DTOJ3123 最大割cut题解题解异或有一个神奇的性质——a∧a=0a\land a=0a∧a=0所以，我们可以把边权转化为点权，点权为所有与这个点相连的边的异或和，对于点集内部的边，异或后就消掉了（因为是无向图），剩下的自然就是割的异或和了所以我们可以线性基来计算但是这题有一个很恶心的点——每加一个点就要重新算一遍线性基，如果暴力修改，就算用bitset效率也只有Θ(nl3)\Th...
2020-04-29 08:50:46
240
原创 DTOJ3084 置换permutation
DTOJ3084 置换permutation题解题解我们先来观察一下置换平方后是什么鬼假设我们有一个置换：(2,3,1,5,4)(2,3,1,5,4)(2,3,1,5,4)它可以被拆解为两个环：[2,3,1][5,4][2,3,1][5,4][2,3,1][5,4]我们把它平方一下：(3,1,2,4,5)(3,1,2,4,5)(3,1,2,4,5)发现它可以拆成三个环：[3,1,2][...
2020-04-28 21:59:07
170
原创 DTOJ3085 树tree
DTOJ3085 树tree题解题解要完成这一题，需要知道一个神奇的数列——prufer数列！每一棵不同的无根树，都对应这不同的prufer数列也就是说，prufer数列和无根树是一一对应的所以我们只需要计算可以组成多少种prufer数列prufer数列有一个神奇的性质——每一个节点出现的次数是它的度数减一这就是我们为什么要使用prufer数列了我们假设计算前iii个点并且每个点的...
2020-04-28 21:32:22
163
原创 DTOJ2162 magic
DTOJ2162 magic题目题目描述输入格式输出格式样例样例输入样例输出数据范围与提示样例说明数据范围题解题目题目描述给定一个nnn个点，mmm条边的有向图对于任意一个点iii，都有两个权值ai,bia_i,b_iai,bi你可以花费bib_ibi的费用将这个点的aia_iai变成000另外对于圈中的每个点你需要付出wi=Max(i,j)∈E ajwi=Max(i...
2020-04-22 22:16:25
89
原创 DTOJ2161 Christmas
DTOJ2161 Christmas题目题目描述输入格式输出格式样例样例输入样例输出样例说明数据范围与提示题解题目题目描述给出一个长度为nnn的整数序列。你的程序需要依次完成如下操作：A a b cA~a~b~cA a b c：将区间[a,b][a,b][a,b]中的每个数加上cccM a b c...
2020-04-22 12:22:21
202
原创 DTOJ2444 祖玛
DTOJ2444 祖玛题目题目描述输入格式输出格式样例样例输入样例输出数据范围与提示题解题目题目描述祖玛是一款曾经风靡全球的游戏，其玩法是：在一条轨道上初始排列着若干个彩色珠子，其中任意三个相邻的珠子不会完全同色此后，你可以发射珠子到轨道上并加入原有序列中一旦有三个或更多同色的珠子变成相邻，它们就会立即消失这类消除现象可能会连锁式发生，其间你将暂时不能发射珠子开发商最近准备为玩家写...
2020-04-22 11:45:37
173
原创 通俗易懂的斯特林数介绍
基础组合总结一、组合中的基本概念与性质1、排列定义性质2、组合定义性质一、组合中的基本概念与性质1、排列定义一般地，从n个不同元素中取出m(m⩽n)m(m\leqslant n)m(m⩽n)个元素，按照一定的顺序排成一列，叫做从nnn个元素中取出mmm个元素的一个排列特别地，当m=nm=nm=n时，这个排列被称作全排列，记作AnmA_n^mAnm性质Anm=n!(n−m)!A_n^......
2020-04-20 11:34:45
1575
2
原创 DTOJ3373 约会
DTOJ3373 约会题目题目描述输入格式输出格式样例样例输入样例输出数据范围与提示样例解释数据范围及约定题解题目题目描述Vincent和他的大学GF不在同一个院系中，但他们每天都要约在校园中的同一个地方见面THU的地图可以抽象为一个nnn个结点的一棵树，即有nnn个地点，n−1n-1n−1条无向边，每条边的长度为111，任意两个地点之间是连通的树还能不连通！？由于每天的课程不同，他们每...
2020-04-20 11:21:20
128
原创 DTOJ3311 寻找
DTOJ3311 寻找题目题目描述题目题目描述“我有个愿望，我希望穿越一切找到你”这是个二维平面世界，平面上有nnn个特殊的果实，我从(0,0)(0,0)(0,0)点出发，希望得到尽量多的果实，但是出于某种特殊的原因，我的运动方式只有三种（假设当前我在(x,y)(x,y)(x,y) (x,y) ）：1、我可以走到 (x+1,y) (x+1,y) (x+1,y)2、我可以走到 (x,y+...
2020-04-20 10:15:51
174
原创 DTOJ3302 星座
DTOJ3302 星座题目题目描述输入格式输出格式样例样例输入样例输出题解题目题目描述为了探索我们头顶那美丽的星空，伟大的C学给了我们一张星图，这张星图可以看做一个平面，其中包含了nnn颗星星，每颗星星可以用平面上的一个点来表示，C学告诉我们这张星图中包含着多种神奇的α−β−γ\alpha - \beta - \gammaα−β−γ星座，这些星座在平面内构成了很多平行四边形，它们的都有一组边...
2020-04-20 08:30:41
126
原创 DTOJ3308 从今以后
DTOJ3308 从今以后题目题目描述输入格式输出格式样例样例输入样例输出数据范围与提示题解题目题目描述小果有一个数列定义这个数列是合法的，指对于这个数列的每个子序列，都存在一个元素在在这个子序列中，只出现了一次请帮小果判断这个数列是否合法输入格式第一行一个整数TTT，表示数据组数接下来TTT组数据，每组数据第一行有一个整数nnn，表示该组数据的序列长度，之后一行有nnn个非负整数...
2020-04-15 11:13:25
149
我的CSDN博客md源码(第1~50篇)
2020-05-05
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人