qingdaobaibai-CSDN博客

原创《Convex Optimization》附录A数学背景

附录A 数学背景1. 范数1.1 内积与夹角n维向量内积： m×n维矩阵内积：向量(矩阵)夹角： Cauchy-Schwartz inequality：，等号成立当且仅当向量x和y共线 1.2 常见范式（A.1.3）向量范数Lp-范数：p=1、2、∞时比较常用L1-范数（绝对值和范数）：L2-范数（Euclidean范数）：L∞-范数...

2018-10-12 15:06:09 504

原创 Convex Optimization介绍

最近在看Stephen Boyd的《Convex Optimization》，其中涉及不少数学知识和习题，在此整理一下阅读此书的学习笔记。因为书上的记号比较详尽，所以在博客中仅摘取一些自己感兴趣的内容和公式的推导。 CVX101网课链接：https://lagunita.stanford.edu/courses/Engineering/CVX101/Winter2014/info...

2018-10-10 19:30:35 7948

原创 Codeforces Round #453 (Div. 1)解题报告（ABCD）

A.Hashing Trees题目大意：给定数组a[i]，其中a[i]表示深度为i的节点有a[i]个，问是否存在两个不同构的树同时满足这个条件。如果有，请输出。简要题解：有很多种构造方案。我的做法是，第一次把所有深度为i的节点都向深度为i-1的第一个节点连边。第二次，尝试分出一个深度为i的节点向深度为i-1的第二个节点连边。如果可以这样生成两棵树，则有解。#include<cstdio>#in

2017-12-21 13:50:51 504

原创牛客练习赛8解题报告

牛客练习赛8解题报告

2017-12-19 16:30:55 517

原创 Wannafly挑战赛4 解题报告

A.解方程题目大意：给出n个整数和x，请问这n个整数中是否存在三个数a，b，c使得ax2+bx+c=0，数字可以重复使用简要题解：枚举a和b，判断是否存在c。#include#include#include#include#include#include#includeusing namespace std;int a[1010];int n,x;map mp;

2017-11-26 00:22:02 378

原创 codeforces小做

打算这一个月做50道codeforces，尽量不刷水吧。

2017-07-23 09:07:56 527

原创 Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals) 总结

重回赛场，第一场比赛，找一找状态A Unimodal Array题意：判断一个数列，是否是先递增，再相等，后递减题解：模拟判断。记录当前位置处于第几段。#include#include#include#include#include#include#define maxn 110using namespace std;int a[max

2017-07-15 09:55:03 593 1

原创声明

非常抱歉，到现在才发声明。由于博主远离OI已久，目前正处于沉迷文化课的状态中，OI知识也忘掉了许多，所以可能已经没有能力回复大家的评论了。很感谢大家的留言和对题目的讨论，博客里可能某些代码有些许的问题，还望指正出来，虽不能改正，也只求不让错误的代码引起误解。欢迎大家在此博客下讨论问题，同样欢迎大家来交朋友，QQ363992115

2017-02-18 20:02:06 1298 6

原创【bzoj1823】[JSOI2010]满汉全席 2-sat

学习一下2-sat算法流程如下：1、建图，图具有对称性(对于有限制的A，从A‘向A连边)2、tarjan算法缩点3、判断是否有解：若存在一组A和A'在同一个强连通分量中，则无解4、缩点后，建反图5、拓扑排序，若当前点A未标记，则选择A，对应的，标记A’；若当前点A标记了，则沿着边传递标记本题是裸题#include#include#include

2016-07-11 21:05:42 858

原创【bzoj3938】Robot 超哥线段树

都说了是水题！！！离线，离散化每个时刻，对应插入直线插入O(nlog^2n)，询问O(m log n)#include#include#include#include#include#include#define maxn 100010#define N 600010using namespace std;struct yts{ int op,id;

2016-07-09 21:11:39 1342

原创【bzoj1568】[JSOI2008]Blue Mary开公司超哥线段树

标记永久化的应用维护若干个一次函数在每个端点的最大值首先将端点离散化(本题不需要)，线段树的每个区间维护的标记代表着覆盖这个区间的一条线段每次下放标记，利用标记永久化的思想，修改对应的区间标记若当前线段完全高于标记线段，则将当前线段进行标记若当前线段完全低于标记线段，则将当前线段扔掉若当前线段与标记线段有交点，考虑在上面的一部分是一个两条线段形成的分段函数，将长的线段作为当

2016-07-09 11:28:21 2257 2

原创【bzoj2109&&2535】[Noi2010]Plane 航空管制拓扑排序+贪心

