crazyX's Blog

给出长度分别为 $ 1 \sim n $ 的珠子，长度为i的珠子有$a[i]$种，每种珠子有无限个，问用这些珠子串成长度为n的链有多少种方案。链接Shell Necklace 题解( 多么好的一个模板题！业界良心！令dp[i]表示用

2017-10-17 ACM

CDQ分治 FFT 多项式求逆

简单来说，给出n个二维点对，求$LIS$长度和编号字典序最小的$LIS$（$x$非增，$y$非减），并输出最优$LIS$。显然有一个$DP[i] = \max{DP[j] + 1\ | \ i > j, L[i] \geq L[j]

2017-10-03 ACM

CDQ分治线段树

偏序关系关系：集合$X$的关系，是$X$与$X$的笛卡尔积$X × X$ 的子集R，即$X$的元素的有序对集合的一个子集属于$X × X$的有序对$(a,b)$记为$aRb$ $R$的一些概念：自反：$\forall x \in X, x

2017-10-03 ACM

CDQ分治总结

最近在尝试使用docker以及docker-py通过python实现一个基于Ubuntu 16.04运行代码的沙箱，之前遇到的问题暂且按下不表，最近遇到了一个很令人烦恼的问题。 Docker本身是有丰富的资源调度控制的，比如说使用的cpu核

2017-09-26 Geek

Tools Ubuntu Resource

主定理用来处理以下形式的复杂度求解问题： $T(n) = \alpha\ T(n / \beta ) + f(n)$ 主定理(Master Theorem)内容例子Karatsuba 大整数的快速乘积算法的运行时间（时间复杂度的递推关

2017-09-24 Geek

算法计算机科学

给定$n (n \leq 5e5, \sum length \leq 5e5)$个01字符串,每个字符串最多包含一个问号，问是否存在一种将所有问号都用$0 /\ 1$替代的方案，并且使得$n$个字符串任意两个都互不是对方的前缀。链接B

2017-09-22 ACM

2-SAT 字典树 Trie SCC缩点

今天要写Java的时候突然发现还没有安装Eclipse，先是直接下载了网络安装包……结果因为墙的问题卡住……然后去下载完整安装包，直接运行却报错了： org.eclipse.e4.core.di.InjectionException: ja

2017-09-18 Geek

Eclipse Java Install

给定了 $m(m \leq 4000)$ 条边，每条边有不同的权值$w_{i}$，问其中权值最小的环的权值是多少，如果不存在环，则输出0 链接Pandaland 题解可以这样想，如果所有的边联通，我们可以按照求最小生成树的方式处理一遍，

2017-09-16 ACM

最小生成树 LCA 图论

给定一个$n × m$的矩阵，每个点可能是陆地、水面或者未定，求最多的陆地联通块的数量。链接G - Maximum Islands 题解首先对于已经给定的图，有一个明显的贪心是，对于每个陆地，周围的未定点我们都可以看做水面，因为如果将

2017-09-14 ACM

图论贪心最大点权独立集

1000*1000的矩形区域内给定$n(n \leq 1000)$盏灯，每盏灯可以横着亮或者竖着亮并照亮该方向上加上自己的$2 l + 1$个格点，要求点亮所有的灯，使得没有两个同一方向上点亮的灯有重合照亮的位置。链接F - Illu

2017-09-14 ACM

2-SAT

今天使用Ubuntu 16.04时，执行apt update时卡在了某个地方： 0% [Connecting to security.ubuntu.com (2001:67c:1360:8001::17)] 就是连接不上更新服务器，一个很

2017-09-10 Geek

Ubuntu Ipv6

维护两种操作，操作1往点$(x, y) (1 \leq x, y \leq 10^6)$加入一个颜色为$c (0 \leq c \leq 50)$的点，操作2查询矩形区域 $(1 \leq a \leq x, y_1 \leq b \leq

2017-09-07 ACM

CDQ分治线段树