就是说一个三角形。。2条边长的平方分别为A和B。。都小于2*10^9 并且这个三角形三个顶点的坐标都是整数。。求最大可能的面积或者没有这样的三角形返回-1.。
首先变长知道了。。那么这个三角形的夹角越接近90越好。。那么只要算出所有可能的角度然后扫描过去就可以了。。。
好烦啊。。程序很长很猥琐。。
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack> a
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <complex>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cassert>
#include <cctype>
using namespace std;
typedef long long ll;
const int maxn=2000000000;
vector<ll> S;
void predo()
{
for(ll i=0;i*i<maxn;i++)
S.push_back(i*i);
}
int inS(int x)
{
int i=lower_bound(S.begin(),S.end(),x)-S.begin();
if(S[i]==x) return i;
return -1;
}
class MaxTriangle
{
vector<double> put(int A)
{
vector<double>res;
double p=acos(0);
for(int i=0;i<S.size()&&S[i]<=A;i++)
{
int B=A-S[i];
int t=inS(B);if(t==-1) continue;
double a=atan2(i,t);
res.push_back(a);
res.push_back(a+p);
}
return res;
}
public:
double calculateArea(int A, int B)
{
predo();double p=acos(0);
vector<double> a=put(A),b=put(B);
sort(a.begin(),a.end());sort(b.begin(),b.end());
if(a.size()==0||b.size()==0) return -1;
double best=0;
for(int j=0,i=0;i<a.size()&&a[i]<=p;i++)
{
while(b[j]-a[i]<p&&j!=b.size()-1)j++;
double q=b[j]-a[i];
if(abs(q-p)<abs(best-p)) best=q;
if(j)j–;
if(abs(q-p)<abs(best-p)) best=q;
}
return sin(best)*sqrt(A)*sqrt(B)/2;
}
};

我在GYH神牛的论文里看到对于RMQ问题有一种很方便的离线算法。。于是写了个程序去AMIPT105这道标准的RMQ题。。
论文在这里：cid-47648079f9d741d1.skydrive.live.com/self.aspx/OI/RMQ%e9%97%ae%e9%a2%98%e7%9a%84%e7%a6%bb%e7%ba%bf%e8%bf%91%e7%ba%bf%e6%80%a7%e7%ae%97%e6%b3%95.doc
Code:
#include<cstdio>
#include<utility>
using namespace std;
typedef pair<int,int> pi;
const int maxn=250000,maxm=2*maxn;
int stack[maxn],top=0,n,cnt=0,m;
int F[maxn];
float A[maxn],Ans[maxm];
inline void makeset(int x){F[x]=x;}
int find(int x){if(F[x]==F[F[x]])return F[x];return F[x]=find(F[x]);}
inline void Union(int x,int y){F[y]=x;}
int first[maxn],next[maxm],qnt=0;
pi data[maxm];
void add_query(int l,int r)
{
data[qnt]=pi(l,cnt++);
next[qnt]=first[r];
first[r]=qnt++;
}
void init()
{
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%f",A+i),first[i]=-1;
scanf("%d",&m);int l,r;
for(int i=0;i<m;i++) scanf("%d %d",&l,&r),add_query(l,r-1);
}
void solve()
{
for(int i=0;i<n;i++)
{
makeset(i);
while(top&&A[stack[top-1]]>=A[i])
{Union(i,stack[–top]);}
stack[top++]=i;pi*tmp;
for(int j=first[i];j!=-1;j=next[j])
{
tmp=data+j;
Ans[tmp->second]=A[find(tmp->first)];
}
}
for(int i=0;i<m;i++)
printf("%fn",Ans[i]);
}
int main()
{
//freopen("in","r",stdin);
//freopen("out","w",stdout);
init();
solve();
}

就是说一个数。。把它+1或-1或者如果是偶数除以2。。求最少次数把它变成0.。。
这个数小于200000。。。
很显然从0开始倒着宽搜就可以了。。不过我为了体现出我的个性。。用了IDFS。。
。。还加了个剪枝，就是+1和-1不能连续两次出现。。然后就0.01sAC了。。
我倒。。。暴力IDFS居然也能过。。4.29s。。晕死了。。大概是因为操作数肯定是logn量级的吧。。
Code：

