touch 使用感受

     最近我买了一个touch。。。我经过多天的钻研。。将其成功变成了一个pda(掌上电脑)
比如说
有wifi可以用safari上网。。可以用stanza在线下小说看。。比如九鼎记之类的。。。可以拼命玩游戏。。。。。。还可以用fileapp装书进去看。。pdf啊word啊ppt啊网页啊txt啊chm啊都可以看。。。
还能打代码编程(这点最NB..)。。只要装个编译器就可以了。。。
不过马上就要中考了。。。我得复习去了。。。

SGU 507

给一棵树。。每个叶子节点有一个权值,对每一个非叶子节点求出其子树中两两对中最小的绝对值差。。
dfs一下。。可以用一个平衡树维护信息,合并就可以启发式插入,并维护最小绝对值差就可以了。。。
加个分析吧。。看上去暴力合并可能会很慢。。但实际上可以证明是很快的。。
你看一个点如果每被插入一次,它所在的树的大小至少*2。。那么它就最多被插入logn次,总共最多也就是nlogn。。实际上还没有nlogn次的。。可以证明插入的是n量级的。。
那么每次插入是logn的。。总算法也就是nlogn的了。。
Code:
ideone.com/3PjCARDF

PKU 1338 Heap

就是说一个数的质因数只有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
杂七杂八的:

SPOJ 4487 GSS6

大意: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

SPOJ 4580 ABCDEF

给一个大小于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;
}

SPOJ 3273 ORDERSET

就是标准的平衡二叉数。。
有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;
}
}
}

sgu 187

就是说给你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();
}

Page 1 of 212