H-1B renew through drop-box 2016

第一次更新H-1B签注。走的是广州领事馆递签。12月11号递给中信，12月21号取回，耗时8个工作日。

选择递签是因为当时在广州已经预约不到面签了，而搜了一些递签经验贴后，判断递签并不会比面签风险高。

递签有一定条件，具体要求在：http://www.ustraveldocs.com/cn_zh/cn-niv-visarenew.asp。

递签缴费同样是在 https://cgifederal.secure.force.com/，$190。递签申请提交完后有一份 “Drop Box Confirmation Letter”，需要打印出来提交的。

准备的材料有：

Drop Box Confirmation Letter
DS160 Confirmation
符合要求的照片
简历
I-797 复印件（有人交原件没有被退还，但我这次是交的所有文件都有退回）
公司开具的 support letter
近期3份 pay statement
护照原件

中信银行是周日也可以收申请的，但是周一才会递给大使馆。

递上去后可以在 https://ceac.state.gov/CEACStatTracker/Status.aspx?eQs=WwjqOlbeRYzCYubaSQI+RA== 查询签证状态。我的情况大概是15号开始是 Administrative processing，直到16号下午 Issued。然后就是在 https://cgifederal.secure.force.com/ 查询护照状态。19号开始是 Passport has been received from the consular section，直到21号早上查变成 Ready for pick up，同时收到邮件。这里我并没有选择快递到家，而是自己到中信取。

整个过程还是比较顺利的。

可以去巴厘岛落地签玩了~~~ ;p

面试题整理

发表回复

各家的面试基本上都告一段落了，整理下自己觉得有意思的题目吧。

1. 一个大小为n的数组，元素有正有负，求将所有负数放在正数前面的稳定的算法。

解：考虑归并排序的思路，每次将两个子段合并整理成一长段的过程，即为[负][正][负][正]，转换成[负][正]的形式。时间复杂度是O(NlgN)的。

2. 有n个囚犯排成一列，每个人头上有帽子，帽子是黑色或者白色。每个人只能看到自己前面的人的帽子，看不到自己和自己后面人的帽子。从后往前，每个人需要报出自己帽子的颜色，如果错了就被处决，否则就被释放。前面的人能听到后面的人报的是黑还是白。求一个确定的策略，使得尽可能多的囚犯被释放。

解：最优解只牺牲最后面的一个人。把黑帽子视作0，把白帽子视作1，每个人求他前面所有人帽子颜色值的异或值。最后面的人报出异或值后，从倒数第二个人开始，每个人都能根据他后面人的帽子颜色来计算出自己头上帽子是什么颜色。

3. 有100个囚徒，每人在不同的房间。另有一个大厅，大厅里有一盏灯，初始是关的。每天会有一个囚徒被从房间叫出到大厅，并能开、关灯。也即每个囚徒能知道的信息包括：1. 当前是第几天；2. 如果被叫到大厅了，灯是开着的还是关着的。每个囚犯到大厅时，都可以选择告诉警官“所有人都至少来过大厅一次了”，如果确实如此，那么所有囚徒都会被释放，不过只有一次机会尝试。问一个确定的方案，使得这些囚徒能够重获自由。并且需要分析该方案完成的期望天数。

解：考虑选第一天出到大厅的囚徒为master，只有master有权力关灯，其他囚徒会且仅会开一次灯，那么当master关了99次灯之后，就知道所有人都至少出来过一次了。期望天数是1 + 100/99 + 100/1 + 100/98 + 100/1 + … + 100/1 + 100/1。

4. 有一个线段，线段上有两点A、B，有两个机器人分别在这两个点上。初始A、B点位置不确定，线段无限长。你需要为这两个机器人写一段相同的程序，使得他们可以相遇。指令集是给定的，包括4种指令：
1. move left 向左移动（耗时1）
2. move right 向右移动（耗时1）
3. if at A点或B点
4. goto 某行

解：考虑使两个机器人同时向右走，一开始都是慢走，其中一个机器人一定会遇到另一个机器人出发的起点（A或B），那么将其转换成快走模式，追赶慢走的机器人。
1: move right
2: move left
3: move right
4: if at A点或B点
5: goto 7:
6: goto 1:
7: move right
8: goto 7:

5. 求一个完全二叉树的结点总数。

解：完全二叉树有这样的性质：对于树上任意的一个结点，其左子树或右子树中至少有一个是满二叉树。可以通过探测最左和最右结点的深度来判断这棵树是不是满二叉树，时间复杂度是O(lgN)的。因此，依次从最高层向下，每层判断是否满二叉树后最多只沿其中一个子树继续向下，这里时间复杂度是O(lgN)+O(lg(N/2))+…+O(lg(N/N)) = O((lgN)^2)的。

6. 有100层楼，以及这样一种鸡蛋：该鸡蛋从某层以上的楼层往下丢会摔碎，而从该层以下往下丢则是怎么摔都不会碎。给你两个鸡蛋，要求通过最少的尝试次数试出这个鸡蛋从哪层开始会碎。扩展：有N层楼和M个鸡蛋的情况。

解：第一个鸡蛋用来大致试探，第二个鸡蛋需要逐层试探。第一个鸡蛋试探的楼层间隔即是第二个鸡蛋最多要尝试的上限。那么第一个鸡蛋划分出的间隔应该是逐渐递减的，这样才能使总尝试次数最小。例如，第一个鸡蛋分别从x、x+(x-1)、x+(x-1)+(x-2)、…开始往下丢，第二鸡蛋分别需要尝试x-1、x-2、x-3…次，那么最坏情况下总是需要x次尝试就能试出楼层数了。这里需要使得x(x+1)/2 >= 100-1，解得x>=14。这里是100-1是因为，如果刚好x(x+1)/2==99还没碎，那么肯定是第100层楼才会碎的，也就不用额外去试了。
扩展的情况下，考虑3个鸡蛋，若设最多尝试次数为x，那么第一个鸡蛋划分出的区间之间的间隔应该是使得两个鸡蛋的总尝试次数递减的，也即需要满足sum{x(x-1)/2} >= M-2。4个鸡蛋的情况就是sum{sum{x(x-1)/2}} >= M-3，依此类推。

