就是说一个数的质因数只有2和3和5的数叫ugly数。。让你求第N个ugly数，N<=1500。。。
注意到第一个是1。。然后用一个最小堆维护当前ugly数集合。。每次取出最小的。并把它的2、3、5倍放入堆中就OK了。。注意要去重。。。
在家复习的累死。。做到编程题放松放松。。。
代码。。
ideone.com/HbO4lIIm

做了很多数据结构题。。以前找题目的时候老师翻遍OJ很痛苦。。以做个合集方便大家啦解法自然会有很多。。我就按我的做法分了。。代码有些我放在idone上了。。一个很好的网站。。代码很漂亮 。。。
几个月过去了。。我再次更新这篇文章。。。
树状数组：
[SDOI2009]HH的项链 用树状数组帮助离线算法的处理。。
平衡树：
Splay：
SPOJ GSS6：http://hi.baidu.com/wjbzbmr/blog/item/de1a10c9b3608cf653664fed.html
动态数列维护的问题
SPOJ QMAX3VN：hi.baidu.com/wjbzbmr/blog/item/de1a10c9b3608cf653664fed.html
动态数列维护
SPOJ ORDERSET：hi.baidu.com/wjbzbmr/blog/item/5574dbefee16b1dfb21cb150.html
基本平衡树操作。。splay太慢过不掉。。。
sgu 187：hi.baidu.com/wjbzbmr/blog/item/aadf04c8bbc59e8dc91768bf.html
动态维护反转。。。
Splay的代码：hi.baidu.com/wjbzbmr/blog/item/72dfd036fd160545251f148e.html
基本的splay。。。
Treap:
SPOJ ORDERSET hi.baidu.com/wjbzbmr/blog/item/5e083684dd53ee3566096e76.html
用Treap也A掉了。。但我自己写的SBT太慢。。没A掉。。
线段树：
POJ3667：hi.baidu.com/wjbzbmr/blog/item/26c1dd0abcc82a9e0b7b82f9.html
很经典的懒标记题目了。。
SPOJ GSS5：hi.baidu.com/wjbzbmr/blog/item/a7f4a5996fd888bfc8eaf4d5.html
普通最大连续和的扩展。。分别限定开始和结束位置
SPOJ GSS1、3：http://hi.baidu.com/wjbzbmr/blog/item/6690a428485cac325343c1aa.html
最经典的最大连续和。。
[Scoi2010]序列操作 复杂的线段树问题，降低Coding复杂度是重点。。。
经典的题目了。。
树：
POJ 1984-1987：http://hi.baidu.com/wjbzbmr/blog/item/3dd10211e494368a6438dbdc.html
1984：并查集
1985：一颗树中距离最远的两点，经典算法。。。
1986：树中两点的距离。。直接Tarjan。。
1987：基于边的分治。。很难饿。。
并查集：
堆，可合并堆：
POJ 1338:hi.baidu.com/wjbzbmr/blog/item/d11f1cb3d9af3e5f082302ee.html
比较有意思的堆题目（也可以不用堆吧。。暴力生成然后再排序应该也可以。。）
块状XX(链表，数组)：
Zju2112 Dynamic Rankings 区间K大值，要支持修改

Hash：
SPOJ ABCDEF：http://hi.baidu.com/wjbzbmr/blog/item/5aa21437dd53dd1a91ef3938.html
杂七杂八的：

大意：NOI维护数列的简化版。。
我什么时候把维护数列也A掉就爽了。。。
4个操作
1:insert(p,x) 在第p-1个数之后插入一个数x
2:delete(p) 删除第p个数
3:max(l,r) 输出l到r之间的最大连续和
4:replace(p,x) 将第p个数换成x。。
我写了两个程序。。一个块状数组，一个splay。。
块状数组妈妈的太慢了。。。
insert直接把第p-1个数转成根，第p个数转到根下面，那么直接把这个数放到第p个数的左子树就行了。。
delete把第p个数找到。。然后一直转到没有左儿子。。再删除它。。
max只要把第l-1个数转成根，第r+1个数转到根下面。。就OK了。。
replace跟insert基本一样。。。
转好了之后，别忘了splay哦！
还有Null的参数设置，也是需要考虑的。。。
splay太NB了。。。
俄。也不是，维护数列里面没要求删除的。。不过也差不多。。
12.4s。。。感觉原来发代码太占空间了。。放到ideone上面吧。。很漂亮。。
Code:http://ideone.com/aoAEParp

