My blog
  • 首页
  • 归档
  • 分类
  • 标签
  • 关于
  • 友链

arc096C | Everything on it

link 不解释题意。
2021-12-02
math
#idea #IN-EX principle

有关 Dilworth 定理的简单证明

本文大量参考了这篇博客,如果您是这篇博客的主人,认为我这么“转载”不妥,请联系我删除我这篇博客。 由于我现在是一名高中生,可能下面的表述不是十分严谨,如果您想看一片比较严谨的证明可以去 wiki 查看 part 1 定理内容 Dilworth 定理 (Dilworth's theorem) 主要说明了覆盖一个 dag 最少需要的不交的链的条数等于最长的反链长度。 此处的覆盖指的是
2021-12-01
#simple thoughts

ARC120 - partial solution

Link 打的不是十分满意。所以写一个全场总结。 A 题意:给出串 \(S\),定义 \({S}_i={S}[0,i-1]+{S}[i+1,n]\) 让你求出 \({S}_i={S}_j\) 的 \((i,j)\) 个数。 挺显然的在比较 \(i,j\) 时,lcp,lcs 可以直接忽略掉。 就考虑中间一段,发现这个是长度为 \(n-1\) 的 border,显然 period
2021-11-29
whole round

cf1606F

题意 Link 考虑询问 \((x,k)\) 等价于以 \(u\) 为根,每个点 \(v\) 权值 \(\mathrm{child}(v)-k-1\),找出 \(u\) 所在的连通块,权值最大的。 如果固定 \(k\) 有很 simple 的 dp。 考虑我们必定以权值为正的结尾,所以考虑建出权值 >=0 的虚树,其中虚树大小是 \(\mathcal{O(n)}\) 级别
2021-11-16
数据结构
#虚树

0,1随机变量k小值期望

[0,1]随机变量的k小值期望。 答案: \(\frac{k}{n+1}\) ET2006大佬大力积分 不认识的大佬的大力积分 不认识的大佬的组合理解 我学到了什么? 分步积分 对不起我不懂微积分,写的一定不严谨。 \[ \begin{aligned} (f(x)g(x))'=f(x)'g(x)+f(x)g(x)'\\ f(x)'g(x)=(f
2021-11-12
数学
#simple thoughts

AGC052 - partly solution

Link 暂时只会了ABC(这就是similar to ABC 吗?) A 题目无关的。 本来想写的是『简单题,考场傻逼』了。 但想想,我真的能在不看题解时想到吗? 这真的不好说,在我看题解的那一瞬间,"我能想到",和"我想不到"两个不确定的状态会瞬间坍塌成"我曾经想不到"这一个状态,时间不会回溯,没看过题解的我也不复存在.....
2021-11-03
whole round

codeforces round 750 [div2]

Link A \(a,b,c \bmod 10\) 然后暴力。 注意如果 \(a,b,c\geq 10\) 那么模完还要加上10。 10只不过是一个大偶数。 B 暴力看 \(0,1\) 个数。 C 枚举删什么字符,然后看是否回文,回文就在两个之间添加该字符。 D 构造 \(b,s.t. \sum a_ib_i=0\)。 两两配对 \(b_i=a_{i+1},
2021-10-25
whole round

AGC006F

Link 这题我大概一年前就做过,现在心情很糟。 直接说现在的心路历程。 看反了 \((x,y),(y,z) \rightarrow (z,w)\) 中的 \((z,w)\)。 受到一个cf题的影响,拼命想并查集,做成了二分图,没什么进展(因为没有联通性)。 看题解,得知应该看成有向图,用边的方向表示。 又看错题意回到了 1,认为这个和 noi day1 t3 很像。 不忍心
2021-10-22
#idea题 #染色

扫描线类线段树正确性分析

对于线段树分析。 \(\mathcal{Goal: }\) 我们希望使用线段树维护区间大于0的数的个数,支持区间加/减。 \(\mathcal{Main\ \ Idea :}\) 方法:通过打加法 tag,直接维护答案。 由于扫描线的性质,区间减法相当于撤销上一次区间加,所以 tag 始终非负。 至于维护的值,我们只需要保
2021-10-22
数据结构
#simple thoughts

Count Multiset

Arc221H-Link Solution 第一步,对于 multiset 计数,我们将其转换成 对于单调不降数列计数。 这时看起来对于单调不降数列计数已经有较好的性质了,我们也可以得到如下的 \(\mathcal{O(n^3)}\) 的 dp。 对于每个 \(t\),更新 dp 数组:\
2021-10-15
dp
#dp
1…5678910

搜索

Hexo Fluid