面试题一则

发表回复

有节点数为n的一棵树，每个节点i有一个权值w[i]，节点i到节点j的距离d[i][j]定义为在树上节点i和节点j之间有多少条边。定义f(i) = sum{w[j] * d[i][j] | -1 < j < n}，求min{f(i) | -1 < i < n}。题源来自qoshi。

基本思路还是树型DP，希望能根据相邻节点的f值计算出当前节点的f值。具体的思路是，如果指定了深搜的起点为0，那么每个节点都会将树上的其他节点分为两个部分，一部分是离0点近的（设为A类节点），一部分是离0点远的（设为B类节点）。

具体的状态转移，包括4个矩阵：lw[i]，记录的是某个节点划分出的属于A类节点的权值和；rw[i]记录属于B类节点的权值和；lws[i]记录的是sum{ w[j] * d[i][j] | j属于i划分出的A类节点}；rws[i]记录的是sum{ w[j] * d[i][j] | j属于i划分出的B类节点}。由此f(i) = lws[i] + rws[i]。使用这4个矩阵是因为，沿着某条边走一步后，某个节点的这4个值可以根据相邻节点的信息O(1)地得到。

其中rws[i]，需要从自底向上的构造，也就是用了深搜遍历完所有孩子节点后，再计算父节点的值；而lws[i]，则是自顶向下的计算。

具体的程序如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define M 100000

int n, w[M], lw[M], lws[M], rw[M], rws[M], hd[M], el;
int ansi, ans;

struct E {
    int v, p;
}e[M*2];

void adde(int u, int v) {
    e[el].v=v; e[el].p=hd[u]; hd[u]=el++;
    e[el].v=u; e[el].p=hd[v]; hd[v]=el++;
}

void init() {
    int i, j, k, l;
    el=0;
    memset(hd, -1, sizeof hd);
    for(i=0; i<n; i++) scanf("%d", w+i);
    for(i=1; i<n ;i++) {
        scanf("%d%d", &j, &k);
        adde(j, k);
    }
    ans=0x7fffffff;
}

void dfsr(int i, int f) {
    int j, k, l;
    rw[i]=rws[i]=0;
    for(l=hd[i]; l!=-1; l=e[l].p) {
        j=e[l].v;
        if(j==f) continue;
        dfsr(j, i);
        rw[i]+=rw[j]+w[j];
        rws[i]+=rws[j]+rw[j]+w[j];
    }
}

void dfsl(int i, int f) {
    int j, k, l;
    if(f==-1) {
        lw[i]=lws[i]=0;
    } else {
        lw[i]=rw[f]+lw[f]-rw[i]-w[i]+w[f];
        lws[i]=rws[f]+lws[f]-rws[i]-rw[i]-w[i]+lw[i];
    }
    for(l=hd[i]; l!=-1; l=e[l].p) {
        j=e[l].v;
        if(j==f) continue;
        dfsl(j, i);
    }
}

void solve() {
    int i;
    dfsr(0, -1);
    dfsl(0, -1);
    for(i=0; i<n; i++) {
        printf("%d: %d + %d = %d\n", i, lws[i], rws[i], lws[i]+rws[i]);
        if(lws[i]+rws[i]<ans) {
            ans=lws[i]+rws[i];
            ansi=i;
        }
    }
    printf("%d %d\n", ansi, ans);
}

int main () {
    while(~scanf("%d", &n)) {
        init();
        solve();
    }
    return 0;
}

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define M 100000

int n, w[M], lw[M], lws[M], rw[M], rws[M], hd[M], el;

int ansi, ans;

struct E {

int v, p;

}e[M*2];

void adde(int u, int v) {

e[el].v=v; e[el].p=hd[u]; hd[u]=el++;

e[el].v=u; e[el].p=hd[v]; hd[v]=el++;

}

void init() {

int i, j, k, l;

el=0;

memset(hd, -1, sizeof hd);

for(i=0; i<n; i++) scanf("%d", w+i);

for(i=1; i<n ;i++) {

scanf("%d%d", &j, &k);

adde(j, k);

}

ans=0x7fffffff;

}

