expect2004

分类

Codeforces Round(2) Contests(11) review(2) 其他(1) 动态规划(19) 动态规划 - 区间DP(3) 动态规划 - 期望与概率DP(1) 动态规划 - 树形DP(4) 动态规划 - 状压DP(1) 动态规划 - 线性DP(1) 动态规划 - 背包(2) 图论 - Tarjan(4) 图论 - 二分图判定(2) 图论 - 拓扑排序(1) 图论 - 最短路(1) 图论 - 生成树(3) 字符串 - AC自动机(2) 字符串 - KMP(2) 字符串 - 后缀数组（SA）(3) 字符串 - 字典树（Trie）(1) 数学 - 其他(2) 数学 - 多项式(3) 数学 - 组合计数(1) 数学 - 莫比乌斯反演(2) 数学 - 高斯消元(2) 数据结构 - 分块(1) 数据结构 - 平衡树(1) 数据结构 - 树状数组(1) 数据结构 - 树链剖分(2) 数据结构 - 珂朵莉树(2) 数据结构 - 线段树(6) 数据结构 - 虚树(1) 未归档(6) 模板(5) 游记(3) 算法 - 2-SAT(2) 算法 - CDQ分治(1) 算法 - 搜索(2) 算法 - 树分治(2) 算法 - 矩阵树定理(1) 网络流(7) 网络流 - 二分图相关(1) 网络流 - 最大流(1) 网络流 - 最小割(6) 题解(22)

/ 注册

全部文章（共149篇）

LG2852/BZOJ1717 「USACO2006DEC」Milk Patterns 离散化+后缀数组

问题描述 LG2852 题解字符串性质：字符串\(s\)的每个字串等于每个后缀的所有前缀对输入的东西离散化，然后把数值看做\(\mathrm{ASCII}\)后缀排序二分答案，二分长度。显然一段相同的字串，一定是连续一段后缀的公共前缀。如此\(check\)即可。 ...

2019-09-08

0 434

LG2447/BZOJ1923 「SDOI2010」外星千足虫高斯消元

问题描述 LG2447 BZOJ1923 题解显然是一个高斯消元，但是求的东西比较奇怪发现这个方程组只关心奇偶性，于是可以用一个\(\mathrm{bitset}\)进行优化，用xor来进行消元操作。 \(\mathrm{Code}\) #include<bits/s...

2019-09-08

0 456

LG4035/BZOJ1013 「JSOI2008」球形空间产生器高斯消元

问题描述 LG4035 BZOJ1013 题解设答案为\((p_1,p_2,p_3,...,p_n)\) 因为是一个球体，令其半径为\(r\)，则有 \[\sum_{i=1}^{n}{(a_i-p_i)}^2={\rm dis}^2\] 拆式子可得 \[\sum_{i=1}^{...

2019-09-08

0 503

LG3389 「模板」高斯消元法高斯消元

问题描述 LG3389 题解高斯消元，是用来解\(n\)元一次方程组的算法，时间复杂度\(O(n^3)\) 这样就构造出了这个方程组的矩阵目标就是把这个矩阵左边\(n \times n\)消为单位矩阵 \(\mathrm{Code}\) #include<...

2019-09-07

0 675

LG4341/BZOJ2251 「BJWC2010」外星联络 Trie

问题描述 LG4341 BZOJ2251 BZOJ需要权限号题解字符串的性质：一个字符串\(s\)所有的字串，等于\(s\)所有后缀的前缀。枚举这个字符串的每一个后缀，将其插入一个\(\mathrm{Trie}\) 在插入\(\mathrm{Trie}\)的过程中可以非常方便...

2019-09-07

0 449

LG4051/BZOJ1031 「JSOI2007」字符加密后缀数组

问题描述BZOJ1031LG4051 题解发现这是一个环，根据经验，破环为链，于是字符环变为了字符串之后对这个复制之后的字符串求后缀数组。$len$代表原字符串长度，代表复制后的字符串长度最后输出的时候，判断一下，如果$SA_i \le len$，则输出$str_i$。 Code ...

2019-09-06

0 426

LG2444/BZOJ2938 「POI2000」病毒 AC自动机

问题描述 LG2444 BZOJ2938 I \(\mathrm{AC}\)自动机 \(\mathrm{AC}\)自动机是一种多模式串匹配算法，本萌新今天刚学了它qwq 约定在构造\(\mathrm{AC}\)自动机的过程中，\(\mathrm{Trie}\)树上的边和由于\(\mat...

2019-09-05

0 450

【题解】会议座位

给一开始座位表顺序中每个老师一个编号，分别为。再根据打乱后的座位表顺序求出新的编号序列。显然是求新编号序列中逆序对个数可以使用归并排序或者树状数组解决。题解区里没有树状数组，那我就发个树状数组的吧。 code #include<bits/stdc++.h> using names...

树状数组归并排序逆序对 STL 分治

2019-08-31

0 429

【题解】快速幂

快速幂运用分治思想显然有：每次根据该公式分治计算即可。 #include<iostream> #include<cstdio> using namespace std; long long int b,p,k,ans=1; int main() { scanf...

分治

2019-08-30

0 494

【题解】合并果子

显然每次选取两堆重量最小的最好。主要要介绍的不是这个解法，而是几个奇奇怪怪的东西。 Heap STL中常用的堆是priority_queue（优先队列），但是STL同样支持一个奇怪的东西为heap heap有几个函数：make_heap，pop_heap，push_heap 具体用法右转百度...

堆贪心

2019-08-30

1 623