1 会飞的小蛇

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 6w+

(dp)CF1225E. Rock Is Push

CF1225E. Rock Is Push题意:你在一个n×mn\times mn×m矩阵中的(1,1)(1,1)(1,1)点,要到达(n,m)(n,m)(n,m)点,你只能向右或者向下走。矩阵中有些格子有石头,你走到一个有石头的点可以按照你的移动方向推动石头,如果那个点上也有一个石头,它就会被按相同方向推的更远,以此类推。但是石头不能被推出矩阵外。问有多少种到达方案,对109+710^9+7109+7取模。思路:非常巧妙的一道dp题。不看题解真的想不到。如果没有障碍物,或者障碍物不能移动,那么是

2020-09-07 20:52:00

(树的直径)POJ1985Cow Marathon

POJ1985Cow Marathon题意:给一个森林,求树的直径的最大值。思路:求树的直径的模板题。两次dfs(bfs)即可。这篇博客讲的比较好。代码:#include<iostream>#include<stdio.h>#include<stdlib.h>#include<algorithm>#include<string.h>#include<ctype.h>#include<queue>#

2020-09-04 17:11:44

(Tarjan)洛谷P3387【模板】缩点

洛谷P3387【模板】缩点思路:虽然是缩点模板题,但是明显感觉比同一个题单中的其他题都难。题目思路已经提供给你:Tarjan缩点+DAGdp。就是用Tarjan缩点,重新建图之后,边拓扑排序边建边。TarjanDAGdp代码:#include<bits/stdc++.h>#define pii pair<int,int>#define ll long long#define cl(x,y) memset(x,y,sizeof(x))#define ct cerr

2020-09-04 09:10:22

(DAGdp)洛谷P1137旅行计划

洛谷P1137旅行计划思路:题目说只能走到东边的城市,又保证xxx再yyy的西面,虽然说是双向道路,但是就可以直接建(x,y)(x,y)(x,y)的边。可以得到dp[v]=max⁡(dp[v],dp[u]+1)dp[v]=\max(dp[v],dp[u]+1)dp[v]=max(dp[v],dp[u]+1),那么怎么解决后效性呢?就是用拓扑排序,因为拓扑排序出来的点就可以保证一个点不会再有入度,这样就不会受到别的点的影响,这样就没有了后效性。代码:#include<bits/stdc++.h

2020-09-04 00:19:26

(Tarjan)洛谷P1262间谍网络

洛谷P1262间谍网络思路:我们可以发现,不能被控制的间谍是不能被收买且不能被出卖。如果能够直接或者间接控制间谍的话,那么要么是收买入度为0的间谍,要么是几个间谍形成一个环,收买其中的最小值。那么我们就通过可以被收买的间谍进行缩点,不断缩小给的钱的值。然后再看看有没有点没有被遍历到的点,如果有,就是有间谍不能被控制。否则,我们就将入读为0的点加起来。注意缩点的时候,将所有的点缩成一个点,类似于并查集一样。在下面遇到这个点的时候,也要注意要用它的fa结点。代码:#include<bits/s

2020-09-03 20:29:27

Johnson全源最短路

Johnson全源最短路思路:对于NNN个顶点MMM条边的图怎么求全源最短路?Floyd,时间复杂度O(N3)O(N^3)O(N3)。NNN次Bellman-Ford/SPFA,以每个顶点为源点跑一遍,时间复杂度O(N2M)O(N^2M)O(N2M),在稠密图中比Floyd还慢,即使尝试一些如SLF的玄学优化也会被特定数据卡掉。NNN次Dijkstra,时间复杂度O(NMlog⁡M)O(NM\log M)O(NMlogM),弊端是无法处理负边权。那么是不是可以考虑把所有边权变非负?考虑如果

2020-09-03 17:20:30

随感&九月计划

希望又失望然后再绝望,然后便是无所事事,消极度日。不知不觉已经落后太多了。临到八月末才又再去看些新东西,可是却感觉少了很多动力。虽然学会了一个新算法依然高兴,理解了一个点依然会和队友报喜,AC了一个题后依然感到满足,依然为了CFranking熬夜打比赛……但总感觉缺少了些什么。或许总感觉热爱没那么纯粹了,而是带了一种证明自己的目的性而缺少了本心。很快又是一年,在半年的时候,我可能能领先同龄人一些;而此时回首,已经差了许多。但是有些事情没有如果,如果没那三个月的消极,可能我图论早就看完了。但是这种事情谁说的

