<?xml version="1.0" encoding="utf-8" ?><rss version="2.0"><channel><title><![CDATA[lunch__的博客]]></title><description><![CDATA[AFO.]]></description><link>https://blog.csdn.net/lunch__</link><language>zh-cn</language><generator>https://blog.csdn.net/</generator><copyright><![CDATA[Copyright &copy; lunch__]]></copyright><item><title><![CDATA[HNOI2019 退役记]]></title><link>https://blog.csdn.net/lunch__/article/details/89302619</link><guid>https://blog.csdn.net/lunch__/article/details/89302619</guid><author>lunch__</author><pubDate>Sun, 14 Apr 2019 21:42:09 +0800</pubDate><description><![CDATA[窗外风雨大作。
凌晨两点又被噩梦惊醒，朦胧中看见书桌的灯还亮着。
走近书桌，有一个人正在敲打着键盘，屏幕上是一些似曾相识的东西。
被水浸湿的头发随意地搭在额头上，鼻梁上架着一副眼镜，镜片上全是小水珠，镜片后的双眼也没有神采。脸上还有些许伤痕，衣服也已经破得不成样子，只有在键盘上飞快舞动的双手才让人意识到这儿的确有人。
“你果然来了。”他长叹道，“你一定想知道我经历了什么。别急，先喝了这杯酒，再听我...]]></description><category></category></item><item><title><![CDATA[[BZOJ4833] [Lydsy1704月赛]最小公倍佩尔数（Min-Max 容斥）]]></title><link>https://blog.csdn.net/lunch__/article/details/88886294</link><guid>https://blog.csdn.net/lunch__/article/details/88886294</guid><author>lunch__</author><pubDate>Fri, 29 Mar 2019 10:50:01 +0800</pubDate><description><![CDATA[题意

令 (1+2)n=e(n)+2f(n),g(n)=lcm(f(1),f(2),...,f(n))(1+\sqrt 2)^n=e(n)+\sqrt 2f(n),g(n)=\text{lcm}(f(1),f(2),...,f(n))(1+2​)n=e(n)+2​f(n),g(n)=lcm(f(1),f(2),...,f(n))，求 ∑i=1ng(i)×i\sum_{i = 1}^ng(i)\t...]]></description><category></category></item><item><title><![CDATA[[BZOJ3809] Gty的二逼妹子序列（莫队 + 值域分块）]]></title><link>https://blog.csdn.net/lunch__/article/details/88808027</link><guid>https://blog.csdn.net/lunch__/article/details/88808027</guid><author>lunch__</author><pubDate>Mon, 25 Mar 2019 22:26:11 +0800</pubDate><description><![CDATA[题意

给你一个长度为 nnn 的序列 aaa， qqq 次询问，每次询问一段区间 [l,r][l,r][l,r] 内有多少种数值域在 [x,y][x,y][x,y] 内（值相等的数算同一种）（ai≤n≤105,q≤106a_i\le n\le10^5,q\le 10^6ai​≤n≤105,q≤106）。

没有修改自然考虑莫队，按一般的方法我们要会插入删除 nqn \sqrt qnq​ 次，询问...]]></description><category></category></item><item><title><![CDATA[[LOJ6061] 「2017 山东一轮集训 Day5」字符串（后缀自动机）]]></title><link>https://blog.csdn.net/lunch__/article/details/88263316</link><guid>https://blog.csdn.net/lunch__/article/details/88263316</guid><author>lunch__</author><pubDate>Wed, 06 Mar 2019 23:22:54 +0800</pubDate><description><![CDATA[题意

给你nnn个字符串，按顺序从每个字符串中选出一个子串（可以为空）拼接起来，求可以拼接出多少种本质不同的串（∑∣S∣≤106\sum |S|\le10^6∑∣S∣≤106 )

我们首先对于每个字符串都建出SAM，我们知道SAM的每个节点都包含了母串中的一些子串，那么我们考虑每个字符串的SAM中选出一个节点串起来的方案数就是我们想要的答案。
但是这样可能会算重，假设有两个串ab,bab,ba...]]></description><category></category></item><item><title><![CDATA[[LOJ2720] 「NOI2018」你的名字（后缀自动机+线段树合并）]]></title><link>https://blog.csdn.net/lunch__/article/details/88208921</link><guid>https://blog.csdn.net/lunch__/article/details/88208921</guid><author>lunch__</author><pubDate>Tue, 05 Mar 2019 23:29:31 +0800</pubDate><description><![CDATA[题意

给你一个字符串S\rm SS，q\rm qq次询问一个区间[l,r]\rm[l,r][l,r]，与一个字符串T\rm TT，求T\rm TT有多少个本质不同的子串没在S[l,r]\rm S[l,r]S[l,r]中出现过。