给一个大小于100的集合S
求满足下两式的六元组个数。。

d！＝0。。。
化一下，a*b+c=(e+f)*d。。
现用Hash把所有efd枚举一下，Hash存下结果。。
然后枚举abc就OK了。。
O(n^3)
这提示我一般的找个数的题目，如果适当Hash都可以降低复杂度。。。
Code:
#include<cstdio>
#include<cstring>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int size=100007;
class Hash
{
struct node
{
int x,s;
node*next;
}*H[size],Data[1000000],*Now;
node* new_node(int x,int s,node*n)
{
Now->x=x;Now->s=s;Now->next=n;
return Now++;
}
int Code(int x)
{
if(x<0)x=-x;
return x%size;
}
public:
Hash()
{
Now=Data;
memset(H,0,sizeof(H));
}
void ins(int x)
{
int h=Code(x);
for(node*p=H[h];p;p=p->next)
if(p->x==x)
{p->s++;return;}
node*q=new_node(x,1,H[h]);
H[h]=q;
}
int find(int x)
{
int h=Code(x);
for(node*p=H[h];p;p=p->next)
if(p->x==x)
return p->s;
return 0;
}
};
class solve
{
int n,A[100];
void init()
{
scanf("%d",&n);
REP(i,n)
scanf("%d",A+i);
}
void work()
{
Hash H;
REP(i,n)REP(j,n)REP(k,n)if(A[k])
H.ins((A[i]+A[j])*A[k]);
int ans=0;
REP(i,n)REP(j,n)REP(k,n)
ans+=H.find(A[i]*A[j]+A[k]);
printf("%dn",ans);
}
public:
solve()
{
init();
work();
}
};
int main()
{
solve now;
}

这道题是说。一列数，两个操作，
(1):insert(p,x)在第p-1个数后插入数x
(2):max(l,r)输出第l个数到第r个数中最大的数
直接上splay。。splay太厉害了。。
Code:ideone.com/WDlkwwnX