void dfsr(int i, int f) {

int j, k, l;

rw[i]=rws[i]=0;

for(l=hd[i]; l!=-1; l=e[l].p) {

j=e[l].v;

if(j==f) continue;

dfsr(j, i);

rw[i]+=rw[j]+w[j];

rws[i]+=rws[j]+rw[j]+w[j];

}

void dfsl(int i, int f) {

int j, k, l;

if(f==-1) {

lw[i]=lws[i]=0;

} else {

lw[i]=rw[f]+lw[f]-rw[i]-w[i]+w[f];

lws[i]=rws[f]+lws[f]-rws[i]-rw[i]-w[i]+lw[i];

}

for(l=hd[i]; l!=-1; l=e[l].p) {

j=e[l].v;

if(j==f) continue;

dfsl(j, i);

}

void solve() {

int i;

dfsr(0, -1);

dfsl(0, -1);

for(i=0; i<n; i++) {

printf("%d: %d + %d = %d\n", i, lws[i], rws[i], lws[i]+rws[i]);

if(lws[i]+rws[i]<ans) {

ans=lws[i]+rws[i];

ansi=i;

}

printf("%d %d\n", ansi, ans);

}

int main () {

while(~scanf("%d", &n)) {

init();

solve();

}

return 0;

}

只有自己做的一些测试数据，没有找到OJ版本的题目：

输入1：

2 3 1 2 4

0 1

1 2

2 3

2 4

输出1：

0: 0 + 23 = 23
1: 2 + 13 = 15
2: 7 + 6 = 13
3: 21 + 0 = 21
4: 17 + 0 = 17
2 13

0: 0 + 23 = 23

1: 2 + 13 = 15

2: 7 + 6 = 13

3: 21 + 0 = 21

4: 17 + 0 = 17

2 13

输入2：

9
5 2 7 6 8 1 4 2 3
0 1
1 2
1 3
3 5
3 6
3 4
4 7
0 8

5 2 7 6 8 1 4 2 3

0 1

1 2

1 3

3 5

3 6

3 4

4 7

0 8

输出2：

0: 0 + 78 = 78
1: 11 + 45 = 56
2: 80 + 0 = 80
3: 35 + 17 = 52
4: 68 + 2 = 70
5: 88 + 0 = 88
6: 82 + 0 = 82
7: 104 + 0 = 104
8: 110 + 0 = 110
3 52

0: 0 + 78 = 78

1: 11 + 45 = 56

2: 80 + 0 = 80

3: 35 + 17 = 52

4: 68 + 2 = 70

5: 88 + 0 = 88

6: 82 + 0 = 82

7: 104 + 0 = 104

8: 110 + 0 = 110

3 52

O(n)找无序数组第k大的元素

发表回复

最近一直在面试，不时会被问到找无序数组中第k大元素的题。基本做法，看到过都是基于快排的partition思想的，时间复杂度虽然说平均O(n)，但是极端情况下会退化成O(n^2)。这个方法写起来不但很麻烦，复杂度方面也一直让我纠结，实在是一百万个不喜欢。

于是开始自己考虑别的解法。

传统的partition中最不好的地方是无法确定中位元的位置，也即难以将数组分成尽可能均等的两份。那么可不可以从别的角度来作划分呢？仔细思考后发现可以从bit方面作文章的。

假设数组存储的全部都是int类型的正整数（如果是long long或者有负数的情况也是类似的），从最高位开始，将所有该位为0的数放到数组的左面，将所有为1的数放到数组的右面，这显然是一个O(n)的划分过程。划分结果可以得到一个中间位置，其左面的数全部小于右边。到这里思路应该很清楚了：依次对更低的每一位重复该操作，就可以逐步逼近第k大的数。由于int正数最多只有31位，那么总的时间复杂度便是O(31n)的。虽然上界情况常数很大，但由于实际上不可能每次都扫遍整个数组的，所以实际的时间会比较接近O(n)。该算法还有很多其他好处，例如空间是O(1)的，也不存在退化的问题。

下面是实现代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n, m, a[10000000];

void init() {
	for(int i=0; i<n; i++) scanf("%d", a+i);
}

int partition(int a[], int n, int m, int b) {
	if(n==1) return a[0];
	int i, j;
	for(i=0, j=n-1; i<j; ) {
		while(i<j && !(a[i]&b)) i++;
		while(i<j && (a[j]&b)) j--;
		if(i<j) swap(a[i], a[j]);
	}
	if(a[i]&b) i--;
	if(n-1-i>=m) {
		return partition(a+i+1, n-1-i, m, b>>1);
	} else {
		return partition(a, i+1, m-(n-1-i), b>>1);
	}
}

void solve() {
	printf("%d\n", partition(a, n, m, 1<<30));
}

int main() {
	while(~scanf("%d%d", &n, &m)) {
		init();
		solve();
	}
	return 0;
}

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n, m, a[10000000];

void init() {

for(int i=0; i<n; i++) scanf("%d", a+i);

}

int partition(int a[], int n, int m, int b) {

if(n==1) return a[0];

int i, j;

for(i=0, j=n-1; i<j; ) {

while(i<j && !(a[i]&b)) i++;

while(i<j && (a[j]&b)) j--;

if(i<j) swap(a[i], a[j]);

}

if(a[i]&b) i--;

if(n-1-i>=m) {

return partition(a+i+1, n-1-i, m, b>>1);

} else {

return partition(a, i+1, m-(n-1-i), b>>1);

}

void solve() {

printf("%d\n", partition(a, n, m, 1<<30));

}

int main() {

while(~scanf("%d%d", &n, &m)) {

init();

solve();

}

return 0;

}

不知道有没错呢，细心的人帮我看看好了。 =)

附送测试数据：

20 1
13 10 0 8 7 3 5 14 11 19 2 12 15 9 16 4 17 6 18 1
20 5
13 10 0 8 7 3 5 14 11 19 2 12 15 9 16 4 17 6 18 1
20 10
13 10 0 8 7 3 5 14 11 19 2 12 15 9 16 4 17 6 18 1
20 15
13 10 0 8 7 3 5 14 11 19 2 12 15 9 16 4 17 6 18 1
20 20
13 10 0 8 7 3 5 14 11 19 2 12 15 9 16 4 17 6 18 1

20 1

13 10 0 8 7 3 5 14 11 19 2 12 15 9 16 4 17 6 18 1

20 5

13 10 0 8 7 3 5 14 11 19 2 12 15 9 16 4 17 6 18 1

20 10

13 10 0 8 7 3 5 14 11 19 2 12 15 9 16 4 17 6 18 1

20 15

13 10 0 8 7 3 5 14 11 19 2 12 15 9 16 4 17 6 18 1

20 20

13 10 0 8 7 3 5 14 11 19 2 12 15 9 16 4 17 6 18 1

从此妈妈再也不用担心我不会解第k大元素啦！！！

ps：吐槽一下，竟然还有人写了这么长的文章来分析时间复杂度…能全部看完的人请一定来教育教育我。

[LeetCode Largest Rectangle in Histogram]

发表回复

Largest Rectangle in Histogram

题意：给出一个长度n的数组，每个值为非负数，描述一个宽为1的立柱的高h[i]，求立柱围成区域中最大的矩形区域面积。

分析：
对于每个立柱i，求出满足h[j]到h[i-1]都不小于h[i]的最左值j，记i-j+1为lc[i]，类似地求出rc[i]，那么位置i对应的最大可行面积即为h[i]*(lc[i]+rc[i]+1)。

以求lc[i]为例，需要一个单调栈，单调栈中由底到顶依次记录扫描到i之前的上升序列d[l]及其位置di[l]，扫描到i时，初始化lc[i]=1，对于所有高度d[l]大于等于h[i]的栈顶元素，依次出栈，并将其lc[di[l]]加到lc[i]中，最后将h[i]和i入栈。

时间复杂度方面，计算lc和rc时，每个元素刚好入栈、出战各一次，因此根据平摊分析，时间复杂度是O(n)的。

int d[100000], di[100000], lc[100000], rc[100000], n, ans;

class Solution {
public:
    int largestRectangleArea(vector<int> &h) {
        n=h.size(); ans=0;
        int i, l;
        for(i=0, l=0; i<n; i++)
        {
            for(lc[i]=1; l&&h[i]<=d[l-1]; l--)
                lc[i]+=lc[di[l-1]];
            d[l]=h[i];
            di[l++]=i;
        }
        for(i=n-1, l=0; i>-1; i--)
        {
            for(rc[i]=1; l&&h[i]<=d[l-1]; l--)
                rc[i]+=rc[di[l-1]];
            d[l]=h[i];
            di[l++]=i;
        }
        for(i=0; i<n; i++)
            ans=max(ans, h[i]*(lc[i]+rc[i]-1));
        return ans;
    }
};

int d[100000], di[100000], lc[100000], rc[100000], n, ans;

class Solution {

public:

int largestRectangleArea(vector<int> &h) {

n=h.size(); ans=0;

int i, l;

for(i=0, l=0; i<n; i++)

{

for(lc[i]=1; l&&h[i]<=d[l-1]; l--)

lc[i]+=lc[di[l-1]];

d[l]=h[i];

di[l++]=i;

}

for(i=n-1, l=0; i>-1; i--)

{

for(rc[i]=1; l&&h[i]<=d[l-1]; l--)

rc[i]+=rc[di[l-1]];

d[l]=h[i];

di[l++]=i;

}

for(i=0; i<n; i++)

ans=max(ans, h[i]*(lc[i]+rc[i]-1));

return ans;

}

};

ps：最早是半年前被问到了这题。现在回头看看，写得真是惨不忍睹。现在做LeetCode又遇到这题，分析题意方面，要比之前稍好一些了吧……

[LeetCode Unique Binary Search Trees II]

1条回复

Unique Binary Search Trees II

题意：输入是n，要求枚举出包含1…n这n个整数的所有二叉搜索树（BST）。

分析：显然这题n不可能很大，考察的是如何枚举每种可能的状态。首先考虑了所有全排列的插入构建BST，发现这样得到的BST有重复。然后发现，若设n的全部BST为T(n)，当根是i时，其左子树的所有可能情况为T(i-1)，右子树的所有可能情况为T(n-i)。这样就可以按n由小到大地递推构造出各个BST了。

int vvpl=0;
vector<vector<TreeNode *>> vvp;
vector<TreeNode *> vp;
vector<TreeNode *>::iterator it1, end1, it2, end2;

TreeNode *mk(TreeNode *p, int d)
{
    if(!p)
        return 0;
    TreeNode *q=new TreeNode(p->val+d);
    q->left=mk(p->left, d);
    q->right=mk(p->right, d);
    return q;
}

class Solution {
public:
    vector<TreeNode *> generateTrees(int n) {
        int i, j, k, l;
        TreeNode *p;
        if(vvpl<=n)
        {
            if(vvpl==0)
            {
                vvp.push_back(vp);
                vvp[0].push_back(0);
                vvpl=1;
            }
            for(; vvpl<=n; vvpl++)
            {
                vvp.push_back(vp);
                for(i=1; i<=vvpl; i++)
                {
                    for(it1=vvp[i-1].begin(), end1=vvp[i-1].end(); it1!=end1; it1++)
                    {
                        for(it2=vvp[vvpl-i].begin(), end2=vvp[vvpl-i].end(); it2!=end2; it2++)
                        {
                            p=new TreeNode(i);
                            p->left=mk(*it1, 0);
                            p->right=mk(*it2, i);
                            vvp[vvpl].push_back(p);
                        }
                    }
                }
            }
        }
        return vvp[n];
    }
};

int vvpl=0;

vector<vector<TreeNode *>> vvp;

vector<TreeNode *> vp;

vector<TreeNode *>::iterator it1, end1, it2, end2;

TreeNode *mk(TreeNode *p, int d)

{

if(!p)

return 0;

TreeNode *q=new TreeNode(p->val+d);

q->left=mk(p->left, d);

q->right=mk(p->right, d);

return q;

}

class Solution {

public:

vector<TreeNode *> generateTrees(int n) {

int i, j, k, l;

TreeNode *p;

if(vvpl<=n)

{

if(vvpl==0)

{

vvp.push_back(vp);

vvp[0].push_back(0);

vvpl=1;

}

for(; vvpl<=n; vvpl++)

{

vvp.push_back(vp);

for(i=1; i<=vvpl; i++)

{

for(it1=vvp[i-1].begin(), end1=vvp[i-1].end(); it1!=end1; it1++)

{

for(it2=vvp[vvpl-i].begin(), end2=vvp[vvpl-i].end(); it2!=end2; it2++)

{

p=new TreeNode(i);

p->left=mk(*it1, 0);

p->right=mk(*it2, i);

vvp[vvpl].push_back(p);

}

return vvp[n];

}

};

ps：LeetCode上面很多这种要求构造出所有可行解的题目，这是之前做的ACM中几乎没有的。虽然题型相对陌生，但解起来也很好玩~

[LeetCode Word Ladder II]

3条回复

Word Ladder II

题意：给出一个初始字符串S和目标字符串T，以及可行的中间字符串集合dict，转换字符串时仅允许一次改变一个字符，要求从S变为T的所有最短可行序列。

分析：首先，需要枚举每个字符串可行的改变方式，并用BFS建图：建立结点编号对可达字符串的映射关系，并记录每个结点的深度。建图结束后，用深搜的方式枚举出所有可行的字符串，剪枝方案只简单记录了无效结点。最后跑出的时间是1096 ms。

vector<vector<string> > vvs;
vector<string> vs;
map<string, int> Msi;
map<int, string> Mis;
int hd[100000], el, si, ti, sl, d[100000];
char b[100000];

struct E
{
    int v, p;
}e[100000];

void adde(int u, int v)
{
    e[el].v=v; e[el].p=hd[u]; hd[u]=el++;
}

void bfs(string s, string t, unordered_set<string> &dict)
{
    int i, j, k, l, u, v;
    queue<string> Q;
    d[si]=0;
    Msi[s]=si++;
    Mis[0]=s;
    Q.push(s);
    while(!Q.empty())
    {
        s=Q.front(); Q.pop();
        u=Msi[s];
        for(i=0; i<sl; i++)
        {
            k=s[i];
            for(j='a'; j<='z'; j++)
            {
                if(j==k)
                    continue;
                s[i]=j;
                if(dict.find(s)==dict.end())
                    continue;
                if(Msi.find(s)!=Msi.end())
                {
                    v=Msi[s];
                    if(d[v]==d[u]+1)
                        adde(u, v);
                    continue;
                }
                v=Msi[s]=si++;
                d[v]=d[u]+1;
                Mis[v]=s;
                Q.push(s);
                adde(u, v);
            }
            s[i]=k;
        }
    }
}

int dfs(int u, int vsl)
{
    if(b[u]||vsl>d[ti])
        return b[u]=1;
    int l, v;
    if(vs.size()<=vsl)
        vs.push_back(Mis[u]);
    else
        vs[vsl]=Mis[u];
    if(u==ti)
    {
        vvs.push_back(vs);
        return 0;
    }
    b[u]=1;
    for(l=hd[u]; l!=-1; l=e[l].p)
    {
        v=e[l].v;
        if(!dfs(v, vsl+1))
            b[u]=0;
    }
    return b[u];
}

class Solution {
public:
    vector<vector<string>> findLadders(string s, string t, unordered_set<string> &dict) {
        dict.insert(t);
        vvs.clear();
        vs.clear();
        Msi.clear();
        Mis.clear();
        memset(hd, -1, sizeof hd);
        memset(b, 0, sizeof b);
        si=el=0;
        sl=s.length();
        bfs(s, t, dict);
        if(Msi.find(t)==Msi.end())
            return vvs;
        ti=Msi[t];
        dfs(0, 0);
        return vvs;
    }
};

100

101

vector<vector<string> > vvs;

vector<string> vs;

map<string, int> Msi;

map<int, string> Mis;

int hd[100000], el, si, ti, sl, d[100000];

char b[100000];

struct E

{

int v, p;

}e[100000];

void adde(int u, int v)

{

e[el].v=v; e[el].p=hd[u]; hd[u]=el++;

}

void bfs(string s, string t, unordered_set<string> &dict)

{

int i, j, k, l, u, v;

queue<string> Q;

d[si]=0;

Msi[s]=si++;

Mis[0]=s;

Q.push(s);

while(!Q.empty())

{

s=Q.front(); Q.pop();

u=Msi[s];

for(i=0; i<sl; i++)

{

k=s[i];

for(j='a'; j<='z'; j++)

{

if(j==k)

continue;

s[i]=j;

if(dict.find(s)==dict.end())

continue;

if(Msi.find(s)!=Msi.end())

{

v=Msi[s];

if(d[v]==d[u]+1)

adde(u, v);

continue;

}

v=Msi[s]=si++;

d[v]=d[u]+1;

Mis[v]=s;

Q.push(s);

adde(u, v);

}

s[i]=k;

}

int dfs(int u, int vsl)

{

if(b[u]||vsl>d[ti])

return b[u]=1;

int l, v;

if(vs.size()<=vsl)

vs.push_back(Mis[u]);

else

vs[vsl]=Mis[u];

if(u==ti)

{

vvs.push_back(vs);

return 0;

}

b[u]=1;

for(l=hd[u]; l!=-1; l=e[l].p)

{

v=e[l].v;

if(!dfs(v, vsl+1))

b[u]=0;

}

return b[u];

}

class Solution {

public:

vector<vector<string>> findLadders(string s, string t, unordered_set<string> &dict) {

dict.insert(t);

vvs.clear();

vs.clear();

Msi.clear();

Mis.clear();

memset(hd, -1, sizeof hd);

memset(b, 0, sizeof b);

si=el=0;

sl=s.length();

bfs(s, t, dict);

if(Msi.find(t)==Msi.end())

return vvs;

ti=Msi[t];

dfs(0, 0);

return vvs;

}

};

ps：不得不说LeetCode做题好刺激，每题都不给数据范围，并且debug非常困难，基本就是各种靠猜。这题整整交了48次才过，实在是太多的血与泪。

[HDU 4836]

发表回复

The Query on the Tree

2014年百度之星复赛的第二题，看了官方题解才会做。

个人觉得这题有意思的地方有：
（1）通过记录DFS顺序+树状数组的方式，动态更新每一棵子树的权值和；
（2）树根改变的时候，根据父子关系巧妙地不修改数据求出当前子树权值和。

#include<cstdio>
#include<cstring>

int t,n,m,el,hd[10000],y[10000],f[10000],dl[10000],dr[10000],di;
int tr[20001],yt,rt;
char s[10];

struct E
{
    int v,p;
}e[20000];

void adde(int u,int v)
{
    e[el].v=v; e[el].p=hd[u]; hd[u]=el++;
    e[el].v=u; e[el].p=hd[v]; hd[v]=el++;
}

void ins(int i,int d)
{
    while(i<di)
    {
        tr[i]+=d;
        i+=i&-i;
    }
}

int qry(int i)
{
    int d=0;
    while(i)
    {
        d+=tr[i];
        i-=i&-i;
    }
    return d;
}

void dfs(int i,int h)
{
    int j,k,l;
    f[i]=h;
    dl[i]=di++;
    for(l=hd[i];l!=-1;l=e[l].p)
    {
        j=e[l].v;
        if(j==h)
            continue;
        dfs(j,i);
    }
    dr[i]=di++;
}

void init()
{
    int i,j,k,l;
    el=0;
    di=1;
    yt=0;
    rt=0;
    memset(hd,-1,sizeof hd);
    memset(tr,0,sizeof tr);
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&j,&k);
        adde(j-1,k-1);
    }
    for(i=0;i<n;i++)
    {
        scanf("%d",y+i);
        yt+=y[i];
    }
    dfs(0,-1);
    for(i=0;i<n;i++)
        ins(dl[i],y[i]);
}

void solve()
{
    int i,j,k,l;
    printf("Case #%d:\n",++t);
    scanf("%d",&m);
    while(m--)
    {
        scanf("%s",s);
        if(s[0]=='Q')
        {
            scanf("%d",&i);
            i--;
            if(i==rt)
            {
                printf("%d\n",yt);
            }
            else
            {
                if(dl[rt]>dl[i]&&dr[rt]<dr[i])
                {
                    for(l=rt;f[l]!=i;l=f[l]);
                    printf("%d\n",yt-(qry(dr[l])-qry(dl[l]-1)));
                }
                else
                {
                    printf("%d\n",qry(dr[i])-qry(dl[i]-1));
                }
            }
        }
        else if(s[0]=='C')
        {
            scanf("%d%d",&i,&j);
            i--;
            ins(dl[i],j-y[i]);
            yt+=j-y[i];
            y[i]=j;
        }
        else
        {
            scanf("%d",&rt);
            rt--;
        }
    }
}

int main()
{
    scanf("%*d");
    while(~scanf("%d",&n))
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

#include<cstdio>

#include<cstring>

int t,n,m,el,hd[10000],y[10000],f[10000],dl[10000],dr[10000],di;

int tr[20001],yt,rt;

char s[10];

struct E

{

int v,p;

}e[20000];

void adde(int u,int v)

{

e[el].v=v; e[el].p=hd[u]; hd[u]=el++;

e[el].v=u; e[el].p=hd[v]; hd[v]=el++;

}

void ins(int i,int d)

{

while(i<di)

{

tr[i]+=d;

i+=i&-i;

}

int qry(int i)

{

int d=0;

while(i)

{

d+=tr[i];

i-=i&-i;

}

return d;

}

void dfs(int i,int h)

{

int j,k,l;

f[i]=h;

dl[i]=di++;

for(l=hd[i];l!=-1;l=e[l].p)

{

j=e[l].v;

if(j==h)

continue;

dfs(j,i);

}

dr[i]=di++;

}

void init()

{

int i,j,k,l;

el=0;

di=1;

yt=0;

rt=0;

memset(hd,-1,sizeof hd);

memset(tr,0,sizeof tr);

for(i=1;i<n;i++)

{

scanf("%d%d",&j,&k);

adde(j-1,k-1);

}

for(i=0;i<n;i++)

{

scanf("%d",y+i);

yt+=y[i];

}

dfs(0,-1);

for(i=0;i<n;i++)

ins(dl[i],y[i]);

}

void solve()

{

int i,j,k,l;

printf("Case #%d:\n",++t);

scanf("%d",&m);

while(m--)

{

scanf("%s",s);

if(s[0]=='Q')

{

scanf("%d",&i);

i--;

if(i==rt)

{

printf("%d\n",yt);

}

else

{

if(dl[rt]>dl[i]&&dr[rt]<dr[i])

{

for(l=rt;f[l]!=i;l=f[l]);

printf("%d\n",yt-(qry(dr[l])-qry(dl[l]-1)));

}

else

{

printf("%d\n",qry(dr[i])-qry(dl[i]-1));

}

else if(s[0]=='C')

{

scanf("%d%d",&i,&j);

i--;

ins(dl[i],j-y[i]);

yt+=j-y[i];

y[i]=j;

}

else

{

scanf("%d",&rt);

rt--;

}

int main()

{

scanf("%*d");

while(~scanf("%d",&n))

{

init();

solve();

}

return 0;

}

[POJ 3074]

发表回复

Sudoku

题意：求解数独问题。

思路：用DLX解。首先，需要将格盘建模为DLX用到的十字链表。数字之间的互斥关系共有4种，因此可以对”每行每个数字”、”每列每个数字”、”每九宫格每个数字”、”每个格点位置”分别建立一个链表列，也即总共是9*9+9*9+9*9+9*9=324个链表列，十字链表中每一行表示在某格点放置某数，分别与4个对应的链表列相交。

然后，就是正式的深搜了。在深搜的每一层：
1) 在十字链表表头中找出元素最少且非零的一列，将该列以及列中包含的所有行元素从十字链表中移除；
2) 枚举列中的每行（作为解的一部分），将与该行相交的所有其他列以及这些列包含的行元素在十字链表中移除，递归下一层深搜;
3) 递归返回时，需要将2)中移除的相应列和行添加回十字链表；
4) 所有行枚举完毕时，需要将1)中移除的相应列和行添加回十字链表。

注意，对链表进行增删操作时，需要以相反的顺序修改各结点。同时，也需要动态维护表头的元素数。

#include<cstdio>
#include<cstring>
#define M 10000

int s[9][9],sl;
int hd,el,tag;
char t[82],r[9][10],c[9][10],b[9][10];

struct E
{
    int l,r,u,d,c,s;
    int ri,ci,bi,v;
}e[M];

void adde(int ei,int ri,int ci,int bi,int v)
{
    e[ei].s++;
    e[el].u=ei;
    e[el].d=e[ei].d;
    e[e[ei].d].u=el;
    e[ei].d=el;
    e[el].c=ei;
    e[el].ri=ri;
    e[el].ci=ci;
    e[el].bi=bi;
    e[el].v=v;
    el++;
}

void addr(int ri,int ci,int bi,int v)
{
    int i,j,k,l;
    adde(1+ri*9+v-1,ri,ci,bi,v);
    adde(1+81+ci*9+v-1,ri,ci,bi,v);
    adde(1+81+81+bi*9+v-1,ri,ci,bi,v);
    adde(1+81+81+81+ri*9+ci,ri,ci,bi,v);
    for(i=0;i<4;i++)
    {
        j=(i+3)%4;
        k=(i+1)%4;
        e[el-4+i].l=el-4+j;
        e[el-4+i].r=el-4+k;
    }
}

void init()
{
    int i,j,k,l,tl;
    hd=el=tag=0;
    sl=81;
    memset(r,0,sizeof r);
    memset(c,0,sizeof c);
    memset(b,0,sizeof b);
    for(i=tl=0;i<9;i++)
    {
        for(j=0;j<9;j++)
        {
            if(t[tl]=='.')
                k=0;
            else
                k=t[tl]-'0';
            if(k)
                sl--;
            r[i][k]=1;
            c[j][k]=1;
            s[i][j]=k;
            l=i/3*3+j/3;
            b[l][k]=1;
            tl++;
        }
    }
    e[el].l=e[el].r=el;
    el++;
    for(i=0;i<324;i++)
    {
        e[el].l=hd;
        e[el].r=e[hd].r;
        e[e[hd].r].l=el;
        e[hd].r=el;
        e[el].u=e[el].d=e[el].c=el;
        e[el].s=0;
        el++;
    }
    for(i=0;i<9;i++)
    {
        for(j=0;j<9;j++)
        {
            if(s[i][j])
                continue;
            l=i/3*3+j/3;
            for(k=1;k<10;k++)
            {
                if(r[i][k]||c[j][k]||b[l][k])
                    continue;
                addr(i,j,l,k);
            }
        }
    }
}

void pnt()
{
    int i,j,tl;
    for(i=tl=0;i<9;i++)
        for(j=0;j<9;j++)
            t[tl++]='0'+s[i][j];
    puts(t);
}

void dfs(int si)
{
    if(si==sl)
    {
        tag=1;
        pnt();
        return;
    }
    int i,j,k,l;
    int ii,jj,kk;
    int ri,ci,bi,v;
    for(i=e[hd].r,j=0x7fffffff;i!=hd;i=e[i].r)
    {
        if(e[i].s&&e[i].s<j)
        {
            j=e[i].s;
            k=i;
        }
        if(j==1)
            break;
    }
    if(j==0x7fffffff)
        return;
    e[e[k].l].r=e[k].r;
    e[e[k].r].l=e[k].l;
    for(i=e[k].d;i!=k;i=e[i].d)
    {
        for(j=e[i].r;j!=i;j=e[j].r)
        {
            e[e[j].c].s--;
            e[e[j].u].d=e[j].d;
            e[e[j].d].u=e[j].u;
        }
    }
    for(i=e[k].d;i!=k;i=e[i].d)
    {
        ri=e[i].ri; ci=e[i].ci; bi=e[i].bi; v=e[i].v;
        for(j=e[i].r;j!=i;j=e[j].r)
        {
            kk=e[j].c;
            e[e[kk].l].r=e[kk].r;
            e[e[kk].r].l=e[kk].l;
            for(ii=e[kk].d;ii!=kk;ii=e[ii].d)
            {
                for(jj=e[ii].r;jj!=ii;jj=e[jj].r)
                {
                    e[e[jj].c].s--;
                    e[e[jj].u].d=e[jj].d;
                    e[e[jj].d].u=e[jj].u;
                }
            }
        }
        s[ri][ci]=v;
        dfs(si+1);
        if(tag)
            return;
        for(j=e[i].l;j!=i;j=e[j].l)
        {
            kk=e[j].c;
            e[e[kk].l].r=kk;
            e[e[kk].r].l=kk;
            for(ii=e[kk].u;ii!=kk;ii=e[ii].u)
            {
                for(jj=e[ii].l;jj!=ii;jj=e[jj].l)
                {
                    e[e[jj].u].d=jj;
                    e[e[jj].d].u=jj;
                    e[e[jj].c].s++;
                }
            }
        }
    }
    for(i=e[k].u;i!=k;i=e[i].u)
    {
        for(j=e[i].l;j!=i;j=e[j].l)
        {
            e[e[j].u].d=j;
            e[e[j].d].u=j;
            e[e[j].c].s++;
        }
    }
    e[e[k].l].r=k;
    e[e[k].r].l=k;
}

void solve()
{
    dfs(0);
}

int main()
{
    while(scanf("%s",t)&&t[0]!='e')
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

#include<cstdio>

#include<cstring>

#define M 10000

int s[9][9],sl;

int hd,el,tag;

char t[82],r[9][10],c[9][10],b[9][10];

struct E

{

int l,r,u,d,c,s;

int ri,ci,bi,v;

}e[M];

void adde(int ei,int ri,int ci,int bi,int v)

{

e[ei].s++;

e[el].u=ei;

e[el].d=e[ei].d;

e[e[ei].d].u=el;

e[ei].d=el;

e[el].c=ei;

e[el].ri=ri;

e[el].ci=ci;

e[el].bi=bi;

e[el].v=v;

el++;

}

void addr(int ri,int ci,int bi,int v)

{

int i,j,k,l;

adde(1+ri*9+v-1,ri,ci,bi,v);

adde(1+81+ci*9+v-1,ri,ci,bi,v);

adde(1+81+81+bi*9+v-1,ri,ci,bi,v);

adde(1+81+81+81+ri*9+ci,ri,ci,bi,v);

for(i=0;i<4;i++)

{

j=(i+3)%4;

k=(i+1)%4;

e[el-4+i].l=el-4+j;

e[el-4+i].r=el-4+k;

}

void init()

{

int i,j,k,l,tl;

hd=el=tag=0;

sl=81;

memset(r,0,sizeof r);

memset(c,0,sizeof c);

memset(b,0,sizeof b);

for(i=tl=0;i<9;i++)

{

for(j=0;j<9;j++)

{

if(t[tl]=='.')

k=0;

else

k=t[tl]-'0';

if(k)

sl--;

r[i][k]=1;

c[j][k]=1;

s[i][j]=k;

l=i/3*3+j/3;

b[l][k]=1;

tl++;

}

e[el].l=e[el].r=el;

el++;

for(i=0;i<324;i++)

{

e[el].l=hd;

e[el].r=e[hd].r;

e[e[hd].r].l=el;

e[hd].r=el;

e[el].u=e[el].d=e[el].c=el;

e[el].s=0;

el++;

}

for(i=0;i<9;i++)

{

for(j=0;j<9;j++)

{

if(s[i][j])

continue;

l=i/3*3+j/3;

for(k=1;k<10;k++)

{

if(r[i][k]||c[j][k]||b[l][k])

continue;

addr(i,j,l,k);

}

void pnt()

{

int i,j,tl;

for(i=tl=0;i<9;i++)

for(j=0;j<9;j++)

t[tl++]='0'+s[i][j];

puts(t);

}

void dfs(int si)

{

if(si==sl)

{

tag=1;

pnt();

return;

}

int i,j,k,l;

int ii,jj,kk;

int ri,ci,bi,v;

for(i=e[hd].r,j=0x7fffffff;i!=hd;i=e[i].r)

{

if(e[i].s&&e[i].s<j)

{

j=e[i].s;

k=i;

}

if(j==1)

break;

}

if(j==0x7fffffff)

return;

e[e[k].l].r=e[k].r;

e[e[k].r].l=e[k].l;

for(i=e[k].d;i!=k;i=e[i].d)

{

for(j=e[i].r;j!=i;j=e[j].r)

{

e[e[j].c].s--;

e[e[j].u].d=e[j].d;

e[e[j].d].u=e[j].u;

}

for(i=e[k].d;i!=k;i=e[i].d)

{

ri=e[i].ri; ci=e[i].ci; bi=e[i].bi; v=e[i].v;

for(j=e[i].r;j!=i;j=e[j].r)

{

kk=e[j].c;

e[e[kk].l].r=e[kk].r;

e[e[kk].r].l=e[kk].l;

for(ii=e[kk].d;ii!=kk;ii=e[ii].d)

{

for(jj=e[ii].r;jj!=ii;jj=e[jj].r)

{

e[e[jj].c].s--;

e[e[jj].u].d=e[jj].d;

e[e[jj].d].u=e[jj].u;

}

s[ri][ci]=v;

dfs(si+1);

if(tag)

return;

for(j=e[i].l;j!=i;j=e[j].l)

{

kk=e[j].c;

e[e[kk].l].r=kk;

e[e[kk].r].l=kk;

for(ii=e[kk].u;ii!=kk;ii=e[ii].u)

{

for(jj=e[ii].l;jj!=ii;jj=e[jj].l)

{

e[e[jj].u].d=jj;

e[e[jj].d].u=jj;

e[e[jj].c].s++;

}

for(i=e[k].u;i!=k;i=e[i].u)

{

for(j=e[i].l;j!=i;j=e[j].l)

{

e[e[j].u].d=j;

e[e[j].d].u=j;

e[e[j].c].s++;

}

e[e[k].l].r=k;

e[e[k].r].l=k;

}

void solve()

{

dfs(0);

}

int main()

{

while(scanf("%s",t)&&t[0]!='e')

{

init();

solve();

}

return 0;

}

没有想出太好的优化。c++下跑了188ms。

ps：
记得最早是11年寒假时，和Arios一起留校做MCM时听他提到，当时那道建模题可以用Dancing Links解。一晃眼，3年多过去了，我这才开始读Knuth的这篇论文。

文章本身的算法不算难懂，因为深搜的优化是很多问题都要用到的。之前做题的时候，确实也有考虑过对链表进行动态调整，但发现无法根本上降低时间复杂度（依然是指数时间）后，也没有深究了。而Knuth这篇论文里介绍的DLX，通过对十字链表进行动态调整从而尽量保持搜索树最优，可以说是在通常情况下将深搜优化到了极致。

做这题数独时，在链表建模那一步想了大概一整天时间。主要是数独问题元素间的互斥情况比较复杂。一开始只用了前3种互斥关系，发现表头记录的元素数无法正确维护，每次暴力重算并加了些优化后竟然勉强过了。然后就一直在想正解。想出应该增加第4种互斥关系后，又用了很长时间才推出要移除与当前行元素互斥的所有行。最后对链表的修改要比一开始想的要复杂得多。

查了下status，Arios在5年前作出的时间是32ms，并且是1A 47ms过的。实在是很强。

[SRM 621]

发表回复

第一场TC。

很好的开局。继续努力。