discover the funny world
  文章分类
ACM 30 Math 1 Geek 29 Diary 8 Something 2
HDU 6270 - Marriage HDU 6270 - Marriage
给出$n$个家庭，每个家庭有$a_i$个男生，$b_i$个女生，保证$\sum{a_i}=\sum{b_i} \leq 10^5$, 现在求每个人不会在家庭内部匹配异性的方案数对$998244353$取模。 链接Marriage 注意题目
2018-05-14 ACM
FFT
cf #474 F.Pathwalks - 整体二分 cf #474 F.Pathwalks - 整体二分
给定$10^5$条边，需要找一条路径，使得路径上的边的权值严格递增，并且边的编号也是严格递增的，求最长路径包含的边的数量。 链接Pathwalks 题解似乎正解是DP，不过赛时没想这么多，因为这题有很显然的两维偏序关系，一个即输入的边的
2018-04-08 ACM
整体二分
多项式求逆总结 - 无向连通图计数 多项式求逆总结 - 无向连通图计数
求$N$个点组成的有标号简单无向连通图个数，答案模 10^9+7 1998585857 由这个问题引入，顺便总结一下多项式求逆的内容。 首先可以设 $f(n)$ 表示有 $n$ 个点的有标号简单连通无向图的个数， $g(n)$ 表示有
2017-10-18 ACM
图论 FFT 多项式
伯努利数及其应用 伯努利数及其应用
伯努利数定义： $$\dfrac{t}{e^t - 1} = \sum_{n = 0}^{\infty} \dfrac{B_n}{n!} t^n$$ 递推式：$$\begin{align}& \sum_{k = 0}^{n}C_{n
2017-10-17 ACM
多项式求逆 数学
hdu 5730 Shell Necklace - [分治FFT|多项式求逆] hdu 5730 Shell Necklace - [分治FFT|多项式求逆]
给出长度分别为 $ 1 \sim n $ 的珠子，长度为i的珠子有$a[i]$种，每种珠子有无限个，问用这些珠子串成长度为n的链有多少种方案。 链接Shell Necklace 题解( 多么好的一个模板题！业界良心！ 令dp[i]表示用
2017-10-17 ACM
CDQ分治 FFT 多项式求逆
HDU - 5324 - Boring Class - CDQ分治 HDU - 5324 - Boring Class - CDQ分治
简单来说，给出n个二维点对，求$LIS$长度和编号字典序最小的$LIS$（$x$非增，$y$非减），并输出最优$LIS$。 显然有一个$DP[i] = \max{DP[j] + 1\ | \ i > j, L[i] \geq L[j]
2017-10-03 ACM
CDQ分治 线段树
偏序和CDQ分治 偏序和CDQ分治
偏序关系关系：集合$X$的关系，是$X$与$X$的笛卡尔积$X × X$ 的子集R，即$X$的元素的有序对集合的一个子集 属于$X × X$的有序对$(a,b)$记为$aRb$ $R$的一些概念：自反：$\forall x \in X, x
2017-10-03 ACM
CDQ分治 总结
CodeForces Gym 101190 B - Binary Code CodeForces Gym 101190 B - Binary Code
给定$n (n \leq 5e5, \sum length \leq 5e5)$个01字符串,每个字符串最多包含一个问号，问是否存在一种将所有问号都用$0 /\ 1$替代的方案，并且使得$n$个字符串任意两个都互不是对方的前缀。 链接B
2017-09-22 ACM
2-SAT 字典树 Trie SCC缩点
CCPC 2016-2017 Finals - HDU 6005Pandaland CCPC 2016-2017 Finals - HDU 6005Pandaland
给定了 $m(m \leq 4000)$ 条边，每条边有不同的权值$w_{i}$，问其中权值最小的环的权值是多少，如果不存在环，则输出0 链接Pandaland 题解可以这样想，如果所有的边联通，我们可以按照求最小生成树的方式处理一遍，
2017-09-16 ACM
最小生成树 LCA 图论
Gym 101201G Maximum Islands 最大点权独立集 Gym 101201G Maximum Islands 最大点权独立集
给定一个$n × m$的矩阵，每个点可能是陆地、水面或者未定，求最多的陆地联通块的数量。 链接G - Maximum Islands 题解首先对于已经给定的图，有一个明显的贪心是，对于每个陆地，周围的未定点我们都可以看做水面，因为如果将
2017-09-14 ACM
图论 贪心 最大点权独立集
Gym 101201F Illumination - 2SAT Gym 101201F Illumination - 2SAT
1000*1000的矩形区域内给定$n(n \leq 1000)$盏灯，每盏灯可以横着亮或者竖着亮并照亮该方向上加上自己的$2 l + 1$个格点，要求点亮所有的灯，使得没有两个同一方向上点亮的灯有重合照亮的位置。 链接F - Illu
2017-09-14 ACM
2-SAT
2017广西邀请赛B题-Colorit-HDU-6183-CDQ分治 2017广西邀请赛B题-Colorit-HDU-6183-CDQ分治
维护两种操作，操作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分治 线段树
1 / 3