- 博客(54)
- 收藏
- 关注
RSS订阅原创 常系数线性递推式的快速求单项值方法
常系数线性递推式的快速求单项值方法前导知识常系数线性递推式 形如f(n)=∑ki=1aif(n−i)f(n)=\sum_{i=1}^{k} a_if(n-i)，其中kk、aia_i为常数的递推式，称为常系数线性递推式。Cayley-Hamilton定理 对于矩阵AA，det(λE−A)\det(\lambda E-A)是一个|A||A|次多项式，称为A的特征多项式（characteristi
2016-05-14 20:31:18
2336
原创 线性基导论
Definition以非负整数集SS中元素为向量，异或为加法，{0,1}\{0,1\} 为数域生成的线性空间V的一组基QQ，满足QQ中二进制下最高非零位为k的向量不存在或唯一，称为SS的线性基。algorithm我们只需要使用Gauss消元求出SS的一个极大线性无关部分组，而这过程中就可以承诺 QQ中二进制下最高非零位为k的向量不存在或唯一 。Application最基础的应用是判断某个非负整数AA
2016-04-07 19:22:55
950
原创 Splay的时间复杂度的一种证明
在这里，我们给出势函数(potential function)的定义，并展示如何通过势函数给出Splay操作的均摊时间复杂度的一个上界，尽管这上界并不是紧的。势函数Φ\Phi定义为数据结构到实数集的一个映射。在这里，我们假设势函数Φ\Phi已经良定义，设T(i)T(i)为第i次操作的实际耗时,Φ(i)\Phi (i)代表第i次操作结束时系统的势函数值。定义A(i)=T(i)−Φ(i−1)+Φ(i)
2015-11-09 17:58:46
4966
原创 大家好我又滚回来了
这个博客以后会成为一个与Oi无关的博客。Tags： MarkdownHello World1.插入代码使用“`+语言名称可以插入代码段并带上代码高亮 eg:#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <algorithm>#include <iostream>using na
2015-09-25 20:12:14
956
原创 BZOJ1060
传送门：BZOJ1060有些意思的树形DP。我只想到了用f(i,j)f(i,j)表示以i为根的子树的权值之和为j的最小花费，但我没有想到这个j居然是可以贪心从而藏进去的……注意到有以下事实成立：在靠近根的节点使用技能更优秀。于是贪心即可，我们维护每个结点与其子树中叶子结点的最大距离，然后枚举它的子结点，加上它的最大距离与它子结点的最大距离与该边权值之差即可。比较坑的是，这题标程统计最大距离时忘开lo
2015-08-27 20:53:16
755
原创 BZOJ1059
传送门：BZOJ1059有趣的题目。做法是二分图完美匹配，其实看到题就可以隐约猜到是把行和列连边。建图方法是把黑点(i,j)的行i向列j连一条边，这显然是一个二分图模型，判断有无完美匹配即可。看上去很符合直觉，下面我来展示它的严谨证明。在证明这个算法的正确性前，首先证明一个引理[1]：设n阶方阵中有n个点，它们互不在同一列也互不在同一列，则可用这n个点构造出n阶的目标矩阵。首先断言：任意两个同一列的
2015-08-27 19:40:46
1112
原创 BZOJ1057
传送门：BZOJ1057大水题（虽然我WA了status的一页）不知道那些搞奇偶性的什么心态……直接悬线法即可。不要忘记判断当前点与上方点有无关系代码上的小细节见下。#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <algorithm>#include <iostream>usin
2015-08-27 15:48:35
940
原创 BZOJ1055
传送门：BZOJ1055傻逼题，然而我居然连状态定义都没有想出来。记f(i,j,k)表示[i,j]的字符能否由k字符扩展来，转移就是怎么暴力怎么来f(i,j,k)表示[i,j]的字符能否由k字符扩展来，转移就是怎么暴力怎么来 我觉得我要摆脱题解依赖了……必须摆脱！代码上的小细节见下。#include <cstdio>#include <cstdlib>#include <cmath>#inc
2015-08-26 19:27:43
874
原创 POJ3261
传送门：POJ3261傻逼题，Hash即可。我把Hash的后缀函数打错了我会乱说？代码上的小细节见下。#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <algorithm>#include <iostream>using namespace std;const unsigned l
2015-08-26 18:55:02
794
原创 ZOJ3643
传送门：ZOJ3643很有意思的KMP。 kmp就不说啥了。 这道题的瓶颈在于暴力删除会超时，于是我们观察注意到[l,r]被删除之后，造成的影响仅仅是下一次我们会从l-1开始匹配。 然后就可以乱搞了…… 栈里面存的是母串在子串中匹配到的位置。代码上的小细节见下。#include <cstdio>#include <cstdlib>#include <cmath>#include <cs
2015-08-26 16:12:40
1019
原创 BZOJ1260
传送门：BZOJ1260傻逼题。记f(i,j)表示把区间[i,j]染色最小操作次数，f(i,j)表示把区间[i,j]染色最小操作次数，则转移是f(i,j)={s[i]=s[j],minf(i+1,j),f(i,j−1),f(i+1,j−1)+1otherwise ,minf(i,k)+f(k+1,j),k∈[i,j−1]f(i,j)= \{^{s[i]=s[j],min{f(i+1,j),f(i,j
2015-08-26 10:23:31
1387
原创 BZOJ1054
传送门：BZOJ1054傻逼广搜题，按位转化为二进制判重。 坑爹之处在于数字居然是黏在一起给出来的……代码上的小细节见下。#include <cstdio>#include <cstdlib>#include <algorithm>#include <iostream>#include <cmath>#include <cstring>#include <queue>using na
2015-08-26 10:06:10
956
原创 BZOJ2773
传送门：BZOJ2773以y为key建树，维护最大值，树上二分即可。吐槽一下学校评测机，我艹我在bzoj上AC的代码T完了。代码上的小细节见下。#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <algorithm>#include <iostream>#include <set>
2015-08-25 20:50:29
683
原创 BZOJ1052
传送门：BZOJ1052傻逼题。二分一个长度，注意到每次正方形必然落在某个角上，枚举判断即可。好久不见的1A……代码上的小细节见下。#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <iostream>using namespace std;const int INF=0x3f
2015-08-25 19:58:33
920
原创 BZOJ3620
传送门：BZOJ3620暴力做法小练习。本质上就是求一个串，又是前缀又是后缀，然后有各种奇奇怪怪的要求。 刚刚做了这种题…… 枚举左端点i，枚举右端点j，对于[i,j],记录它们之间>k的最小的既是前缀又是后缀的值，判断这个值是否小于等于(j-i)/2即可。 数据给出来就是暴力的，O(n2)O(n^2)能过真是感人肺腑。 代码上的小细节见下。#include <cstdio>#includ
2015-08-24 21:10:33
1019
原创 BZOJ3670
传送门：BZOJ3670k(n)m(o)p(i)傻逼题。记num[i]为既是i前缀也是后缀的串的个数，这可以在kmp时一并求出。然后对于每个i，只要暴力找到最大的j令2*j<=i且j在i意义下既是前缀也是后缀就可以了，这只要一路检测条件然后pre回去，依然是线性的。代码上的小细节见下。#include <cstdio>#include <cstdlib>#include <cmath>#inc
2015-08-24 19:44:22
912
原创 HDU4333
传送门：HDU4333扩展KMP小应用，把原串复制一遍就行了。对着某位博主的代码，死活改不出来，然后发现这货的代码是WA的……代码上的`小细节见下。#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <algorithm>#include <iostream>using namespa
2015-08-24 16:33:38
912
原创 BZOJ1355
传送门：BZOJ1355（权限题）显然[pre[len]+1..len]可作为一个循环串。 对于它是前缀的情况，以后缀拼接即可。 代码上的小细节见下。#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <algorithm>#include <iostream>using name
2015-08-24 09:37:59
1124
2
原创 BZOJ1053
传送门：BZOJ1053我喜欢数学题，我讨厌结论题…… 约数个数定理： 记Φ(p)为p不平凡的约数的个数，对∀q∈N∗,q>1,作Lagrange分解q=∏pa,则Φ(a)=∏(a+1)记\Phi (p)为p不平凡的约数的个数，对\forall q \in \mathbb N^{*} ,q>1,作Lagrange分解q=\prod p^{a},则\Phi (a)=\prod (a+1)对
2015-08-23 19:53:42
1369
原创 POJ2752
传送门：POJ2752傻逼题，注意前缀函数的定义就行了。代码上的小细节见下。#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <algorithm>#include <iostream>using namespace std;int ans[1000005];int f[10000
2015-08-22 14:51:29
986
原创 BZOJ2882
传送门：BZOJ2882（权限题）最小表示法的模板。传送门：周神论文代码上的小细节见下。#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <algorithm>#include <iostream>using namespace std;int n;int da[300005];i
2015-08-22 10:05:31
1631
原创 BZOJ1051
传送门：BZOJ1051Tarjan算法求强联通分量，缩点，记录出度。 现学的Tarjan算法……++cnt写错了orz。 最近眼睛不舒服，做题好慢……代码上的小细节见下。#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <algorithm>#include <iostream>
2015-08-21 20:26:02
816
原创 BZOJ1050
传送门：BZOJ1050CODEVS上做过这道题，当时写了一个二分＋贪心…… 今天回来看发现就是傻逼贪心。 枚举最大值，贪心最小值，并查集维护即可。 代码上的小细节见下。#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <iostream>#include <algorithm>
2015-08-21 14:55:01
990
原创 POJ3368
传送门：POJ3368注意到不降，于是序列一定是连续的。 然后就是傻逼题了。 代码上的小细节见下。#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <iostream>using namespace std;struct Node{ int ls,rs; i
2015-08-21 11:40:53
1113
原创 BZOJ1048
传送门:BZOJ1048 记f(i,j,k,l,n)为以点(i,j)为左上角，点(k,l)为右下角，需要分成n块的矩形能得到的最少的∑q=1n(Si−μ)2\sum_{q=1}^{n} (S_i-\mu)^2然后就是傻逼记搜。AC之后的吐槽：把标准差求错了卧槽。代码上的小细节见下。#include <cstdio>#include <cstdlib>#include <cmath>#incl
2015-08-20 20:14:35
880
原创 BZOJ1071
传送门：BZOJ1071枚举minH，minV，单调性优化+计不可行方案数即可。 代码上的细节较多。代码上的小细节见下。#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define N 5050using namespace std;int A,B,C;struct KSD{
2015-08-20 16:50:32
966
原创 BZOJ1047
传送门：BZOJ1047我们用f(i,j)表示第j列上区间[max(i-n+1,1),i]的最小值。 这一步的转移可以用单调队列来完成。 然后，我们用g(i,j)来表示以点(i,j)为右下角的边长为n的正方形中元素的最小值。 转移是：g(i,j)=min:f(i,j’),j’∈[max(j-n+1,1),j]，于是它也可以用一个单调队列来优化。 注意细节。代码上的小细节见下。#include
2015-08-19 21:07:04
1208
原创 BZOJ1046
传送门：BZOJ1046反着构造f(i)，表示以i结尾的最长的下降子序列。这就等效于以i开头的最长的上升子序列。然后枚举即可。#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <algorithm>#include <iostream>using namespace std;cons
2015-08-19 19:26:05
908
原创 BZOJ1045
传送门：BZOJ1045结论题。设i顺时针传给下一个人的数量为xi，目标平均值值为ave设i顺时针传给下一个人的数量为x_{i}，目标平均值值为ave 则目标就是让ai−xi+xi−1=ave的前提下最小化则目标就是让ai-x_{i}+x_{i-1}=ave的前提下最小化∑i=1n|xi|\sum_{i=1}^{n} \left| x_i \right| 可以构造出 a1−x1+x2=avea
2015-08-19 16:58:13
1260
原创 BZOJ1044
传送门：BZOJ1044第一问：傻逼二分，设答案为ans，二分贪心即可。第二问：f(i,j)f(i,j)表示第i刀切在第j处的合法方案数 转移是f(i,j)=∑len[k,j]≤ansj−1f(i−1,k)f(i,j)=\sum_{len[k,j] \le ans}^{j-1} f(i-1,k) 显然这个Dp空间是O(nm)O(nm)的，时间是O(nm2)O(nm^{2})的，无法承受。 首先
2015-08-19 09:45:54
1052
1
原创 BZOJ1042
传送门：BZOJ1042首先，计算出购买面值为i的物品的方案数f(i),这一步强制有序就可以了。 然后，每一次查询时ans=(f(s)-d1溢出方案-d2…+d1d2+d2d3+…-d1d2d3….+d1d2d3d4)，即容斥原理。 注意到d1溢出时，至少使用了d1+1个物品，于是剩下S-(d1+1)c1都可以随意分配，于是d1溢出的方案就是f(S-(d1+1)c1)代码上的小细节见下。#inc
2015-08-18 20:13:35
1040
原创 BZOJ1037
传送门：BZOJ1037令f(i,j,k,l)表示区间[1,i]中有j个男生，包含在[1,i]中的区间中最多的男女生差距为k，最小的为l的方案数，转移则有f(i,j,k,l)表示区间[1,i]中有j个男生，包含在[1,i]中的区间中最多的男女生差距为k，最小的为l的方案数，转移则有 f(i+1,j,max(k−1,0),l+1)+=f(i,j,k,l)f(i+1,j,max(k-1,0),l+1)+
2015-08-18 16:52:04
1046
原创 BZOJ1798
传送门：BZOJ1798双状态的线段树，注意优先级。#include <cstdio>#include <cstdlib>#include <iostream>#include <algorithm>#include <cstring>using namespace std;struct Node{ int ls,rs; long long w; long long
2015-08-17 20:50:18
1327
原创 BZOJ1009
传送门：BZOJ1009KMP构造转移矩阵，矩阵加速DP。 以后题解都会简单一些。/************************************************************** Problem: 1009 User: Jerusalem Language: C++ Result: Accepted Time:56 ms
2015-08-17 20:40:31
1422
原创 BZOJ1034
传送门:BZOJ1034类似田忌赛马的贪心。 按照 我的最小能否赢过敌方最小？[1] 是：赢过，迭代 否：我的最大能否赢过敌方最大？[2] 是：赢过，迭代 否：我方最小比拼对方最大，迭代。的流程进行。 让我们证明这个算法的正确性。当[1]成立时，最优性显然成立。当[1]不成立时，如我方最小输对方最小，正确性也是显然的。 在这里我们观察我方最小平敌方最小的情
2015-08-16 09:25:54
961
原创 BZOJ1029
传送门:BZOJ1029还记得线段覆盖吗？我们将建筑物按Deadline排序，然后扫描排序后数组，如果当前建筑物可以被修建，则修建，否则，如果当前建筑物所用时间小于修过的建筑物最大时间，则放弃最大时间，改修它。 这个算法的正确性是显然的。 代码上的小细节见下：#include <cstdio>#include <cstdlib>#include <cmath>#include <cstri
2015-08-15 08:32:42
1090
2
原创 BZOJ1024
传送门：BZOJ1024首先注意到以下事实：每一刀必然割在kn处,其中k∈N+\frac {k} {n}处,其中k\in \mathbb N^+然后就可以深搜了。代码上的小细节见下。#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <algorithm>#include <iostre
2015-08-14 16:22:00
975
原创 BZOJ1025
传送门：BZOJ1025首先，容易证明解的存在性。 于是排数就等于1回到1,2回到2…所需步数的lcm。然后，容易发现∑ib(i)=n\sum_{i} b(i)=n 其中i取一类步数为b(i)的i,i’,i”…于是问题变成已知k个正整数的和为n，求这k个数可能的lcm的种数。套一个Lagrange唯一分解定理即可。代码上的小细节见下。#include <cstdio>#include <cst
2015-08-14 11:47:07
911
原创 BZOJ1017
传送门：BZOJ1017比较复杂的树形Dp。 复杂的是这道题Dp方程的定义:fi,j,kf_{i,j,k}表示以节点i为根的子树，向i的父节点提供j个物品，在子树上总花费k元能得到的最大力量值。转移时我们先不考虑以i为根的子树合成了n个i却未完全上交的情况。i为树叶时，Dp是显然的，如果i不为树叶，则转换是显然的。但在这转移中，假设我们给子节点j′j'分配了k′k'元，则我们要考虑其它所有的情况。
2015-08-13 18:18:04
1321
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人