就是标准的平衡二叉数。。
有insert,delete,rank,select四个操作。。
我用splay就是超时。。。妈呀。。最后用别人的SBT过掉了。。
Code:
#include<cstdio>
using namespace std;
const int inf=~0U>>1;
class splay
{
struct node
{
int k,s;
bool d;
node*c[2],*p;
void sc(node*_c,bool d)
{c[d]=_c;_c->p=this;_c->d=d;}
}*root,*Null,*Now,*stack[100000],Data[200000],*tmp;
int top;
typedef node* Node;
Node new_node(int k)
{
if(top) tmp=stack[–top];
else tmp=Now++;
tmp->k=k;tmp->s=1;
tmp->c[0]=tmp->c[1]=Null;
return tmp;
}
void del_node(Node p)
{
stack[top++]=p;
}
void upd(Node t)
{
t->s=t->c[0]->s+t->c[1]->s+1;
}
void rot(Node t)
{
node*p=t->p;bool d=t->d;
p->sc(t->c[!d],d);
p->p->sc(t,p->d);
t->sc(p,!d);
upd(p);upd(t);
}
void spl(Node x,Node f)
{
while(x->p!=f)
{
if(x->p->p==f) rot(x);
else x->d==x->p->d?( rot(x->p),rot(x) ):( rot(x),rot(x) );
}
}
Node select(int k)
{
int r;
for(Node t=root->c[1];;)
{
r=t->c[0]->s;
if(r==k) return t;
t=t->c[k>r];
if(k>r) k-=r+1;
}
}
Node ser(Node t,int k)
{
for(;t!=Null&&t->k!=k;t=t->c[k>t->k]);
return t;
}
Node insert(int k)
{
bool d;Node t=root;
for(;t->k!=k;)
{
d=k>t->k;
if(t->c[d]==Null)
{
Node p=new_node(k);
t->sc(p,d);
}
t=t->c[d];
}
return t;
}
int rank(int k)
{
int ans=0;
for(Node t=root->c[1];t!=Null;)
{
if(k>t->k) ans+=1+t->c[0]->s;
t=t->c[k>t->k];
}
return ans;
}
public:
splay()
{
top=0;Now=Data;
Null=new_node(0);Null->s=0;
root=new_node(-inf);root->p=root;
}
void ins(int x)
{
Node p=insert(x);
spl(p,root);
}
int sel(int x)
{
if(x>=root->c[1]->s) return inf;
Node p=select(x);
return p->k;
}
int ran(int x)
{
return rank(x);
}
void del(int k)
{
Node tmp=ser(root->c[1],k);if(tmp==Null) return;
while(tmp->c[0]!=Null)
rot(tmp->c[0]);
if(tmp->c[1]==Null)
{
tmp->p->c[tmp->d]=Null;
tmp->p->s–;
spl(tmp->p,root);
del_node(tmp);
return;
}
tmp->p->sc(tmp->c[1],tmp->d);
spl(tmp->c[1],root);
del_node(tmp);
}
}*sp;
int main()
{
int n,t,a;char c;sp=new splay;scanf("%dn",&n);char C[1000];
for(int i=0;i<n;i++)
{
scanf("%c %dn",&c,&t);
switch(c)
{
case ‘I’:sp->ins(t);break;
case ‘D’:sp->del(t);break;
case ‘K’:a=sp->sel(t-1);
if(a==inf) puts("invalid");
else printf("%dn",a);break;
case ‘C’:printf("%dn",sp->ran(t));break;
}
}
}

就是说给你1到n一排数每次把从l到r的数反过来。。让你输出最后的那列数。。
动态表。。明显用splay。。最近刚学了splay，爽阿。。
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int inf=~0U>>1;
class splay
{
int n;
struct node
{
int k,s;
bool d,rev;
node*c[2],*p;
node(){c[0]=c[1]=p=0;}
void sc(node*_c,bool d)
{c[d]=_c;_c->p=this;_c->d=d;}
}*root,*Null,*Now,Data[130100];
typedef node* Node;
Node new_node(int k)
{
Now->c[0]=Now->c[1]=Null;
Now->rev=false;Now->s=1;
Now->k=k;return Now++;
}
void rev(Node t)
{
if(t==Null) return;
t->rev^=1;
swap(t->c[0],t->c[1]);
t->c[0]->d=0;
t->c[1]->d=1;
}
void pus(Node t)
{
if(t->rev)
rev(t->c[0]),rev(t->c[1]);
t->rev=false;
}
void upd(Node t)
{
t->s=t->c[0]->s+t->c[1]->s+1;
}
void rot(Node t)
{
Node p=t->p;
pus(p);pus(t);bool d=t->d;
p->sc(t->c[!d],d);
p->p->sc(t,p->d);
t->sc(p,!d);
upd(p);upd(t);
if(p==root) root=t;
}
void spl(Node x,Node f)
{
for(pus(x);x->p!=f;)
{
if(x->p->p==f) rot(x);
else x->d==x->p->d?( rot(x->p),rot(x) ):( rot(x),rot(x) );
}
}
Node sel(int k)
{
int r;
for(Node t=root;;)
{
pus(t);
r=t->c[0]->s;
if(r==k) return t;
t=t->c[k>r];
if(k>r) k-=r+1;
}
}
void print(Node t)
{
if(t==Null||!t) return;
pus(t);
print(t->c[0]);
if(t->k)printf("%d ",t->k),fflush(stdout);
print(t->c[1]);
}
public:
void out()
{
print(root);
}
splay(int n):n(n)
{
Now=Data;
Null=new node;Null->s=0;
root=new_node(0);root->p=Null;
Node p,q=root;
for(int i=1;i<=n;i++)
{
p=new_node(i);
q->sc(p,1);
q=p;
}
Node last=new_node(0);
q->sc(last,1);
spl(last,Null);
}
void reverse(int l,int r)
{
Node x,y;
x=sel(l-1);
spl(x,Null);
y=sel(r+1);
spl(y,root);
rev(y->c[0]);
}
}*sp;
int main()
{
int n,m,l,r;cin>>n>>m;
sp=new splay(n);
while(m–)
{
scanf("%d %d",&l,&r);
sp->reverse(l,r);
}
sp->out();
}

