- 博客(127)
- 收藏
- 关注
RSS订阅
原创 About Me
来自月亮中学的高一蒟蒻OIer 目前只有NOIP一等奖… 随时有着退役的风险 QQ:3526419002QQ:3526419002QQ:3526419002 有什么看不懂的可以加我QQ问我QAQQAQQAQ
2018-07-25 20:36:40
559
10
原创 HNOI2019 退役记
窗外风雨大作。凌晨两点又被噩梦惊醒，朦胧中看见书桌的灯还亮着。走近书桌，有一个人正在敲打着键盘，屏幕上是一些似曾相识的东西。被水浸湿的头发随意地搭在额头上，鼻梁上架着一副眼镜，镜片上全是小水珠，镜片后的双眼也没有神采。脸上还有些许伤痕，衣服也已经破得不成样子，只有在键盘上飞快舞动的双手才让人意识到这儿的确有人。“你果然来了。”他长叹道，“你一定想知道我经历了什么。别急，先喝了这杯酒，再听我...
2019-04-14 21:42:09
552
3
原创 [BZOJ4833] [Lydsy1704月赛]最小公倍佩尔数（Min-Max 容斥）
题意令 (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)+2f(n),g(n)=lcm(f(1),f(2),...,f(n))，求 ∑i=1ng(i)×i\sum_{i = 1}^ng(i)\t...
2019-03-29 10:50:01
329
原创 [BZOJ3809] Gty的二逼妹子序列（莫队 + 值域分块）
题意给你一个长度为 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 次，询问...
2019-03-25 22:26:11
344
原创 [LOJ6061] 「2017 山东一轮集训 Day5」字符串（后缀自动机）
题意给你nnn个字符串，按顺序从每个字符串中选出一个子串（可以为空）拼接起来，求可以拼接出多少种本质不同的串（∑∣S∣≤106\sum |S|\le10^6∑∣S∣≤106 )我们首先对于每个字符串都建出SAM，我们知道SAM的每个节点都包含了母串中的一些子串，那么我们考虑每个字符串的SAM中选出一个节点串起来的方案数就是我们想要的答案。但是这样可能会算重，假设有两个串ab,bab,ba...
2019-03-06 23:22:54
431
原创 [LOJ2720] 「NOI2018」你的名字（后缀自动机+线段树合并）
题意给你一个字符串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中本质不同的子...
2019-03-05 23:29:31
519
原创 [LOJ2731] 「JOISC 2016 Day 1」棋盘游戏（DP计数）
题意给你一个3×n\rm 3 \times n3×n的棋盘，棋盘上有一些棋子，问有多少种不同填棋子的顺序可以填满棋盘，一个位置可以被填棋子当且仅当它的左右已经填了棋子或者它的上下都填了棋子。（n≤2000\rm n \le2000n≤2000）首先判掉无解的情况，如果第一行或者第三行有连续两个空棋子，或者四个边角没有填棋子，就不存在填满棋盘的方案。把这个棋盘当做一个四联通图，我们可以发现...
2019-02-27 11:27:26
669
原创 [FZOJ195] 「2019冬令营提高组」树（树哈希+DP计数）
题意给你一个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(...
2019-02-26 18:40:45
280
原创 [FZOJ194] 「2019冬令营提高组」密文（Trie+贪心）
题意有一个序列a\rm aa，你可以花费vl xor vl+1 xor...xor vr−1xor vr\rm{v_l \ xor\ v_{l+1}\ xor...xor \ v_{r-1} xor \ v_{r}}vl xor vl+1 xor...xor vr−1
2019-02-26 18:28:59
223
原创 [FZOJ183] 「2019冬令营提高组」排序（堆）
题意在选择排序的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位是什么，那...
2019-02-23 17:29:04
212
原创 [51nod 1222] 最小公倍数计数（莫比乌斯反演）
题意给定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后反演就转化成了求有多少个三...
2019-02-22 21:31:58
237
原创 [Tsinsen A1482] 登顶计划（计算几何+单调栈）
题意有一个nnn个点构成的折线，有一个人在这些折现中行走，问从每个点出发到达最高点的最小距离（n≤105\rm{n \le10^5}n≤105）。发现可能出现转向的点一定是前i\rm ii个点构成的上凸壳最后一条线与折线的交点，那么这样总点数就是O(n)O(n)O(n)级别的，我们可以利用单调栈来维护凸包同时求出所有关键点。假设我们知道了所有关键点，那么每个点肯定是先走到一个看到最高点比...
2019-02-22 20:06:35
321
原创 [LOJ6515] 「雅礼集训 2018 Day10」贪玩蓝月（线段树分治）
题意维护一个双端队列，支持两端插入物品和删除物品，询问队列中体积取模在[l,r][l,r][l,r]中的物品选择方案中的最大价值。（m≤5×104，mod≤500）m\le5\times10^4，\text{mod}\le500）m≤5×104，mod≤500）动态增删不好做那就线段树分治离线下来，读入询问的时候把每个物品出现时间和结束时间都插入线段树中，对于背包只要维护好当前有多少个物品...
2019-02-12 10:35:24
607
原创 [BZOJ4025] 二分图（线段树分治+可撤销并查集）
题意给你nnn个点，mmm条边，每条边有一个出现时间和一个消失时间，求出每一个时刻当前图是否为二分图（n≤105,m≤2×105n\le10^5,m\le2\times10^5n≤105,m≤2×105）。感谢Inspector_Javert的这篇博客，让我看懂了什么是线段树分治。首先我们要知道如何判定一个图是不是二分图，那就是这个图不存在奇环。然后我们可以以时间为轴建立线段树，把每条边...
2019-02-11 22:21:02
255
原创 [LOJ2187] 「SHOI2014」三叉神经树（LCT）
题意给你一颗满三叉树，每个点权值定义为所有子节点权值和，叶子节点有一个属于[0,1][0, 1][0,1]的权值，每次修改一个叶子节点的权值，在修改后回答根节点的权值（n≤5×105n\le5\times10^5n≤5×105）。首先感谢Hany01的讲解，我们首先观察一下性质，发现每次修改只会修改修改点到根节点路径的一端前缀，而且这连续一端的位置权值是相同的，那么我们要找到这个前缀的末尾...
2019-02-11 14:35:43
322
2
原创 [LOJ2083] 「NOI2016」优秀的拆分（后缀数组）
题意给你一个字符串，问其所有子串的优秀拆分方案数之和，优秀拆分定义为S = AA + BB，其中A, B都是字符串。我们发现只需要算每个位置作为AA串开头的方案数与每个串作为BB串结尾的方案数，然后相邻位置乘起来就可以了。我们可以枚举AA串的长度xxx，把整个序列下标为xxx的倍数的位置标记为关键点，那么任何一个长度为xxx的AA串它一定会跨过且仅跨过2个关键点，那么我们统计相邻两个关键...
2019-02-10 19:42:45
208
原创 [LOJ2133] 「NOI2015」品酒大会（后缀数组+并查集）
题意给你一个字符串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,...
2019-02-02 10:13:51
258
原创 [51nod 1238] 最小公倍数之和 V3（杜教筛）
题意ans=∑i=1n∑j=1nlcm(i, j).(n≤1010)ans=\displaystyle\sum_{i = 1}^n\sum_{j = 1}^n\text{lcm(i, j)}.(n\le10^{10})ans=i=1∑nj=1∑nlcm(i, j).(n≤1010)这个题目比公约数那个题麻烦多了，首先还是把这个式子拆成公约数的形式：ans=∑i=1...
2019-01-24 22:01:25
266
原创 [LOJ2542] 「PKUWC2018」随机游走（期望DP）
题意给你一个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)...
2019-01-16 22:31:06
479
原创 [51nod 1237] 最大公约数之和 V3（莫比乌斯反演+杜教筛）
题意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∑nj=1∑n(i,j)，(n≤1010)首先是套路的化式子为枚举gcd：ans=∑d=1nd∑i=1n∑j=1n[(i,j)=d]ans=\sum_{d = 1}^nd\sum_{i...
2019-01-16 19:44:34
243
原创 [BZOJ4671] 异或图（容斥计数+线性基）
题意定义两个结点数相同的图 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...
2019-01-10 22:11:16
377
原创 [UOJ164] 【清华集训2015】V（线段树）
题意给你一个序列，支持区间加上一个数，区间减去一个数，区间赋值，单点查询，单点历史最大值查询。题目链接题解首先发现三种操作可以转化为同样的形式，定义(x,y)(x,y)(x,y)为区间加上xxx后与yyy取max的标记，那么区间加就是(x,0)(x, 0)(x,0)，区间减就是(−x,0)(-x, 0)(−x,0)，区间赋值就是(−inf,x)(-inf,x)(−inf,x)...
2019-01-03 15:45:28
240
原创 [LOJ2541] 「PKUWC2018」猎人杀（分治+NTT）
题意有nnn个人，每个人有一个权值wiw_iwi，每次随机杀一个人，杀第iii个人的概率是wi∑j[j is alive]\frac{w_i}{\sum_j[j\ is \ alive]}∑j[j is alive]wi，求第一个人最后一个死的概率，对998244353998244353998244353取模。题解这题不是很难但
2018-12-26 20:52:20
264
原创 [BZOJ1415] [NOI2005]聪聪和可可（期望DP）
题意在一个魔法森林里，住着一只聪明的小猫聪聪和一只可爱的小老鼠可可。虽 然灰姑娘非常喜欢她们俩，但是，聪聪终究是一只猫，而可可终究是一只老鼠， 同样不变的是，聪聪成天想着要吃掉可可。 一天，聪聪意外得到了一台非常有用的机器，据说是叫 GPS，对可可能准确 的定位。有了这台机器，聪聪要吃可可就易如反掌了。于是，聪聪准备马上出发， 去找可可。而可怜的可可还不知道大难即将临头，仍在森林里无忧无虑的玩...
2018-12-09 17:25:07
137
原创 [LOJ2434] 「ZJOI2018」历史（DP+LCT）
题意给你一颗树上每个点的accessaccessaccess次数，计算轻重链切换次数的最大值.代码能力还是太弱了啊我，什么题看懂后自己还是写不出来，以后要练下自己码力了。首先要发现一个性质，那就是一个点的选择是无后效性的，就是对于每个点贡献的时候，只跟它的所有子树的大小有关，然后每个点的贡献就可以这样算fu=valu+∑fav=xfv，f_u=val_u+\sum_{fa_v=x}f_v...
2018-12-08 22:18:17
247
原创 [LOJ2334] 「JOI 2017 Final」JOIOI 王国（二分答案）
题目链接JOIOI 王国是一个 HHH 行 WWW 列的长方形网格，每个 1×11\times 11×1 的子网格都是一个正方形的小区块。为了提高管理效率，我们决定把整个国家划分成两个省 JOI 和 IOI 。我们定义，两个同省的区块互相连接，意为从一个区块出发，不用穿过任何一个不同省的区块，就可以移动到另一个区块。有公共边的区块间可以任意移动。我们不希望划分得过于复杂，因此划分方案需满足以下...
2018-12-07 19:20:49
805
原创 [LOJ2019] 「AHOI / HNOI2017」影魔（离线+线段树）
题意每次询问一个区间的贡献，一个区间的贡献可以这样计算，每存在一个点对(i,j)(i,j)(i,j)满足ki,kjk_i,k_jki,kj分别为区间[i,j][i,j][i,j]的最大值和次大值就有p1p1p1贡献，满足(j−i>1(j-i>1(j−i>1且ki<maxx=i+1j−1<kjk_i<\max_{x...
2018-12-07 19:20:00
584
原创 [BZOJ4828] [HNOI2017]大佬（DP+搜索）
4828: [Hnoi2017]大佬Time Limit: 30 Sec  Memory Limit: 256 MBSubmit: 82  Solved:&a
2018-12-07 09:36:25
222
原创 [BZOJ1555] KD之死（贪心+堆）
题意给你nnn个盒子，每个盒子有重量www和可以承受的最大重量ttt两个属性，有些盒子是必选的，你现在要在把所有的必选的盒子选定的基础上，使选择的盒子最多，最开始你有一辆能承重vvv的车，如果不能选完必选的盒子就输出Foolish SD!Foolish \ SD!Foolish SD!首先对于两个盒子aaa和bbb如果aaa放在bbb上方 那么承重为bt−awb_t-...
2018-11-09 17:47:39
235
原创 [LOJ2736] 「JOISC 2016 Day3」回转寿司（分块+堆）
题意给出一个有 NNN 个点的环，环上各点有一个初始权值 aia_iai给出QQQ个询问，每次询问给出一个区间 [l,r][l,r][l,r] 和一个值 AAA ，对于 AAA 的变动定义如下（rrr 可能会小于 lll 因为是环形）for (int i = l; i <= r; i++) if(a[i] > A) swap(a[i],A);对于每个询问，回答遍历完区...
2018-10-24 07:54:13
549
原创 [BZOJ4355] Play with sequence（线段树）
题意给你一个序列，有三种操作, 111是区间赋值，222是区间加法后区间取对000取maxmaxmax,333是询问区间内000的个数首先111操作可以转化为区间加上−inf-inf−inf后取maxmaxmax那么我们就只要维护区间加和区间取maxmaxmax操作了区间取maxmaxmax操作可以用吉司机线段树来实现这里有个比较重要的点就是加的−inf-inf−inf不能影响到区间...
2018-10-12 10:45:59
342
原创 [LOJ2523] 「HAOI2018」奇怪的背包（数论+DP)
题意有一个奇怪的背包,背包的重量是放入其中的物品总体积对P 取模后的结果.现有n种体积不同的物品,第i种占用体积为V i ,每种物品都有无限个.q次询问,每次询问给出重量w i ,你需要回答有多少种放入物品的方案,能将一个初始为空的背包的重量变为w i .注意,两种方案被认为是不同的,当且仅当放入物品的种类不同. 输出答案对1e9 + 7取模的结果.首先对于一个体积为vvv的物品能取到...
2018-10-12 08:26:57
289
原创 [Tsinsen A1210] 光棱坦克（动态规划+前缀和优化）
题意一个平面直角坐标系上，有N个点，标号为1到N，其中第i个点的坐标为(x[i], y[i])。 求满足以下两个条件的点列{p[i]}的数目(假设{p[i]}的长度为M) (1) 对任意1 <= i < j <= M，必有y[p[i]] > y[p[j]]； (2) 对任意3 <= i <= M，必有x[p[i-1
2018-10-05 08:40:23
326
原创 [51nod 1766] 树上最远点对（线段树+树的直径）
题意多次询问一个点在[a,b][a, b][a,b], 另一个点在[c,d][c, d][c,d]内的树上最远距离有一个结论对于两个联通块S,TS, TS,T设d(S)d(S)d(S)表示联通块直径的两个端点那么d(S∪T)∈d(S)∪d(T)d(S∪T) ∈d(S)∪d(T)d(S∪T)∈d(S)∪d(T)这个东西仔细想下不是很难证然后我们用线段树维护就好了但是每次pushup...
2018-10-02 21:02:40
262
原创 otyczki-algorytmiczne-2012 tas 中国剩余定理相关
题意给你一个初始为1,2,...,n1, 2, ..., n1,2,...,n的排列，一个置换AAA，一个排列BBB，询问是否可以通过初始序列置换到序列BBB.首先根据相关知识可以知道一组置换是一个环分别考虑每一个数如果iii和bib_ibi不在一个环中，那么就肯定无解了不然那置换次数kkk一定满足k=bi到i的变换步数(mod环的大小)k = b_i到i的变换步数(mod环的大小...
2018-09-21 21:52:12
107
原创 potyczki-algorytmiczne-2012 dwa 动态规划优化
题意给你两个排列A,BA, BA,B，每次可以从一个排列中拿出其中的第一个数，当两个排列的第一个数不相同时可以同时拿出两个排列的第一个数，求最少多少次能把所有数拿完，n<=1e6n<=1e6n<=1e6不难想到设dp[i][j]dp[i][j]dp[i][j]为AAA序列取到了iii, BBB序列取到了jjj的最小步数dp[i][j]=min(dp[i−...
2018-09-21 19:48:20
239
原创 Atcoder Grand Contest 002 F - Leftmost Ball
题意给你nnn种颜色的球，每个球有kkk个，把这nknknk个球排成一排，把每一种颜色的最左边出现的球涂成白色(初始球不包含白色)，求有多少种不同的颜色序列，答案对1e9+71e9 + 71e9+7取模这个题不是很好处理 但是可以发现一个性质第iii个白球前面有且仅有i−1i - 1i−1种颜色那么我们可以设f[i][j]f[i][j]f[i][j]为放了iii个白球,jjj种颜色的...
2018-09-19 22:00:19
156
原创 #LOJ2264. 「CTSC2017」吉夫特 DP计数
题意输入一个长度为nnn的序列aia_iai，求有多少个长度大于等于222的不上升子序列满足∏i=2k(abi−1abi) mod 2>0\displaystyle\prod_{i = 2}^{k} \binom{a_{b_{i - 1}}}{a_{b_i}} \bmod 2 &am
2018-09-19 19:49:08
191
原创 CodeForces1010 D. Mars rover 位运算相关？
题意给你nnn个数字，每个数字有无穷多个，从这nnn个数选择一些数加起来模kkk有多少种不同的值，并输出它们由裴祖定理可知 ax+by=gcd(a,b)ax+by=gcd(a, b)ax+by=gcd(a,b) 当x,yx, yx,y取任何值的时候ax+byax + byax+by都是gcd(a,b)gcd(a, b)gcd(a,b)的倍数那么考虑筛去其中一些数的倍数首先对于一个数xx...
2018-09-19 12:21:35
160
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人