2020-09-02 00:08:58

Tarjan总结

Tarjan算法:tarjan算法中比较重要的是dfndfndfn和lowlowlow数组。dfndfndfn是时间戳,或者理解是dfs序。lowlowlow是所谓的追溯值。先令low[x]=dfn[x]low[x]=dfn[x]low[x]=dfn[x]。现在有一条边(x,y)(x,y)(x,y),如果xxx是yyy的父节点,low[x]=min⁡(low[x],low[y])low[x]=\min(low[x],low[y])low[x]=min(low[x],low[y]);否则low[x]=m

2020-08-31 21:02:05

(Pick定理)POJ2954Triangle

POJ2954Triangle题意:给三角形的三个顶点(保证是整数),求三角形内部的点数。思路:Pick定理模板题,由定理可得:a=S−b2+1\begin{aligned}a=S-\frac{b}{2}+1\end{aligned}a=S−2b​+1​。用叉积求面积,可得a=∣AB→×AC→∣−b2+1\begin{aligned}a=\frac{|\overrightarrow{AB}\times\overrightarrow{AC}|-b}{2}+1\end{aligned}a=2∣AB×A

2020-08-30 18:39:10

(半平面交)POJ3335Rotating Scoreboard

POJ3335Rotating Scoreboard题意:给你一个多边形,问是否有一个区域能被所有边界上看到。思路:求多边形的核,自然用到半平面交。但是所给点的顺序不知道是顺时针还是逆时针序,我们可以通过求面积来判断,如果面积为正,那么就是逆时针序;反之为顺时针序。然后把直线方向全部按逆时针给出,这样的半平面交才正确。代码:#include<iostream>#include<stdio.h>#include<stdlib.h>#include<a

2020-08-30 10:58:45

(半平面交)POJ2451Uyuw‘s Concert

POJ2451Uyuw’s Concert题意:在一个10000×1000010000\times1000010000×10000的正方形有nnn条直线穿过,问左边半平面交所构成的多边形的面积是多少。思路:半平面交的板子题,再加上求多边形面积即可。但是依旧很些东西需要注意的。要加上四周的直线,注意是有方向的!要保证这四条线构成的半平面交就是这个正方形。poj提交G++的时候要用%.1f,不是%.1lf。代码:#include<iostream>#include<stdio

2020-08-29 23:00:47

(旋转卡壳)Gym101606Breaking Biscuits

Gym101606Breaking Biscuits题意:给你一个NNN个点组成的多边形,你可以三维旋转它,使它能够通过一个圆柱,问圆柱底的最小直径。思路:这题可以转换为对于一个多边形,现在用一组平行线,使得凸多边形都在平行线内(上),求最小的平行线之间的距离。这就成了求多边形的宽。...

2020-08-27 16:26:18

(单调栈)洛谷P2422良好的感觉

