- 博客(814)
- 收藏
- 关注
RSS订阅
原创 漫长的告别
这是我漫长竞赛生涯的故事，这些故事是我最幸福最真实的记忆，写下这些文字时也是我最热忱，最感恩的时刻。退役后和 OI 的藕断丝连让我发现，做题与比赛是我最真实的时刻，没有外面的纷争或者内心的矛盾，只有大脑的思维在碰撞，它们把我带到了另一个世界，这里很安静，纯洁，简单而又精致。当我意识到这点时，已经没有剩下的比赛让我享受了，我和 OI 的关系也仅仅是藕断丝连，在出题，讲题和盼望着比赛中与它漫长地告别。初识初一在联中的时候有社团班，当时我们班很大一部分同学选择了”信息学“，每周有一个下午去到机房学习编程。后来
2022-04-12 19:56:10
2783
7
原创 About Me
谢谢大家光临敝人博客本人准高二蒟蒻一枚来自 SC cdss一直被学长 ldxyyds 教育一直仰慕又强又帅的 dzyo 学长初二考普及组，因为歪打正着多拿了几分所以就有了一等奖，于是就认识了 Mr.Z，来到了 cdss初三考了一个压线一等奖，去省选打了个酱油，被各种初三大神打爆了高一考 csp 挂了好多好多分，最后还是去了 pkuwcpkuwcpkuwc连续两天被安排在了 $E /se 的旁边，感觉十分自闭停了 4 个月的课去参加 SCOI，侥幸进队WC 的时候一道题都没有签到成功，感觉
2020-08-26 13:06:35
778
原创 最大子段和
但这里就有严谨的小朋友要问了， 这个证明真的是对的吗？（这份 15KB 的代码刷新了小编的代码长度记录）小编也非常好奇，那么我们就来证明一下吧！那么，最大子段和为什么是正确的呢？那么，让我们用 agda 证明吧！
2022-12-11 15:36:07
701
1
原创 牛顿插值多项式
感觉是很好玩的东西，而且好像比拉格朗日插值有用，可以用来动态更新插值多项式（维护每个区间的均差。但我只理解了均差的定义和它的巧妙，还没有完全 get 背后的原理 …然后又可以继续往前和，最后发现剩下的就是。然后再拆，发现可以变成。
2022-11-21 13:53:27
723
原创 神经网络，英文字母识别
在去年的时候，学习了神经网络，实现了手写数字识别：https://www.cnblogs.com/FSYo/p/14802599.html这个很容易实现的原因是，数据全部可以在 MNIST 下载之后，我一直想实现一个生活场景中的文字识别，中文太难啦所以我们就做识别 English 的吧！我用我曾经存下来的英语作文作为训练数据，这一步主要需要克服的困难为，将字母一个一个抠出来，做成 28 * 28 的灰度图，做成之后，就可以用之前写过的神经网络来跑了。第一步：我们要从 jpg 或 png 文件里面读
2022-05-07 19:48:18
1606
原创 捧杯 ~ 图染色
学习了 pb 大师的集训队论文 《图染色问题初探》很有趣！论文介绍了如下几个（并没有相互关联的）问题：离线边染色平面图 5 染色的构造离线三分图染色问题，给出了多项式时间内 O(n1/2)O(n^{1/2})O(n1/2) 种颜色的简单的做法，以及我看不懂的 O(n2/5)O(n^{2/5})O(n2/5) 种颜色的做法 /cy。在线特殊图染色：区间图，没有长为 3 和 5 的环的图。在线 kkk 分图染色，给出了 O(k2knk−2k−1(logn)1k−1)O(k2^kn^{\frac
2022-05-05 21:24:01
353
原创 Run Run Run
学习了 2022 年集训队论文 《浅谈与 Lyndon 理论有关的字符串组合问题》写得很好，像我这样的字符串小白也能看懂Lyndon 分解若字符串 www 小于它的每一个真后缀，则称 www 是 Lyndon 串。若字符串 www 是 Lyndon 串，则 wkw′w^kw'wkw′ 是近似 Lyndon 串，其中 w′w'w′ 是 www 的前缀。串 www 可以分解位 w1c1…wkckw_1^{c_1}\dots w_{k}^{c_k}w1c1…wkck，其中 w1>⋯&
2022-04-27 18:36:31
515
原创 Van der Waerden 定理
https://zhuanlan.zhihu.com/p/150790806https://www.bilibili.com/video/av86801472/题外话：我发现 Van der Waerden 很帅 /se定理内容大概为，将自然数划分成 mmm 个集合，存在任意长度的等差数列。这里给出小学二年级 都能懂的证明（我乱想的，有错请指出）（参考了上面知乎的回答和 B 站的那个视频，不过我感觉知乎的太深奥，B 站的讲得不是很清楚）我们设 F(m,k)F(m,k)F(m,k) 表示若将 [1
2021-11-05 00:14:09
780
2
原创 正态分布？
全是个人理解正态分布是一种广泛出现的连续概率分布，比如升高，分数二项分布是离散情况下的概率分布比如仍硬币，正面的可能性是 ppp，那么仍 nnn 次，xxx 次正面的概率为 (nx)px(1−p)n−x\binom nxp^x(1-p)^{n-x}(xn)px(1−p)n−x容易得到均值 μ=np\mu=npμ=np，方差 σ2=np(1−p)\sigma^2=np(1-p)σ2=np(1−p)并且画柱状图画出来就是钟形，而且和正态分布的概率密度函数特别像对于均值为 μ\muμ 方差为 σ2\
2021-09-05 23:28:19
435
原创 NOI 2021 游记
7.23在前面墙写了个 “阿克瑞阿克”，dqa 大师补了一个 p_b_捧_杯晚上被 wss 拉去卷，我只卷了两道 NOI 的 T1 /kk，wss 就卷了好多题了7.24上午又被 wss 拉去卷，又卷了道 NOI 的简单题，然后就是笔试了听说 cy 哥哥错了道 “考前触摸键盘和鼠标” 的题，跟我去年错的一模一样 /kk试机的时候写了下去年的 d1t2，回去交发现阿掉了，心态稳健7.25因为有台风所以直接休息一天，干了啥我都忘了记得斗地主没豆豆了，看了场电影，晚上跟 wss 打 ARC因为
2021-08-02 14:05:18
1417
2
原创 杨表与钩子公式
搬运 2019 袁方舟论文我们先来简单认识一下杨表：一个标准杨表是说，每一行严格上升，每一列严格上升设杨表 λ=(λ1,λ2,…,λm)\lambda=(\lambda_1,\lambda_2,\dots,\lambda_m)λ=(λ1,λ2,…,λm) 表示有 mmm 行，每行有 λi\lambda_iλi 个数，并且 λ1≥λ2≥⋯≥λm\lambda_1\ge \lambda_2\ge\dots\ge \lambda_mλ1≥λ2≥⋯≥λm杨表的边角说的是 {(i,j)}\{(
2021-03-05 20:59:32
781
原创 「ZJOI2018」树
设大小为 nnn 的不同的树为 Tn,1,…,Tn,mT_{n,1},\dots,T_{n,m}Tn,1,…,Tn,m其中每个 TTT 表示这类树的一个集合那么求的就是 1(n−1)!k∑i∣Tn,i∣k\frac{1}{(n-1)!^k}\sum_{i}|T_{n,i}|^k(n−1)!k1∑i∣Tn,i∣k参考：传送门设 置换 fff 下的不动点为 fix(f)fix(f)fix(f)所有 fff 使得状态 XXX 在该置换下为不动点的集合为 SG(X)SG(X)SG(X)我们设
2021-02-02 21:44:56
1084
原创 CF # 1477 简要题解
有 nnn 个巧克力棍，每个长为 LiL_iLi，每次每根木棍有 Li∑L\frac{L_i}{\sum L}∑LLi 的概率被选中然后它会被分为两个长为 x,Li−xx,L_i-xx,Li−x 的巧克力棍，其中 xxx 是在 [0,Li][0,L_i][0,Li] 随机的实数求 maxL≤K\max L\le KmaxL≤K 的期望我们先从简单的问题入手，分析 n=1n=1n=1 的情况我们不看成将其分成两根，那么问题可以看成随机在 [0,L][0,L][0,L] 切若干刀注意到
2021-01-30 23:20:08
265
原创 JOI 2019 Final
A统计后缀和#include<bits/stdc++.h>#define cs const#define pb push_backusing namespace std;typedef long long ll;cs int N = 3e3 + 50;int n, m; char mp[N][N];int a[N][N], b[N][N];int main(){ #ifdef FSYo freopen("1.in", "r", stdin); #endif cin &
2020-12-31 08:53:36
284
原创 CF # 1458 简要题解
A模拟BDP\mathcal{DP}DPC我们将一个格子看成三元组 (i,j,ai,j)(i,j,a_{i,j})(i,j,ai,j)那么 III 就相当于是将所有 (x,y,z)(x,y,z)(x,y,z) 变成 (x,z,y)(x,z,y)(x,z,y)我们维护一下三维的置换，对平移打上标记就可以了#include<bits/stdc++.h>#define cs const#define pb push_backusing namespace std;cs int
2020-12-21 16:54:38
658
1
原创 NOIP 2020 游记
Day -4上午开题发现一道都不会，跑路了，下午啥都没干，题目一道都改不来，感觉要完蛋了Day -2上午开题发现一道都不会，跑路了，下午啥都没干，题目一道都改不来，感觉要完蛋了Day -1做了一道 NOIP 2018 填数游戏又写了个 NOIP 2018 保卫国王，叕叒双又挂分了晚上在空间开了个 ldx buff /seDay 1看压缩包发现有字符串，之前更同学们说不考字符串感觉很愧疚，谢罪谢罪开题发现 A 是拓扑排序题，用 ullullull 写了一发然后看 B 发现大概是个 kmp
2020-12-05 20:15:28
731
原创 NOIP 模拟 20/12/03
A用 Hall\mathcal{Hall}Hall 定理进行判断二分答案，在子集处打上 Tag\mathcal{Tag}Tag，最后做高维前缀和复杂度 O(n2k+n22n)\mathcal{O}(n^2k+n^22^n)O(n2k+n22n)B跑多元最短路就可以了，复杂度 O(Vlog2V)\mathcal{O}(V\log^2V)O(Vlog2V)Cai≤bia_i\le b_iai≤bi 的贪心否则考虑枚举选择的集合 SSS，如何判断 SSS 是否合法即选择一种顺序使得 ∀i,
2020-12-03 14:36:32
286
原创 NOIP 模拟 20/12/01
B考虑行列极值 ai,bia_i,b_iai,bi那么答案上界为 ∑ai+∑bi\sum a_i+\sum b_i∑ai+∑bi注意到一个位置可能同时满足取到所在行列的极值这种位置我们称之为匹配，跑一个费用流就可以了C考虑答案从 d→d+1d\rightarrow d+1d→d+1那么就是从 ddd 的每个末尾结点往下走一步，走不动的就不走我们会贪心走最长的链现在就是支持将一个元素 +1+1+1，插入一个为 111 的元素查询最大的 lll 个，由于 lll 是不变的所以我们直接
2020-12-01 14:33:28
241
原创 NOIP 模拟 20/11/27
C注意到若一种颜色不合法那么永远不会合法会划分成若干区间，启发式分裂即可D考虑如何判断，维护当前点 ppp，考虑所有 p∈[l,r]p\in[l,r]p∈[l,r] 的区间那么我们会取 rrr 最小的，用堆维护就可以了考虑求答案，对于每个区间，我们贪心在它最后面的时间取到（这样就可以更其它颜色的一起）最后面的时间定义为过了这个时间但没有取会存在不合法的情况每种颜色单独求，当前必须取的条件就是 ∃i,s.t.i−p<count(p,i)\exist i,s.t.i-p< coun
2020-11-27 14:10:43
194
原创 NOIP 模拟 20/11/25
C考虑两行要么互补要么相等且 0/10/10/1 交替若满足 0/10/10/1 交替，则有 222 的系数，我们称这样的行为自由行我们只需要统计 ∑2cnt\sum 2^{cnt}∑2cnt 作为答案首先可以将不同的行拆成 nnn 个区间考虑两个位置 (i,i+1)(i,i+1)(i,i+1)，若相等，则包涵它的区间都会变成不自由行基于此在笛卡尔树上 DP\mathcal{DP}DP我的做法要维护最左边最右边，以及有无一个位置 (i,i+1)(i,i+1)(i,i+1) 相等复杂度 O(n
2020-11-25 22:14:47
141
原创 NOIP 模拟 20/11/24
B若 www 合法则 w+maxaiw+\max a_iw+maxai 合法，二分答案，检查 [mid−maxai,mid][mid-\max a_i,mid][mid−maxai,mid] 的答案C考场写了个 Hash\mathcal{Hash}Hash 暴力找循环节 T\mathcal{T}T 惨了打表得到循环节长度为 min(t∣t×(t+1)2≥∑ai)\min(t\mid \frac{t\times (t+1)}{2}\ge \sum a_i)min(t∣2t×(t+1)≥∑a
2020-11-24 17:13:03
224
原创 NOIP模拟 20/11/19
A我们按 aaa 进行排序那么限制即为前 iii 个不能选超过 i2\frac{i}{2}2i 个这是一个拟阵，可以贪心做B设 111 的个数为 mmm 个限制就是任意一个环中 ≤m\le m≤m 的个数 ≤2\le 2≤2，那么我们直接上 GF\mathcal{GF}GF[xn−mym]exp[∑kyxk−1+k−12y2xk−2+xkk]exp(∑kyxk)×exp(∑kk+12y2xk)×11−x[x^{n-m}y^m]\exp\Big[\sum_kyx^{k-1}+\frac{
2020-11-19 14:03:14
224
原创 Codechef November Challenge 简要题解
Chef and the Combination Lockfif_ifi 表示需要 ≥i\ge i≥i 次操作的方案数fi=∏max(0,aj+1−i×2)f_i=\prod \max (0,a_j+1-i\times 2)fi=∏max(0,aj+1−i×2)找到 t=min(ai+1)/2t=\min (a_i+1)/2t=min(ai+1)/2求 ∑i=1tfi\sum_{i=1}^t f_i∑i=1tfi注意到 fif_ifi 是关于 iii 的 NNN 次多项式我们只
2020-11-17 12:47:03
424
原创 NOIP 模拟 20/11/16
A略B考虑两个栈合并，第二个栈的贡献可以直接算然后要用第二个栈的 min\minmin 去找到第一个 <<< 它的位置算贡献枚举这个位置算 >>> 它的 min\minmin 有多少个就可以了C注意到每次就是抠出来一个集合 SSS，它的补集填一种颜色首先这样操作一定是合法的（充分性）下面证必要性：只需证明合法的染色方案一定存在 zzz 使得包涵 zzz 的集合为同一种颜色若不存在 zzz，设 UUU 为全集且为黑色，那么我们考虑所有为白色的集合由
2020-11-17 11:52:51
206
原创 NOIP 模拟 20/11/11
B考虑一个直观的想法我们枚举两个端点 u,vu,vu,v，求出到它们距离的 min\minmin >du,v>d_{u,v}>du,v 的点数这个可以通过预处理 Su,dS_{u,d}Su,d 表示到 uuu 的距离 ≤d\le d≤d 的点的个数然后找到中间点 / 边容斥然后计数有两条边取 min\minmin 的情况用上述做法可以求出 min=du,v\min=d_{u,v}min=du,v 的点数容易发现上述情况会在此计数两次而等边三角形的情况会计数三次那
2020-11-11 19:52:22
204
原创 数学题
第三波数学题独孤玖 orz设 f(n)=lcm(1,2,…,n)f(n)=\text{lcm}(1,2,\dots,n)f(n)=lcm(1,2,…,n)证明：f(2n)∣f(n)×(2nn)f(2n)\mid f(n)\times \binom{2n}{n}f(2n)∣f(n)×(n2n)我们设 f(n)=n!p,f(2n)=2nn‾qf(n)=\frac{n!}{p},f(2n)=\frac{2n^{\underline n}}{q}f(n)=pn!,f(2n)=q2nn我们用 2nn
2020-11-08 16:00:51
259
原创 NOIP 模拟 20/11/05
A转成补图，二分图染色最后做一个背包B跑一个倍增然后做一个分层图就可以 O(n3log2nω)\mathcal{O}(\frac{n^3\log^2n}{\omega})O(ωn3log2n)C注意到不合法当且仅当开辟的连成一溜用并查集维护就可以了由于可以转圈圈，所以要把第一列 copy\text{copy}copy 一下移到最后一列D一个简单的想法是让每个点都到根然后找另外子树的点但这样可能存在 >n2>\frac{n}{2}>2n 的子树导致不合法我们找到重
2020-11-05 19:40:11
224
原创 NOIP 模拟 20/11/03
A首先有 b≤a−2b\le a-2b≤a−2归纳证明两颗子树，合并时最多多出两个根要么减少一个 111 度点要么增加一个 333 度点，故 b≤a−2b\le a-2b≤a−2然后有 b≠a−3b\neq a-3b=a−3我们知道 ∑di=2(n−1)=3×(a−3)+a+∑i=1cdi=2(2a−4+c)\sum d_i=2(n-1)=3\times (a-3)+a+\sum_{i=1}^cd_i=2(2a-4+c)∑di=2(n−1)=3×(a−3)+a+∑i=1cdi=2(2a
2020-11-03 19:34:57
197
原创 NOIP 模拟 20/11/02
A略BB\mathcal{B}B 开头的算法，通过维护前缀最大次大值可以做到 O(nlogn)\mathcal{O}(n\log n)O(nlogn)C考虑枚举一个数并判断它合不合法， 将这个数写成 KKK 进制小数容易发现这个小数是 111 放到树的对应深度里面的个数进位后的结果合法的必要条件是这个数 0.z1z2…zl0.z_1z_2\dots z_l0.z1z2…zl 满足 ∑zi≤n,∑zi≡nmod K−1\sum z_i\le n,\sum z_i\equiv n\mod
2020-11-03 11:34:50
168
原创 NOIP 模拟 20/10/30
A我们维护 KKK 个并查集，每次二分看可以在哪一个B全部填黑的充要条件就是要有一行全黑枚举是哪一行C注意到问题是对称的，我们只需要统计等于 nmn^mnm 的个数就可以了考虑每个 ptp^tpt 的贡献就是 [zmt](1−zt+11−z)2m[z^{mt}](\frac{1-z^{t+1}}{1-z})^{2m}[zmt](1−z1−zt+1)2m，O(mlogn)\mathcal{O}(m\log n)O(mlogn)D用主席树比大小，Set\mathcal{Set}Set 维护
2020-10-30 15:25:57
197
原创 NOIP 模拟 20/10/28
A我们需要寻找一些性质1：若一个点可以在第 iii 个，那么一定可以在 j≥ij\ge ij≥i 个有了这个性质我们只需要统计能在第 iii 个的个数就可以快速计算答案2：若 ttt 最早可以在第 iii 个，那么 r≥tr\ge tr≥t 不会最早在第 j<ij<ij<i 个知道了这个我们可以直接枚举当前最早的时间然后考虑怎么移动一个贪心策略上将棋子放在 1,3,5…1,3,5\dots1,3,5…考虑求 ttt 能否在第 kkk 个，将前 k−1k-1k−1 个移除于
2020-10-28 11:43:34
268
原创 NOIP 模拟 20/10/27
ADP\mathcal{DP}DPB就是让你算 min∑max(0,ci−ci−1)\min \sum \max(0,c_i-c_{i-1})min∑max(0,ci−ci−1) 其中可以给 cic_ici 加上 4k4k4k设一个上界 DP\mathcal{DP}DP 就可以了正解大概是对 ccc 差分，设为 ddd，要最小化 ∑max(0,di)\sum \max(0,d_i)∑max(0,di)可以给任意一个 dld_ldl 加上 444，dr+1d_{r+1}dr+1
2020-10-27 15:53:40
215
原创 CF # 679 简单记录
A题意就是给每个 bib_ibi 分配一个 aja_jaj，最小化 max(bi−aj)−min(bi−aj)\max(b_i-a_j)-\min(b_i-a_j)max(bi−aj)−min(bi−aj)我们枚举最小值，用双指针 + 数据结构维护最大值就可以了BC若 a>b×ca>b\times ca>b×c 那么为 +∞+\infty+∞令 k=⌊abd⌋k=\lfloor \frac{a}{bd}\rfloork=⌊bda⌋，那么我们会在用了 k+1k+
2020-10-26 11:37:34
326
原创 CF # 678 Div2 简单记录
被队友带飞了D写了二分答案写 TTT 了，于是抄的队友的E考虑枚举答案，就是要看存不存在一个区间使得 [1,t)[1,t)[1,t) 存在且 ttt 不存在ttt 会把序列分成很多段，每一段是一个区间数颜色，用数据结构维护就可以了F你先不管 gcd=1\gcd=1gcd=1 的限制，其实是我没有看到发现大概是算S×S×cnt−S×S=S×S×(cnt−1)S\times S\times cnt-S\times S=S\times S\times (cnt-1)S×S×cnt−S×S=S×
2020-10-25 00:43:48
341
3
原创 NOIP 模拟 20/10/24
A每个质因子做一遍B倍增C考虑每个数贡献几次，将 >>> 它的赋成 111，那么就是要求区间包涵它且 111 的个数 <k<k<k双指针维护D考虑 fi,ai=∑fi,jf_{i,a_i}=\sum f_{i,j}fi,ai=∑fi,j，注意到 111 的个数要么为 000 要么为 111，状压就可以了...
2020-10-24 15:03:59
123
原创 数树
即统计交集的连通块个数，并有 ycy^cyc 的贡献对于问题 111：考虑点 n−cn-cn−c 条边作为交集，即硬点出 ccc 个联通块，设每个联通块大小为 aia_iai，那么方案数就是 ∏ai×nc−2\prod a_i\times n^{c-2}∏ai×nc−2，求出 fc=∏ai×nn−c−2f_c=\prod a_i \times n^{n-c-2}fc=∏ai×nn−c−2 表示点 ccc 条边断掉的方案数， 然后二项式反演（注意我们直接点联通块的话不好容斥）Ans=∑cyn∑
2020-10-20 19:47:31
687
原创 小 H 爱染色
写出答案的式子∑if(i)[(n−im)2−(n−i−1m)2]\sum_{i}^{}f(i)\Big[\binom{n-i}{m}^2-\binom{n-i-1}{m}^2\Big]i∑f(i)[(mn−i)2−(mn−i−1)2]是关于 nnn 的 3m+13m+13m+1 次多项式，我们需要知道各个点值利用 f(k)=∑if(i)∏j≠ii−jk−j=∑if(i)(m−i)!i!(−1)m−ikm+1‾1k−if(k)=\sum_if(i)\prod_{j\neq i}\frac{i-j}
2020-10-20 19:00:09
269
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人