3 caoyang1123

尚未进行身份认证

我要认证

夜如果有千万个回头的理由 请原谅所有失忆的影子 原谅他们不只一次地将思念撒向无边无际的漆黑 长而且直的影子那么孤单 在长街上不断延长 八月的花蕾上有席卷荒野的风暴 相信一个属于抗争的季节 紧握着太阳骄傲的碎片,此刻 你慢慢把手心摊开 一片月光打落露水的声音 在那里凝结成坚固歌唱 …… 我不会坚持用火焰说话 悲伤使我看到希望 你要听一听地底的呼叫 那个用紫色记忆的年代就要回来了 我不知道他曾经坍塌了多少回 我又曾经抱头痛哭在旷野中狂奔了多少回 那个怒吼着的年代就要回来了 在我的心灵里永远有一座煤矿 有挖掘不尽的火种

等级
TA的排名 4w+

[NOI2018]你的名字

https://www.luogu.org/problemnew/show/P4770sam根本不理解.jpg,自己想只会搞一个n根号的做询问1~n的垃圾68分做法真实做法我是对着洛谷little_gift大佬的题解学的,写的很好。考虑68分里把每个T扔到S的sam上跑匹配,跑到T的下标位置x时它的意义是对T【1~x】这个前缀,从S的所有子串里,找能和 该前缀的后缀 匹配长度最大 的某...

2019-07-11 10:22:17

CF848E Days of Floral Colours

链接:https://codeforces.com/problemset/problem/848/E被拿来做训练题,两个小时码出n<=25爆搜30分。。。带图更详细的做法可以直接看官方题解:https://codeforces.com/blog/entry/54233这里讲下大致思路:环的问题一般很难直接考虑,所以考虑从简单的链入手,考虑一段左右是相对的连,中间还有x对没连的...

2019-07-11 09:58:42

「LibreOJ NOI Round #2」不等关系

主席花费1sec秒的题,我看着主席的题解想了一年。。链接:https://loj.ac/problem/575考虑容斥其中大于或小于其中一个限制,推式子,然后上分治fft优化。具体的Orz主席https://www.cnblogs.com/Mr-Spade/p/11115654.html附对着主席题解的蒟蒻学习笔记:代码:#include<bits/stdc++...

2019-07-11 09:35:12

长链剖分优化树形dp

apio铁牌告辞(开场想打暴力然后gedit码代码5个小时没写完三题最低档暴力真是快乐),听课也就学到了一丢丢这个东西。模板题:https://www.luogu.org/problemnew/show/P5384首先k级兄弟可以一遍dfs的时候丢到k级父亲上变成求k级孩子的询问。求k级孩子有个很简单的做法,直接dfs的时候维护扫到某个点时记录下的每种dep出现次数,对于所有求这个...

2019-05-19 22:40:30

prufer序列学习笔记