首先求的东西可以转化成T\rm TT中本质不同的子串减去S[l,r]\rm S[l,r]S[l,r]与T\rm TT的本质不同的公共子串数，T\rm TT中本质不同的子...]]></description><category></category></item><item><title><![CDATA[[LOJ2731] 「JOISC 2016 Day 1」棋盘游戏（DP计数）]]></title><link>https://blog.csdn.net/lunch__/article/details/87969401</link><guid>https://blog.csdn.net/lunch__/article/details/87969401</guid><author>lunch__</author><pubDate>Wed, 27 Feb 2019 11:27:26 +0800</pubDate><description><![CDATA[题意

给你一个3×n\rm 3 \times n3×n的棋盘，棋盘上有一些棋子，问有多少种不同填棋子的顺序可以填满棋盘，一个位置可以被填棋子当且仅当它的左右已经填了棋子或者它的上下都填了棋子。（n≤2000\rm n \le2000n≤2000）

首先判掉无解的情况，如果第一行或者第三行有连续两个空棋子，或者四个边角没有填棋子，就不存在填满棋盘的方案。
把这个棋盘当做一个四联通图，我们可以发现...]]></description><category></category></item><item><title><![CDATA[[FZOJ195] 「2019冬令营提高组」树（树哈希+DP计数）]]></title><link>https://blog.csdn.net/lunch__/article/details/87941347</link><guid>https://blog.csdn.net/lunch__/article/details/87941347</guid><author>lunch__</author><pubDate>Tue, 26 Feb 2019 18:40:45 +0800</pubDate><description><![CDATA[题意

给你一个n\rm nn个点的树A，一个m\rm mm个点的树B，求A树有多少个不同的生成子图与B同构。（n≤2000,m≤12\rm n \le 2000,m\le12n≤2000,m≤12）

我们首先可以枚举B树是哪个点作为根，B树同构的情况只能算一次，有一个DP就是设f(i,j)f(i,j)f(i,j)表示A树上点iii与B树上点jjj匹配的方案数。我们每次遍历A树的时候多记一个g(...]]></description><category></category></item><item><title><![CDATA[[FZOJ194] 「2019冬令营提高组」密文（Trie+贪心）]]></title><link>https://blog.csdn.net/lunch__/article/details/87940716</link><guid>https://blog.csdn.net/lunch__/article/details/87940716</guid><author>lunch__</author><pubDate>Tue, 26 Feb 2019 18:28:59 +0800</pubDate><description><![CDATA[题意

有一个序列a\rm aa，你可以花费vl&amp;amp;nbsp;xor&amp;amp;nbsp;vl+1&amp;amp;nbsp;xor...xor&amp;amp;nbsp;vr−1xor&amp;amp;nbsp;vr\rm{v_l \ xor\ v_{l+1}\ xor...xor \ v_{r-1} xor \ v_{r}}vl​&amp;amp;nbsp;xor&amp;amp;nbsp;vl+1​&amp;amp;nbsp;xor...xor&amp;amp;nbsp;vr−1​]]></description><category></category></item><item><title><![CDATA[[FZOJ183] 「2019冬令营提高组」排序（堆）]]></title><link>https://blog.csdn.net/lunch__/article/details/87894854</link><guid>https://blog.csdn.net/lunch__/article/details/87894854</guid><author>lunch__</author><pubDate>Sat, 23 Feb 2019 17:29:04 +0800</pubDate><description><![CDATA[题意

在选择排序的n(n−1)2\rm{\frac{n(n-1)}{2}}2n(n−1)​判断中，求出第K\rm KK次判断后的序列。

我们可以求出第K\rm KK次判断后执行了k\rm kk轮的排序，那么剩下的一遍暴力做就好了。
考虑怎么求出执行k\rm kk轮后的序列，我们依次确定第k+1\rm{k + 1}k+1位到第n\rm nn位的数，假设我们当前正在考虑第i\rm ii位是什么，那...]]></description><category></category></item><item><title><![CDATA[[51nod 1222] 最小公倍数计数（莫比乌斯反演）]]></title><link>https://blog.csdn.net/lunch__/article/details/87885958</link><guid>https://blog.csdn.net/lunch__/article/details/87885958</guid><author>lunch__</author><pubDate>Fri, 22 Feb 2019 21:31:58 +0800</pubDate><description><![CDATA[题意

给定a,b\rm{a,b}a,b，求有多少对i≤j\rm{i\le j}i≤j满足lcm(i,j)∈[a,b]\rm{lcm(i,j)\in[a,b]}lcm(i,j)∈[a,b]（a≤b≤1011)\rm{a\le b\le 10^{11}})a≤b≤1011)。

