现在位置: 首页 > 算法 > 文章
2019年09月07日 算法 ⁄ 共 1145字 评论关闭
#include <iostream> #include <cmath> #include <algorithm> #include <cstdio> using namespace std; #define INF 50005 struct Node { double x, y; }; Node point[INF]; int n, s[INF], top; double cross(Node a, Node b, Node c) { double x1 = a.x - c.x; double y1 = a.y - c.y; double x2 = b.x - c.x; double y2 = b.y - c.y; return x1 * y2 >= x2 * y1; } dou...
阅读全文
2019年09月06日 算法 ⁄ 共 1265字 评论关闭
#include <cstdio> //EK()算法。时间复杂度(VE^2) #include <queue> #include <cstring> using namespace std; const int maxn = 1200; const int INF = (1<<30)-1; int g[maxn][maxn]; int flow[maxn],pre[maxn]; int rank[maxn][2],pig[maxn]; bool vis[maxn]; int n,m; int bfs(int s,int e) { memset(pre,-1,sizeof(pre)); memset(vis,false,sizeof(vis)); queue<int&g...
阅读全文
2019年09月04日 算法 ⁄ 共 1926字 评论关闭
题意:给定一棵 N (1 <= N <= 10000) 个结点的带权树,定义 dist(u, v) 为u, v 两点间的最短路径长度,路径的长度定义为路径上所有边的 权和。再给定一个 K (1 <= K <= 10^9 ) ,如果对于不同的两个结点 a, b ,如果满足 dist (a, b) <=K ,则称 (a, b) 为合法点对。求合法点的 个数。 思路:点分治。详见漆子超的《分治算法在树的路径问题中的应用》,详见代码: // file name: poj1741.cpp // // author: kereo //...
阅读全文
2019年09月04日 算法 ⁄ 共 3965字 评论关闭
题意:在spoj375基础上增加了一条路径的取反操作,其他都一样。 思路:剖分没有变化,在线段树部分,需要一个tag标记该段是否需要需要取反,记录一个最大值、最小值即可。=  =(打tag的那 段应该已经跟新好,push_down的时候如果tag=1那么直接对两个子段进行更新。。一开始意识模糊了。。)详见代码: /********************************************************* file name: poj3237.cpp author : kereo create time:...
阅读全文
2019年09月04日 算法 ⁄ 共 1435字 评论关闭
题意:n个结点构成一颗树,问最少切断几条边使得一个子树恰有m个结点。 思路:设dp[i][j]为当前i结点及其子树结点共j个需切多少条边。初始更新每个结点i的dp[i][1],即dp[i][1]=deg[i] (为i的入度)。那么当前访问到结点u,已访问到子结点v,那么dp[u][j]=min( dp[u][j], dp[v][k]+dp[u][j-k]-2 ), 因为合并的时候将会少掉2个入度,详见代码: // file name: poj1947.cpp // // author: kereo ...
阅读全文
2019年09月04日 算法 ⁄ 共 1295字 评论关闭
题意:题目写的很难读懂。。其实本质是给定n个矩形,将他们并在一起,然后你要在里面尽可能挖一块尽可能大的矩形,求矩形的 面积。 思路:单调栈。我们从左到右扫,维护h单调增。考虑当前第i个矩形,其高为p[i].h,如果比栈顶的h高那么直接将该矩形压栈,不 然,将栈中的点一个个弹出直到栈顶元素的h比p[i].h小。在弹出的时候,初始一个len=0,每次len加上当前弹出元素的w,用 len*h来更新ans,(画图可知这是当前h能画的最...
阅读全文
2019年09月04日 算法 ⁄ 共 1816字 评论关闭
题意:由n个结点组成的树,每个结点有个点权,你从结点1出发,问最多走m步可以获得点权和(重复走一个结点只有第一次走过会 获得点权值)的最大值。 思路:设dp[i][j][k]表示从i结点走j步( k=0表示回到i结点共j步,k=1表示j步之后不回到i节点 )可获得点权和的最大值。 考虑当前的结点u,以及它的子结点v,那么只有三种情况。 (1)dp[u][j + 2][0]=max( dp[u][j + 2][0],dp[u][j - k][0]+ dp[v][k]...
阅读全文
2019年09月03日 算法 ⁄ 共 1164字 评论关闭
题意:给你n和h,问有多少棵n个节点高度为h的二叉搜索树(标号为1-n,只有一个节点的树高为0),答案对10^9+7取模。 思路:设dp[ n ][ h ]为 n 个节点高度不超过 h 的二叉搜索树的个数。那么dpn,h=∑i=0n-1dpi,h−1⋅dpn−i-1,h−1   即选定一个点,枚举左子树的个数为 i ,剩余右子树的个数即为n - 1 - i 。详见代码: /********************************************************* file name: spoj8549.cpp author : kereo ...
阅读全文
2019年09月03日 算法 ⁄ 共 4288字 评论关闭
SPOJ Problem Set (classical) 7758. Growing Strings Problem code: MGLAR10       Gene and Gina have a particular kind of farm. Instead of growing animals and vegetables, as it is usually the case in regular farms, they grow strings. A string is a sequence of characters. Strings have the particularity that, as they grow, they add characters to the left and/or to the right of the...
阅读全文
2019年09月03日 算法 ⁄ 共 4491字 评论关闭
题意:中文题。 思路:很好的一道树链剖分。树剖后,线段树要记录左端点l,右端点r,左端点的颜色lc,右端点的颜色rc,区间成段更新的标记tag,区间 有多少颜色段。区间合并的时候要注意如果左子树的右端和右子树的左端颜色相同那么数量要减一。但是存在一个问题当前剖到 的链与上一次的链在相交的边缘可能颜色相同,如果颜色相同答案需要减一。所以统计答案的时候要记录下上一次剖到的链的左端 点的颜色,与当前剖到的链右端点的...
阅读全文