/**
* 二维ACM计算几何模板
* 注意变量类型更改和EPS
* #include <cmath>
* #include <cstdio>
* By OWenT
*/
const double eps = 1e-8;
const double pi = std::acos(-1.0);
//点
class point
{
public:
double x, y;
point(){};
point(double x, double y):x(x),y(y){};
static int xmult(const point &ps, const point &pe, const point &po)
{
return (ps.x - po.x) * (pe.y - po.y) - (pe.x - po.x) * (ps.y - po.y);
}
//相对原点的差乘结果…The 35th ACM/ICPC Asia Regional Tianjin Site —— Online Contest
2010年天津赛 网络赛 I题 Convex
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3629
题目大意是给你700个点，问从中选4个点组成凸四边形的方法数
比赛的时候其实最终得到了正确的方法，结果因为写搓了导致TLE，HDU的64位整形必须用I64d，导致WA
Catalan数:
$$ h(1)=1,h(0)=1 $$$$ h(n)=\begin{cases} \sum_{i=0}^{n-1} h(i) \times h(n-i-1) & \text{if }(n>=2) \\\\ \frac{C(2n,n)}{n+1} & \text{if }(n=1,2,3,\mathellipsis) \end{cases} $$相关结论： n边形能分解成三角形的分法数为 h(n – 2) n个节点能组成的二叉树个数为 h(n) 一个栈(无穷大)的进栈序列为1，2，3，…，n，出栈序列种数为 h(n)
参考（转载）： http://zh.wikipedia.org/wiki/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0 http://baike.baidu.com/view/4076365.htm
/**
* 简易四则运算（栈实现）
* #include <stack>
* #include <cstring>
*/
std::stack<char> opr;
std::stack<double> num;
char oprPRI[256];
//初始化调用
void initCalc()
{
//优先级设置
char oprMap[7][2] = { {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'^', 3}, {'(', 100}, {')', 0} };
for(int i = 0; i < 7; i ++)
oprPRI[oprMap[i][0]] = oprMap[i][1];
}
bool checkNum(char c)…// 最大公约数,欧几里得定理
int gcd(int a, int b)
{
return b?gcd(b, a % b): a;
}
// 拓展欧几里得定理
// 求解ax + by = gcd(a,b)
int ext_gcd(int a, int b, int &x, int &y)
{
int tmp, ret;
if(!b)
{
x = 1;
y = 0;
return a;
}
ret = ext_gcd(b, a % b, x, y);
tmp = x;
x = y;
y = tmp - (a / b) * y;
return ret;
}
//交换数值
void swap(int &a, int &b)
{
a ^= b ^= a ^= b;
}
/**
* a的b次方Mod c…题目链接： http://acm.pku.edu.cn/JudgeOnline/problem?id=2826
大致意思是给你两条线段，问组成的开口向上的V形区域能盛多少雨水。雨水是垂直落下的。
显然线段不相交，或者平行，重合，或者有一条斜率为0时结果为0.00
然后还有一种情况结果为0的，就是高的那条线段被低的挡住了。
关于差分约束（转载）
（本文假设读者已经有以下知识：最短路径的基本性质、Bellman-Ford算法。） 比如有这样一组不等式：
$$ \begin{cases} X1 - X2 <= 0 \\\\ X1 - X5 <= (-1) \\\\ X2 - X5 <= 1 \\\\ X3 - X1 <= 5 \\\\ X4 - X1 <= 4 \\\\ X4 - X3 <= (-1) \\\\ X5 - X3 <= (-3) \\\\ X5 - X4 <= (-3) \end{cases} $$(1)
一、引言
计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。
题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1986
这是一道并查集+树的题，采用Tarjan离线算法
首先BS一下出题的人，也太懒了吧，还要我们看1984题才知道输入
题目的意思是告诉一个节点数为40000的树，问我们两个节点间的距离。实际上就是找出公共父节点，Tarjan算法写挫了很容易TLE，我开始用Vector就写搓了，结果TLE，后来重写，自己写邻接表然后AC了。
题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=2446
这是一道匹配题，把行数（r）和列数（c）按（r+c）%2分成两组，然后连边，做一次二分图匹配，可以直接用匈牙利算法
匹配数等于两组的元素个数则为YES，否则NO
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
using namespace std;
int py[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
/**
* 最大二分图匹配
* 最大二分图匹配 = 最小点覆盖
* Base 1
*/
#define MAXM 1024 //行
#define MAXN 1024 //列
bool mat[MAXM][MAXN] = {false};…好久不写代码，省赛之后一直在赶作业和复习。对自己还真没什么信心
话说回来试了一下联系赛
三道水题，虽然钱两题很快，但是竟然多敲了几个没用的字符导致WA掉了，会范这种错误表示最近状态不宜写算法题啊
第三题想水一把结果我推得结论有漏洞+有道难题的服务器让人不爽的程度
int a = 12345678;
//格式为sring输出
Label1.Text = string.Format("asdfadsf{0}adsfasdf",a);
Label2.Text = "asdfadsf"+a.ToString()+"adsfasdf";
Label1.Text = string.Format("asdfadsf{0:C}adsfasdf",a);//asdfadsf￥1,234.00adsfasdf
Label2.Text = "asdfadsf"+a.ToString("C")+"adsfasdf";//asdfadsf￥1,234.00adsfasdf
double b = 1234.12543;
int a = 12345678;
//格式为特殊的string样式输出
Label1.Text =…题目链接：http://202.120.106.94/onlinejudge/problemshow.php?pro_id=143
这道题嘛，怎么说呢，好吧中等题
要求算出下山的前k短路的路长度
由于一定是下山所以可以用邻接表记录路径，然后用一个优先队列记录已有的到n的路长度
但是优先队列中计算下一个值得时候只要计算前k个数值就可以了，超过k的显然可以抛弃
题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=3659
这题不算难题了，基本算是中等题
题目大意是给出一颗树，在一些点建一个信号塔，信号塔覆盖范围是其所在点和邻近点，问最少几个信号塔可以覆盖全区域
思路是树状DP（后序遍历），有三个状态，分别记录父节点建塔，本节点建塔和子节点建塔的最少建塔数量
这次比赛成绩比预期差
开始Ultramanhu调整IDE
Q Boy从头开始看题
我的任务是倒数看题，最后看的题目是J，I，H，G
我看完J觉得J可做（哈密顿回路），但是需要很长时间。就首先放着继续看题
这时候Q Boy看完A提，觉得A题诗简单的图论，就交给Ultramanhu敲代码了，我大致想了一下J题的思路就开始看H题
树状数组模块
ACM个人模板
POJ 2155 题目测试通过
/**
* 树状数组模块
* 下标从0开始
*/
typedef long DG_Ran;
typedef long DG_Num;
const DG_Num DG_MAXN = 1005;
//2^n
DG_Num LowBit(DG_Num n)
{
return n & (-n);
}
//获取父节点索引
DG_Num DGFather(DG_Num n)
{
return n + LowBit(n + 1);
}
//获取小的兄弟节点索引
DG_Num DGBrother(DG_Num n)
{
return n - LowBit(n + 1);
}
//查找增加树状数组前pos项和
//参数(树状数组[in],索引[in],初始赋0即查找前n项和[out])
//复杂度:log(n)
void DGFind(DG_Ran *g,DG_Num pos,DG_Ran…题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3398
题目要我们计算1，0的排列方式总数，并且对任意长的字符串，1的数量大于等于0的数量
我们可以把题目转化为从（0，0）点到（m，n）点的方法总数，且路径不经过y=x-1这条直线
然后我们可以把从（-1，-1）到（m，n）的所有路径按以y=x-1翻转，所得到的路径显然就是经过y=x-1的所有方案
/**
* 线性筛法求素数表
* 复杂度: O(n)
*/
const long MAXP = 1000000;
long prime[MAXP] = {0},num_prime = 0;
int isNotPrime[MAXP] = {1, 1};
void GetPrime_Init()//初始化调用
{
for(long i = 2 ; i < MAXP ; i ++)
{
if(! isNotPrime[i])
prime[num_prime ++]=i;
for(long j = 0 ; j < num_prime && i * prime[j] < MAXP ; j ++)
{
isNotPrime[i * prime[j]] = 1;
if( !(i % prime[j]))…题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3400
这题就是一道简单的两重三分
首先设e点为从ab上离开的点，f为从cd上进入的点
显然对固定点e,f从距c的距离的长度是一个单调函数或者先减后增的函数，这里可以三分算出最优解。这里是第一个三分
然后对e点的最优解易证也存在这个性质，所以再来一个三分，就能解除最优解
又是我们的OJ
题目链接：
http://www.cn210.com/onlinejudge/problemshow.php?pro_id=92
tancu likes space travels but he is a poor software developer and will never be able to buy his own spacecraft. That is why he is preparing to steal the spacecraft of Petru. There is only one problem - Petru has locked the spacecraft with a sophisticated cryptosystem based on the ID numbers of the stars from the Milky Way Galaxy. For breaking the system Stancu has to check each subset of four…