4 CaptainHarryChen

尚未进行身份认证

I solemnly swear that I am up to no good.

等级
博文 115
排名 4w+

【BOI2019-Day1T2】Alpine valley(DP+倍增)

题目大意在山谷中有N个村庄,有N-1条道路将村庄连成一棵树,每条道路有一定长度。第E号村庄为山谷的出口。有S个村庄中有商店,商店可提供补给。由于山谷中天气恶劣,一条道路会被封死。当你处于某一个村庄中时,得知一条道路已经封死,你想知道自己能否活下去,即对于每一个询问,你需要计算,你是否能走出山谷,如果不能走出,则计算到最近的商店获得补给品所需最短路程。输入第一行:N,S,Q,E,即村庄数,...

2019-06-18 21:38:13

【洛谷P4719】动态DP(全局平衡二叉树)

题目大意给定一棵n个点的树,点带点权。有m次操作,每次操作给定x,y,表示修改点x的权值为y。你需要在每次操作之后求出这棵树的最大权独立集的权值大小。题解如果不带修改操作,正常的DP式:dp[u][1]dp[u][1]dp[u][1]表示当前结点保证选择,这个结点的子树独立集最大权值。dp[u][0]dp[u][0]dp[u][0]表示当前结点不选择,这个结点的子树独立集最大权值。...

2019-03-23 15:51:19

线性规划——单纯形法

问题标准型问题:最大化∑j=1ncjxj\sum\limits_{j=1}^{n}c_jx_jj=1∑n​cj​xj​满足约束∑j=1naij⋅xj≤bi (i=1,2,...,m)\sum\limits_{j=1}^{n}a_{ij}\cdotx_j\leb_i\(i=1,2,...,m)j=1∑n​aij​⋅xj​≤bi​ (i=1,2,...,m)且xj≥...

2019-03-18 21:46:23

Min_25筛

简介求积性函数前缀和,线性筛需要把函数的每一位值都算出来,作了许多不必要的操作。线性筛中,通过计算最小质因子幂的函数值,与之前已计算出的函数值相乘,得到新的函数值。如果我们能批量执行上面的操作,即用最小质因子幂的函数值,与另一些函数值的和相乘,就可以得到更多的函数值的和。我们还能发现,当我们要求前n项的和时,大于根号n的质因子都不能用于计算任何其它的积性...

2019-03-07 11:36:19

【BZOJ5223】有理有据题(K-D树)

题目大意有n颗炸弹,第i颗炸弹的爆炸范围为[li,ri][l_i,r_i][li​,ri​].有m个房子,标号为i的房子为一条线段[ai,bi][a_i,b_i][ai​,bi​](只要房子线段与炸弹相交视为炸弹能摧毁房子)几种操作:Axy:增加一个房子[x,y][x,y][x,y],按顺序标号。Ci:查询第i个炸弹能炸毁的连续标号的房子,最多连续多少个。Q:查询每个C1~n...

2019-03-02 21:57:21

生成树计数——矩阵树定理(Matrix-Tree)

