SGU 502

给你一个小于17位的数,改变它的排列让它被17整除。。。
直接搜索。。居然25ms就过了。。本来我还想写个状压DP的。。
Code:gedit太漂亮了。。直接发图了。。



呵呵。。拼的不错吧。。真是漂亮的东西啊。。
http://ftp.gnome.org/pub/gnome/binaries/win32/gedit/2.25/gedit
发个地址。。

SGU 499

这道题是给N个数。。都小于10^6次方,求出其中两两之间最大的最大公约数是多少。。
很显然可以暴力求。。不过那是N^2的。。注意到所有数都在10^6次方一下。。所以
可以吗枚举答案来检测。。就是说开一个数组,大小为10^6。。每个中记录其中在这个索引的数有多少个。。。那么可以很方便的检测出一个数的倍数有多少个。。只要>1就更新答案。。。
计算复杂度是10^6*log(10^6)的。。。
Code:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000000;
class solve
{
short Num[maxn+1];int M;
void init()
{
int n,x;scanf("%d",&n);memset(Num,0,sizeof(Num));M=0;
while(n–) scanf("%d",&x),Num[x]++,M=max(M,x);
}
bool check(int x)
{
int cnt=0;
for(int i=x;i<=M&&cnt<2;i+=x)
cnt+=Num[i];
return cnt>1;
}
int work()
{
for(int i=M;i;i–) if(check(i)) return printf("%dn",i);
}
public:
solve()
{
init();
work();
}
};
int main()
{
solve now;
}顺便发一下Gedit的图片。。代码漂亮死了。。享受啊。。

又小雪。。。

OK。我承认我标题抄了VAE的歌。。。

安吉下雪了。。。都是雪。。白花花的。。。。

OK。。照套路我可能要说雪树银花之类的了。。。

但我看到的,是肮脏的雪。。。

干净的不代一点杂质的雪。。千人踏万人踩的。。。比什么都脏。。看的我想哭。。。

也许终究是梦吧。。雪还在下。。雪下过就下过。。脏过就脏过。。终究是要融化的。。。

美丽的就要这么消逝么。。。受不了。。或者说压根就没什么美丽的。。。。

现在的人越来越来脱离悲剧了。。越来越虚无了。。或许是好事,也或许是坏事吧。。。

总觉得有些事看得太透也不好。。如果没那么多的什么。。或许人类可以活的更好。。

如果我们蠢一点的话。。。OK。。。我们是万物之灵。。是最NB的。。

好像回到那跟雪一样的年代里啊。。。。

平衡树。。

我在wiki上发现了N种平衡树。。不得不感叹数据结构的博大精深。。
AVL和SBT实际上思想上差不多。。
都是运用某种数值将树平衡起来。。
AVL是高度。。SBT是大小。。
在AVL中两棵子树高度不会差太多(从而保证大小不差太多)。。
SBT中大小不会差太多。。
甚至我感觉SBT就是简化版的AVL。。
因为其中左孩子大小不小于右边的两个孙子大小的规定
太像高度不差一了。。

Treap比较NB。。它利用了随机树是平衡的
所以用了一种tree+heap的方法动态产生随机树。。
但树高度就不怎么样了。。
但他是最好写的。。

红黑树是用节点的颜色来是树中任意两条路径长度不差2倍。。
所以也是平衡的。。不过总是让我感觉太精巧和复杂了。。
不知是怎么想出来的。。算法导论上有。。就不多说了。。

2-3树更诡异。。它跟AA树是同构的。。
他一个节点可以是普通的2节点。。就是两个孩子。。
也可以是3节点。。就是说3个孩子。。
一般的节点存一个值。比如是x。。
将子树分为<x和>x的。。
而3节点存两个值x,y。。
将子树分为<x,(x,y),>y三个部分。。
然后在插入的时候如果2节点变成3节点了。。没事。。
如果3节点变4节点了。。就分裂一下。。把中间那个提上去。。。。
2-3树高度是严格logn的。。不过3节点很多。。
查起来也差不多是2logn的。。。

2-3-4树。。就是说不但有2,3节点。。还有4节点。。搞死人的东西。。
跟2-3树差不多。。

splay。。我最喜欢的。。它主要就是每次访问到一个节点。。就把它转成根。。
算是最NB和自然的数据结构了。。不过就是太慢了。。
个人感觉是最好写的。。这家伙的长度一般是3-4*logn。。

红黑树有一个很BT的特点就是维护的时候最多旋转2次。。。所以stl就用这个了。。
而AA树是红黑树的一个变种。。规定左边的孩子不能为红色。。所以维护的时候可能转的
更多。。但似乎是AA树更快一点。。不过stl追求的是稳定。。

Scapegoat tree是让两个孩子的大小都小于a*父亲的大小。。
维护起来很诡异。。每次都是找一个最高的那个不满足的顶点。。
直接暴力重建成近完全2叉树。。均摊是logn的。。

SPOJ ORDERSET Treap 3273

上次我使用splay。。没有A掉这道题。。非常的不爽。。
这次使用treap。。总算亲自把它A了。。
题目就看上一个吧。。基本的平衡树。。。
据说如果随机数据的话。。
AVL和SBT差不多是1*logn
Splay是3~4*logn的。。
Treap是2~3*logn的。。
实际上这道题离散化一下。。然后用线段树也能A。。估计快很多。。
Code:
http://ideone.com/Fie69wNz

Page 7 of 7« First...34567