可以用于处理一类有关生成树计数类的问题。prufer序列是有关无根树的序列,并且n点无根树能唯一对应n-2长度的prufer序列。一、prufer序列生成方法:把无根树里所有度数为1的点定义为叶子,重复执行以下操作直至原树里只剩下两个节点:选取当前标号最小的叶子,把它的父亲接在当前生成的prufer序列末尾,并在原树里删除该点。二、prufer序列还原无根树:设一个点集V={1...

2019-05-13 09:09:45

斯特林数-离散微积分学习笔记

一、定义1.第一类斯特林数:表示方法:S1(n,m)或[nm]n \brack m[mn​]组合意义:指n个点组成m个圆排列的方案数。递推求法:S1(n,m)=S1(n-1,m-1)+(n-1)*S1(n-1,m)快速求法:∏i=0n−1(x+i)\prod_{i=0}^{n-1}(x+i)∏i=0n−1​(x+i)的第k次项系数就是S1(n,k),所以可用分治fft做到n*log^...

2019-05-10 08:23:38

全局平衡二叉树学习笔记

感觉是树剖和lct的一种结合,把树剖的log^2变成log,把lct的常数变小,但是能维护的东西也有局限性...实际上就是有时候维护的东西不需要lct的link-cut操作,所以可以将树建成一棵棵二叉平衡树连在一起而不需要splay。具体建法就是先轻重链剖分,对每条重链建一棵bst,然后这棵bst的根通过虚边连向这棵bst内深度最浅的点在原树中的父亲。而对于每条重链建bst时,注意为了保证平衡...

2019-05-07 09:18:49

agc 033 D-Complexity

https://atcoder.jp/contests/agc033/tasks/agc033_d场上没想出来...做法:可以发现答案上界是log(H*W)的,所以考虑暴力枚答案,那么的当前状态可以表示为选取(r,c)和(r',c)两个点能扩展到最右的c'在哪里以及选取(r,c)和(r,c')两个点能扩展到最下面的r'在哪里,所以一层里状态数是n^3的。对于转移考虑由于它的复杂度计算是取max...

2019-05-05 09:24:20

zjoi day2 语言

https://www.luogu.org/problemnew/show/P5327最可做的题结果场上根本没想打了60分,后来听说想写正解的都被卡了......做法:考虑对一个点x来说,可以到达它的点一定构成一个树上包含x的连通块,而连通块里距离x点最远的点一定是跨过这个点的路径的端点,发现这个连通块的求法可以用类似虚树的方法做,把所有跨过该点的路径的端点按dfs序排序,先假设根会在连通块里...

2019-05-04 16:48:05

带修改主席树学习笔记

在主席树的外层套树状数组,即下标为x的线段树维护x~x+lowbit(x)的区间,修改很简单,查询的话就把log个需要用的树提取出来,每一层查询个数和k比,在树上往左往右走。时空都n*log^2模板题:https://www.luogu.org/problemnew/show/P2617#include<bits/stdc++.h>using namespace s...

2019-04-22 08:07:52

可持久化trie+线段树分治题 火星商店

链接:https://www.luogu.org/problemnew/show/P4585做法:首先观察到每个人能买的商品是一段区间,考虑将这个区间拆成log段存在线段树节点上(开vector),这样就可以考虑对线段树每个节点所代表的商品区间建一棵可持久化trie,然后更新它这个节点上的所有询问,这样做其实算是一种整体二分,复杂度n*log^2(做这题第一发wa了,调了1个小时发现空间开...

2019-04-21 16:30:53

CF868F 分治优化dp

链接:https://codeforces.com/problemset/problem/868/F首先n^2m的dp很容易想,f(j,i)表示考虑划分了j个集合,最后一个集合结尾在i的最小值。显然它具有决策单调性,即如果f(j,i)最后一个划分的集合在最优方案下起始位置是k,那么当i增加k一定单调不降(如果有多个最优决策位置选任意一个都是满足的,因为实际上i增大一定是在最右边的最优决策对它影...

2019-04-19 18:56:17

bitset做多维偏序

很久以前就听说这个大名鼎鼎的东西(暴力)了,现在才去写。其实很简单,对每一维排序,从左到右扫,维护一个bitset表示这位之前的某个点是否出现(即出现则该位为1否则0),查询某个数时则在每一维的排序完数组二分找到最右边<=这个数这一维权值的位置,取出该位的bitset,将每一维的bitset与起来即可得到答案,每次查询n/w,但这样空间要维数*n^2/w,因此可以分块增加查找时的一些时间换空...

2019-04-18 19:38:34

可持久化数据结构

1.可持久化线段树(可持久化数组)https://www.luogu.org/problemnew/show/P3919#sub最基础的可持久化数据结构,每次修改开新的log个点即可。#include<bits/stdc++.h>using namespace std;const int N=1e6+100;template<class T>void...

2019-04-17 21:26:46

[Topcoder SRM 590]Fox And City

将原来就有的边转化为|dis(u)-dis(v)|<=1的约束,然后建图最小割,一个点拆n个点的从S到T的链表示最终离0号点距离的情况,然后在T中的点pt(i,x)表示满足dis(i)<=x,在S中的点表示不满足,而要保证这些限制就从T到S每条边连inf反向边,这样显然可以保证靠T的边被连续取到,即满足<=x也满足<=x+1...,之后把原图的边转化为<=1约束在u,...

2019-04-16 22:17:04

最短路树学习笔记及例题

定义构建一棵树,使得任意不属于根的节点x,dis(root,x)=原图走到x的最短路。构建方法:就是在跑dijkstra时同时维护每个点是哪个点哪条边更新的,这个点这条边就是它在最短路树上的父亲/到父亲的边例题:T1.bzoj3694 最短路题意:给定了最短路树要求不经过树上到i点最后一条边的到i点最短路。显然到一个点走法一定是经过一条非树边到达的,那么考虑每一条非树边会产生怎...

2019-04-15 22:22:53

快速求解原根

设模数为p,所求数为1.O(p1/2)O(p^{1/2})O(p1/2)预处理+O(log2)O(log^2)O(log2)判断一个对p-1分解质因数,一个数x是模p意义下原根当且仅当对任意y⊂y\subsety⊂{p-1的质因数}有x(p−1)/y!=1(modp)x^{(p-1)/y}\quad !=1 \quad (mod \quad p)x(p−1)/y!=1(modp)2.O(p∗...

2019-04-15 16:18:11

动态dp学习笔记

基本是维护一个矩阵,它的矩阵乘法是a(i,j)=max(a(i,j),b(i,k)+c(k,j))模板题:https://www.luogu.org/problemnew/show/P4719树剖后一个点f(x,0/1)表示x点取或不取,x子树最大独立集大小;g(x,0/1)表示x点取或不取,不考虑x重儿子情况下x子树最大独立集大小。这样转移就变成(son(x)为x重儿子)∣g(x,0)g...

2019-04-15 08:56:19

cf414g-思维好题转载

知道结论才能做,而证明结论才是这题精髓(但我根本不会,以下均转载自大佬博客https://blog.csdn.net/xaphoenix/article/details/72681794?utm_source=blogxgwz2)---------------------------------------------------------------------------------...

2019-04-14 20:40:21

整体二分学习笔记

用于处理一些维护区间k大k小的问题。以区间k小为例,将询问和修改离线下来,然后对所有询问修改二分值L、R以及Mid并同时维护哪些修改的值<=Mid,哪些询问答案会在[L,R]内,那么用树状数组跑当前这层的修改(即小于等于Mid的在bit上位置+1),然后对每个询问查询当前答案是否达到k,是的话分到[L,Mid],不然当前k减掉k然后分到[Mid+1,R],再把当前这层修改撤销并把修改也判断一...

2019-04-12 20:05:59

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv3
    勤写标兵Lv3
    授予每个自然周发布7篇到8篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。