文章目录结论无向图有向图口胡Matrix-Tree证明前置技能行列式定义初等变换拉普拉斯展开求法柯西-比尼定理(Cauchy-Binet)Matrix-Tree定理证明基尔霍夫矩阵性质基尔霍夫矩阵行列式为0不连通的图的主余子式行列式为0树的主余子式为1关联矩阵证明主体证毕结论无向图对于无向图GGG,设第iii个点的度数为did_idi​,第iii个点与第jjj个点相连的边数为aija_{ij...

2019-01-18 20:00:50

第一类斯特林数

概念[nk]n\brackk[kn​]表示将nnn个数的序列划分为mmm个圆排列的方案数。递推公式[nk]=[n−1k−1]+[n−1k]×(n−1){n\brackk}={{n-1}\brack{k-1}}+{{n-1}\brackk}\times(n-1)[kn​]=[k−1n−1​]+[kn−1​]×(n−1)[n−1k−1]n-1\brackk-1[k−1n−...

2019-01-12 12:05:12

【2019.1雅礼集训DAY2 T2】bracket(点分治+FFT)

题意给定一棵有n个节点的无根树,每个节点上是一个字符,要么是(,要么是)。定义S(x,y)为从x开始沿着最短路走到y,将沿途经过的点上的字符依次连起来得到的字符串。合法括号序定义如下:1,()是合法的。2,若A,合法,则(A)也合法。3,若A,B分别合法,则AB也合法。函数f(x,y)等于对S(x,y)进行划分,使得每一个部分都是合法括号序,能...

2019-01-10 11:54:07

【BZOJ4543】Hotel加强版(长链剖分 + 启发式合并)

题意给一棵树,从中选三个点,使得三个点两两间距离相等,求方案数。题解对每一个结点,用num[u][d]num[u][d]num[u][d]表示子树中到当前结点u的距离为d的节点数,用way[u][d]way[u][d]way[u][d]表示已经有很多两个结点的配对,再添加一个到当前结点距离为d的结点即可构成一个方案的结点对数。枚举子节点v,先计算答案Ans+=way[u][d+1]×num...

2019-01-09 21:43:30

【2019.1雅礼集训 DAY1 T2】permutation(可持久化线段树)

题意给出nnn个数AiA_iAi​定义排列一个1~n的排列P的价值为:∑i=1nAi×Pi\sum_{i=1}^nA_i\timesP_ii=1∑n​Ai​×Pi​求出排列价值前kkk小的kkk个排列的价值。...

2019-01-09 20:54:39

【BZOJ2216】Lightning Conductor (决策单调性DP)

题目大意给一个序列aia_iai​,对每一个i,求出最小的非负整数p,使得对任意j满足aj≤ai+p−∣i−j∣a_j\leqa_i+p-\sqrt{|i-j|}aj​≤ai​+p−∣i−j∣​题解移项得p≥aj−ai+∣i−j∣p\geqa_j-a_i+\sqrt{|i-j|}p≥aj​−ai​+∣i−j∣​绝对值可以去掉,正着算一遍,倒着算一遍,取最大值即可此时保证i>...

2018-12-27 19:53:52

【BZOJ3864】Hero meet devil(dp)

题目大意对每一个i(1<=i<=n),求长度为m,与给定字符串S的最长公共子序列的长度为i的字符串有多少个?题解DP新套路刚开始想的时候,怎么定义状态都会造成重复等各种问题,于是搜题解。。。考虑求LCS时的dp:定义lcs[i][j]lcs[i][j]lcs[i][j]表示A串的前i位与B串的前j位的LCS长度lcs[i][j]=max{lcs[i−1][j−1]+1&nb...

2018-12-27 17:12:56

【CodeForces553E】Kyoya and Train(DP+FFT+CDQ分治)

题目大意给一个有向图,有一个人要从111走到nnn,第iii号边花费的钱为cic_ici​,花费的时间为111~TTT中随机的值,每种时间的概率为pi,jp_{i,j}pi,j​,如果这个人在TTT时刻之后走到nnn,就要交XXX的罚款,求这个人花钱的最小期望。题解令dp[u][t]dp[u][t]dp[u][t]表示当前走到了u号结点,已经花费的时间为t,走到终点的最小期望代价。dp[u...

2018-12-25 20:27:55

【CodeForces793E】Oleg and chess(扫描线+线段树+网络流)

题目大意给一个n×n (n≤10000)n\timesn\(n\leq10000)n×n (n≤10000)的棋盘,有q (q≤10000)q\(q\leq10000)q (q≤10000)个不相交的矩形区域不能放棋子,在剩余的格子里最多能放多少个车,使得他们无法互相攻击。题解十分综合的题目如果nnn很小,对每一个横坐标和纵坐标建立一个结点...

2018-12-25 20:00:35

最小费用流——原始对偶(Primal-Dual)

EK算法的改进版,不知道名字(也许是ZKW??)EK算法EK算法就是不断的用SPFA寻找一条最小费用的增广路径,直到无法增广为止。改进类似于Dinic,先将结点用到汇点T的最短距离标号,每次只走dis[v]==dis[u]+cost[u->v]的边进行增广,保证了费用最小。在这种情况下,就可以类似Dinic,同时增广多条路径。细节较多,见代码及注释代码#include<...

2018-12-25 09:17:59

【CodeForces908H】New Year and Boolean Bridges (FWT)

题目大意对一个有向图(1≤n≤47)(1\leqn\leq47)(1≤n≤47),定义f(u,v)f(u,v)f(u,v)的值为true,当且仅当存在一条路径使得uuu能走到vvv给一个“邻接矩阵”A[i][j]A[i][j]A[i][j]:如果A[i][j]=='A',则f(u,v)andf(v,u)为true如果A[i][j]=='X',则f(u,v)xorf(v,u)为tr...

2018-12-23 11:44:43

【AtCoder2387】+/- Rectangle

题意构造一个H×WH\timesWH×W的矩阵,满足一下条件所有元素为整数,且属于[−109,109][-10^9,10^9][−109,109]所有元素和为正数对每个h×wh\timeswh×w的子矩阵,它的元素和为负数题解根据样例,最朴素的想法即为,给满足x mod h=0x\mod\h=0x mod h=0且y m...

2018-10-02 20:58:49

【AtCoder2376】Black and White Tree(博弈)

题意A和B轮流给树上的结点染色,A每次选择没染过的点染成白色,B每次选择没染过的点染成黑色,最后若所有白色都与黑色相邻,则B胜,否则A胜。双方以最优策略,求A胜还是B胜。题解A首先选择叶子结点的父亲u,则B只能选择叶子结点(否则叶子节点染白后,永远不可能与黑色相邻),所以,如果存在u有两个以上叶子结点,则A胜;然后删去u,则u的父亲v,如果v没有了子节点,v就成为新的叶子结点,A可继续先前...

2018-09-30 21:46:22

【AtCoder2307】Tree Game(博弈)

题意有一棵树,每个结点上有A[i]个石子,A开始把一个棋子放在任意一个结点上,然后由A开始,A,B轮流操作将当前棋子的结点石子数减1将棋子移动到相邻的结点上不能操作者输求A开始把棋子放在哪儿保证能赢。题解性质:棋子不会往比自己石子多的地方走(如果这样走,对方可以再走回来,自己就少了一颗棋子,对方又比自己多,打消耗战打不赢的。。。)然后就可以直接模拟计算NP状态枚举一个点作为起点,...

2018-09-25 22:01:24

【AtCoder2306】Rearranging(拓扑)

题意黑板上有n个数,A首先按照自己的意愿将n个数重新排列(可以是原来的顺序),然后让B进行如下操作:选择一对相邻且互质的数,交换它们的位置.(这个操作B可以进行无数次.)A想要这个序列的字典序尽可能小,而B想要这个序列的字典序尽可能大。两人都采取最优策略的情况下,最后形成的序列是什么样子的.题解发现不互质的数,只要在一开始A放好后,顺序就固定下来,无法改变。为了使得字典序最小,我们对...

2018-09-25 21:55:37
奖章
  • GitHub
    GitHub
    绑定GitHub第三方账户获取
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周上午根据用户上周的博文发布情况由系统自动颁发。