- 博客(54)
- 收藏
- 关注
RSS订阅原创 【搜索】UVa211 —— The Domino Effect
题目传送门还是水啊…预处理出骨牌的编号,然后暴力dfs,完事…(code by lljd)#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int MAXN=10;int lo[MAXN][MAXN],vis[MAXN][MAXN],g[...
2018-10-31 19:52:30
312
原创 【搜索】UVa225 —— Golygons
题目传送门水啊水啊…可以直接暴力,判断是否经过障碍也可以暴力判断,注意搜索的顺序按照字典序最小即可.另注意一个可行性剪枝,即判断当前的位置能否在之后的步数中回到原点.#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int L=100;c...
2018-10-31 19:46:47
296
原创 【KMP】【伪思维题】BZOJ - 1511 —— OKR-Periods of Words
题目传送门可能是我太弱了,想了很久才想明白首先,KMP的fail数组可以看作是某一个前缀的最长公共前后缀的长度.即f[i]是前i个字符,前后缀相同的最长长度.在通俗地举个例子:abcabcf[5]=3,前缀一个’abc’,后缀一个’abc’,所以是3.用i-f[i],求得是最短的循环长度.红色区域表示前后缀相同的区域,用i-f[i]后得到下面的蓝色区域将蓝色区间复制一份放到后面...
2018-10-29 14:44:30
1176
原创 【树的点分治】【ST表】BZOJ 3784 —— 树上的路径
题目传送门(权限题警告)总有一个序列，能够满足题目中所需求的一切性质。—— 鲁迅 （没说过）这里引入一个叫做点分治序列的东西,它通过下列步骤生成.1.找到当前树的重心,将重心加入序列.2.从重心出发,dfs遍历整个树,将遍历到的点加入序列.3.将与重心相连的边断掉,生成若干子树,对于每一个子树重复上述过程.显然,点分治序列不是唯一的.例如下图的一个点分治序列是4&amp;nbsp;7&amp;n...
2018-10-28 15:13:13
297
原创 【DP】SRM642 D1L2(TopCoder - 13319) —— TaroCutting
题目传送门稍微有点思维难度的DP首先可以明确一个性质,每棵树只会被砍一次.假设砍两次,那么完全可以第一次不砍,第二次砍,这样做是不会影响答案的.同时可以看出,树的生长速度对答案的影响比树初始的高度大.不妨利用一下贪心的思想,将生长速度最快的树,放到最后一天用dev值最小的机器砍它.因此我们将树按照生长速度降序排序,将机器按dev值升序排序.然后从最后一天开始DPd[i][j][k]表示...
2018-10-26 19:37:23
166
原创 【树形DP】SRM621 D1L2(TopCoder - 13086) —— TreesAnalysis
题目传送门题意给定两棵树,树上的点分别用0~n-1标号,定义两条不在同一棵树上的边的相似度S(e1,e2)S(e1,e2)S(e1,e2),且定义两棵树的相似度为所有边的相似度的平方和.S(e1,e2)S(e1,e2)S(e1,e2)的计算方法:将e1从第一棵树中删除,得到两个联通块,且记两个联通块中点的标号的集合为A,B.将e2从第二棵树中删除,得到两个联通块,且记两个联通块中点的标...
2018-10-25 17:57:29
176
原创 三校联考 10.15 总结
时间安排通览题目,大致确定T1组合数学,T2数据结构,T3比较麻烦,可能是数据结构.(20min)首先做第一题,将暴力的式子推出后先写了一个暴力.(20min)利用Dp进行优化+调试(40min)手造大样例后发现会T,进行预处理优化(10min)开始第一题对拍第二题首先码10%的暴力,途中发现第一题对拍出错,遂转去调试第一题.(30min)思考到第二题用线段树维护区间信息可得40%....
2018-10-15 20:53:44
137
原创 【回滚莫队】三校联考 10.15 —— ants
题目描述然而贪玩的 dirty 又开始了他的第三个游戏。dirty 抓来了 n 只蚂蚁，并且赋予每只蚂蚁不同的编号，编号从 1 到 n。最开始，它们按某个顺序排成一列。现在 dirty 想要进行 m 场比赛，每场比赛给出 l 和 r ，表示选出从左向右数第 l只至第 r 只蚂蚁。被选出的蚂蚁需要快速地按编号从小到大排序，之后这些蚂蚁中编号连续的蚂蚁将围成一个圈。每场比赛结束后，蚂蚁们还需...
2018-10-15 19:54:33
194
原创 【单调栈】三校联考 10.15 —— array
题目描述在放完棋子之后，dirty 又开始了新的游戏。现在他拥有一个长为 n 的数组 A，他定义第 i 个位置的分值为 i − k + 1，其中 k 需要满足：对于任意满足 k ≤ j ≤ i 的 j，有 A[k] ≤ A[j] ≤ A[i]。当对于第 i 个数，有多个 k 满足条件时，取能获得较大分值的 k。现在，dirty 想要知道 A 数组中分值最大的位置对应的分值为多少。分析...
2018-10-15 19:34:10
131
原创 【组合数学】【DP】三校联考 10.15 —— Chess
题目描述dirty 在一个棋盘上放起了棋子。棋盘规格为 n ∗ m，他希望任意一个 n ∗ n 的区域内都有 K 个棋子。dirty 很快就放置好了一个满足条件的棋盘方案，但是他认为这样过于简单了，他希望知道有多少个满足条件的方案。看题第一眼即可知道是关于组合数学的.通过观察发现,如果棋盘上前n列已经定了,那么之后的情况只会是前面n列的循环.因此只需考虑n列.可以得出以下式子sum=...
2018-10-15 19:25:46
154
原创 【思维题】【二分图】TopCoder 12316 —— ThreeColorability
题目传送门虽然这道题标签有个二分图,实际上只是用来判断解的.此题的精髓应该是思维的过程首先利用样例 (题解),观察出2*2的格子中,如果有解,那么解一定为四个一样或者各两个的情况.不可能存在三个与一个的情况.也就是说,如果其中三条对角线的方向已经确定了,那么第四条的方向也是确定的.将上述的性质转换为式子就是 cells[x1][y1]⨂cells[x1][y2]⨂cells[x2][y1]⨂...
2018-10-14 19:47:03
267
原创 【思维题】【生成树计数】BZOJ 2467 —— 生成树
题目传送门思维题?利用破圈算法的思想,想要将每一个环都删去一条边.首先考虑周围的五边形,每一个五边形都是一个环所以要删掉一条边,注意.观察剩下的图后发现有两种情况.中心多边形和周围五边形剩下的边组成了一个环周围五边形连起来构成了一个环不论哪种情况,我们都还需要删除一条边.对于情况1,删除一条中心多边形上的边.对于情况2,有些特殊.之所以能够达到情况2,是五边形删边的时都删除了与中心多...
2018-10-11 10:37:21
263
原创 【最短路树】BZOJ 3694 —— 最短路
题目传送门(权限题警告)显然可以发现,将1到i路径上的最后一条路切断后,需要重新找到一条从i的子树出发的最短路径重新回到最短路树上去.因此考虑一条边什么时候会被计算在答案中.设一条边u->v权值为val,只会可能对u,v到 lca(u,v) 之间的点产生影响.记录源点1到节点i的距离为dep[i],那么就可以把答案更新为 dep[u]+dep[v]+val-dep[i].可以预处理出...
2018-10-10 20:53:07
278
原创 【最短路】BZOJ 3445 —— Roadblock
题目传送门[权限题警告]暴力算法:枚举改变哪一条边的权值,然后跑最短路求max这样做可能会T掉.因此想办法优化,然后显然地可以看出只有改变了最短路上的边,对最后的答案才有可能有影响.因此先跑一遍最短路,统计出最短路上的边,然后暴力枚举.#include&lt;cstdio&gt;#include&lt;algorithm&gt;#include&lt;queue&gt;using na..
2018-10-10 19:17:01
293
原创 【Tarjan】POJ 2942 —— Knights of the Round Table
题目传送门题目中给出的是骑士中矛盾关系,可以转换一下,得到原图的补图.然后观察题目中的条件,即选择的骑士数是奇数,并且相邻之间不矛盾.对应到现在的补图上,即寻找一个奇环,使得环的大小大于等于3.也就是说,只要一个骑士能够出现在一个符合条件的奇环中那么这个骑士便是合法.首先用Tarjan将点双连通分量全部求出,对于一个点双连通分量,可以利用交替染色的方法判断是否存在奇环,如果存在一个奇环那么这个...
2018-10-09 20:42:26
141
原创 【Tarjan】【割边割点】HDU4738 —— Caocao's Bridges
题目传送门讨论版是个好地方,本题三大坑都有说比较水的Tarjan基础题,大概就是求一个权值最小的割边,水过去.但是,有重边,要注意处理;有可能不连通,这个时候不需要有人去炸桥;最后答案是0,要输出1,因为需要一个人抗炸药过去.#include&lt;cstdio&gt;#include&lt;algorithm&gt;#include&lt;vector&gt;using names.
2018-10-09 18:58:59
328
原创 【Tarjan】【强连通分量】 BZOJ 5201 —— Connections
题目传送门(没有权限号打不开)对于每一个节点,我们保留一条树边,以及最多一条返祖边.注意这条返祖边要指向尽可能高的位置.这样下来保留的边数一定小于等于2n,并且满足图依旧是强连通的.至于为什么,贪心的想一想.既然之前满足强连通,我们保留走到dfn最小的返祖边后也一定是强连通的.最后随意乱加边直到2n即可.只需进行一次Tarjan,保留树边,并在过程中维护出当前点通过返祖边走向的dfn最小的点,...
2018-10-09 15:54:24
187
原创 【思维题】【DP】AGC019 B —— Reverse and Compare
题目传送门一开始在想关于回文串的操作,直到我意识到这个数据范围d[i]表示前i个字符进行操作能够得到的不同串数量.那么转移分为两部分,一部分是当前这个位置不动,加上前i-1个位置的答案;另一个部分是将以i结尾的某个区间翻转.注意如果直接算这两个部分会有一部分是重叠的,所以进行翻转操作的区间起点不能和当前位置一样.综上,d[i]=d[i-1]+sum-cnt[s[i]-'a'].其中sum是...
2018-10-08 20:36:27
176
原创 【思维题】【欧拉回路】AGC018 D —— Two Trees
题目传送门持续看官方题解,顺便复习一下欧拉回路的求法.刚刚T过几次题目中要求的子树之和的绝对值为1,也就意味mod 2为1.那么对于每个节点,如果它的亲儿子数为偶数,它的权值就应该为奇数,反之亦然.通过上面的性质我们可以推出每个节点最终答案的奇偶性,从而判断是否有解.当且仅当两棵树中,同一个节点的答案奇偶性相同时,才有解.现在只是确定了答案的奇偶性,接下来就需要运用欧拉回路求得具体的值了....
2018-10-08 20:07:35
281
原创 【思维题】【组合数】【数学】AGC018 E —— Sightseeing Plan
题目传送门看官方题解都理解了半天真的能够在考试时间内做出来吗题意可以抽象为有三个矩形,分别从中选出一个点为A,B,C,要求A->B->C总的方案数.直接暴力枚举然后计算肯定不可行的,需要想方法进行转换.定义F(x,y)为(0,0)到(x,y)的方案数,则F(x,y)=Cxx+yF(x,y)=C_{x}^{x+y}F(x,y)=Cxx+y,然后发现F(x+1,y)=∑j=0yF...
2018-10-08 17:25:20
271
原创 【思维题】【树】【哈密顿路径】AGC018 D —— Tree and Hamilton Path
题目传送门想到了按边算贡献,然而却偏向了在直径上鬼畜的道路.通过观察,可以发现如果多次经过重心,答案应该是最优的.因为这样使得除了某一条特殊的边之外,所有的边都会被计算两次.而这条特殊的边有两种情况,首先是只有一个重心,那么我们选择边权最小的且其中一个端点为重心的边;另一种情况是具有两个重心,选择两个重心之间的边即可.此处复习一下求重心的方法,首先任选一个节点为根,统计出每一个节点对应子树的...
2018-10-07 21:41:37
368
原创 【思维题】【贪心】AGC018C —— Coins
题目传送门尝试了一下弱化条件想题的方法,还不错?题目中有三种硬币,并不利于直接贪心.我们不妨先考虑只有两种硬币的情况.按照贪心的思想,应该按照两种硬币的差值(即一个人金币的个数减去银币的个数)进行排序,然后从前选Y个,剩下的X个都为金币.然后我们将条件加回来,发现性质有了一点点变化.因为有铜币的影响,所以并不能直接选取Y个这样做.但是我们还是可以发现,从前开始选银币,和从后开始选金币的区间是...
2018-10-07 21:33:25
359
原创 【思维题】【线段树】AGC011 F ——Train Service Planning
题目传送门比较有思维难度的一道题,绞了好久.首先先不考虑双向的轨道,记第i条轨道需要的行驶时间为AiAiAi,从左边出发的车在i停留pipipi,从右边出发的车停留qiqiqi.那么如果当前的这条轨道 x 没有发生冲突就可以转换为使区间(∑i=0x−1pi+∑i=1x−1Ai,∑i=0x−1pi+∑i=1xAi)(\sum_{i=0}^{x-1} pi+\sum_{i=1}^{x-1} Ai,...
2018-09-26 21:40:33
190
原创 【思维题】【图论】AGC011 C——Squared Graph
题目传送门考场上企图用归纳法来做,然而事实证明我依旧似乎走错了方向.题目中的定义了图的乘法,然后来根据图的不同特征进行讨论.首先我们考虑一种最简单的情况,设A,B是两个图,并且它们都是一个单点,那么A对答案的贡献为∣B∣\mid B \mid∣B∣.反之对B同理.然后考虑两个图都没有奇环的情况,(似乎这样可以看作二分图),这样的两个图乘起来对联通块的个数贡献是2.因为形如(u1,u2)-&...
2018-09-26 21:16:58
324
原创 【思维题】【细节】AGC010 C——Cleaning
这道题应该是比较简单的,但是有很多限制条件需要考虑进去,所以很容易漏掉一些条件.首先我们只考虑一种比较基本的情况一个根节点和它的若干儿子.
2018-09-25 19:46:05
225
原创 2018NOIP知识梳理(四)——数论相关(三)
排列圆排列重复排列有限个数无限个数项链排列错排问题有限制的排列相关题目排列从n个不同元素中,取r(1&amp;amp;amp;amp;amp;amp;amp;amp;lt;=r&amp;amp;amp;amp;amp;amp;amp;amp;lt;=n)r(1&amp;amp;amp;amp;amp;amp;amp;amp;lt;=r&amp;amp;amp;amp;amp;amp;amp;amp
2018-09-06 20:47:39
452
原创 2018NOIP知识梳理(二)——数论相关(一)
线性筛莫比乌斯函数欧拉函数约数个数约数和莫比乌斯反演线性筛线性筛可以筛出一堆积性函数,逐一复习一下.莫比乌斯函数定义:μ(1)=1,若n可以分解为k个互异素数的乘积,则μ(n)=(−1)k,其他情况,μ(n)=0μ(1)=1,若n可以分解为k个互异素数的乘积,则μ(n)=(−1)k,其他情况,μ(n)=0\mu(1)=1,若n可以分解为k个互异素数的乘...
2018-09-02 20:58:20
1052
原创 Codeforces Round #466 (Div. 2)
Points on the line 940AOur Tanya is Crying Out Loud 940BPhone Numbers 940CAlena And The Heater 940DOther这次考试炸得有点严重，虽然是简单题，但是脑残严重。赛后一会找到了程序的错误，感觉题是不难的，思路方向也是对的，是我自己细节的问题。Points on the l...
2018-02-25 09:44:50
213
原创 寒假训练3
n^n的末位数字 （51Nod - 1004）题意：传送门思路与小结：嗯，快速幂，然后只要最后一位数，于是我觉得可以不用longlong，但忘了先模再快速幂，WA了一次。Code#include<cstdio>#include<cstring>#include<algorithm>#include<queue>...
2018-02-21 20:20:49
144
原创 寒假训练2
此次比赛虽然题做起来比较顺，但是最后两道题却没有做出。经查网上的题解后，最后两道题都是思维题，没有实现难度，可以看出我思维的欠缺。另外这套题中的E题是道实现细节题，所以可以看出我的实现能力相对以前较好了。Pairwise Sum and Divide（51Nod - 1305）题目描述有这样一段程序，fun会对整数数组A进行求值，其中Floor表示向下取整：fun(A) ...
2018-02-14 21:08:45
294
原创 可持久化数据结构——可持久化线段树
可持久化线段树个人认为大部分数据结构转变为可持久化都是比较简单的，只需要保存历史版本的信息即可。在每次进行更改操作时，先复制的到之前的一个版本，然后对要进行更改的节点，复制一个出来改。并且将它的父亲指向新复制出来的点。也就是说，我们只是在原来的历史版本上加边加点，并没有重新建一个树。除此之外我觉得还可以有一个大胆的搞法。历史版本我们可以不用线性的结构保存，我们可以用树状数组来快速实现。...
2018-02-13 12:20:08
288
原创 寒假训练1(分析与总结)
此次训练有原题，以巩固基础为目的，理应达到AK，但在Dp方面有所欠缺。完美字符串（51Nod - 1182）题意约翰认为字符串的完美度等于它里面所有字母的完美度之和。每个字母的完美度可以由你来分配，不同字母的完美度不同，分别对应一个1-26之间的整数。约翰不在乎字母大小写。（也就是说字母F和f）的完美度相同。给定一个字符串，输出它的最大可能的完美度。例如：dad，你可以将26分配给...
2018-02-13 12:05:29
628
原创 数论相关
数论相关线性筛相关线性筛相比传统的筛法要快的多，因为我们保证了每个数一定都是由它最小的一个质因子筛出来的，因此平摊的时间复杂度大概在O(n)左右，可以看作是线性的复杂度。所以叫做线性筛。 线性筛的应用可以说是十分的广泛了，积性函数可以通过它迅速求得。例如欧拉函数，莫比乌斯函数，约数和等。莫比乌斯函数及莫比乌斯反演首先莫比乌斯函数的定义为 μ(1)=1 一...
2018-02-12 10:56:50
214
原创 树链剖分初步学习
树链剖分初步学习类比线段树在数据结构的处理中，我们会遇到一些单点/区间修改，单点/区间询问等问题。针对这类问题我们常常用线段树来解决。 但普通线段树能解决的问题都是在线性的，如果要在树上进行这些操作，那就是十分的困难。因此我们需要引用树链剖分来进行解决问题。树链剖分目的正如上文所说，树链剖分用来解决一些在树上的信息维护问题。我们将树分为若干条链，然后用一些线性的数据结构维护信息。方法树链剖分的方法
2017-12-15 20:48:19
165
原创 1143 快速求和
给定一个数字字符串，用最少次数的加法让字符串等于一个给定的目标数字。每次加法就是在字符串的某个位置插入一个加号。在需要的所有加号都插入后，就象做普通加法那样来求值。 例如，考虑字符串”12”，做0次加法，我们得到数字12。如果插入1个加号，我们得到3。因此，这个例子中，最少用1次加法就得到数字3。 再举一例，考虑字符串”303”和目标数字6，最佳方法不是”3+0+3”，而是
2017-12-09 11:11:45
249
原创 NOIP2017总结
Day 1T1第一眼看就想到是拓展欧几里得，通过解出X0,Y0推出c(能取到的值)关于t(拓展欧几里得解系常数变量)的不等式。把t的每一个取值中，c的范围看作区间。然后再列不等式将，一个最大的t，使得相邻两个区间中间有数，答案即为这个数。
2017-11-13 16:49:27
647
原创 BZOJ 2301 Problem b
题目传送门 这个问题等价于询问有多少个数对(x,y)满足l首先我们根据容斥原理将一个询问拆分为四个询问即ans=f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1) f(i)为gcd(x,y)=i的个数(1我们令F(i)为i|gcd(x,y)的个数(1则可以得到F(i)=∑i|df(i)F(i)=\sum_{i|d}f(i)f(i)=∑i|dμ(di)F(d)f
2017-07-12 08:57:12
202
原创 莫比乌斯反演初涉
首先我们直接来看莫比乌斯函数(μ(d)\mu(d)). 若d=1则，μ(d)=1\mu(d)=1 若d可以分解为k个互不相同的质数的乘积，即d=p1∗p2∗......∗pkd=p_1*p_2*......*p_k且p1p2......pkp_1那么μ(d)=(−1)k\mu(d)=(-1)^k 除此之外的所有情况，μ(d)=0\mu(d)=0 那么问题来了，这个函数有什么用呢？
2017-07-11 19:40:39
186
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人