- 博客(461)
- 收藏
- 关注
RSS订阅
原创 NOI2019 复习
GDOI2018复习图论( )网络流相关（二元关系，最大权闭合子图、最长反链，上下界网络流） ( )差分约束系统 ( )欧拉回路 ( )2-SAT动态规划树形依赖DP，数位DP、斜率优化DP搜索、博弈( )SG函数 ( )A*、IDA* Nim游戏字符串KMP ( )扩展KMP ( )AC自动机 ( )SA (D)SAM mana...
2019-07-09 19:54:04
1646
原创 OI中一些常见实用的套路【更新中】
数据结构在维护树上路径时，如果只是点的独立的加减，可以考虑用括号序来维护（拆成两部分）需要求树上很多路径中k近/距离和 一类，考虑点分治/在点分树上解决。子树求和可以转化为DFS序上区间求和树状数组可以区间查询/修改（差分）需要查询序列上区间数据结构，只要满足总和是可以接受的范围，可以用线段树，每个区间维护一个这样的数据结构（例如AC自动机等）多维偏序问题，排序可以降维，CDQ分治可...
2018-10-20 22:04:46
1600
原创 比赛注意事项
Text比赛结束前检查文件名、文件夹，并且将所有程序编译一遍尽量打对拍，实在不能打对拍就多出几组数据。多组数据的情况下尽量清空数组。注意常数优化，能用int尽量用int，尽量减少函数向外带的东西、读多几遍题，有些题目有一些关键点不要漏掉（比如说+1。。。）不要轻易放弃某一种思路，尽量将所有想到的思路记录下来。 。 。 。
2017-10-30 16:00:17
800
原创 About Me
Who am I中山纪念中学2017届初中一名蒟蒻 中文名：HZJ English name:Jim QQ and Wechat :1054689699My friendsalan_cty HOWARLI lyd729 等等
2016-04-15 19:32:13
1477
转载 【WSL】WSL运行32位程序
WSL是64位，运行32位程序会出一些莫名其妙的Bug一种解决办法：安装 qemu and binfmt在shell中键入sudo apt updatesudo apt install qemu-user-staticsudo update-binfmts --install i386 /usr/bin/qemu-i386-static --magic '\x7fELF\x01\x01\x01\x03\x00\x00\x00\x00\x00\x00\x00\x00\x03\x00\x03\x00
2021-09-25 23:20:31
575
原创 【AI学习总结】均方误差（Mean Square Error,MSE）与交叉熵（Cross Entropy,CE）损失函数
这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题，有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注释也是必不可少的KaTeX数学公式新的甘特图功能，丰富你的文章UML 图表FLowchart流程图导出与导入导出导入欢迎使用Markdown编辑器你好！ 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Mar
2021-07-05 00:37:48
1683
原创 【学习小记】Berlekamp-Massey算法
PrefaceBM算法是用来求一个数列的最短线性递推式的。形式化的，BM算法能够对于长度为n的有穷数列或者已知其满足线性递推的无穷数列aaa，找到最短的长度为m的有穷数列ccc，满足对于所有的i≥ni\geq ni≥n，有ai=∑j=1mcjai−ja_i=\sum\limits_{j=1}^{m}c_ja_{i-j}ai=j=1∑mcjai−jTextBM算法的流程十分简洁明了—...
2019-07-03 22:27:10
611
原创 【总结】【NOI2019模拟7.3】
TextT1：爆精度题DP？多项式？可以乱搞？确实是爆精度大概不用很多轮精度就够了，题解是10^7只靠虑非中性多少轮考虑非中性i轮的次数期望，以及i轮非中性后合法的概率，乘在一起求和这两个东西都可以递推概率直接考虑意义期望轮数可以考虑它的生成函数，等比数列求和以后是一个1阶的线性递推，第0项和第1项要暴力算。T2：线性基？可以试一下进制数为2写了个猎奇搜索搜了17...
2019-07-03 21:50:40
374
原创 [JZOJ6247]【NOI2019模拟2019.7.2】C【计数】
Descriptionn<=200000Solution比赛时没做出这道题真的太弟弟了首先我们从小到大插入数i，考虑B中有多少个区间的最大值为i恰好出现的次数不太好计算，我们考虑计算最大值小于等于i，再做一个差分即可。然后直接分成长度在一段内的和长度跨过一段边界的考虑，跨过完整的一段的区间的答案一定是整个序列最大值分类讨论即可，式子并不难推，有一个地方可以直接暴力计算前缀和。...
2019-07-02 22:18:16
243
原创 【总结】【NOI2019模拟7.2】
Text今天这比赛打的相当的弟弟T1: 树上关于链的计数，感觉是点分治：60分送的前20 N方3 单独计算边的贡献一条链直接算。8:49先写暴力！！60分暴力拍过然后就不管了（事实上这个题感觉当时再想多一会就想出来了）T2:直接MTT多项式exp根号DP？？不会MTT一秒十万应该能过0.93s有点慌后来优化到了0.89sT3序列计数？33分暴力走人估分60...
2019-07-02 15:36:14
350
原创 [JZOJ6244]【NOI2019模拟2019.7.1】islands【计数】【图论】
Descriptionn<=1e9,M,K<=100Solution显然任选m个港口的答案是一样的，乘个组合数即可。考虑枚举m个港口的度数之和D可以DP计算记Fm,DF_{m,D}Fm,D为将D的度数分给m个港口的方案数枚举新的一个度数分配给谁，然后此时可能某一个超出了限制，减掉这一个的贡献。接下来我们可以用一个超级根把D个点连起来prufer序简单计数即可n−m...
2019-07-01 22:16:20
272
原创 [JZOJ6244]【NOI2019模拟2019.7.1】Trominoes 【计数】
Descriptionn,m<=10000Solution考虑暴力轮廓线DP，按顺序放骨牌显然轮廓线长度为N+M轮廓线也是单调的1表示向上，0表示向右N个1,M个0只能放四种骨牌四种转移写出来，就是1000 00011110 01111010 00111100 0101相当与一个1和后面3格的一个0换过来，中间不变把模3相同的分组， 转换成只换相邻的10再把...
2019-07-01 22:07:40
239
原创 【总结】【NOI2019模拟7.1】
Text一看题感觉T1比较有搞头，后面两题比较毒，先肝T1题目想法：T1 容斥？题目要求某些位或必须为１容斥若干位必须为０多组询问？高维前缀和F(T)=\sum [S is a subset of T] G(S) (-1)^|S|G(S) 为1的位置强制选0算出这样的个数，直接组合数计算G(S)=C(cnt(S),k)高维前缀和：f全部小于等于g前i位等于，后面小于等...
2019-07-01 19:33:30
259
原创 [JZOJ6241]【NOI2019模拟2019.6.29】字符串【数据结构】【字符串】
Description给出一个长为n的字符串SSS和一个长为n的序列aaa定义一个函数f(l,r)f(l,r)f(l,r)表示子串S[l..r]S[l..r]S[l..r]的任意两个后缀的最长公共前缀的最大值。现在有q组询问，每组询问给出L,R,xL,R,xL,R,x你需要找到一个子串S[l,r]S[l,r]S[l,r]满足[l,r]⊂[L,R][l,r]\subset[L,R][l,r]...
2019-06-30 22:29:59
228
原创 [JZOJ6231] 【NOI2019模拟6.25】等你哈苏德【图论】【欧拉回路】【网络流】
Description数轴上有一些线段，需要将它们染成黑或白色，有些已经染好了颜色，现在求一种染色方案使得对于所有整点，覆盖它的黑色线段和白色线段数之差的绝对值不超过1n<=30000n<=30000n<=30000Solution我们把白色看做+1，黑色看做-1，问题变成要求每个位置的值只能是[−1,0,1][-1,0,1][−1,0,1]由于是区间加...
2019-06-30 22:15:35
352
原创 [JZOJ5553] 【NOI2019模拟6.24】谜【线性代数】
Description有一个两个部分均为n个点的二分图，给出它的邻接矩阵，求这个二分图的完美匹配数量模2的结果。两个部分另外各有m、k个备用点，给出它们与原图中点的连边关系。现给出q组询问，每次询问形如将某一个部分的某个点u替换成该部分的某一个备用点v后，求这个二分图的完美匹配数量。询问没有后效性，也就是说每个询问都是在原矩阵的基础上做的。n,m,k<=1000,q&...
2019-06-30 22:15:29
565
原创 [JZOJ5551] 【NOI2019模拟6.24】旅途【最短路】
Description给出一个n个点m条边的带边权无向图定义1到n的K最短路为所有1到n的路径中，路径上的边权前K大和的最小值。求K=1~n的最短路。n,m<=3000,边权<=10^9Solution首先我们考虑枚举第K大的边，将小于这条边的所有边记为0（相等的话强行给一个顺序）考虑一个朴素的DPf[i][j][0/1]f[i][j][0/1]f[i][j][0/1]，...
2019-06-30 22:15:24
251
原创 [JZOJ6223] 互膜 【线段树】【单调栈】【DP】
DescriptionSolution我们可以设一个朴素的DP记f[i][0/1]f[i][0/1]f[i][0/1]表示第i−1i-1i−1轮上一个人是否操作了i这个位置，当前先手-当前后手的权值的最大值。显然Ans=Sum+f[1][0]Ans=Sum+f[1][0]Ans=Sum+f[1][0]容易得到转移f[i][0]=−f[i+1][1]+s[i]f[i][0]=-f[i+1...
2019-06-30 22:15:18
194
原创 [JZOJ6221] 担心 【区间DP】【概率】
Description有n个人，每个人有水平值AiA_iAi每一轮随机挑选剩余的相邻两人单挑，假设两人能力值为a,ba,ba,b，则能力值为aaa的人有aa+ba\over a+ba+ba的概率获胜，能力值为bbb的人有ba+bb\over a+ba+bb的概率获胜。给出n,m以及A，问第m个人获胜的概率，答案对998244353取模。n≤100000,A≤109n\leq 1000...
2019-06-30 22:15:12
192
原创 [JZOJ6217] Area【计算几何】
Description给定平面上的n个点，记为A1...nA_{1...n}A1...n现在给出q组询问，每次给出一个向量P，你需要找一个区间[L,R][L,R][L,R]，使得2∑i=lrSΔOPAi2\sum\limits_{i=l}^{r}S_{\Delta OPA_i}2i=l∑rSΔOPAi最大，输出这个最大值。n<=100000,q<=1000000，坐标绝对...
2019-06-30 22:15:07
185
原创 [省选联合集训2019] 小结
Preface总体上来说，这段时间的比赛状态有好有坏，第一天的状态不是很好，后面就渐入佳境，比赛的成绩和题目理解的程度也提高了很多。Text模拟赛Day1，Day2 By SamjiaDay1的题目很有种PKUWC的感觉，三道题两道计数一道排列构造，数据范围都是什么20之类的，感觉很不符合Samjia的出题风格。T1一开始大家都以为是简单题，结果大部分人（包括我都是做了3h没有做出来心态...
2019-06-30 22:14:31
247
原创 【GDSOI2019】滑稽二乘法【数据结构】【LCT】
Description点数<=100000，操作数<=200000Solution经典的LCT维护子树路径信息的问题。具体来说，我们对于每一个节点，它在splay上的子树对应了原树中的一条祖先后代链（换过根的），记录这个点的splay子树中的所有黑点以及它们的虚子树中的所有黑点分别到这条祖先后代链的链顶和链底的0次，1次，2次距离和，另外记录splay的子树的所有虚儿子到这条...
2019-06-26 20:24:22
287
原创 【学习小记】支配树【图论】
Preface给定一个有向图和一个起点ststst，我们需要知道起点到某个点的关于必经点的信息。若起点到点v的所有路径均经过点u，则我们称点u支配点v，显然一个点支配自己本身顾名思义，支配树就是由某些支配关系构成的树。定义约定一些记号(u,v)(u,v)(u,v)，表示一条从u到v的有向边fa(u)fa(u)fa(u)，表示uuu在DFS树上的父亲。dfn(i)dfn(i)dfn(...
2019-06-26 15:16:21
322
原创 一类三维子长方体计数问题【计数】
Description有一个n∗m∗ln*m*ln∗m∗l的长方体，每个位置有0/1的权值对于每个为1的位置，要求包含这个位置且内部全为1的子长方体个数。n≤60n\leq 60n≤60Solution我们不妨考虑二维该如何数子矩形。如果我们枚举每个合法的矩形，矩形内部+1，可以在左上角，右下角+1，左下右上-1，做一遍二维前缀和就可以得到答案，三维是类似的。如果我们能求出每个位置分...
2019-06-26 14:36:05
266
原创 【总结】【NOI2019模拟2019.6.20】
Text今天精神状态还算好看题T1又是大数据结构？暴力分不少emmmT2乱搞？暴力分不少…T3？？？暴力分不少…随便猜了个T2结论，似乎是对的。然后就一直想T2原本想着9:50再弄不出来就写暴力结果刚好想出来了但是我的做法细节比较多，然后就一直写写写加上思路并不是很清晰又一直调调调调到最后总算拍上了，测大数据发现要跑4s心态炸了然后又开始调调调到最后发现是线段树有个地...
2019-06-21 16:22:42
332
原创 【杂题】[CodeForces 1172F] Nauuo and Bug【数据结构】【线段树】
Description给出一个长度为n的序列a和一个整数p有m组询问，每组询问给出一个区间[l,r][l,r][l,r]你需要给出下面这个过程的结果ans = 0 for i from l to r{ ans = ans + a[i] if ans > p then ans = ans - p;}return ans n≤106n\leq 10^6n≤106m&am...
2019-06-19 20:13:57
214
原创 【杂题】[CodeForces 1172E] Nauuo and ODT【LCT】【口胡】
Description给出一棵n个节点的树，每个点有一个1~n的颜色有m次操作，每次操作修改一个点的颜色需要在每次操作后回答树上n2n^2n2条路径每条路径经过的颜色种类数和。n,m<=400000n,m<=400000n,m<=400000Solution挺有意思的一个套路首先我们单独计算每种颜色的贡献，对于每种颜色的点集分开考虑，我们需要计算至少...
2019-06-16 22:16:13
279
原创 【杂题】【CometOJ Contest #5】E：迫真大游戏【概率】【排列组合】【多项式】
Description有一个n个点的环，有一个指针会从1号点开始向后扫描，每次扫描有p的概率删除当前点询问每个点最后一个被删除的概率。答案对998244353取模n<=200000Solution直接计算要考虑前后两部分比较麻烦，我们不妨先考虑1号点如何计算。记fnf_nfn表示n个点的环1号点最后一个被删除的概率。枚举一轮中删去了几个fn=∑i=0n−1pi(1−p)n...
2019-06-15 21:13:00
266
原创 【杂题】[CodeForces 1172D] Nauuo and Portals【构造】
Description有一个n*n的网格，你需要在上面设置一些传送门，传送门由两个配对的格子组成，从一个进入会立刻从另一个同一方向出来。现在有n个人从第1列出发向右走，位于(i,1)的人要走到(ri,n)n个人从第一行出发向下走，位于(1,i)的人要走到(n,ci)求一种设置传送门的方案。n<=1000Solution很有意思的一个构造。我们先考虑第一行第一列如果他们都是一...
2019-06-13 22:35:27
182
原创 有向图邻接矩阵的幂敛指数与周期【图论】
Description定义有向图邻接矩阵A的周期为最小的d，使得存在正整数k，对于任意n>=k，都有An=An+dA^n=A^{n+d}An=An+d最小的k称为A的幂敛指数。现给出一个n个点，m条边有向图，求它的邻接矩阵的周期对10^9+7取模的结果。n<=100000,m<=200000对于n<=200,m<=3000的数据，你还需要求出它的幂敛指数。...
2019-06-13 17:40:07
645
原创 【杂题】[AGC034F] RNG and XOR【集合幂级数】【FWT】【DP】
Description你有一个随机数生成器，它会以一定的概率生成[0,2^N-1]中的数，每一个数的概率是由序列A给定的，Pi=Ai/sum(Ai)现在有一个初始为0的数X，每一轮随机生成一个数v，将X变成X xor v求X变成0~2^N-1的期望轮数答案对998244353取模N<=18,Ai<=1000Solution不妨反过来做，f[i]为i到0的期望轮数，显然等价...
2019-06-12 22:03:09
589
原创 【杂题】[AGC034D] Manhattan Max Matching【费用流】
Description有一个无限大的平面，有2N个位置上面有若干个球（可能重复），其中N个位置是红球，N个位置是蓝球，红球与蓝球的总数均为S。给出2N个位置和上面的球数，现要将红球与蓝球完美匹配，匹配的权值是每一对匹配两个球的位置坐标的曼哈顿距离之和。求最大权值。N<=1000,每个位置上球数<=10，坐标非负且<=10^9Solution直接两两连边显然不行但又不...
2019-06-12 21:54:37
278
原创 【杂题】[ARC070F] Honest Or Unkind【交互】
Description这是一道交互题有A+B个人，编号从0~A+B-1，其中有A个人是诚实的，B个人是居心叵测的。你想知道每个人是诚实的还是居心叵测的。询问可以用二元组(i,j)表示，代表问编号为i的人 编号为j的人是否诚实。诚实的人总会说真话，你不知道居心叵测的人会如何回答。（你可以理解为，交互库是自动适应的）你只知道A,B，需要在2N次询问内得到答案，或者判断居心叵测的人一定存在一...
2019-06-12 20:16:34
168
原创 【杂题】[LibreOJ #6608] 无意识的石子堆【容斥原理】【FFT】
DescriptionSolution943718401=225*2^22+1显然每行必须有两个，我们不妨枚举有k列有2个石子，那么有2(n-k)列有1个石子。Ans=∑k=0n(mk)(m−k2(n−k))SkAns=\sum\limits_{k=0}^{n}{m\choose k}{m-k\choose 2(n-k)}S_kAns=k=0∑n(km)(2(n−k)m−k)Sk...
2019-06-10 21:16:26
386
1
原创 【PKUSC2019】线弦图【计数】【树形DP】【分治FFT】
Description定义线图为把无向图的边变成点，新图中点与点之间右边当且仅当它们对应的边在原图中有公共点，这样得到的图。定义弦图为不存在一个长度大于3的纯环，纯环的定义是在环上任取两个不相邻的点，它们之间都没有边，也就是不存在没有弦的环的无向图。现在给出一棵n个点的树，你可以在上面添加任意多条边（不能重边），要求得到的图的线图是弦图，求加边的方案数。n<=200000Solut...
2019-05-29 20:08:12
464
原创 【PKUSC2019】树染色【线段树合并】【树形DP】
Description给出一棵n个点的树，现在有m种颜色，要给每个节点染色，相邻节点不能同色。另外有k条限制，形如x号点不能为颜色y同一节点有可能哟多条限制。求方案数对998244353取模的结果。Solution考场上一直在想怎么容斥做，怎么都弄不出来。学傻了。考虑暴力DP设f[i][j]f[i][j]f[i][j]为当前处理了以i为根的子树，i的颜色为j的方案数。记g[i]...
2019-05-29 11:54:54
723
原创 [LibreOJ 3124]【CTS2019】氪金手游【容斥原理】【概率】【树形DP】
DescriptionSolution首先它的限制关系是一个树形图首先考虑如果它是一个外向树该怎么做。这是很简单的，我们相当于每个子树的根都是子树中最早出现的点，概率是容易计算的。设DP状态f[i][j]f[i][j]f[i][j]为做到以i为根的子树，子树中权值W的和为j且满足限制关系的概率。然后就可以直接利用子树背包DP来转移了。如果有些边是反向（儿子到父亲）的，我们可以通过...
2019-05-21 20:14:06
259
原创 [LibreOJ 3120]【CTS2019】珍珠 【生成函数】【计数】
DescriptionSolution有一个直观的思路是考虑每种颜色个数的奇偶性，奇数个数的颜色不能超过n−2mn-2mn−2m因此若n−2m≥Dn-2m\geq Dn−2m≥D则答案一定是DnD^nDn否则由于每种颜色其实没有区别，我们考虑一种颜色为奇数和为偶数的指数型生成函数奇数是ex−e−x2e^x-e^{-x}\over 22ex−e−x，偶数是ex+e−x2e^x+e^{...
2019-05-21 19:59:09
2422
2
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人