给定一个完全图和一些必须包含在哈密顿路中的边。。求这样的哈密顿路有几条。。
很显然如果一个点连接了3条或以上的必须边的话。。就无解了。。所以必须边一定是成链出现的。。
一个有2个或以上节点组成的必须链有一个方向，就是因子2
同时如果有n条链的话（单个节点也算链。。）。。那么排列也有n！的因子。。
全部乘起来就OK了。。
Code:
#include<string>
#include<vector>
#include<cstring>
using namespace std;
const int mod=1000000007;
class HamiltonPath
{
bool vis[50];
vector<string> map;
int num;
void dfs(int x)
{
vis[x]=true;num++;
for(int i=0;i<map.size();i++)
if(map[x][i]==’Y’&&!vis[i]) dfs(i);
}
public:
int countPaths(vector <string> m)
{
vector<int> d(m.size(),0);int cnt=0;map=m;long long ans=1;
for(int i=0;i<m.size();i++)
for(int j=0;j<m.size();j++)
{
if(m[i][j]==’Y’) d[i]++;
if(d[i]>2) return 0;
}
memset(vis,0,sizeof(vis));
for(int i=0;i<m.size();i++)if(!vis[i]){num=0;dfs(i);cnt++;if(num>1)ans*=2,ans%=mod;}
for(int i=1;i<=cnt;i++)ans*=i,ans%=mod;
return ans;
}
};

经神牛指点。。注册了topcoder。。今天有比赛的样子。。所以先做个上次的比赛找找感觉。。
1：
直接计算。。很easy啊。。
#include<cstdio>
#include<cmath>
using namespace std;
class RecursiveFigures
{
public:
double getArea(int len,int k)
{
double ans=0;double d2=len*len,p=acos(0);
for(int i=0;i<k;i++)
{
d2/=2;
ans+=d2*p-d2;
}
ans+=d2;
return ans;
}
};
2：
扫描线。。把每个方程看成一个线段。。那么就变成了在平面上找一个点在最多的线段中了。。
然后从左往右扫描就OK了。。注意可能那个点不是整数。。转换的时候+/-个0.5就OK了。。
#include<string>
#include<vector>
#include<algorithm>
#include<iostream>
#include<sstream>
using namespace std;
typedef vector<string>::iterator it;
class Inequalities
{
struct event
{
double x;int a;
event(double _x,int _a):x(_x),a(_a){}
bool operator<(const event&o) const
{return x<o.x;}
};
vector<event> list;
typedef vector<event>::iterator lit;
void add(double l,double r)
{
list.push_back(event(l,1));
list.push_back(event(r,-1));
}
void deal(const string&a)
{
istringstream in(a,istringstream::in);string tmp;
in>>tmp;int x;in>>tmp;in>>x;
if(tmp=="<") add(-1,x);
if(tmp=="<=") add(-1,x+0.5);
if(tmp=="=") add(x,x+0.5);
if(tmp==">") add(x+0.5,1001);
if(tmp==">=") add(x,1001);
}
public:
int maximumSubset(vector<string> Is)
{
for(it i=Is.begin();i!=Is.end();i++)
{
deal(*i);
}
sort(list.begin(),list.end());int ans=0,now=0;double last=-1;
for(lit i=list.begin();i!=list.end();i++)
{
if(i->x!=last){ans=max(ans,now);last=i->x;}
now+=i->a;
}
ans=max(ans,now);
return ans;
}
};
3：还是水题。。设dp(i,k)使从i点经过k条边出去的概率。。。然后直接dp就可以了。。
这个图是无环的。。我还以为是有环的准备解方程的说。。水啊。。
那么根据条件概率公式，答案就是dp (start,k)/sum{dp(all i,k)}。。
#include<vector>
#include<cstring>
#include<string>
using namespace std;
const int maxn=50;
class ParkAmusement
{
vector<string> map;
int n;
bool e(int x){return map[x][x]==’E’;}
bool p(int x){return map[x][x]==’P’;}
bool c(int x,int y){return map[x][y]==’1′;}
double dp[maxn][maxn];
bool save[maxn][maxn];
double pro(int pos,int len)
{
double&ans=dp[pos][len];
if(save[pos][len]) return ans;
save[pos][len]=true;
if(p(pos)) return ans=0;
if(e(pos)) return ans=(len==0?1:0);
if(len==0) return ans=0;
double sum=0;int num=0;
for(int i=0;i<n;i++)
if(c(pos,i))
{
sum+=pro(i,len-1);
num++;
}
if(num==0) return ans=0;
return ans=sum/num;
}
public:
double getProbability(vector<string> land,int start,int k)
{
map=land;n=map.size();
memset(save,0,sizeof(save));double p=pro(start,k);double sum=0;
for(int i=0;i<n;i++) sum+=pro(i,k);
return p/sum;
}
};
DIV2的题目好水的说。。但是DIV的题目第一题还好说。。第二题我就吴宇森了。。。

