永远鲜红的幼月

未归档

CF(19) dp(6) gcd的应用(1) sort(4) spfa(1) 二分(12) 几何(1) 博弈(2) 固定算法(1) 图论(11) 套题(5) 字符串匹配(1) 并查集(4) 思维(2) 搜索(4) 数学题(2) 数据结构(10) 数论(4) 树状数组(1) 状压DP(1) 科普(3) 线段树(2) 网络流(3) 计算几何(4) 计算几何学习(17) 贪心(1) 题解(1)

/ 注册

全部文章 / 未归档（共192篇）

POJ-2318-TOYS（二分+线段相交）

题目链接：http://poj.org/problem?id=2318 题目大意：给出一个盒子，然后从左到右给出n条线，将盒子划分成了n+1个格子，然后再给出m个点，判断每个点在那个格子中。思路：从左上角到每一个点拉一根线，然后判断与每个格子的边缘的线是否相交。一开始我用的暴力，一个个线判断T...

2019-03-25

0 387

Codeforces Round #547 (Div. 3) A（分解质因数）B（思维）C（规律）D（简单模拟）E（简单模拟）F1，F2（大胆暴力）G（贪心）

A - Game 23（分解质因数）题目链接：https://codeforces.com/contest/1141/problem/A 题目大意：给出两个数a，b，通过*2||*3的操作能否让a变成b，如果可以，输出最小的变化次数。不行就输出-1 思路：判断b是否是a的倍数，然后看倍数是否...

2019-03-25

0 427

HDU-4807-Lunch Time(二分+费用流，思维)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4807 题目大意：n个点，m条边，k个人从点0到点n-1。有向图（题目中没有说）每条边长度1，有最大的人流承受量。人的速度是1.求所有人都到n-1点的时间。思路：一开始的时候以为是最大流，写了个板子...

2019-03-24

0 492

HDU-1007-Quoit Design（最近点对，分治）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1007 题目大意：给出n个点，输出这n个点中最近距离的两个点的距离/2。思路：数据范围不允许暴力，那么就开始想有什么更高效的算法，具体的代码推断自行百度。分治的思路。算法大致流程： Ste...

2019-03-19

0 790

POJ-2079-Triangle（凸包+旋转卡壳，暴力）

题目链接：http://poj.org/problem?id=2079 题目大意：给出n个点，然后求出这n个点中能够围城的三角形面积的最大值的三个点，输出面积。思路：首先易得三个点都位于凸包上。然后我们枚举凸包上的每个点i。然后j=i+1，k=j+1，旋转k点，直到得到最大的三角形，此时旋转j...

2019-03-15

0 450

POJ-2187-Beauty Contest（凸包+旋转卡壳板子）

题目链接：http://poj.org/problem?id=2187 题目大意：给出n个点，让你从中找出一对距离最大的点，输出(距离^2)。思路：将这些点构成一个凸包，易得最大距离的点对在凸包上，因此我们对这个凸包进行旋转卡壳，然后维护最大值即可。 ACCode： //#pragma ...

2019-03-13

0 524

Manacher（马拉车）算法-最长回文子串O(n)

存一个板子最长回文子串的线性处理方法，注意是子串，和子序列不同写一个板子：照着手跑一遍在参考一下别人的博客就很清楚了。 code： string Manacher(string s){ // Insert '#' string t="$#"; for(int ...

2019-02-20

0 467

POJ-2983-Is the Information Reliable?（线性约束，最长路，判断正环）

题目链接：http://poj.org/problem?id=2983 题目大意：给出n个点，m个关系，每个关系说明P a b val，a在b的北边val远，V a b，a在b的北边至少1单位远。问这些关系是否能推出一个不矛盾的大关系。思路：确定距离的双向路，建立两个边，即:f[a]-f[...

2019-02-17

0 574

POJ-1364，UVA-515-King （区间约束）

题目链接：http://poj.org/problem?id=1364 题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=...

2019-02-13

0 552

POJ-1201-Intervals，POJ-1716-Integer Intervals（区间约束）

题目链接：http://poj.org/problem?id=1201 题目大意：给出n个区间，每个区间[a,b]能最少能够选择c个数，问，最后能选多少个数，使这些数对所有的区间都满足。思路：区间约束的一道例题了，但是我感觉我写的好玄学？？麻瓜代码，看别人是最长路过的，我怎么还是最短路？？反向...

2019-02-12

0 391