学会表达
正是面试之后才开始慢慢体会到一些东西学会了理解了还远远不够，要懂得表述你自己的观点，或者解释某个术语，某种技术又是另外一种能力（也说是另一种境界）。毕竟给一个完全不懂这门技术的人介绍这门技术需要相当的功底——传教抑或如此。由此看来自己先前学到的知识是多么单薄！所以趁现在有时间给自己安排一些复习计划是很有必要的。接下来一段时间试着用自己的认识把设计模式一一表述出来，且当旁边有一位不耐烦的倾听者吧
至于为什么选择这个是一位当时HR问的就是这个，顿时间没办法用自己语言组织好，更别说恰当的表达了。语无伦次的表述，整个给人的感觉就是大骗子，大忽悠 囧。事后就想：不管你的能力怎么样，但是正确地表述你知识，表达你的观点是必须的。不然想不水都不行= =|||说到这个又不得不对YOYO大人表示仰慕
sigh 人才啊...........
有道普及赛的郁闷
由于陪人吃饭晚了一点时间开始做题，一开题直接做A，B看都没看（汗！！据说是模拟题...）从开场到结束B一直都没看 囧！！
下面说说A题吧，实在是很不错的题目老实说...只是我太水了= =...开始想广搜试试，后来看看由于对称性可以考虑层次搜索：
我是一层层往里搜（层数最多4层，田形为边界条件，由于对称性，所以每一层也一定对称，所以每一层只有2^((n*2 - 2))的状态数，接着就是没搜一层判断是否 连通和满足井的条件。敲完就提交= =很自然的一个TLE..接着就想啊想，最后发现每一层的状态搜索有重复严重影响时间效率，所以想开个4×（2^(8*2 -2)）的二维数组记录状态，然后记忆化搜索。 然后写啊写就写到德国队第一个进球了= =（代码能力实在惭愧...
赛后和wzc交流，然后他发了一个他也很囧的标程给我，开始两个人都没搞懂如此简洁的代码= =，接着德国队又进球了，然后英格兰也进球了..这个时候对所谓标程有点感觉了，就是因为是对称关系 而且联通 那就一定存在一个分割线而且 井的位置一定是在划分线上 分割线确定状态也确定了，加上分割线本身是对称的 ，所以深搜分割线就解决问题了....确实是不错的题目！
然后问wzcB题做了没，结果他告诉我是土土的模拟题。感慨，感慨的是可能就模拟题自己可能没法在时间内做出来 sigh！
叹气之时看到英格兰又进球了 结果被S13裁判无视F××k！！！！！！！！！！！！！！
杯具的有道精彩的世界杯杯具的英格兰...
No RP no Answer ...Just do it？
一句话Coding能力太差了！ 别人三分钟的代码我要二十分钟 嗯 这是参加这次有道最大的体会！
然后就是排错能力 if （status == AC）while(RP<0){prin(Wrong Answer) ; RP++} 情何以堪？反省到底是将近两年没碰这个的原因还是向来就如此臭！？？
再者就是反应速度慢，一个算法至少比别人多想5分钟才能理清！ 可能做题少点缘故，更是能力问题
多少还是认清自己有多水的.. 这是个长期问题
但是对于这次参赛还是很开心的，从新回到了以前的专注度；也复习了常用算法，发现现在看这些多少感觉不一样了，可以思考更多问题并且有一个全新的认识...感触每次coding的紧张感 然后省略等等 = =...
说说近期打算就是：YM YOYO大人Coding能力 ！！然后拜师 ...大三了这种Coding能力实在不应该！
PS：第二轮 RP++ 不要倒数一百名
数据结构三
左偏树可能各个方面都是最优的，可能他的最大缺点是插入操作O(n)，但是综合并操作与代码难度考虑还是不错的选择
至于他的已知节点删除和变种没实现，待以后用的话再补上吧，觉得几乎没用处？（
不敢说XD...
/****************************************
* LeftHeap.h
* Describe: 可并优先队列——左偏树
* Created: 2010-5-27
* CopyRight 2010,Leek
*
******************************************/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef int Type;
typedef struct LNode
{
Type key;
int dis;
LNode *left;
LNode *right;
LNode (Type key)
{
dis = 0;
left = NULL;
right = NULL;
this->key = key;
}
}LNode;
typedef LNode *PLNode;
void Swap (int &a, int &b)
{
a ^= b, b ^= a, a ^= b;
}
void Swap (PLNode &a, PLNode &b)
{
PLNode tmp = a;
a = b, b = tmp;
}
PLNode LHeap_Merge (PLNode a,PLNode b)
{
if (a == NULL)
return b;
if (b == NULL)
return a;
if (a->key > b->key)
Swap (a->key,b->key);
a->right = LHeap_Merge (a->right, b);
if (a->left == NULL || a->right->dis > a->left->dis)
Swap (a->right,a->left);
if (a->right == NULL)
a->dis = 0;
else
a->dis = a->right->dis + 1;
return a;
}
PLNode LHeap_Build (queue<PLNode> &a)
{
PLNode tmp = a.front();
while (a.size() > 1)
{
a.pop();
tmp = LHeap_Merge (tmp,a.front());
a.push(tmp);
a.pop();
tmp = a.front();
}
return a.front();
}
PLNode LHeap_Insert (Type key,PLNode root)
{
PLNode tmp = new LNode(key);
return LHeap_Merge (tmp,root);
}
Type LHeap_Delete_Min (PLNode &root)
{
PLNode tmp = root;
root = LHeap_Merge (root->left, root->right);
Type top = tmp->key;
delete tmp;
return top;
}
觉得建树和并操作值得思考多少有点启发性吧
顺便贴上败者树的模板 今天复习结束看漫画去
/****************************************
* Loser.h
* Describe: 败者树
* Created: 2010-5-27
* CopyRight 2010,Leek
*
******************************************/
#include <iostream>
using namespace std;
const int N = 1 << 16; //N大于n，并为2的次方
const int n = 234;
typedef int Type;
Type f[N * 2];
Type a[n];
void BuildTree (int n, int f[2 * N])
//建树a存在f N-N+n
{
memcpy (f + N,a,sizeof (a[0]) *n);
for (int i = N,j = N + n - 1; i > 1;i >>= 1,j >>= 1)
{
for (int k = i; k < j;k += 2)
f[k >> 1] = f[k] > f[k + 1] ? f[k] : f[k + 1];
//求得是最大值，可改为最小值
if (!(j&1))
f[j >> 1] = f[j];
}
}
int findmax (int s, int t)
//查询s t中的最大 最小值
{
int r = f[s] >= f[t]? s: t;
for (int i = s,j = t; i < j; i >>= 1, j >>= 1)
{
if (!(i & 1) && i + 1 < j && f[i + 1] > f[r])
r = i + 1;
if ((j & 1) && j - 1 > i && f[j - 1] > f[r])
r = j - 1;
}
return f[r];
//以下程序可求a【s t】最大最小值的下标
while (r < N)
if (f[r] == f[r << 1])
r <<= 1;
else
if (f[r] == f[(r << 1) + 1])
r = (r << 1) + 1;
}
数据结构二
关于平衡二叉树只会AVL和傻X树：（ 由于AVL各方面都不如SBT 所以只整理SBT算了。
但是杯具的是我把以前整理的SBT和代码等Ctrl+A Shift+Delete了（
...
其中删除是最有技巧的好好结合平衡操作很精妙
/****************************************
* SBT.h
* Describe: SBT平衡二叉树
* Created: 2010-5-26
* CopyRight 2010,Leek
*
******************************************/
#include <iostream>
using namespace std;
typedef int Type;
// SBT存储结构
class SBTNode
{
public:
SBTNode *child[2];
SBTNode *parent;
Type key;
int size;
SBTNode (Type key,int size);
};
typedef SBTNode *SBTree;
enum {Left,Right=1};
SBTNode::SBTNode (Type key,int size)
{
this->key = key;
this->size = size;
child[Left] = child[Right] = parent = NULL;
}
inline void SBT_Rotate (SBTree &root, bool num)
{
//num == Left 右旋num == Right左旋
SBTNode *tmp = root->child[!num];
tmp->parent = root->parent;
if (tmp->child[num] != NULL)
tmp->child[num]->parent = root;
root->child[!num] = tmp->child[num];
tmp->child[num] = root;
tmp->size = root->size;
root->size = root->child[Left]->size + root->child[Right]->size + Right;
root = tmp;
}
void SBT_Maintain (SBTree &root, bool num)
{
//退化版本
if (root->child[num]->child[num]->size > root->child[!num]->size)
SBT_Rotate (root, !num);
}
void SBT_Insert (SBTree &root, SBTNode *x)
{
if (root == NULL)
root = x;
else
{
root->size++;
x->parent = root;
SBT_Insert (root->child[x->key > root->key], x);
SBT_Maintain (root, x->key > root->key);
}
}
SBTNode *SBT_Search (SBTree &root,Type key)
{
return root == NULL || root->key == key? root: SBT_Search (root->child[key > root->key], key);
}
SBTNode *SBT_Delete (SBTree &root, Type key)
{
if (root == NULL)
return NULL;
root->size--;
if (root->key == key || root->child[key > root->key] == NULL)
{
SBTNode *tmp;
if (root->child[Left] == NULL || root->child[Right] ==NULL)
{
tmp = root;
root = root->child[root->child[Left] == NULL];
if (root != NULL)
root->parent = tmp->parent;
}
else
{
tmp = SBT_Delete (root->child[Right], key - Right);
root->key = tmp->key;
}
return tmp;
}
else
return SBT_Delete (root->child[key > root->key], key);
}
SBTNode *SBT_Pred(SBTree root, Type key)
{
if (root == NULL)
return NULL;
if(key <= root->key)
return SBT_Pred(root->child[Left],key);
else
{
SBTNode *tmp=SBT_Pred(root->child[Right],key);
return tmp != NULL?tmp:root;
}
}
SBTNode *SBT_Succ (SBTree &root,Type key)
{
if (root == NULL)
return NULL;
if (key >= root->key)
return SBT_Succ(root->child[Right],key);
SBTNode *tmp = SBT_Succ(root->child[Left], key);
return tmp != NULL? tmp:root;
}
SBTNode *SBT_Select(SBTree root, int i)
{
int r = root->child[Left]->size+Right;
if (i == r)
return root;
else
return SBT_Select(root->child[i>r],i>r?i-r:i);
}
int SBT_Rank(SBTree root, Type key)
{
if (root == NULL)
return Left;
if (root->key == key)
return root->child[Left]->size+Right;
else
if(key < root->key)
return SBT_Rank(root->child[Left],key);
else
{
int r = SBT_Rank(root->child[Right],key);
return r == Left? Left: r + root->child[Left]->size + Right;
}
}
等有时间改成模板实现吧
第一次应聘实习 | 排列与阶乘进制
昨天去ND面试 （车上收到有道短信 说下午视频答疑 舅舅的估计也没什么问题问的就算了 ，主考官直接问我什么时候有时间过去 （囧。然后说暑假吧，直接被他否决了 ，说是不能那么晚，现在就得去，平时没时间可以请假一个星期有到三四天就行了...就这样默默地答应了。之后回来打电话给我说明天要过去签协议，补贴方面800保障，出勤好的话每个月加80（可是网上说是1100，这里怎么变了呢 ，他解释什么税收管理费等（= =不是2k以上才要税收吗，显然地有猫腻...
于是乎要我考虑考虑...被人坑的感觉自然不爽加上路途漫漫（温泉路口
所以今天一大早打电话过去说不去了 酱紫第一次很山寨的笔试面试经历结束了...
回来继续复习和整理算法。发现模板的《排列与阶乘进制》有猫腻，大牛的代码写的很玄乎看不出是不是真的错了（
代码不能多几个注释嘛，然后按自己的想法改动了下VC6上跑了一下果然假想没错（XD，期间还问yayamao模板是不是有问题 回答：没用过 （
大牛风范...
现在就说说Coding吧，之前排列与顺序等问题直接都是土土地写地，看了阶乘进制赞叹Knuth大师的伟大（... 然后再看逆过程无比纠结（反正死活看不懂喽，然后偷偷暗想他Coding有问题吧，然后就觉得越看越有问题（= = 鄙视一下自己，经过简单数据验证还好真的是模板的问题（XD
原先的逆过程：
void back(__int64 perm)
{
int i, j, k, p[N + 1] = {0},mark[N + 1] = {0};
i = 1;
while (perm)
{
p[i] = perm % (i + 1);
perm /= ++i;
}
for (i = n-1; i >= 1; --i)
{
j = n,k = 0;
while (k <= p[i])
{
if (!mark[j++])
k++;
}
j++;
a[j] = i + 1;
mark[j] = 1;
}
j = 1;
while (mark[j])
j++;
a[j] = 1;
}
修改后代码：
void back(__int64 perm)
{
int i, j, k, p[N + 1] = {0},mark[N + 1] = {0};
i = 1;
while (perm)
{
p[i] = perm % (i + 1);
perm /= ++i;
}
for (i = n-1; i >= 1; --i)
{
j = 1,k = 0;
while (k <= p[i])
{
if (!mark[j++])
k++;
}
j--;
a[n-i] = j;
mark[j] = 1;
}
j = 1;
while (mark[j])
j++;
a[N] = j;
}
顺便贴上转化为阶乘进制代码：
int KnuthPEncode()
{
int i,j;
int place = n,e = 0;
for (i = 1; i <= n; ++i)
{
int t = a[i];
e *= place--;
for (j = i+1; j <= n ; ++j)
a[j] < t && e++;
}
return e;
}
数据结构一
由于应聘网龙实习生耽搁了，先把整理好的基础部分贴出来
据说ND招实习生就是招廉价劳动力？随便吧，反正不打算能做成怎么样可以向大牛们学点东西才是关键。在想要是实习住宿问题怎么解决？YOYO大人赞助吧？嗯..
不扯淡了直接晒代码
//*************二叉堆相关操作*********************
void Sink（int p）
{
int q = p << 1, tmp = heap[p];
while (q <= hs)
{
if (q < hs && heap[q + 1] < heap[q])
++q;
if (heap[p] < heap[q])
break;
heap[q] = heap[p];
p = q;
q <<= 1;
}
heap[p] = tmp;
}
int Delete_MinI()
{
int r = heap[1];
heap[1] = heap[hs--];
Sink(1);
return r;
}
int Delete_MinII()
{
heap[1] ^= heap[hs], heap[hs] ^= heap[1], heap[1] ^= heap[hs--];
Sink(1);
return heap[hs + 1];
}
void Swim(int p)
{
int q = p >> 1, tmp = heap[p];
while(q && tmp < heap[q])
{
heap[p] = heap[q];
p = q;
q >>= 1;
}
heap[p] = tmp;
}
void Insert(int p)
{
heap[++hs] = p;
Swim(hs);
}
void Build()
{
for (int i = hs / 2; i ; --i)
Sink(i);
}
/**********并查集************************/
void Make_Set(int x)
{
rank[x] = 0;
p[x] = x;
}
int Find_Set(int x)
{
int px = x, tmp;
while (px != p[px])
px = p[px];
while (x != px)
{
tmp = p[x];
p[x] = px;
x = tmp;
}
return px;
}
void Union_Set(int a,int b)
{
a = Find_Set(a);
b = Find_Set(b);
if (rank[a] < rank[b])
{
p[a] = b;
}
else
{
p[b] = a;
if (rank[a] == rank[b])
++rank[a];
}
}
/************哈希表********************/
//质数1811 5087 10657 50503 100109 500119
int hash[Size * Size][2];
int first[Size][Size];
int next[Size * Size];
int entry = 1;
/*********************/
// 值太大二维存储 ps：从没用过 似乎没必要?
/*********************/
int Insert_Find_Hash()
{
long long a, b;
a = 前半部分的值（可按位存储）;b = 后半部分;
c = a % Size; d = b % Size;
e = first[c][d];
while (e != 0)
{
if (hash[e][0] == a && hash[e][1] == b)
return 0;
e = next[e];
}
hash[entry][0] = a;
hash[entry][1] = b;
next[entry] = first[c][d];
first[c][d] = entry;
entry ++;
return 1;
}
bool Insert_Find_Hash(Type x)
{
unsigned int key;
key = Hash(x);
p = first[key];
while (p)
{
if (hash[p] == x)
return false;
p = next[p];
}
hash[entry] = key;
next[entry] = first[key];
first[key] = entry;
entry ++;
return true;
}
//字符串用的Hash函数
unsigned int SDBMHash(char *str)
{
unsigned int hash = 0;
unsigned int len = 0;
while (*str)
{
// hash = 65599*hash + (*str++);
hash = (*str++) + (hash << 6) + (hash << 16) - hash;
++len;
}
hash = (len) + (hash << 6) + (hash << 16) - hash;
return (hash & 0x7FFFFFFF);
}
/**********Good to the last code************/
下期：平衡二叉树
准备有道 重拾那段往事？
好好准备最后一次大学里重大的Coding
有点乱，不知道是天气的原因还是心情，有些许激动，也有些许躁动。只希望好好整理Code可以抚平一些躁动 兴许往事？
while(RP && Passion)
{
RP--;
Coding();
++Day;
//...我的RP早已负溢出才得以我继续..
}