AATree真是太简单了。。比Treap写起来都爽。。我看了wiki上的AAtree介绍后。。写了个AATree。。
那个pdf版本在我的空间有发。。
http://ideone.com/YZ4Dftk0#

USACO的最新的月赛出来了。。本菜去被题虐了。。
我感觉第一题是将环拆成2份。。然后将每条线段。。如果跨越环的话，就只有一份。否则有两份。。然后去掉被包含的线段。。那么题目就变成了在这个2*C长 的大线段上取一些线段时其并集为线段切长度>=C。。那么就好办了。。维护两个指针扫描过去就可以了。。当左边界递增的时候右边界也是递增的。。
第二题好猥琐啊。。直接拆点构图然后bfs？似乎可以但是节点会有重合。。也就是说会有长度为0的边。。那么怎么半呢？我的办法是。。bfs不是维护一个 队列嘛。。我改成一个双端队列。。然后遇到为0的边加在头部，否则加在尾部。。就OK了。。这道题写的我脑子都大了。。。写了我3KB。。神牛一定有更简 单的办法。。我太菜了。。
第三题感觉最简单。。构造树的先序数列。。然后用一个线段树维护每个点到根节点的染色点的个数（就是有Cow的点的个数）。。然后那么一个点染色之后只影 响它的子孙的哪一段区间。。只要用标准的线段树就OK了。。
比赛嘛。。代码就不发了。。

       OK…我无论怎么搞都是TLE。。。这道题我是按离线和启发式合并的思想来做的。。
就是说在dfs的时候对每个点维护一个treap表示其中所有点的权值。。然后dfs的时候启发式合并。。就是把小的拆开加到大的里面去。。然后直接select就可以了。。
我用了Treap和启发式暴力拆合并的思想来搞这道题。。无论如何都悲剧。。
我都快疯了。。我一开始是用暴力指针的treap的。。后来自己写了个回收管理器。。没用。。又改用数组了。。照样TLE。。然后我又把树的结构有vector改成用数组的链表。。TLE。。然后我优化输入输出。。TLE。。。然后我改成前向星。。TLE。。然后我想到随机数可能很慢。。于是直接用随机打乱的1-n排列来作为key的值。。TLE。。
….然后我感觉treap不是随机的嘛。。就狂交拼RP。。交了N次。。快疯了。。然后有神牛告诉我插入和选K大改成的非递归的。。TLE。。然后他告诉我用SBT。。然后我直接撞墙了。。
还能有什么优化啊。。就不能用treap AC这道题么。。。
我去写写SBT了。。上次我写了个比treap还慢。。真想撞死。。
我好菜啊。。整天被题虐的。。一个下午搞的我内分泌都快失调了。。

这道题就是在一个方格矩阵中求出一个最大的空矩形。。
由于方格行列都《=1000.。。所以要使用o(nm)的算法。。
LRJ大神的学习指导上有讲。。
就是说一层层扫描过去。然后得出以该层为底个列能衍生多少。。
然后DP求出每列往左往右能延伸多少。。枚举每一个作为最高列。。更新答案。。是最优的了。。。
PS我写了个类。。感觉码代码手感不错。。
Code：

www.spoj.pl/problems/EXPRESS/
我看到这道题之后P思路也没有。。苦思冥想了半天。没想法。。于是就搁置了。。
到了半夜1点。。我突然反映过来。。用队列当结构有不同吗？直接倒过来推不久好了。。
首先根据逆波兰表达式构建表达式树。。然后先在队列里面放入树的根节点。。然后可以一步一步往后推。在我的程序中为了方便。。实现的队列是真正的队列倒过来。。
Code:



我在程序中使用了一个技巧就是说直接用一个指针来代替一个数组。。省了一半的内存。。增强了可读性。。。。。。