PKU 2008 Individual Practice 7
  3666 Problem A Making the Grade 大意。。就是用最小的代价把一群数变成单调的。。变化一个数的代价是变化的绝对值。。
首先很明确是可以离散的，就是说如果一个数不这N个数中，也没有必要把其他的数变成这个数。。
所以实际上有用的数只有N个。。设这些数为A1..N
那么设D[i][j]为1..i,第i个数为Aj让所有数递增的最小代价。。
那么D[i][j]=|Ai-Aj|+min(D[i-1][k])(1<=k<=j)
那么答案就是min(D[N][1..N])。。
实际上这是BOI的原题。。当时N<=100000，所以N^2只能见鬼去，
但这个N只<=2000。。可以过。。。
有一个用左偏树的NLogN的算法。。但是太麻烦了。。
Code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<utility>
#include<cstdlib>
#include<string>
#include<cmath>
using namespace std;
const int maxn=2010,inf=~0U>>1;
int A[maxn],B[maxn],DP[maxn],n;
inline int cost(int i,int j){return i>j?(i-j):(j-i);}
int solve()
{
for(int i=0;i<n;i++)
DP[i]=cost(B[i],A[0]);
int tmp;
for(int i=1;i<n;i++)
{
tmp=inf;
for(int j=0;j<n;j++)
{
tmp=min(tmp,DP[j]);
DP[j]=tmp+cost(B[j],A[i]);
}
}
return *min_element(DP,DP+n);
}
int main()
{
freopen("in","r",stdin);
cin>>n;for(int i=0;i<n;i++) scanf("%d",A+i),B[i]=A[i];
sort(B,B+n);int ans=solve();
for(int l=0,r=n-1;l<r;l++,r–)
swap(A[l],A[r]);
ans=min(ans,solve());
cout<<ans<<endl;
}   3667 Problem B Hotel
用一个线段树维护就OK了。。需要使用懒标记。。
Code：
#include<iostream>
 
#include<algorithm>
 
#include<cstring>
 
#include<utility>
 
#include<cstdio>
 
#define Renew(x,c) x=max(x,c)
 
using namespace std;
 
struct Tree
 
{
 
bool sign,e;
 
int max,Lmax,Rmax,size,l,r;
 
Tree*Lch,*Rch;
 
}A[150000],*now,*root;
 
Tree* NewNode(int l,int r)
 
{
 
now->sign=false;
 
now->max=now->Lmax=now->Rmax=r-l+1;
 
now->size=r-l+1;
 
now->l=l;
 
now->r=r;
 
return now++;
 
}
 
void Update(Tree*Fa)
 
{
 
if(Fa->Lch->max==Fa->Lch->size)
 
Fa->Lmax=Fa->Lch->size+Fa->Rch->Lmax;
 
else
 
Fa->Lmax=Fa->Lch->Lmax;
 
if(Fa->Rch->max==Fa->Rch->size)
 
Fa->Rmax=Fa->Rch->size+Fa->Lch->Rmax;
 
else
 
Fa->Rmax=Fa->Rch->Rmax;
 
Fa->max=Fa->Lch->Rmax+Fa->Rch->Lmax;
 
Renew(Fa->max,max(Fa->Lch->max,Fa->Rch->max));
 
}
 