洛谷P2422良好的感觉思路:求max⁡{∑i=lrai×min⁡{ai∣l≤i≤r}}\max\{\sum_{i=l}^{r}a_i\times\min\{a_i|l\le i\le r\}\}max{∑i=lr​ai​×min{ai​∣l≤i≤r}}。我们可以发现,我们如果假定aia_iai​最小,那么为了使ai×∑j=lraja_i\times\sum_{j=l}^{r}a_jai​×∑j=lr​aj​尽可能大且满足∀aj≥ai,j∈[l,r]\forall a_j\ge a_i,j\in[l,

2020-08-27 14:38:07

(单调队列)洛谷P2629好消息,坏消息

洛谷P2629好消息,坏消息思路:题目可以选一个kkk,然后按照k∼n,1∼k−1k\sim n,1\sim k-1k∼n,1∼k−1,暴力枚举的话是O(n2)O(n^2)O(n2)。我们可以把这个像环一样的东西拆开,即an+i=ai,i∈[1,n]a_{n+i}=a_i,i\in[1,n]an+i​=ai​,i∈[1,n],将数组变成2n2n2n的长度,然后判断长度为nnn的每段是否符合要求。即计算满足∀∑i=jkai≥0,k∈[j,j+n−1]\forall\sum_{i=j}^{k}a_i\ge

2020-08-27 13:58:56

(单调队列)洛谷P1714切蛋糕

洛谷P1714切蛋糕思路:题意即给一个长度为NNN的数组a1,a2,⋯ ,aNa_1,a_2,\cdots,a_Na1​,a2​,⋯,aN​,求max⁡{∑i=lrai∣r−l+1≤M}\max\{\sum_{i=l}^{r}a_i|r-l+1\le M\}max{∑i=lr​ai​∣r−l+1≤M}。可以转换成sumi=∑i=1raisum_i=\sum_{i=1}^{r}a_isumi​=∑i=1r​ai​,求max⁡{sumi−sumj∣i−j+1≤M}\max\{sum_i-sum_j|i-j

2020-08-27 13:22:32

(尺取,单调队列)牛客I名家之壁

牛客I名家之壁思路:先看数据范围,只能用O(n)O(n)O(n)的写法去写,那么就用单调队列去维护最大最小值。那么接下来就是怎么解决寻找区间[l,r][l,r][l,r]的问题了。我们不妨固定lll,右移rrr,可以发现,最大值不可能减小,最小值也不可能增大,也就是最大值和最小值的差值是非递减的。也就是如果有一点rrr满足max⁡l≤i≤ra[i]−min⁡l≤i≤ra[i]>m\begin{aligned}\max\limits_{l\le i\le r}a[i]-\min\limits_{l

2020-08-27 10:54:03

(计算几何)洛谷P3829 [SHOI2012]信用卡凸包

洛谷P3829 [SHOI2012]信用卡凸包思路:题目上面已经很明确的写上了凸包。我们也可以通过画图得到,如下图:把圆心和切点相连,得到了几个矩形和扇形。题目所求的周长可以转换为求由每个信用卡四角上得圆心构成得点集所组成的凸包的周长再加上几个圆弧的长度。所以C=C凸包+∑C圆弧C=C_{凸包}+\sum C_{圆弧}C=C凸包​+∑C圆弧​。那么就要求圆弧的长度了,不妨猜测 :∑C圆弧=2πr\sum C_{圆弧}=2\pi r∑C圆弧​=2πr。以下证明∑C圆弧=2πr\sum C_{圆

2020-08-19 19:26:41

(计算几何)POJ1066Treasure Hunt

POJ1066Treasure Hunt题意:在一个正方形中,有n条线段(端点都在正方形的边上)将正方形分隔开。有一个点,想要从正方形外到这个点,只能走线段的中点。问最少需要经过多少个中点。思路:比较有意思的一道题。朴素的可以想到,它虽然说是走中点,但是你走出的其实是一个“封闭区域”,你只要找从外面到目标点最少经过几块“封闭区域”。而我们又可以发现,你走出一块“封闭区域”,走中点或者边上其他的点的效果是相同的。那么我们就可讲边上的点与目标点连线,然后判断有条线和它相交。注意n=0时候特判一下。

2020-08-17 20:24:35

(计算几何)POJ2653Pick-up sticks

POJ2653Pick-up sticks题意:按照顺序给你n根棍子,判断最后有多少棍子在最上面,就是它不会和之后的棍子相交。思路:N2N^2N2判断每根棍子和后面的是否相交即可。代码:#include<iostream>#include<stdio.h>#include<stdlib.h>#include<algorithm>#include<string.h>#include<ctype.h>#include

2020-08-17 19:30:09

(计算几何)POJ1269Intersecting Lines

POJ1269Intersecting Lines题意:给你两条直线,相交输出交点,重合输出“LINE”,平行输出“NONE”。思路:直线相交的模板题,就是在平行和重合的时候可以用叉乘判断。注意点: 提交G++的时候,不要用%.2lf,要用%.2f。代码:#include<iostream>#include<stdio.h>#include<stdlib.h>#include<algorithm>#include<string.h&

2020-08-17 19:11:15

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。