贪心题果然都非常有意思呀正着想不太方便，倒着想就好建出反图，不考虑任何点的情况下，倒着枚举时间，每次选择k最大的，度数为0的点考虑点i的情况下，先忽视点i，倒着枚举时间，同样每次选择k最大的，度数为0的点，当某个时刻没有点可以选择时，这时必须选择点i，这就是点i出现的最早时间这个过程可以用堆来维护#include#include#include#inc

2016-07-09 11:03:47 1275

原创【bzoj3611】[Heoi2014]大工程虚树+dp

无脑的dp，不想写题解了#include#include#include#include#include#include#include#define maxn 1000010using namespace std;int head[maxn],to[2*maxn],next[2*maxn];vector v[maxn],g[maxn];int size[ma

2016-07-08 21:34:02 691

原创【bzoj2286】[Sdoi2011消耗战虚树+dp

学一下虚树单次dp是O(N)的，总复杂度O(NM)但实际用不到O(N)个节点，只有O(K)个节点是有用的，若能建出一棵O(K)个节点的树，那么复杂度会变成O(∑K)把给定节点按照dfs序排序，维护一个栈，栈中的节点是根到栈顶元素的链上的节点加入节点x，设栈顶元素为p，t=LCA(p,x)若t==p，则直接加入x若t!=p，则找到栈中最后一个深度小于t的节点y，在y到p之间的

2016-07-08 15:40:15 489

原创【bzoj2500】幸福的道路单调队列+树形dp

重要的事情说三遍我是傻逼！！！我是傻逼！！！我是傻逼！！！把%d打成了%lld一直WA题意坑爹，求从i出发的最长链的长度a[i]，求最长的一段a[i]，满足最大值-最小值第一问，树形dp解决第二问，单调队列解决#include#include#include#include#include#include#include#define ma

2016-07-07 19:42:04 920

原创【bzoj4199】[Noi2015]品酒大会后缀自动机

听说对反串建SAM，fa树就是后缀树？听说两个后缀的LCP就是LCA的mx？然后就是个树上dp？靠，老子边界打错了#include#include#include#include#include#include#define maxn 600010using namespace std;int head[maxn],next[2*maxn],to[2*m

2016-06-30 20:44:59 1061

原创【bzoj3926】[Zjoi2015]诸神眷顾的幻想乡后缀自动机

注意到叶子节点只有20个，从每个叶子节点开始dfs，在得到的trie树上建后缀自动机比较神奇的是，我们不用考虑那么多奇怪的问题，每个节点只需要从它trie树上的父亲节点开始建后缀自动机，就是对的讲道理，我连增量法都没理解透，更何况树上的呢，反正直接建就对了#include#include#include#include#include#include#define

2016-06-29 21:37:36 796

原创【bzoj3676】[Apio2014]回文串后缀自动机+倍增+manacher

每找到一个回文串，就在所有的串中查找出现了多少次因为暴力跳非常的慢，所以用倍增优化f[i][j]表示从第i个节点向上跳2^j步到哪里每次查询都是从末尾节点开始，倍增找到最后一个长度大于等于p的节点manacher算法证明了本质不同的回文串只有O(n)个，复杂度O(nlogn)原来manacher可以直接求偶数长度的回文串呀#include#includ

2016-06-29 20:52:41 1317

原创【bzoj3998】[TJOI2015]弦论后缀自动机

非常好的一道裸题T=1每个节点的出现次数=它的right集合大小初始时，每加入一个节点，它对应的right集合大小就为1T=0每个节点算一次，即把right集合大小强制变为1对深度计数排序后，节点i对fa[i]产生贡献计算出size[i]表示包含节点i在内，所有的能转移到的子串的出现次数之和注意：不能按bfs序处理size，因为计算size时，还

2016-06-29 17:57:10 604

原创【bzoj4516】[Sdoi2016]生成魔咒后缀自动机

入坑，持续更新SAM系列题目……感觉后缀自动机的构建好难理解，背过代码就可以吧应用好像不难，这道题只需要在所有修改fa的操作时更新ans即可每个节点对应若干个子串，所有节点代表的所有子串本质不同，节点i代表的子串个数为mx[i]-mx[fa[i]]#include#include#include#include#include#include#include#

2016-06-29 15:39:32 1405

原创 codeforces爆做

从现在起，最后几天刷题，从7月1日开始复习以前做过的题目和考试，整理模板和经典题目622E 贪心考虑每个1的子节点，把子树中所有叶子节点按深度排序，那么贪心的让深度小的叶子先上去dp[i]表示i最快用多久到根dp[i]=max{dp[i-1]+1,dep[i]}最后这一个转移方程没有想到啊，挺巧妙的

2016-06-27 15:54:29 879

原创【bzoj3205】[Apio2013]机器人斯坦纳树

f[l][r][i][j]表示把l到r的机器人合并，停在(i,j)点的最小步数f[l][r][i][j]=min{f[l][k][i][j]+f[k+1][r][i][j]}f[l][r][i][j]=min{f[l][r][i'][j']+1}记忆化搜索一下每个点从每个方向出发会走到哪里注意，题目里可能出现环，要特判spfa要加上一个优化才能通过先把初始队列中的点按距离排

2016-06-23 15:04:23 1081

原创【bzoj4006】[JLOI2015]管道连接斯坦纳树+子集dp

f[i][S]表示使S集合中的点联通的最小值g[S]表示把颜色为集合S的点联通的最小值g[S]=min{g[s]+g[S-S]}g[S]=f[i][SS] SS中的点均为S集合中的颜色跑的死慢，感觉正解应该比我的简单吧#include#include#include#include#include#include#include#define maxn

2016-06-23 11:05:34 605

原创【bzoj2595】[Wc2008]游览计划斯坦纳树

学一下这个模型，以前一直以为是到插头dp，实质上只是个状压dpf[i][j][S]表示现在在点(i,j)，与(i,j)联通的点的集合为S的最小值f[i][j][S]=min{f[i][j][s]+f[i][j][S-s]-a[i][j]}f[i][j][S]=min{f[i'][j'][S]+a[i][j]}由于同层之间的转移有环，所以用spfa来转移本题需要记录一下从哪个状态

2016-06-23 09:58:00 629

原创【bzoj1975】[Sdoi2010]魔法猪学院 A*

A*算法还是比较有意思的，本来以为就是个搜索加减枝，现在看来是有复杂度保证的我们到一个状态后，处理出当前状态的估价函数，每次选择估价函数最小的来更新估价函数g(n)的选取，若g(n)=实际值时，是有时间复杂度保证的，并且每次得到的答案一定是当前的最优解bfs就是一个特殊的A*算法这里的估价函数g(i)可以设置成为从T点到i点的最短路，每次用优先队列选估价最小的那个点更新

2016-06-20 10:38:02 938

原创坑

挖坑1、FFT和生成函数2、奇怪的曼哈顿生成树3、后缀自动机4、李超线段树5、通刷一下NOI题目6、在SDOI和JLOI中选一些题7、在ZJOI和HNOI中选一些题8、写模拟赛的总结

2016-06-17 11:07:56 550

原创【bzoj1068】[SCOI2007]压缩区间dp

比较有意思的题目就拿来写一写很明显的区间dp模型，状态很好设计，但是转移的时候有一些小注意因为一开始我们可以看做左端点有一个Mf[l][r][0/1]表示区间[l,r]中间是否加入了M，默认在L-1处有一个M时的最小长度f[l][r][0]=min{f[l][k][0]+r-k} 注意，这里不能是f[k+1][r][0]，因为这样默认了在k和k+1之间加入了一个Mf[l][r]

2016-06-14 19:31:11 1396 2

原创【bzoj2753】[SCOI2012]滑雪与时间胶囊最小生成树

遇到一个比较有意思的题目，写出来看看。如果没有高度相等的点，那么就是一个有向无环图的最小树形图，贪心的让每一个点选入边中权值最小的就可以加上了高度相等的点后，变成了部分无向的最小树形图，或者说是一个分层后的最小生成树因为，层与层之间的边都是有向的，而同一层之间的边都是无向的如何定义层这个概念呢？高度相等的点就是一层用一种比较巧妙的方式来做最小生成树，就可以避免处理层之间的问题

2016-06-13 23:24:19 1432

原创【bzoj1086】[SCOI2005]王室联邦树分块

比较有意思的题目，听说这是树分块的裸题？我们开一个栈，遍历一个节点，若该节点的几棵子树的大小>=B，那么就把他们分到一块，省会为当前节点这样做会剩下不到B个节点，这时候就利用栈传到上一层节点就可以最后会剩下不到B个节点，因为我们原来的块都是一定不超过2B的，于是把这B个节点放到最后一个块就可以#include#include#include#include#incl

2016-06-12 19:29:07 1253

原创【bzoj4262】Sum 线段树+单调队列

看了晨神的题解，确实很厉害呀http://blog.csdn.net/heheda_is_an_oier/article/details/51199299这道题利用了数据随机的性质，单调队列中期望O(log n)个元素，这就非常有趣了。我们把每个询问拆成两个，这样可以做差，右端点每往后移一个位置，对应加入一遍所有的答案，因为单调队列中有logn个元素，所以一共有logn中不同的答案

2016-06-10 10:05:27 714

原创这一阵子的总结吧……

比较匆忙，今天刚刚赶回青岛，过几天又是高考中考，所以在家里可以歇几天……本来打算明天再写，因为名额大概是明天才能确定下来，不过应该是个D吧5月份是一个糟糕的月份，状态不好？男人嘛，一个月总有那么三十几天……月初CTSC、APIO的惨败，让我开始质疑自己，我发现自己完全不会考试了，不知道该如何面对一场5个小时的考试不会分配时间，拿到一眼题想不出来，做到一半就开始心慌，害怕考砸，害怕时

2016-06-06 21:49:14 1052 4

原创【bzoj2809】[Apio2012]dispatching 主席树+dfs序

这分明就是一道主席树傻逼题呀，在dfs序上建出主席树，每次在主席树上二分就可以了。#include#include#include#include#include#include#define maxn 101000#define inf 1000000000#define N 3400000using namespace std;int head[maxn],

2016-05-23 20:46:05 631

原创【bzoj3624】[Apio2008]免费道路贪心+并查集

特殊边加完后，剩下的联通块越少，使用的普通边越少。考虑特殊边如何加？首先，把特殊边中必须加的边加入，如果必须加的边数>k或者原图不连通，则无解。之后，把特殊边能加则加，即不形成环就加入，直到加入k条。若都加完后还不够k条，则把剩下的边随便加。最后，把非特殊边能加则加。上课的时候，没有想到要处理必经边的问题。算是一道不错的题。#include#include

2016-05-23 19:41:14 814

原创 2016百度之星 - 初赛（Astar Round2A）题解

作为线下选手，非常不要脸的写一份题解……A、hdu5690题意：求m个x组成的数模k是否等于cm题解：两种做法，第一种，裸的矩阵乘法，构造矩阵{f(x,i),x}*{10 0}={f(x,i+1),x} {1 1}复杂度O(Tlog m)#include#include#include#include#include#i

2016-05-21 22:29:03 1792 2

原创【bzoj4602】[Sdoi2016]齿轮 dfs

我竟然会忍痛写了这道题，边写边想骂人，mdzzdfs一遍就可以，取对数后乘除化加减。考场上能让直接long double乘的人过去了，出题人我也是服了。#include#include#include#include#include#include#define maxn 20010#define eps 1e-8using namespace std;

2016-05-20 22:54:48 1195

原创【bzoj1369】[Baltic2003]Gem dp

怎么又刷水题？f[i][j]表示以i为根的子树i的权值为j的最小总权值咦？这不是O(n^2)的嘛？SDOI2015R2D2T2 doc证明了整棵树最多只能用到O(log n)种颜色%考场上敢自信开大数组的人#include#include#include#include#include#include#define maxn 10010using nam

2016-05-20 22:14:16 833 1

原创【bzoj4569】[Scoi2016]萌萌哒倍增+并查集

确实挺有意思的，暴力就是并查集直接缩，O(nm)如何快速维护区间是否对应相同？倍增！！！f[i][j]表示i开始的2^j个字符与谁对应相同，若f[i][j]=k，则从i开始的2^j个字符与从k开始的2^j个字符对应相同利用RMQ的思想，每次合并对应两段区间的合并，每次合并f[i][j]和f[k][j]时，把f[i][j-1]与f[k][j-1]、f[i+(1这个思路非常的有趣，没有

2016-05-20 21:53:35 1493 1

原创【bzoj4570】[Scoi2016]妖怪凸包

二分竟然过不去，真可恶。二分答案，判断每个点是否可行，转换成解二次不等式，在数轴上求交集。TLE正解是凸包。n个点(x,y)，在点(x,y)处的斜率为k(k单独使点(x,y)最小，得到的答案为x+y+2*sqrt(xy)求出这n个点的凸包，最大的答案永远在凸包上，每个点作为最大值都有一个斜率k的取值范围，只需求出每个点在这个区间内的最小值即可。如果单独使点i最小的同时，

2016-05-20 19:04:01 2001 2

原创【bzoj4571】[Scoi2016]美味主席树

只能想出个大概没有加法是主席树有了加法对应的就是主席树上一个区间而不是一个儿子了查询的时候，并不是在主席树上查询，而只是一种线段树式的查询如果+x后[l,mid]或[mid+1,r]有数，则往对应方向走查询[l,mid]和[mid+1,r]就在主席树上查询左儿子[l,mid]对应了区间[l-x,mid-x]右儿子[mid+1,r]对应了区间[mid+1-x,r-x]

2016-05-20 11:02:28 1340

原创【bzoj4568】[Scoi2016]幸运数字线性基+树链剖分

什么鬼东西呀？就是把两个线性基合并的过程放在线段树上，倍增可做，反正我写的树剖，听说学校里某人在某次考试的考场上的O(nlogn)算法被O(nlog^2n)的树剖秒成渣了。异或没打括号，调了好久。#include#include#include#include#include#include#define maxn 20010using namespace st

2016-05-20 08:07:50 1283

空空如也

空空如也