Tree* Build(int l,int r)
 
{
 
if(l==r)return NewNode(l,r);
 
int mid=(l+r)/2;
 
Tree* T=NewNode(l,r);
 
T->Lch=Build(l,mid);
 
T->Rch=Build(mid+1,r);
 
return T;
 
}
 
void Set(Tree*T,bool e)
 
{
 
T->sign=true;
 
T->e=e;
 
T->Lmax=T->Rmax=T->max=e?T->size:0;
 
}
 
void Push(Tree*T)
 
{
 
if(T->sign)
 
{
 
if(T->size>1)
 
{
 
Set(T->Lch,T->e);
 
Set(T->Rch,T->e);
 
}
 
T->sign=false;
 
}
 
}
 
int l,r;
 
void set(Tree*T,bool e)
 
{
 
if(T->l>=l and T->r<=r)
 
{
 
Set(T,e);
 
return;
 
}
 
int mid=T->Lch->r;
 
Push(T);
 
if(mid>=l)
 
set(T->Lch,e);
 
if(r>mid)
 
set(T->Rch,e);
 
Update(T);
 
}
 
int len;
 
int Put(Tree*T)
 
{
 
Push(T);
 
if(T->Lch->max>=len)
 
return Put(T->Lch);
 
if(T->Lch->Rmax+T->Rch->Lmax>=len)
 
return T->Lch->r-T->Lch->Rmax+1;
 
if(T->Rch->max>=len)
 
return Put(T->Rch);
 
return 0;
 
}
 
void In(int D)
 
{
 
len=D;
 
int a=Put(root);
 
printf("%dn",a);
 
if(a)
 
l=a,r=a+D-1,set(root,false);
 
}
 
void Out(int l,int r)
 
{
 
::l=l;::r=r;
 
set(root,true);
 
}
 
int n,m;
 
void init()
 
{
 
cin>>n>>m;
 
now=A;
 
root=Build(1,n);
 
}
 
void work()
 
{
 
int k,l,d;
 
while(m–)
 
{
 
scanf("%d",&k);
 
if(k==1)
 
scanf("%d",&d),In(d);
 
else
 
scanf("%d %d",&l,&d),Out(l,l+d-1);
 
}
 
}
 
int main()
 
{
 
init();
 
work();
 
}   3668 Problem C Game of Lines 就是所有直线中不同斜率的个数。。直接set就可以了。。
Code:
#include<iostream>
#include<cstdio>
#include<utility>
#include<set>
using namespace std;
typedef pair<int,int> pi;
int n;
pi A[300];
int gcd(int a,int b)
{return b?gcd(b,a%b):a;}
pi operator-(pi x,pi y)
{
return pi(x.first-y.first,x.second-y.second);
}
int main()
{
freopen("in","r",stdin);
cin>>n;
for(int i=0;i<n;i++)
cin>>A[i].first>>A[i].second;
set<pi> S;pi get;
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
{
get=A[j]-A[i];
int d=gcd(get.first,get.second);
get.first/=d;
get.second/=d;
S.insert(get);
}
cout<<S.size()<<endl;
}   3669 Problem D Meteor Shower BFS…
Code:
#include<iostream>
#include<cstdio>
#include<utility>
#include<queue>
#define Renew(x,c) x=min(x,c)
using namespace std;
typedef pair<int,int> pi;
const int maxn=310,inf=~0U>>1;
int T[maxn][maxn],D[maxn][maxn];
queue<pi> Q;
inline bool inarea(int x,int y)
{return x>=0 and y>=0 and x<maxn and y<maxn;}
int main()
{
freopen("in","r",stdin);
int m,x,y,t;cin>>m;
for(int i=0;i<maxn;i++)
for(int j=0;j<maxn;j++)
T[i][j]=D[i][j]=inf;
const int di[]={-1,0,1,0},dj[]={0,1,0,-1};
while(m–)
{
scanf("%d %d %d",&x,&y,&t);
Renew(T[x][y],t);
for(int ii,jj,d=0;d<4;d++)
{
ii=x+di[d];jj=y+dj[d];
if(inarea(ii,jj))
Renew(T[ii][jj],t);
}
}
D[0][0]=0;Q.push(pi(0,0));int c;
while(Q.size())
{
pi t=Q.front();Q.pop();c=D[t.first][t.second];
if(T[t.first][t.second]==inf)
{
cout<<c<<endl;
return 0;
}
for(int ii,jj,d=0;d<4;d++)
{
ii=t.first+di[d];jj=t.second+dj[d];
if(inarea(ii,jj) and D[ii][jj]==inf and T[ii][jj]>c+1)
D[ii][jj]=c+1,Q.push(pi(ii,jj));
}
}
cout<<-1<<endl;
}

