- 博客(84)
- 收藏
- 关注
RSS订阅原创 Computational Geometry Templates
//author: birdstorm#includeusing namespace std;/*************useful TIPS in complex*********//***1. use eps carefully*2. remember useful functions in complex:* abs() for distance,* arg() for
2016-02-14 22:08:03
645
原创 AOJ 2534 Dictionary
Aizu 2534题意：给n个字符串，问是否存在一个合法的字典，使得这些字符串是字典序递增的。对相邻两个字符串的第一个不相等字符建边，拓扑排序即可。 注意边界判断。
2015-08-27 23:26:10
656
原创 ASC 41 Problem D. Data Mining
ASC 41题意：给n个数，q个查询，每次询问序列中以第L个数为开头的后缀中，第x个数在这个后缀中是第几个出现的。离线查询。将查询按L从小到大排序，预处理每个数上一次出现的位置。每次插入上一次出现位置在L之前的数，显然会将所有L之前的数都加入，然后查询这个数在后缀中第一次出现的位置(设为p)之前的前缀和。由于L之前所有数都被加入，且[L,p]之间的所有数有且仅有被插
2015-08-27 17:41:23
613
原创 AOJ 2537 Billiard
Aizu 2537题意：打台球，已知母球及所有球的半径、位置，求母球打出后第一个碰到的球的编号。计算几何的模拟。考虑每个球的中心点，母球中心的运动轨迹只在台的中央，由(r, r), (r, w-r), (h-r, w-r), (h-r, r)四个点组成的矩形内部。将其设为新的四边，沿着运动方向的射线去和这些边求交点，经过反射后的每个球的坐标可以预处理出来。模拟至运动
2015-08-27 17:30:06
528
原创 AOJ 2541 Magical Bridges
Aizu 2541题意：n个岛屿，由m条桥连接，其中有k条是魔法桥，你可以用魔法把他们变成相同长度。求在执行魔法后，两个起点S1和S2到终点T的最短路的最小绝对差。（1S1和S2到T的最短路将会是如 ax+b 的形式。x为相同长度，a为该最短路上魔法桥的个数。画出所有的直线，现在等价于求多条射线的最低点。利用线段交暴力即可。用dij进行预处理，每个点可以得到最多
2015-08-27 17:21:32
623
原创 AOJ 2538 Stack Maze
Aizu 2538题意：给一个迷宫，有一些珠宝和洞，起始位置是左上角，只能往右边和下面走。你可以通过捡起一些珠宝放到一些对应的洞里来得到分数，可以捡起无限多的珠宝，但是背包是一个栈，每次退栈必须得分。问最大的得分。(1记忆化搜索。每次求一个矩形里的最大得分情况。由于背包是栈，所以该矩形的情况不具有前效性和后效性。#include using names
2015-08-27 16:57:50
615
原创 AOJ 2543 Ancient Scrolls
Aizu 2543题意：给三个长度相等的串A，B，C，已知他们与原串的海明距离不大于d，要求还原出字典序最小的原串。贪心。对于原串S的每一位来说，有四种可能性：S[i]=AS[i]=A[i]S[i]=B[i]S[i]=C[i]除此之外，三个串在第i位上有五种可能的相同：A[i]，B[i]，C[i]互不相等A[i]=B[i]A[i]=C[i
2015-08-27 16:45:57
538
原创 AOJ 2539 Counting 1's
Aizu 2539题意：询问是否存在区间[A,B]，使得[A,B]之间，从后往前二进制第i位为1的数个数为k[i]。（1要求判断无解，多解或者确定唯一解。非常有趣的思想题，我们设区间大小W=B-A+1，注意到k[0]，也就是最后一位二进制可以将W的范围约束住。一共有三种情况：W=2*k[0]-1W=2*k[0]W=2*k[0]+1所以我们分别对三种W进行判断
2015-08-27 15:42:58
646
原创 HDU 5027 Help!
三分趣题, 分类讨论.之前C++读入被各种卡时间= = 真是坑, G++就过了计算几何什么的就别卡时间啦...P.S. 为何网上有人用圆与线段交(疑惑)?附上奇怪的代码#include#include#include#include#include#include#includeusing namespace std;const double eps=1
2015-04-16 20:21:07
634
原创 Andrew Stankevich's Contest 23
Problem A. Bike Roads分段三分套三分注意分段区间内需保证导函数单调ac前一炮分了3*3=9个区间, WA在test 77我最后分了最多4*4=16个区间= =Problem B. Diversion题意是给出一个无向图, 由一颗生成树的边(type1)和一些其他边(type2)组成, 保证所有点两两双联通现在求删去type1和type2各
2015-02-07 11:09:26
622
原创 AOJ 2121 Castle Wall
/*author: birdstorm*/#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define MAXN 100//#define
2014-09-01 12:39:39
663
原创 AOJ 2124 Magical Dungeon
在一个迷宫（图）中有一个起点和一个终点，现在你有一个最大血量maxhp，需要从起点满血出发，每条边上的权值如果是正的表示走这条边会加血，如果是负的即表示会扣血。求抵达终点时的最大血量，如果中途血小于等于0即为game over。最简单的想法是使用Extended Bellman-Ford，对所有点进行松弛，在可以回血的环上不停更新各个节点直到没有可以更新的节点。这样复杂度为O(
2014-09-01 12:22:26
737
原创 AOJ 2130 Billion Million Thousand
/*author: birdstorm*/#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define MAXN 1005//#define
2014-09-01 11:54:24
661
原创 AOJ 2131 Pi is Three
/*author: birdstorm*/#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define MAXN 1005//#define
2014-09-01 11:48:05
541
原创 BOJ 2014新生暑假个人排位赛07 整合
#include #include #include #include #include #include #include #include #include #include #include #include #include #define MAXN 100005#define eps 1e-5#define MOD 1000000009 #defin
2014-08-08 20:28:55
654
原创 BOJ 2014新生暑假个人排位赛05 整合
#include #include #include #include #include #include #include #include #include #include #include #include #include #define MAXN 100005#define eps 1e-5#define MOD 1000000009 #defin
2014-07-26 17:55:57
655
原创 BOJ 2014新生暑假个人排位赛04 整合
A. 大家一起点外卖/*USER_ID: test#adnimPROBLEM: 437SUBMISSION_TIME: 2014-07-21 15:09:29*/#include #include #include #include #include #include #include #include #include #include
2014-07-26 17:33:36
709
原创 2014 Multi-University Training Contest 2 ZCC loves cards
#include #include #include #include #include #include #include #include #include #include #include #include #include #define MAXN 100005#define eps 1e-5#define MOD 1000
2014-07-25 12:50:55
733
原创 BUPTOJ 409. 数的关系
/*USER_ID: test#ggvalidPROBLEM: 409SUBMISSION_TIME: 2014-07-14 18:31:44*/import java.math.BigInteger;import java.util.Scanner; public class Main { public static void main(String[] args)
2014-07-14 18:50:30
726
原创 BUPTOJ 407. BLOCKS
/*USER_ID: test#ggvalidPROBLEM: 407SUBMISSION_TIME: 2014-07-14 17:45:35*/#include #include #include #include #include #include #include using namespace std; int t, n, m;int dp[1005][1
2014-07-14 18:32:40
794
原创 图论相关(更新5.31)
int v, e, x, y;int vis[MAXN], low[MAXN], dfn[MAXN];bool cut[MAXN], bridge[MAXN][MAXN];vector g[MAXN];void cut_bridge(int cur, int father, int dep, int n){ vis[cur]=1; dfn[cur]=low[cur]=dep;
2014-05-31 21:19:27
781
1
原创 AOJ 2127 Japanese Style Pub
dfs+状压dp/*author: birdstorm*/#include #include #include #include #include #include #include #include #include #include #include #include #include #define MAXN 1005#define N 105#
2014-05-30 14:51:29
843
原创 AOJ 2126 Alien Pianist
题意繁琐, 不想写了/*author: birdstorm*/#include #include #include #include #include #include #include #include #include #include #include #include #include #define MAXN 1005#define N
2014-05-29 13:50:46
800
原创 AOJ 2083 Black Force
/*author: birdstorm*/#include #include #include #include #include #include #include #include #include #include #include #include #include #define MAXN 205#define N 105#define inf 1.0e
2014-05-27 16:42:51
593
原创 AOJ 2084 Hit and Blow
非常有趣的模拟题, tiyi/*author: birdstorm*/#include #include #include #include #include #include #include #include #include #include #include #include #include #define MAXN 205#defin
2014-05-26 21:24:41
1098
原创 hdu 2224 The shortest path
/*author: birdstorm*/#include #include #include #include #include #include #include #include #include #include #include #include #include #define MAXN 205#define N 105#define inf 1.0e
2014-05-26 11:17:16
644
原创 poj1556 The Doors
几何+最短路, 判断的时候暴力jiuxin/*poj1556-dijkstra author:birdstorm*/#include #include #include #include #include #define MAXN 1005#define N 105#define inf 1.0e9#define INF 1<<30#define eps
2014-05-07 10:47:46
600
原创 ACM-ICPC 4836 Gomoku
暴力枚举l/*author: birdstorm*/#include #include #include #include #include #define MAXN 1005#define N 205#define INF 1<<30#define eps 1.0e-10#define For(i,m,n) for(i=(m);i<n;i++)#define
2014-04-30 17:09:50
803
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人