- 博客(100)
- 资源 (1)
- 收藏
- 关注
RSS订阅
原创 #mark 后端踩坑之旅(一)
作为一个前端工程师，总想着有一天能够搭建自己的个人主页，所以前期要做好准备工作，从熟悉一套后端的搭建环境着手。笔记:依赖：node.js/pm2/express等，视需求而定。首先有一台具有公网IP的服务器，目前尝试用阿里云服务器，之后可能更换。服务器目录:--dist(npm run build生成的vue项目)--app.js--xx.jsonapp...
2019-04-14 23:16:44
199
原创 消失多年的老人正在盼望后来人
虽然我的oi经历非常惨淡，但是我还是希望我的有些内容能够给后来人一点点小小的借鉴。有的内容是在学习了各位大神的博客后总结出来的，相对来说容易理解。内容主要是川内省选后的部分题，因为没有系统规划的学习而显得比较杂，多为数据结构。现目前大一正在学习离散数学，其中图论的prufer编码(原来翻译错了，翻译成purfer)和切尔霍夫矩阵有一点用处。至于线代，行列式的算法思路和高斯消元的代码实现
2017-11-06 13:12:24
515
1
原创 有上下界的网络流
稍微学一下····对于无源汇的图一定有流量平衡∑f(u,i)=∑f(i,v)如果f(u,i)>=B(u,i)，则B(u,i)为流量下界。定义f(u,i)=B(u,i)+g(u,i)则 ∑B(u,i)+∑g(u,i)=∑B(i,v)+∑g(i,v)即∑B(u,i)-∑B(i,v)=M（i）=∑g(i,v)-∑g(u,i)M(i)为该点i的入流下界之和-出流下界之和。
2016-04-05 09:23:23
358
原创 scoi2015小凸想跑步
http://www.lydsy.com/JudgeOnline/problem.php?id=4445这次是重做，但发现自己被读入优化坑了，不造为什么，反正改了就过了，坑爹~~~double坑爹scoi2015day1 攻克完成（虽然是看了题解的很水攻克~~）之前写过思路了，这里不再说了~~~转成不等关系跑半平面交（吐槽：还是推不等式ax+by+c#include#
2016-04-01 16:01:53
502
原创 scoi2015 bzoj4444 国旗计划
http://www.lydsy.com/JudgeOnline/problem.php?id=4444其实我并没想到正解~~首先把环拆成链，两倍链。然后要离散化f[i]表示左端点在i之前的最多能覆盖到哪个位置可以先处理f[i]在i的时候最多能覆盖到哪里，然后向前缀和一样搞一下。暴力计算出1-m的最小次数L，所有人的最小人数和这个数之差的绝对值不会超过1.
2016-04-01 15:57:46
747
原创 scoi小凸玩矩阵 匈牙利+二分
http://www.lydsy.com/JudgeOnline/problem.php?id=4443参考leijp思想：每行只选一个，每一列只选一个，我们把每行当成左边，把每一列当成右边，每一行和一列只会有一条边。然后，把矩阵的值放在边上，比如(i,j)的值放在左边i行 到 右边j列上。这里要求第K大（没注意，以为是第K小。 然后K=n-K+1，求第K小）
2016-04-01 15:41:03
408
原创 方伯伯的商场之旅
http://www.lydsy.com/JudgeOnline/problem.php?id=3598能做的最后一道方伯伯~~看了一下，一开始以为是区间dp，后来才知道是数位dp.考虑这样一种做法，先枚举当前石子是全部搬到mid处最优，然后计算，这样貌似对于每一个数都需要枚举。那么假设我们处理搬到mid处最优的数有多少个，能计算出来，答案也就出来了。怎
2016-03-31 17:43:07
798
原创 bzoj3597方伯伯运椰子
http://www.lydsy.com/JudgeOnline/problem.php?id=3597运呀运呀运椰子QAQ听说是分数规划，然后就先去学了一发，顺便水了一发poj2728.（先吐槽：马丹，题面好长啊）然后，贴上分析历程：每条边u->v建立 bi+di表示往这边多跑一次流量和运费都增加 最多inf 反向建立v->u ai-di表示少跑
2016-03-31 10:31:56
781
原创 分数规划初步
poj2728:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=11063给定(x,y,z). w[i][j]=h[i]-h[j] d[i][j]=dis(i,j) 求∑xi w[u][v] /∑xi d[u][v]最小值定义∑xi w[u][v]=f(d
2016-03-31 08:59:20
331
原创 方伯伯的oj bzoj3594
http://www.lydsy.com/JudgeOnline/problem.php?id=3594（貌似比维护数列更恶心QAQ，虽然我只是看了一眼不想写）这道题真够恶心，它坑了我一上午~~还是下午来的时候调出来的。
2016-03-30 16:58:59
477
原创 bzoj3594&&方伯伯的玉米田
http://www.lydsy.com/JudgeOnline/problem.php?id=3594考虑dp[i][j]表示以i结尾，拔高了j次的lis.dp[i][j]=dp[k][l]+1枚举前一个最后以什么结尾，拔高了多少次。这里需要满足a[i]+j-l>=a[k]然后貌似就出来了：k但是这些值都不是定值（所以貌似CDQ不能做啊）然后就上二维树状数组。
2016-03-30 15:58:05
797
原创 莫比乌斯3题小结 hdu4746,1695 && poj2154
我们约定，[x]表示x取下整hdu4746: n m求∑ ∑ f(gcd(a,b)) i=1j=1 min(n,m) min(n/d,m/d)我们可以看成是：∑ ∑ u(t)* [n/dt]*[m/dt] 其中d的因子个数
2016-03-29 17:21:23
418
原创 bzoj4407于神之怒
看到好多大神留下的题解能看得懂，但是对于那个线性筛我表示我是蒟蒻我不会QAQ~于是我决定来水一发（顺便留下这道权限题，什么时候有权限了再去交一(交易)发）目前找了个过了的代码对拍发现并无错误&& 测试时间大致和那份程序差不多（应该能过吧~~）题意： n m求 ∑ ∑ gcd(i,j)^k mod 1e9+7
2016-03-29 09:20:07
614
1
原创 bzoj2820&&YY的GCD
马丹，又是一道权限题。问我怎么搞到题面：vjudge:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=37167HOMEPROBLEMSTATUSCONTESTAdd ContestStatisticLOGOUTnikelongUPDATE
2016-03-28 17:35:22
536
原创 bzoj3122 线性同余方程
http://www.lydsy.com/JudgeOnline/problem.php?id=3122看了一眼，以为是脑残题，可以先找出一个循环，然后再搞搞，发现找出循环代价太大，或者说有可能有些数多次出现了，但并没有循环。然后推公式吧：（卧槽，就几个月没碰数列就tm不会做了~ 然后搞出一个通项）xn= a^(n-1) x1 +b* (a^(n-1)-1)/(a
2016-03-28 16:04:10
394
原创 bzoj2326 矩阵乘法
http://www.lydsy.com/JudgeOnline/problem.php?id=2326递推：f[i]= f[i-1]*(10^log(i))+i mod M构造矩阵：{f[i-1] i-1 1} {10^log(i) 0 0 } { f[i] i 1} * {1
2016-03-28 10:19:58
683
原创 bzoj2301 莫比乌斯函数
http://www.lydsy.com/JudgeOnline/problem.php?id=2301其实就是求：b d∑ ∑ [gcd(x,y)==k]x=a y=c然后：b d∑ ∑ gcd(x,y)==kx=a y=c a b令f[a][b]= ∑ ∑ gcd(x,y)=k
2016-03-28 08:54:44
424
原创 poj1222高斯消元解XOR方程
http://poj.org/problem?id=1222题意：给定一个5×6的的矩阵，每次可以选择一个，使得它和四周的值翻转（开关变向），问怎样操作使得全为0.(PS：我交C++给我CE了，它不让我直接swap二维数组的第一维；G++给了我开了个优化)。利用高斯消元。我们可以得到30个方程。套用之前的思路，把f[][]看成是i,j是否相连，然后就会有一系列形
2016-03-27 21:22:22
495
原创 bzoj2753滑雪与时间胶囊
http://www.lydsy.com/JudgeOnline/problem.php?id=2753因为景点数要尽可能多，所以一定要在景点数最大的情况下代价最小。景点数要尽可能大，就是从1能到的所有点都要被遍历。所以利用了一个dfs+vis数组。 遍历复杂度是O(n)的。然后代价尽可能小。考虑一些生成树的边，如果两条边的出边的点一样
2016-03-27 20:46:34
481
原创 高斯消元求解多元一次方程组
最近刚接触高斯消元，懂得不多，但是这玩意琢磨起来很有意思。我们把一系列方程 a1x1+b1x2+c1x3+`````=M1 a2x1+b2x2+c2x3+````=M2 a3x1+b3x2+c3x3+````=M3看成是矩阵:{a1 b1 c1 ````} {x1} {M1}{
2016-03-26 16:17:28
4481
原创 bzoj2466高斯消元求解XOR方程
http://www.lydsy.com/JudgeOnline/problem.php?id=2466不会做，暴力- - 所以T掉不解释（n正解是高斯消元。预备知识：矩阵乘法，行列式的基本变换(其实不需要，只是掌握了之后可以把消元的过程看成是行列式转成上三角的过程)，XOR操作.对于一个不会高斯消元的蒟蒻，看网上的大神的题解都是各种被虐，所以慢慢补一下高斯
2016-03-26 11:35:15
1324
1
原创 bzoj2467 生成树 Matrix-tree定理
http://www.lydsy.com/JudgeOnline/problem.php?id=2467不知道为什么，一看到这道题就果断想到了Maxtrix-tree定理，然后搞kirchhoff矩阵。but首先我需要搞懂样例，测试了3种情况才搞懂样例。样例是两个五边形圈共用一条边，所有中心多边形的点都搞成度数为4，并且和周围的+1，-1都有边且累加-1（为了2的情况不写特
2016-03-25 16:33:55
1256
原创 bzoj2150部落战争 最小路径覆盖
http://www.lydsy.com/JudgeOnline/problem.php?id=2150之前一直不会的二分图。然后百度百科普及了一下有关最小路径覆盖的知识。详情请见：http://baike.baidu.com/link?url=pl9hFEA9_3-doYR5FlcLwrtorTZb3hLrpFL6ySNIrdE2ICQAOFRSaFvqf13
2016-03-25 16:26:54
451
原创 bzoj2140稳定婚姻
我比较蒟蒻，不会啊。http://www.lydsy.com/JudgeOnline/problem.php?id=2140~~题意好像是，如果删除这条边，仍能找到一个匹配，使得匹配数和原来的匹配数相等，就是unsafe，否则就是safe.n^2吧，好像要T那就换方法吧。试想，如果几对婚姻可以构成一个环，那么这个环转一下，还是能保证匹配数
2016-03-25 16:20:56
370
原创 bzoj1503 splay
运用一个整体变量处理全局修改，在减工资的时候处理删除。反正我是不会的，理解了别人的代码（改成了指针）：int del(node *&u,node *f){ if(u==null)return 0; int k;//删除人数 if(u->key+lazy<m) { k=del(u->ch[1],u)+u->ch[0]->sz+1; u->ch[1]->sz=u->sz-k
2016-03-24 11:15:06
315
原创 poj2420 模拟退火
害怕爬山算法挂掉，所以改成了新的模拟退火模拟退火就是在爬山算法的基础上又新增加了一个 以一定概率接受最优解。就是一个exp 比一个随机在(0,1)的概率小，就接受。#include#include#include#include#include#include#include#includeusing namespace std;const int m
2016-03-23 19:11:19
604
原创 POJ2187-最远点对->旋转卡壳（怎么开心怎么读）
给n个点，求最远点对,nn^2暴力可以过么- -|| 给了3s不过据说凸包+n^2暴力可以过，没有卡数据。不过跑的最快的应该就是凸包+旋转卡壳了。对于一个凸多边形，我们可以尝试用两条相平行但反向的有向直线去夹，一定能够夹住。 夹住的两个点为对踵点。我们可以看成是对于每一条边，都找到一个最高的点，使得和它构成的三角形面积最大。 然后再转动
2016-03-23 15:16:37
832
原创 UVA10652【凸包计算】
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1593给一些矩形（给定中心（x,y）长w宽h,和旋转角j）求一个最小多边形把所有的矩形包围，输出矩形所占多边形的面积比。可以想到是把矩形拆成4个点然后跑凸包。由于第一
2016-03-23 11:44:46
1035
原创 POJ - 3335 旋转计分板nlog n
http://poj.org/problem?id=3335判断一个多边形内核是否存在。先搞一下顺时针和逆时针，统统改为逆时针，然后求一下半平面交，这里onleft要用《=，我调了很久也没看出个所以然，然而不用《=就挂了。跪求路过的神犇解释一下~#include#include#include#include#include#include#includ
2016-03-22 19:50:38
441
原创 poj1375 圆的切线
给一个源点s，给一些圆，源点和s相切会形成阴影，求阴影并。如果能求出所有的圆构成的阴影，sort扫一遍就好了。怎么求，我们可以看成是s到圆的切线的直线和x正半轴求交点。我们可以计算圆心到s的距离，也可以得到那条直线，利用arcsin(r/d)得到一个角度，把直线旋转这个角度就得到了s和圆的切线（顺指针逆时针各得到一条），一段阴影就求到了。多段阴影拆成进边和出
2016-03-22 19:37:49
632
原创 bzoj2618凸多边形面积交
http://www.lydsy.com/JudgeOnline/problem.php?id=2618(⊙v⊙)嗯，几何大水题题意是要求n个凸多边形（逆时针给定点）的面积并，数据很弱。把每个多边形拆成直线，然后扫一遍做半平面交，最后统计答案就可以了：#include#include#include#include#include#include#i
2016-03-22 10:08:08
1520
原创 scoiday1T3&&bzoj4445小凸想跑步
几何题啊，据说是裸的半平面交，but我还是WA了好几发。逆时针给定一些点，求多边形内到第一条边面积比到其它边小的点的概率（用范围/总面积）然后可以设该点为（x,y），到所有边的面积表示出来，然后建立不等关系，化简约分后我们可以得到一系列关于x,y的不等式，形如ax+by然而有两个bug我没考虑到，一个就是要保证(x,y)的点在凸多边形内部，怎么保证？先把所有的半
2016-03-22 08:34:28
1464
1
原创 计算几何速成
之前一直没接触过计算几何，不过几何题大多都是嘴上说起来轻松，操作起来恶心的~~先来看看怎么定义一些东西：①定义点类(向量类)：struct point{ double x,y;};要计算点可以先重载+,-,*,/ 以及各种比较。（向量也可以看成是点，如果它的端点是原点的话 ||同理，点也可以看成是向量）②定义线段： 记录2个端点③定义直线：stru
2016-03-21 10:27:43
371
原创 POJ2420爬山算法
给出n(n怎么搞，依次找每个点？不行二分？很明显没有单调性质所以就乱搞！！用一个NP的算法：先在平面上找一个点，然后确定一个半径，在这个圆上找一个点，看是否更优，是就更新x,y.半径要不断缩小。这种做法带有很强的随机性，但是在一定精度下他是对的。这里我们就需要考虑这样一个问题：半径缩小的越慢，找到的点越精确，但同时速度也就
2016-03-19 21:28:30
646
原创 差分约束
其实我并不懂- - QAQ做题遇到了没办法，就来普及一下、差分约束，我觉得就是差分+约束。例如看这样一个例子：（有语病？QAQ）给一列数x1,x2,x3,````xk如果要满足x3+x4+x5
2016-03-13 20:44:28
272
原创 URAL 1553【CAVE and TUNNEL】
给一些点初始为0，每次增加一个点的权值，或者访问两点之间权值的最大值.裸的LCT,套一下模板：#include#include#include#include#include#include#includeusing namespace std;const int maxn=100000+20;struct node{ node *f; node *ch[2
2016-03-11 15:39:03
397
原创 LCT解法解决数据结构神薙bzoj1036
确实是神(mo ban)薙(ti)好多数据结构都靠这个入门- -用LCT解这道题也很简单。维护val,maxval,sum.CHANGE的时候把这个点旋到当前splay的根，然后进行操作QMAX，先把u设为整棵树的根，再把v旋到当前splay的根，然后找到当前树(u-v这条路径)的根，读取信息QSUM,和上面一样，读取SUM.然后就是模板了：#include
2016-03-11 09:50:26
358
原创 数据结构数据生成器--生成树 bzoj1036
今天写了一道数据结构的经典题---树的统计，尝试用LCT写，结果不造怎的可以过样例，但交上去就WA，苦于肉眼找不出错，于是翻出了以前写的树立剖分的版本，想来搞搞对拍。然而~~~~~尼玛树怎么构造啊- -然后沉思- -，网上搜索，找不到- - -- - - - -- - - - 然后想起来了purfer编码,咦,purfer编码不就是搞树的么。还记得purfer编码是
2016-03-11 09:43:39
1899
原创 bzoj2049[洞穴勘测]纯粹的LCT
http://www.lydsy.com/JudgeOnline/problem.php?id=2049就像lct=link-cut-tree一样，这道题是纯粹的LCT.为什么呢，它的操作一共就只有link,cut.(query是查询)可以说是非常的裸，但是对于我这个刚学的菜鸟还是有一个地方比较纠结首先初始化所有的点，是他们各自是一棵树。然后一旦两个点两边就link两个森林
2016-03-10 10:49:13
708
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人