- 博客(410)
- 收藏
- 关注
RSS订阅原创 [题解]CSP2019 Solution - Part B
orz\text{orz}orz 一波现场 A\text{A}A 掉 D1T3\text{D1T3}D1T3 的神仙D2T3 centroidSolution考虑每个点 uuu 作为重心的贡献假设以 uuu 为根时，存在 uuu 的一个子节点 vvv现在要在 vvv 的子树内删掉一个子树，使得 uuu 成为重心考虑删子树之后，vvv 的子树大小需要满足什么条件设 uuu 除 v...
2019-11-20 22:56:54
487
原创 [题解]CSP2019 Solution - Part A
至于为什么是 Part A\text{Part A}Part A 而不是 Day 1\text{Day 1}Day 1那是因为 Day1 T3 还没改（那这六题的 solution\text{solution}solution 就按难度顺序写吧）感觉今年的画风和 NOIP 2016\text{NOIP 2016}NOIP 2016...
2019-11-20 20:28:28
352
原创 [Other]CSP2019 游记
一些有趣的事情Day 0上午颓废，下午到宾馆15:4015:4015:40 左右去试机试机题是 A+B Problem\text{A+B Problem}A+B Problem ，发现是个线段树模板题，直接码上某初二学弟写了主席树回到宾馆颓了一段时间之后去外面吃饭再次回来之后继续颓颓颓10:0010:0010:00 要睡觉突然被叫起来（老董开会）开完会...
2019-11-17 23:16:55
722
1
原创 [LOJ#3177][IOI2019]矩形区域（分治 + 单调栈）
AddressLOJ #3177Solution首先有一个性质对于长度为 nnn 的数组 a1...na_{1...n}a1...n满足对于所有 l≤i≤rl\le i\le rl≤i≤r 都有 al−1>ai,ar+1>aia_{l-1}>a_i,a_{r+1}>a_ial−1>ai,ar+1>ai 的...
2019-08-18 15:23:40
521
1
原创 [LOJ#2320][UOJ#335][清华集训2017]生成树计数（prufer序列 + 生成函数）
Address洛谷 P4002BZOJ 5119UOJ #335LOJ #2320Solution我们知道，一棵 nnn 个节点的无根树对应一个长度为 n−2n-2n−2 的 prufer 序列且 prufer 序列中 uuu 的出现次数为树上 uuu 的度数 dud_udu 减 111而在原题中，一个节点 uuu 本质上是一个大小为 aua_uau 的连通块故如果 d...
2019-08-12 20:31:55
345
原创 [题解][LOJ #3156~#3161]NOI2019 简要题解集合
AddressD1T1 ：洛谷 P5468 / LOJ #3156D1T2：洛谷 P5469 / LOJ #3157D1T3 ：洛谷 P5470 / LOJ #3158D2T1：洛谷 P5471 / LOJ #3159D2T2：洛谷 P5472 / LOJ #3160D2T3 ：洛谷 P5473 / LOJ #3161...
2019-08-04 14:41:50
670
原创 [UOJ#346][清华集训2017]某位歌姬的故事（DP）
Address洛谷 P4229UOJ #346LOJ #2331Solutionorz 讲课现场切掉此题的神仙 Lagoon可以发现，如果一个限制为 maxi=lrhi=x\max_{i=l}^rh_i=xmaxi=lrhi=x ，另一个限制为 maxi=abhi=y\max_{i=a}^bh_i=ymaxi=abhi=y 且 y<xy<x...
2019-08-03 18:03:06
275
原创 [LOJ#3124][CTS2019]氪金手游（概率 + 树形 DP + 容斥）
Address洛谷 P5405LOJ #3124Solution先考虑如果以某个点（下面定为 111 ）为根时，如果所有的限制二元组 (u,v)(u,v)(u,v) 都满足 uuu 是 vvv 的父亲（即 uuu 向 vvv 连边构成外向树）怎么做显然，对于任意一个点 uuu ， uuu 必须是在 uuu 的子树内第一个被翻到的如果每个点的 WWW 已经确定，则这个概率就等于∏...
2019-06-28 17:59:52
265
原创 [题解][Codeforces 1172A~1172D]Codeforces Round #564 (Div. 1) 前四题题解
中国场，最后两题为毒瘤数据结构题，还未写，见谅Address洛谷 RemoteJudgeABCDEFCodeforcesABC1C2DEFAMeaning两个序列 aaa 和 bbb ，长度为 nnn ，每个数均为 000 或者 111 到 nnn 之间的整数，且 111 到 nnn 的每个数出现且仅出现一次每次操作可以在第一个序列里抽走一个数...
2019-06-11 20:19:14
628
原创 [LOJ#6617][THUPC2019]摆家具（矩阵乘法 + 子集和变换）
AddressLOJ #6617SolutionTask 1先解决一个小问题如何求 TTT 次操作之后，对于所有的 0≤i≤k0\le i\le k0≤i≤k ，求出最后恰好有 iii 个家具不在原来的房间内的方案数容易设计一个 DPf[i][j]f[i][j]f[i][j] 表示 iii 次操作之后，恰好有 jjj 个家具不在原来的房间内的方案数转移（自行理解）f[0][...
2019-06-07 18:00:58
253
原创 [UOJ#461]新年的Dog划分（交互 | DFS + 二分）
AddressUOJ #461Solution看到题目只需要求二分图的两个点集而不需要求所有的边我们可以想到求出二分图的一棵生成树而这棵生成树就能唯一确定二分图的两个点集看到操作次数限制，我们可以猜测需要使用的操作次数为 O(nlogn)O(n\log n)O(nlogn)考虑钦定一个生成树的根每次把根 uuu 删掉，对剩下的每个连通块各找一个点 vvv 满足边 (u,v)...
2019-06-04 19:46:04
396
原创 [LOJ#3119][CTS2019]随机立方体（容斥）
Address洛谷 P5400LOJ #3119Solution考虑容斥具体地，用「选出 kkk 个格子，这 kkk 个格子极大的概率之和」×Ckk\times C_k^k×Ckk减去「选出 k+1k+1k+1 个格子，这 k+1k+1k+1 个格子极大的概率之和」×Ck+1k\times C_{k+1}^k×Ck+1k再加上「选出 k+2k+2k+2 个格子，这 k+2k...
2019-06-02 21:54:26
197
原创 [题解]一道 DP 思路好题
Description数轴上对于所有的 1≤i≤n1\le i\le n1≤i≤n ，点 iii 上有一个物品，价值为 aia_iai从 000 开始走路，每次可以向左或向右走如果点 iii 上有一个没有取过的物品，则可以取之但初始你有 xxx 点能量在任何时候，如果你身上的物品价值总和为 aaa ，则走一个单位距离要消耗 a+1a+1a+1 点能量求在回到起点 000 时剩余能量...
2019-05-18 10:49:08
304
原创 [日常训练]Hard（组合数学 + FMT）
Meaning有一棵 nnn 个点的树，根结点为 111 号结点，初始时每个结点有一个值 aia_iai每一轮，你需要从根结点开始，将每个结点的权值更新为它子树中所有结点上一轮结束后权值的异或和有 qqq 个询问，每个询问给定轮数 TTT ，你需要输出 TTT 轮后根结点的值0≤T,ai≤1018,1≤n,q≤1060\le T,a_i\le10^{18},1\le n,q\le10^...
2019-04-21 15:43:56
222
原创 [题解][Codeforces 1137A~1137F]Codeforces Round #545 (Div. 1) 简要题解
第一次打 Div. 1 ，感觉题目质量还是比较好的然后就把我这个菜鸡选手区分到了榜末题目洛谷 RemoteJudgeABCDEFCodeforcesABCDEFA题意一个 n×mn\times mn×m 矩阵 aaa定义 f(x,y)f(x,y)f(x,y) 表示在矩阵中取出第 xxx 行和第 yyy 列设一个新矩阵 bbb ，这个矩阵只有第...
2019-04-01 21:47:47
498
原创 [BZOJ4651][Noi2016]网格（Tarjan 求割点）
Address洛谷 P1173BZOJ 4651UOJ #220LOJ #2084Solution下面把跳蚤视为白点，蛐蛐视为黑点可以发现答案只可能是 −1-1−1 、 000 、 111 、 222 四种然后随机输出一个，你可以以 1 / (4 ^ T) 的高概率通过此题易得， 如果没有黑点，则有三种情况（1） n×m≤2n\times m\le 2n×m≤2 ： −1...
2019-04-01 16:43:14
233
原创 [题解][Codeforces 1139A~1139F]Codeforces Round #548 (Div. 2) 简要题解
终于 rank < 10 了题目洛谷 RemoteJudgeABCDEFCodeforcesABCDEFA题意一个长度为 nnn 的数字串 sss求 sss 有多少个子串，满足子串内的数字顺次连接后得到的数是偶数1≤n≤650001\le n\le 650001≤n≤65000 且 sss 不包含 000题解∑i=1ni[s[i]...
2019-03-26 21:47:17
1258
原创 [Codeforces 1098C]Construct a tree（二分 + 构造）
Address洛谷 RemoteJudgeCodeforces 1098CSolution看到要最小化每个点子节点个数的最大值，想到二分答案 midmidmid考虑通过构造进行判断首先要知道：所有节点的子树大小之和，等于所有节点的深度之和所以在此题中，一棵树可以被量化成一个数组 d[]d[]d[] ，其中 d[i]d[i]d[i] 表示深度为 iii 的点数然后尝试分析一下每...
2019-03-14 20:52:32
364
原创 [Codeforces 1097F]Alex and a TV Show（bitset + 莫比乌斯反演）
Address洛谷 RemoteJudgeCodeforces 1097FSolution发现我们要查询的是某集合内某数的出现次数模 222 的结果可以对于每个可重集维护一个 bitset ，第 iii 个集合的 bitset 第 jjj 位表示第 iii 个集合中 jjj 的出现次数的奇偶性但我们发现这样做无法解决第 333 种操作我们不妨把维护的东西换一下A[i][j]A...
2019-03-09 11:06:17
175
原创 [LOJ#2983][WC2019]数树
Address洛谷 P5206LOJ #2983Solution这是一道计数 (shen) 好 (xian) 题，综合性很强 ，虽然是三合一鉴于此题用到的算法较多，我就不在标题里列出了，此题用到的算法及技巧如下容斥原理prufer 序列计数组合数学树形 DP多项式 expTask 1 ： op=0op=0op=0首先分析下问题，很容易得出，如果设 T0T_0T0...
2019-03-08 21:55:51
341
原创 [Codeforces 1100F]Ivan and Burgers（线性基）
Address洛谷 RemoteJudgeCodeforces 1100FSolution一道好题看到「最大异或和子集」，很容易想到线性基然后看到区间限制，直接想到线段树维护线性基，合并信息时 O(log2c)O(\log^2c)O(log2c) 合并线性基然后你会发现你 TLE 了， O(nlognlog2c)O(n\log n\log^2c)O(nlognlog2c)...
2019-02-17 22:16:55
456
原创 [BZOJ4730][UOJ#266][清华集训2016]Alice和Bob又在玩游戏（SG 函数 + Trie + 线段树合并）
AddressBZOJ 4730UOJ #266Solution设 SG[u]SG[u]SG[u] 表示当前存在的点只剩下 uuu 的子树时的状态的 SGSGSG 值显然整个游戏的 SGSGSG 值为XORu是根节点SG[u]XOR_{u是根节点}SG[u]XORu是根节点SG[u]如果上式非零则先手必胜，否则先手必败考虑通过 DP 求得 SG[u]SG[u]SG[u] 。...
2019-02-17 10:27:34
574
原创 [题解][Codeforces 1111A~1111E]Codeforces Round #537 (Div. 2) 简要题解
题目洛谷 RemoteJudgeABCDECodeforcesABCDEA题意给定两个字符串 SSS 和 TTT ，仅包含小写英文字母你可以找到 SSS 中的一个元音字母，把它变成另一个元音字母或者找到 SSS 中的一个辅音字母，把它变成另一个辅音字母求能不能把 SSS 变成 TTT1≤∣S∣,∣T∣≤10001\le|S|,|T|\le10001≤...
2019-02-08 20:53:08
913
1
原创 [BZOJ3812][UOJ#37][清华集训2014]主旋律（状压 DP + 容斥原理）
AddressBZOJ 3812UOJ #37Solution考虑状压 DP ，定义状态f[S]f[S]f[S] 表示原图的点集 SSS 的导出子图中，有多少个边子集能强连通点集 SSSg[S]g[S]g[S] 表示将原图的点集 SSS 分割成一些非空子集，每个点子集分别用其内部的边将其强连通的方案数，分成的子集个数为奇数时计入 g[S]g[S]g[S] ，子集个数为偶数时从 g...
2019-02-04 17:03:10
279
原创 [BZOJ4005][JLOI2015]骗我呢（组合数学好题）
Address洛谷 P3266BZOJ 4005LOJ #2109Solution非常有意思，思路非常棒的题目发现一个很优秀的条件：对于 1≤i≤n1\le i\le n1≤i≤n ， 1≤j≤m1\le j\le m1≤j≤m 满足 0≤xi,j≤m0\le x_{i,j}\le m0≤xi,j≤m ，并且对于任意的 1≤i≤n1\le i\le n1≤i≤n ， 1≤j&amp;a...
2019-02-02 16:09:23
922
1
原创 [LOJ#2585][APIO2018]新家（扫描线 + 二分 + 线段树）
Address洛谷 P4632BZOJ 5462UOJ #414LOJ #2585Solution自从来到 GZ 市来一直都鸽着没去调这题，几天之后才去调最直接的 O((n+q)log3n)O((n+q)\log^3n)O((n+q)log3n) 思路看到我们的询问要求「最小值的最大值」，容易想到二分答案具体地，假设我们在某个时间点，知道了这时候所有点的出现位置，那么...
2019-01-30 20:19:18
238
原创 [Other]THUWC 2019 游记
Day [-6,-2]模拟赛天天垫底，药丸最近在 OJ 上没做什么题，药丸cx Log_x dalao 555 天连续 777 场模拟赛 777 个 rk1 ， orzDay -1考前日常颓废早上一直睡到 11 : 20下午无限颓废晚上开始做数据结构题热身选择了一道不错的数据结构水题 APIO 2018 新家边写边颓， 21 : 50 才写完，还没编译Day 09...
2019-01-23 23:04:27
1688
2
原创 [Codeforces 903G]Yet Another Maxflow Problem（线段树）
Address洛谷 RemoteJudgeCodeforces 903GMeaning一张图， 2n2n2n 个点，分成两部 AAA 和 BBB ，每部 nnn 个点其中 AiA_iAi 到 Ai+1A_{i+1}Ai+1 有容量为 xix_ixi 的边（ 1≤i&amp;amp;lt;n1\le i&amp;amp;lt;n1≤i&amp;lt;n ）BiB_iBi 到 Bi+1B_{i+1}...
2019-01-15 21:35:09
289
原创 [BZOJ3811][UOJ#36][清华集训2014]玛里苟斯（期望 + 线性基）
AddressBZOJ 3811UOJ #36Solution看到异或，首先想到拆位下面 xor(A)\text{xor}(A)xor(A) 表示子集 AAA 的异或和， bit(x,i)bit(x,i)bit(x,i) 表示 xxx 的第 iii 个二进制位（最低二进制位为第 000 位）可以得出ans=E(xor(A)k,A⊂S)=E((∑i≥0bit(xor(A),i)2...
2019-01-14 21:34:26
421
原创 [Codeforces 438E]The Child and Binary Tree（生成函数 + 多项式开平方）
Address洛谷 RemoteJudgeCodeforces 438EMeaning给定一个 nnn 元正整数集合 SSS对于任意的 1≤i≤m1\le i\le m1≤i≤m求有多少棵不同（形态不同或点权不同）的点带权无标号有根二叉树的所有点权和为 iii （所有的点权都在集合 SSS 内）1≤n,m,S内的元素≤1051\le n,m,S内的元素\le10^51≤n,m,...
2019-01-13 14:00:24
273
原创 [BZOJ2797][Poi2012]Squarks（数学）
Address洛谷 P3540BZOJ 2797Solution一道不错的数学题先将读入的数组 AAA 从小到大排序显然 X1+X2=A1X_1+X_2=A_1X1+X2=A1 ， X1+X3=A2X_1+X_3=A_2X1+X3=A2（上面的 XXX 是递增的）设 X2+X3=AkX_2+X_3=A_kX2+X3=Ak ，则很容易得到比 AkA_kAk ...
2019-01-11 16:59:45
191
原创 [2018 FJ 省队集训 Day6][校内训练]传统题（组合数学妙题）
Meaning一个长度为 nnn 的序列，每个位置可以被染成 [1,m][1,m][1,m] 中的任一颜色求所有 mnm^nmn 种染色方案的最长连续同色子段长度之和答案对 ppp 取模1≤n≤3000001\le n\le3000001≤n≤3000002≤m≤1082\le m\le10^82≤m≤1080.99×109≤p≤1.01×1090.99\times10^9\le p...
2019-01-11 16:16:15
387
原创 [BZOJ5287][Hnoi2018]毒瘤（虚树 + 树形 DP）
Address洛谷 P4426BZOJ 5287LOJ #2496Solution - Step 1首先我们看到非树边最多 111111 条很容易想到暴力枚举每条非树边的两个端点是否在独立集内然后树上 DP 求独立集个数复杂度 O(3m−n×n)O(3^{m-n}\times n)O(3m−n×n)然后我们发现对于一条非树边 (u,v)(u,v)(u,v) ，如果强制 uu...
2019-01-10 20:08:30
242
原创 [Codeforces 666E]Forensic Examination（广义后缀自动机 + 线段树合并 + 树上倍增）
Address洛谷 RemoteJudgeCodeforces 666EMeaning给定一个字符串 SSS 和 mmm 个字符串 T1,T2,...,TmT_1,T_2,...,T_mT1,T2,...,Tm有 qqq 个询问，每个询问给出四个参数 lll 、 rrr 、 plp_lpl 、 prp_rpr求 SSS 的子串 [pl,pr][p_l,p_r][pl,...
2019-01-03 21:00:24
264
原创 [Codeforces 79D]Password（BFS + 状压 DP）
Address洛谷 RemoteJudgeCodeforces 79DMeaning有 nnn 枚硬币，一开始全部正面朝上给定一个大小为 lll 的正整数集合 aaa每次可以选定一个长度 w∈aw\in aw∈a ，将一段连续的 www 枚硬币全部翻转求使得最后仅有给定的 kkk 枚硬币 a1,a2,...,aka_1,a_2,...,a_ka1,a2,...,ak 反面...
2019-01-03 17:42:49
4689
原创 [学习笔记]网络流·最小割题目选讲
已经 2 周没写博客了引入最小割的概念：给定一个图，含源点 SSS 和汇点 TTT ，每条有向边有容量选出一些边删掉，使得没有从 SSS 到 TTT 的路径求选出的边的容量和的最小值最大流和最小割都是线性规划问题中的一类最小割可以看成是最大流的对偶问题定理：最大流 === 最小割证明显然最小割不能小于最大流我们知道，跑完最大流之后，残余网络中没有从 SSS 到 TTT 的...
2019-01-01 16:12:23
693
原创 [Codeforces 1042E]Vasya and Magic Matrix（期望 DP）
Address洛谷 RemoteJudgeCodeforces 1042EMeaning一个 nnn 行 mmm 列的矩阵，每个位置有个权值给定一个起始位置 (r,c)(r,c)(r,c)每次等概率随机地移动到一个权值严格比自己小的位置，得分为移动前和移动后的两个位置的欧几里得距离的平方，这样一直移动直到无法移动为止求得分的期望1≤n,m≤10001\le n,m\le 10...
2018-12-16 22:36:04
290
原创 [BZOJ5020][THUWC 2017]在美妙的数学王国中畅游（LCT + 一点数学知识）
Address洛谷 P4546BZOJ 5020LOJ #2289Solution如果只有一次函数 ax+bax+bax+b ，那么这是非常裸的 LCT ，维护 aaa 之和与 bbb 之和即可然后你会发现ea1x+b1×ea2x+b2=e(a1x+b1)(a2x+b2)=ea1a2x2+(a1b2+a2b1)x+b1b2e^{a_1x+b_1}\times e^{a_2x+b...
2018-12-16 17:43:39
249
原创 [BZOJ2655]calc（DP + 拉格朗日插值）
Address洛谷 P4463BZOJ 2655Solution显然我们有个 DPf[i][j]f[i][j]f[i][j] 表示选出 iii 个无序的， [1,j][1,j][1,j] 内的互不相同的整数的所有方案乘积之和∀j≥0,f[0][j]=1\forall j\ge 0,f[0][j]=1∀j≥0,f[0][j]=1∀i&gt;0,f[i][0]=0\fora...
2018-12-16 16:18:08
324
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人