阿阿阿阿阿阿阿阿。。。总算做出来了。。错误这一个那一个的，调试的快疯了。。
大意：
一棵带权树，有两种询问：
（1）：Dist（a，b）询问a到b的距离
（2）：Kth（a，b，k）询问a到b的路径上的第一k个点。。
分析：
用传统的RMQ+对每个节点记录第2^i个(i=0、1、2…)祖先的在线做法，
时间是NlogN。。比较慢。。。
我的办法是首先Tarjan求出所有询问中a和b的lca。。然后dist可以直接算，
kth就需要看第k个节点是在a的祖先还是b的祖先，可以归结为求一个节点的第几个祖先的问题，
可以再dfs一遍。。用一个deque储存根到当前节点的路径。就可以离线KO了。。。
不过在码代码的时候我精神失常。。错误一箩筐。。。
Code：http://ideone.com/p9PZ8PvR

赞赞阿。。
Splay绝对是最完美的平衡树。。除了时间比较慢。。其他绝对是最NB的。。
想出这玩意的人绝对是天才中的天才。。。
写了个Code。。贴一下。。
#include<cstdio>
#include<iostream>
using namespace std;
const int inf=~0U>>1;
class splay
{
struct node
{
int k,s;//k是值,s是子树大小
bool d;//d是该节点是父亲的那种节点
node*c[2],*p;//c[0]、c[1]分别是左，右孩子，p是父亲
node(int _k,node*_c):k(_k),s(1){c[0]=c[1]=_c;}
void sc(node*_c,bool d) //sc means set child
{c[d]=_c;_c->p=this;_c->d=d;}
}*root,*Null,*Now;
typedef node* Node;
void upd(Node t)
{
t->s=t->c[0]->s+t->c[1]->s+1;
}
void rot(Node t)
{
node*p=t->p;bool d=t->d;
p->sc(t->c[!d],d);
p->p->sc(t,p->d);
t->sc(p,!d);
upd(p);upd(t);
}
void spl(Node x,Node f)
{
while(x->p!=f)
{
if(x->p->p==f) rot(x);
else x->d==x->p->d?( rot(x->p),rot(x) ):( rot(x),rot(x) );
}
}
Node select(Node t,int k)
{
int r;
for(;;)
{
r=t->c[0]->s;
if(r==k) return t;
t=t->c[k>r];
if(k>r) k-=r+1;
}
}
Node insert(Node t,int k)
{
bool d=k>t->k;
if(t->c[d]==Null)
{
Node p=new node(k,Null);
t->sc(p,d);
return p;
}
return insert(t->c[d],k);
}
public:
splay()
{
Null=new node(0,0);Null->s=0;
root=new node(-inf,Null);
}
void ins(int x)
{
Node p=insert(root,x);
spl(p,root);
}
int sel(int x)
{
Node p=select(root->c[1],x);
spl(p,root);
return p->k;
}
}*sp;
int main()
{
freopen("in","r",stdin);
int n;int k,a;sp=new splay;cin>>n;
for(int i=0;i<n;i++)
{
scanf("%d %d",&k,&a);
if(k==0)
sp->ins(a);
else
printf("%dn",sp->sel(a));
}
}