参考了ww3113306的这篇博客。
其实也比较套路，枚举gcd\mathtt{gcd}gcd后反演就转化成了求有多少个三...]]></description><category></category></item><item><title><![CDATA[[Tsinsen A1482] 登顶计划（计算几何+单调栈）]]></title><link>https://blog.csdn.net/lunch__/article/details/87884880</link><guid>https://blog.csdn.net/lunch__/article/details/87884880</guid><author>lunch__</author><pubDate>Fri, 22 Feb 2019 20:06:35 +0800</pubDate><description><![CDATA[题意

有一个nnn个点构成的折线，有一个人在这些折现中行走，问从每个点出发到达最高点的最小距离（n≤105\rm{n \le10^5}n≤105）。

发现可能出现转向的点一定是前i\rm ii个点构成的上凸壳最后一条线与折线的交点，那么这样总点数就是O(n)O(n)O(n)级别的，我们可以利用单调栈来维护凸包同时求出所有关键点。
假设我们知道了所有关键点，那么每个点肯定是先走到一个看到最高点比...]]></description><category></category></item><item><title><![CDATA[[LOJ6515] 「雅礼集训 2018 Day10」贪玩蓝月（线段树分治）]]></title><link>https://blog.csdn.net/lunch__/article/details/87072666</link><guid>https://blog.csdn.net/lunch__/article/details/87072666</guid><author>lunch__</author><pubDate>Tue, 12 Feb 2019 10:35:24 +0800</pubDate><description><![CDATA[题意

维护一个双端队列，支持两端插入物品和删除物品，询问队列中体积取模在[l,r][l,r][l,r]中的物品选择方案中的最大价值。（m≤5×104，mod≤500）m\le5\times10^4，\text{mod}\le500）m≤5×104，mod≤500）

动态增删不好做那就线段树分治离线下来，读入询问的时候把每个物品出现时间和结束时间都插入线段树中，对于背包只要维护好当前有多少个物品...]]></description><category></category></item><item><title><![CDATA[[BZOJ4025] 二分图（线段树分治+可撤销并查集）]]></title><link>https://blog.csdn.net/lunch__/article/details/87027848</link><guid>https://blog.csdn.net/lunch__/article/details/87027848</guid><author>lunch__</author><pubDate>Mon, 11 Feb 2019 22:21:02 +0800</pubDate><description><![CDATA[题意

给你nnn个点，mmm条边，每条边有一个出现时间和一个消失时间，求出每一个时刻当前图是否为二分图（n≤105,m≤2×105n\le10^5,m\le2\times10^5n≤105,m≤2×105）。

感谢Inspector_Javert的这篇博客，让我看懂了什么是线段树分治。
首先我们要知道如何判定一个图是不是二分图，那就是这个图不存在奇环。然后我们可以以时间为轴建立线段树，把每条边...]]></description><category></category></item><item><title><![CDATA[[LOJ2187] 「SHOI2014」三叉神经树（LCT）]]></title><link>https://blog.csdn.net/lunch__/article/details/86997160</link><guid>https://blog.csdn.net/lunch__/article/details/86997160</guid><author>lunch__</author><pubDate>Mon, 11 Feb 2019 14:35:43 +0800</pubDate><description><![CDATA[题意

给你一颗满三叉树，每个点权值定义为所有子节点权值和，叶子节点有一个属于[0,1][0, 1][0,1]的权值，每次修改一个叶子节点的权值，在修改后回答根节点的权值（n≤5×105n\le5\times10^5n≤5×105）。

首先感谢Hany01的讲解，我们首先观察一下性质，发现每次修改只会修改修改点到根节点路径的一端前缀，而且这连续一端的位置权值是相同的，那么我们要找到这个前缀的末尾...]]></description><category></category></item><item><title><![CDATA[[LOJ2083] 「NOI2016」优秀的拆分（后缀数组）]]></title><link>https://blog.csdn.net/lunch__/article/details/86925501</link><guid>https://blog.csdn.net/lunch__/article/details/86925501</guid><author>lunch__</author><pubDate>Sun, 10 Feb 2019 19:42:45 +0800</pubDate><description><![CDATA[题意

给你一个字符串，问其所有子串的优秀拆分方案数之和，优秀拆分定义为S = AA + BB，其中A, B都是字符串。

