- 博客(170)
- 收藏
- 关注
RSS订阅
原创 图论整理
文章目录最短路连通性生成树团和独立集欧拉和汉密尔顿流树others最短路SPFAdijkstra：已处理集合和待处理集合floyd：DP差分约束最短路图，最短路树：例题：每第一次到一个点可以ban掉一条边，求最坏情况最短路k短路：A*连通性强连通点双边双tarjan支配树（dominator tree）例题：DZY loves Chinese II，claris th...
2019-08-08 11:57:34
172
原创 狄利克雷卷积 & 莫比乌斯反演 & 杜教筛 の 学习笔记
狄利克雷卷积性质常见积性函数常见积性函数证明莫比乌斯反演前置知识——整除分块推公式和gcd的关系还有各种例题各种例题[POI]Zapluogu 简单的数学题bzoj2154 Crash的数字表格杜教筛优秀blogbzoj 3944 sum复杂度？？？...
2019-07-18 21:12:56
203
原创 决策单调性和斜率优化
文章目录决策单调性[poi]lightning conductor[noi2009]诗人小G斜率优化[jsoi2011]柠檬[noi2007]货币兑换决策单调性[poi]lightning conductor[noi2009]诗人小G斜率优化[jsoi2011]柠檬[noi2007]货币兑换...
2019-07-17 20:39:43
243
原创 莫队算法（在更）
文章目录莫队例题小z的袜子树上莫队带修莫队莫队运用了分块的思想。排序来尽量减少重复的计算。具体理解请看例题。例题小z的袜子来源：bzoj2038题意：给出序列，每个询问求一个区间内等概率随机取两个数，有多大概率两数相等。那我们分三步思考：一、单个询问对于一个询问，总可能数：C(n,2)=n∗(n−1)/2C(n, 2) = n*(n-1)/2C(n,2)=n∗(n−1)/2...
2019-05-23 12:02:13
194
原创 分块学习笔记（待更）
文章目录简介注意点用多大的块好呢例题模板简介就是暴力注意点I . n\sqrt{n}n的大小先输出来看看II . 块数===块大小///块大小+1，所以最好用blo[n]blo[n]blo[n]表示III . 特判block[l]==block[r]block[l] == block[r]block[l]==block[r]的情况IV . 对拍技巧（by hzwer）：用两份分块大...
2019-03-02 16:04:02
159
原创 各种模板
文章目录1矩阵2图（邻接表）2.1有边权2.2没边权3快读4树状数组4.1区间求和4.2区间最值(max)5平衡树5.1无旋Treap5.2 Splay6主席树6.1静态7计算几何7.1凸包8后缀数组1矩阵void add(int &x, int y){if ((x += y) >= mod) x -= mod;}int mul(int x, int y){return 1ll...
2019-02-17 11:32:46
538
原创 数学整理
文章目录线性筛欧几里得和拓展欧几里得欧拉函数欧拉定理费马小定理乘法逆元的三种求法中国剩余定理及其扩展卡特兰数斯特林数持续更新。线性筛欧几里得和拓展欧几里得欧拉函数欧拉定理费马小定理乘法逆元的三种求法中国剩余定理及其扩展卡特兰数斯特林数...
2019-02-01 10:58:06
402
原创 BZOJ 刷题记录
前言这篇博客完全是为了个人记录用的，用来防止计划咕咕咕。对除了博主本人之外的任何人没有参考价值，而且没有题解。开始2019年1月23：[HNOI2008] 水平可见直线...
2019-01-23 21:50:39
422
2
原创 2022 年 box 小游戏项目总结
文章目录box-game-2021 项目总结技术方面寻路算法js 模块下载一些比较细小的点组内交流规划分锅组间交流交接部分参数的确定设计理念的沟通box-game-2021 项目总结今天是 2022 年 1 月 30 日。到今天为止，box 小游戏的技术部分大概算是告一段落了。box 小游戏是我进入求是潮之后写的第一个完整的项目，第一次写出一个表现自己 idea 的 js 小游戏，也是我第一次在项目中与队友和其他小组的成员合作。虽然准备不充分，中途甚至大改了一次算法；交流也不够，最后技术和设计双方都不得
2022-01-30 18:39:02
2632
原创 2022年寒假复健
文章目录cf1622(div.2)cf1622(div.2)前 4 题注意特判就好，C 题要注意解的合理性，舍掉小于 0 的解。E 题主要突破口在 n≤10n \leq 10n≤10，又因为每个人的贡献有绝对值，有绝对值了就不能把所有人放在一起考虑，不能算每道题的贡献，只能对每个人单独考虑。所以用 O(2n)O(2^n)O(2n) 枚举拆绝对值，然后就可以算每道题的贡献了。F 题题干非常简洁，一看就是结论题。题目问前 nnn 个数中最多可以取出多少个数，使得 ∏i=1kai\prod_{i=1}^k
2022-01-19 12:04:43
297
原创 C盘存储空间不够？拓展C盘空间的方法
一些废话（请直接跳过）：本来想直接复制 D 盘中的内容到其他分区，然后合并 C 和 D，但无奈复制速度非常慢。其实小文件复制很慢是正常的，好像每秒钟复制的文件个数不能超过几十个，所以文件小了复制速度就受这个限制了。具体原因现在未知，总之就先规避这种很慢的复制。分区管理的一些简单原理：同一块硬盘可以分为各个分区。比如说一般电脑都只配一块固态硬盘，然后在这个盘上分不同的分区（C,D,E,etc）。换句话说，虽然看起来是不同的 C 盘、D 盘，实际上在同一块硬盘上。存储空间是有顺序的，所以分区合并只能是
2021-12-05 22:05:57
2696
1
原创 bat的一些语法
文章目录loop循环赋值loop循环:start//循环内容goto start赋值什么参数也没有是让一个变量等于一串普通字符set /a 执行数学计算set /p 提示用户输入比如 set /p a=等待POP输入： ，然后窗口提示“等待POP输入：” ，输入完后 按回车下面是一个例子，它的功能是从172.19.5.1开始到172.19.5.255每一个都ping一次,然后把能ping到的IP写入ip.txt@echo offset a=1:startecho %a%pin
2021-08-11 19:58:56
296
原创 快速沃尔什变换（FWT）
文章目录概述最近学了 min-max 容斥，好像几乎每一道 min-max 容斥题都要用到 FWT 来辅助，所以顺便学一下 FWT。概述与 FFT 类似。需要求的是C(k)=∑i⊕j=kA(i)∗B(j)C(k)=\sum_{i\oplus j=k}A(i)*B(j)C(k)=i⊕j=k∑A(i)∗B(j)其中 ⊕\oplus⊕ 可以指代位运算符号，例如按位和，按位或，按位异或。实...
2019-12-16 17:12:38
423
原创 原根的性质及其求法
文章目录定义性质求原根应用1.指标2.NTT在很多地方都用到了原根，比如 NTT 用到了原根的性质，比如离散对数需要用到的指标也与原根有关。然而在此之前我对原根并不是非常了解，所以来补一补知识盲区。定义称 ggg 为 ppp 的原根，当且仅当 ggg 在 mod pmod \;pmodp 意义下的阶为 ϕ(p)\phi(p)ϕ(p) （这里的 ϕ(p)\phi(p)ϕ(p) 是欧拉函数）...
2019-12-14 16:13:29
1850
3
原创 【香蕉OI】GCD 和 LCM （莫比乌斯反演）
文章目录题意思路代码题意给出 TTT 组询问，每组询问求 ∑i≤n∑j≤m[gcd(i,j)≤a]lcm(i,j)\sum_{i\le n}\sum_{j\le m}[gcd(i,j)\le a]lcm(i,j)i≤n∑j≤m∑[gcd(i,j)≤a]lcm(i,j)T≤104,n,m,a≤105T\le 10^4,n,m,a\le 10^5T≤104,n,m,a≤105思路比赛的送...
2019-12-14 10:57:29
478
原创 二项式反演证明
二项式反演有两种形式：对称形式f(n)=∑i=0n(−1)i(ni)g(i)⇔g(n)=∑i=0n(−1)i(ni)f(i)f(n)=\sum_{i=0}^n(-1)^i{n\choose i}g(i)\Leftrightarrow g(n)=\sum_{i=0}^n(-1)^i{n\choose i}f(i)f(n)=i=0∑n(−1)i(in)g(i)⇔g(n)=i=0∑n(−1...
2019-12-13 11:52:06
875
原创 线段树合并复杂度证明
摘抄自 styx的博客假如初始所有的线段树点数总和为 NNN 。因为只要合并两个节点，节点总个数就会少掉一个，所以复杂度应该是 O(N)O(N)O(N) 的。所以不是所有情况下的线段树合并都是 O(nlogn)O(n \log n)O(nlogn) 的。一般情况下我们只会对每个节点开动态开一条链，所以 N=nlognN=n\log nN=nlogn ，复杂度才会是 O(nlogn)O(...
2019-12-11 07:46:21
906
原创 【香蕉OI】染色游戏（容斥，树型DP）
文章目录题意思路代码恢复训练。题意有一棵树，节点个数 n≤1000n \le 1000n≤1000 。初始每个点都是白色，每次等概率选一个点，把他和与他直接相连的点染成黑色。求将整棵树染成黑色的期望步数。思路首先，设 PiP_iPi 表示染了 iii 次还没有把整棵树全部染黑的概率。所求的答案可以转化为∑i=0+∞Pi\sum_{i = 0}^{+\infty}P_ii=0∑+...
2019-12-09 14:31:49
224
原创 【noip 2015】 斗地主（搜索、记忆化搜索）
文章目录题意思路代码题意斗地主。问你最少几次能把所有牌出完。具体出牌规则详见各大 OJ 。思路很明显，先把所有顺子暴力搜掉，然后处理带的问题。我原本想直接贪心做带的问题，但是非常麻烦。考虑到牌数非常少，可以直接记录一个状态 fc1,c2,c3,c4,c0f_{c1,c2,c3,c4,c0}fc1,c2,c3,c4,c0 分别表示有 1,2,3,4 张牌的牌种的数量和王的数量。然后...
2019-11-14 14:40:40
174
原创 【牛客 CSP-S 模拟 4】 排列计数姬（第二类斯特林数、DP 线段树优化）
文章目录题意思路注意代码题意一个序列的权值定义如下：假设该序列为 a1,...aka_1,...a_ka1,...ak ，他的权值就是 ∀1≤i≤k,max(a1,a2,...ai)\forall 1\le i\le k,max(a_1,a_2,...a_i)∀1≤i≤k,max(a1,a2,...ai) 有多少种不同的取值。现在有一个 111 到 nnn 的排列（ n≤105n ...
2019-11-13 15:49:35
170
原创 【bzoj 4289】 tax（最短路）
文章目录题意思路代码题意一张无向图，经过一个点的代价是入边和出边的较大值，起点是出边的值，终点是入边的值。求 1 到 n 的最短路。思路化边为点很显然。但是假如碰到菊花就萎了。所以下面是一种挺神奇的思路。把无向边拆成两个有向边。每个点的所有出边排序，出边之间，代价小的向代价大的连边权为他们边权差的边，代价大的向小的连边权为 0 的边。对于每一条边 iii ，假如他从 uuu 走...
2019-11-12 20:28:14
173
原创 【香蕉OI】11.12 模拟赛
文章目录T1题意思路代码T2题意思路代码T3题意思路代码后记今天做的太差了，全都写一写。T1题意一棵有根树，每个点有一个颜色。离线询问，每次询问一个子树中第 k 大的颜色。空间 16 MB。思路卡空间的题。主席树显然不行，但是 dsu on tree 却可以。没有难度，没想到 dsu on tree 是我菜。代码#include<bits/stdc++.h>usi...
2019-11-12 19:20:21
235
原创 【香蕉OI】月之美兔（最短路）
文章目录题意思路代码题意有一条线上有 nnn 个点，有 mmm 个人，第 iii 个人站在 aia_iai 位置，可以花一个代价向左或者向右跳 fif_ifi 的距离。现在一个东西在 111 号人手里，想要把这个东西交到 222 号人手里。一个人可以把东西转交给另一个人当且仅当两个人在同一个位置。求转交的最小代价。n,m≤2∗104n,m\le 2*10^4n,m≤2∗104思路首...
2019-11-11 19:41:00
197
原创 【NOIP 2018】 旅行（贪心）
文章目录题意思路代码时隔一年，终于做掉了这题。当时思维僵化，连这种贪心都想不出来，真的是菜的不行。题意有一棵树或者基环树，每个点有一个标号。要求以一定的顺序深度优先遍历这棵树，使 dfs 序的字典序最小。思路因为字典序最小，只要有某一位的标号不够优了，后面的决策就不可能使他再次变为最优。所以显然可以贪心。对于树的情况，dfs 从 1 号点开始，并且每次把一个点的所有儿子拖出来排序，从...
2019-11-11 15:39:43
184
原创 【luogu 3898】大新闻（数位 DP）
文章目录题意思路代码题意**记者弄了个大新闻，这个新闻是一个在 [0,n) 内等概率随机选择的整数，记其为 x。为了尽可能消除这个大新闻对公众造成的不良印象，我们需要在 [0,n)内找到某一个整数 y，使得 x ⊕ y 达到最大值。这里 ⊕ 代表异或。问题在于，**记者有可能对大新闻进行了加密。情报显示，大新闻没有被加密的概率为 p。我们决定采取这样的策略：如果大新闻没有被加密，那么我们选出...
2019-11-10 21:25:46
172
原创 【香蕉OI】扫雷（概率期望）
文章目录题意思路注意代码题意如题，你在玩扫雷。有些格子是雷，不是雷的格子有一个数字，表示他周围 8 个格子里有多少雷。有一个 n∗mn*mn∗m 的游戏界面。一共有 www 个雷，其中有 kkk 个已经确定，其他的所有 Cn∗m−kw−kC_{n*m-k}^{w-k}Cn∗m−kw−k 种布雷方案概率相等。求所有不是雷的格子的数字之和的期望和方差。(n∗m≤4∗105)(n*m\le 4...
2019-11-08 20:34:38
407
原创 【codeforces 954 D】 fight against traffic （最短路）
文章目录题意思路代码题意一张无向连通图。现在要求再加一条无向边，保证加边之后无重边自环，且 sss 到 ttt 的最短路长度不变。问有多少种加边方案。思路简单图论题，但是我胡了一个假的做法并且在长达一天的时间里一直以为自己是对的 qwq做法是先分别求出所有点 sss 和 ttt 的最短路。然后枚举两个原图中没有连边的点 i,ji,ji,j，判断连上之后 (s,i,j,t)(s,i,...
2019-11-08 11:39:47
245
原创 【牛客 CSP-S 模拟 1 B】 乃爱与城市拥挤度（树型 DP）
文章目录题意思路代码题意给一棵树， n≤105n\le 10^5n≤105。对每个点，先钦定他为根，然后把与根的距离超过 k(k≤10)k(k\le 10)k(k≤10) 的点删掉。对于剩下的树，求两个值：树上点的个数树上所有点的子树大小的乘积思路简单 毒瘤树型 DP。状态很显然，f[u][k]f[u][k]f[u][k] 表示 uuu 为根的大小为 kkk 的子树的点数， 而...
2019-11-07 21:36:09
150
原创 【codeforces 442 B】 Andrew and problem（贪心）
文章目录题意思路代码题意你有 nnn 个朋友，每个朋友有 pip_ipi 的概率切出一道题。现在需要选一个朋友集合，最大化集合内朋友恰好只切出一道题的概率。思路胡结论好题。结论是按 pip_ipi 从大到小排序，取的肯定是一个前缀。现在来证明结论：首先假如我有一个集合 SSS ，恰好切出一道题的概率是WS=∏i∈S(1−pi)∑i∈Spi1−piW_S=\prod_{i\in...
2019-11-06 20:51:36
137
原创 【香蕉OI】hope（概率期望）
文章目录题意思路代码题意有一棵树，初始所有点是黑色，给出一个概率 ppp ，有以下两种操作：把点 xxx 和与他直接相连的点都染色，有 ppp 的概率染白， 1−p1-p1−p 的概率染黑询问当前状况下白点个数的方差思路首先要知道方差是什么。 方差等于平方的期望减去期望的平方。那么考虑如何设计随机变量。先假设 ai=[colori=white]a_i=[color_i=white...
2019-11-05 19:43:49
172
原创 【香蕉OI】阅读（AC自动机、拓扑排序）
文章目录题意思路代码题意有 n(n≤105)n(n\le 10^5)n(n≤105) 个字符串， ∑l≤105\sum l\le 10^5∑l≤105 。现在要将所有字符串的所有前缀分组，保证每组内的字符串不能有包含关系。求最小的组数。思路首先考虑建出 AC 自动机，每个前缀就是 AC 自动机上的一个节点。我考虑不出来，但是好像处理字符串也就那么几个算法，挑一个用就好了。然后考虑子串...
2019-11-04 21:06:39
224
原创 【香蕉OI】 chy2003 Contest 1
文章目录T1 night题意思路代码T2 dawn题意思路注意代码T3 light题意思路代码chy2003 大爷出的题。本来这套题一眼看上去对我这种蒟蒻挺友好的，但是，反正每次只要是我自我感觉蛮良好的时候，最后成绩都挺惨的。期望得分 240 ，实际得分 175 。T1 night题意有一些 m(m≤20)m(m\le 20)m(m≤20) 位二进制数 aia_iai 和一个 bbb...
2019-11-04 15:28:29
309
3
原创 【香蕉OI】 假期生活 【codeforces 300iq contest 1 D】 Dates （贪心）
文章目录题意思路代码题意来自 租酥雨在接下来的 ttt 天时间里，有 nnn 个女孩子想要和 xxx 约会。第 iii 个女孩子想要在 [li,ri][li,ri][li,ri] 中的某一天和 xxx 约会，且约会后 xxx 会得到 pip_ipi 的偷税值。在这里，我们保证 li≤li+1,ri≤ri+1li≤li+1,ri≤ri+1li≤li+1,ri≤ri+1 。xxx 在第 iii...
2019-11-03 21:53:24
353
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人