我们发现只需要算每个位置作为AA串开头的方案数与每个串作为BB串结尾的方案数，然后相邻位置乘起来就可以了。
我们可以枚举AA串的长度xxx，把整个序列下标为xxx的倍数的位置标记为关键点，那么任何一个长度为xxx的AA串它一定会跨过且仅跨过2个关键点，那么我们统计相邻两个关键...]]></description><category></category></item><item><title><![CDATA[[LOJ2133] 「NOI2015」品酒大会（后缀数组+并查集）]]></title><link>https://blog.csdn.net/lunch__/article/details/86747685</link><guid>https://blog.csdn.net/lunch__/article/details/86747685</guid><author>lunch__</author><pubDate>Sat, 02 Feb 2019 10:13:51 +0800</pubDate><description><![CDATA[题意

给你一个字符串SSS，对于r∈[0,n)r\in[0,n)r∈[0,n)，求有多少对位置(i,j)(i,j)(i,j)满足∀k∈[0,r]\forall k\in[0,r]∀k∈[0,r]，有Si+k=Sj+kS_{i+k}=S_{j+k}Si+k​=Sj+k​，并求出这些位置中任意两位置权值最大值。

首先如果两个位置对rrr满足条件，那么它们对k∈[0,r)k\in[0,r)k∈[0,...]]></description><category></category></item><item><title><![CDATA[[51nod 1238] 最小公倍数之和 V3（杜教筛）]]></title><link>https://blog.csdn.net/lunch__/article/details/86633999</link><guid>https://blog.csdn.net/lunch__/article/details/86633999</guid><author>lunch__</author><pubDate>Thu, 24 Jan 2019 22:01:25 +0800</pubDate><description><![CDATA[题意

ans=∑i=1n∑j=1nlcm(i,&amp;nbsp;j).(n≤1010)ans=\displaystyle\sum_{i = 1}^n\sum_{j = 1}^n\text{lcm(i, j)}.(n\le10^{10})ans=i=1∑n​j=1∑n​lcm(i,&amp;nbsp;j).(n≤1010)

这个题目比公约数那个题麻烦多了，首先还是把这个式子拆成公约数的形式：
ans=∑i=1...]]></description><category></category></item><item><title><![CDATA[[LOJ2542] 「PKUWC2018」随机游走（期望DP）]]></title><link>https://blog.csdn.net/lunch__/article/details/86516103</link><guid>https://blog.csdn.net/lunch__/article/details/86516103</guid><author>lunch__</author><pubDate>Wed, 16 Jan 2019 22:31:06 +0800</pubDate><description><![CDATA[题意

给你一个nnn个点的树，询问从sss号点出发，每次等概率选择一个相邻的点移动，求把集合SSS每个点至少访问一次的期望步数。

首先我们很自然设f[u][S]f[u][S]f[u][S]为从uuu号点出发访问SSS集合至少一次的期望步数，那么我们可以写出DP方程：
f[u][S]=1de[u]∑edge(u,v)(f[v][S]+1)(u∉S)f[u][S]=1de[u]∑edge(u,v)...]]></description><category></category></item><item><title><![CDATA[[51nod 1237] 最大公约数之和 V3（莫比乌斯反演+杜教筛）]]></title><link>https://blog.csdn.net/lunch__/article/details/86513569</link><guid>https://blog.csdn.net/lunch__/article/details/86513569</guid><author>lunch__</author><pubDate>Wed, 16 Jan 2019 19:44:34 +0800</pubDate><description><![CDATA[题意

ans=∑i=1n∑j=1n(i,j)，(n≤1010)ans=\displaystyle\sum_{i = 1}^n\sum_{j = 1}^n(i,j)，(n\le10^{10})ans=i=1∑n​j=1∑n​(i,j)，(n≤1010)

首先是套路的化式子为枚举gcd：
ans=∑d=1nd∑i=1n∑j=1n[(i,j)=d]ans=\sum_{d = 1}^nd\sum_{i...]]></description><category></category></item><item><title><![CDATA[[BZOJ4671] 异或图（容斥计数+线性基）]]></title><link>https://blog.csdn.net/lunch__/article/details/86259436</link><guid>https://blog.csdn.net/lunch__/article/details/86259436</guid><author>lunch__</author><pubDate>Thu, 10 Jan 2019 22:11:16 +0800</pubDate><description><![CDATA[题意

定义两个结点数相同的图 G1G_1G1​ 与 G2G_2G2​ 的异或为一个新的图 GGG， 其中如果 (u,v)(u, v)(u,v) 在 G1G_1G1​ 与 G2G_2G2​ 中的出现次数之和为 111， 那么边 (u,v)(u, v)(u,v) 在 GGG 中， 否则这条边不在 GGG 中。现在给定 sss 个结点数均为 nnn 的图 G1,...,GsG_1, ..., G_sG...]]></description><category></category></item></channel></rss>