二胎准生证终于下来了 (2012-01-18 22:45:42)转载▼# Parenting - 为人父母
a*2
1 楼
不能用swap，只能用给定的function
reverse(i): reverse first i element in array.
有没有O(nlogn）解啊?
reverse(i): reverse first i element in array.
有没有O(nlogn）解啊?
d*l
2 楼
二胎准生证终于下来了 (2012-01-18 22:45:42)转载▼
经过了近三个月的准备，美女程的二胎准生证终于被批准了，明天可以拿到。以下是本
次办理活动简介：
第一步：收集信息：
美女程仔细研究了户口所在地街道网站上的信息，以及档案所在地FESCO的政策，确认
了所需要的基本材料：双方结婚证、双方独生子女证、双方婚育情况证明、未领取或已
退还小谢独生子女费的证明、小谢出生证明和独生子女证、第一胎准生证。
此外，美女程凑巧与一有二胎的同事户口所在地一样，于是，积极借鉴他的经验，了解
到需要准备双方父母的结婚证或婚育证明。这是因为街道需要证明我们的父母们只结了
一次婚，只生了一个孩子。
综合上述情况，美女程积极发动双方父母搞定了他们的结婚证（居然能找到，上面还印
着革委会的章，以及办酒席用的鱼肉票已领的证明）
第二步：个人准备阶段：
美女程充分利用自己和FESCO的关系，迅速搞定了自己的婚育证明以及没有领取独生子
女费。但是档案在海淀人才的谢同学迟迟无法搞定。美女程果断地要求谢同学把自己的
档案转移到FESCO，并因此搞定谢同学的婚育证明以及独生子女费问题。此举证明极其
英明，因为这样在后续无数次要求FESCO盖章的时候，美女程都可以一次性搞定两个人
需要的章。
解决掉存档单位证明问题后，美女程很挠头的就是如何撰写《二胎指标申请书》。根据
同事的说法，街道会无数次刁难，因此美女程希望尽可能地完善准备，减少被挑刺儿的
机会。百度了多次后，选择了网络上可以看到的最完善的一个版本参考写了自己的申请
书。结果发现，最重要的一句话 -- 双方都是独生子女 -- 压根没有体现在模板中。
除了写，就是大量的复印。所以你能想到的文件都要复印。
第三步：初次提交：
美女程她娘受托带着厚厚的材料跑了街道办事处。办事处说这事情要先回居委会。只有
居委会审批通过后才上报街道。亲爱的娘带着材料来到了居委会，居委会说二胎事宜必
须有指定居委会办理。亲爱的娘再次奔波到了指定居委会。太佩服亲爱的娘了，这么偏
僻的地方她都能找得到。
指定居委会说：材料复印方式不对，必须要A4纸竖着印，复印材料退回。双方父母光有
结婚证不行，谁知道他们有没有离婚未登记啊。所以需要双方父母4个人的单位的人事
部门出具初婚证明且说明只生了一个孩子。感谢政府感谢党，幸好4位的单位都还健在
，要不然我不知道应该怎么开这个证明。指定居委会说，怎么没有填写专用申请表呢？
（靠，我都百度那么久，就是没有找到所谓的专用申请表，压根就是你们没有贴出来嘛
，凭啥challenge我？）亲爱的娘热情地找人要了好多份回来。幸亏要了好多份，要不
然以后就惨了。还有还有，指定居委会说：“两个孩子年两差距不到5岁，与规定不符
！”幸亏我对我娘进行了充分的宣传。亲爱的娘理直气壮地回答：“俺闺女过30了，符
合规定！”指定居委会从此在这个问题上沉默了。
第四步：再次提交：
根据指定居委会的意见，美女程迅速展开修复工作，在两周之内按要求搞定了所有文件
以及复印件。材料之多，俺的1.8米双人床都铺满了
指定居委会继续挑刺：这个女方父亲怎么能用一代身份证呢？这个男方母亲的户口本页
面不平整，有涂改嫌疑，还是让派出所证明一下吧！另外，专用申请表上夫妻两个既然
只有一个孩子，就不用把孩子的信息填两遍了！（那为什么设计表格的时候不加个说明
啊！）那个夫妻作为申请人怎么没有在每一页材料上签字啊？（靠，不是你说的，要等
你在每页材料上盖章以后我才能签字吗？而且日期还要按照你说的签）
第五步：第三次提交：
美女程继续改进，终于准备好了所有材料，要去指定居委会正式提交。指定居委会大姐
说她忙，不一定在，预约也不一定在。这个时候，守株待兔是个好方法。亲爱的娘和美
女程在指定居委会大姐上班前40分钟到了她的办公室门口候着，终于在那个穿金戴银的
大姐上班的时候逮到了她。大姐这次实在挑不出毛病，只好登记造册接收。大姐说：“
要过年了，都很忙，等通知吧。正常30个工作日。你怎么不早点办啊？你这样医院能接
收你？现在规定没有指标不能产检！”美女程满脸堆笑：“慢慢来，您别急。产检的事
情我自己搞定就好。”
第六步：出其不意地提前被批准：
周一，指定居委会给亲爱的娘打电话，说批完了，年前来拿吧。哇咔咔，政府效率很高
嘛。从周一开始，小龙女阿当同志终于有了合法身份了。为了这一天，回想过去那次次
准备，就当是个纪念吧。幸亏我们的父母们东西保存得好，幸亏他们的单位都在，要不
然这个指标是绝对办不下来滴。
最后综述所有材料清单：
夫妻双方准备：户口本、结婚证、身份证、本人独生子女证、单位出具初婚证明、独生
子女费未领取或退还证明、二胎指标申请书（个人拟）x1、二胎指标申请表（居委会给
）x2、一胎准生证（政府收回）、一胎出生证、一胎独生子女证（政府收回）。特别说
明，如果一胎独生子女证丢失，一胎独生子女证夫妻双发申请表可以作为证明
夫妻双方父母准备：结婚证、身份证、户口本、单位出具的初婚未离且只生育一个子女
的证明
上述所有文件为原件，必须配套复印件。提交材料时，原件与复印件必须同时提交。待
原件审核通过后，复印件加盖审核通过章，申请人（夫妻其中一方）亲笔签字，并按照
要求签署日期
经过了近三个月的准备，美女程的二胎准生证终于被批准了，明天可以拿到。以下是本
次办理活动简介：
第一步：收集信息：
美女程仔细研究了户口所在地街道网站上的信息，以及档案所在地FESCO的政策，确认
了所需要的基本材料：双方结婚证、双方独生子女证、双方婚育情况证明、未领取或已
退还小谢独生子女费的证明、小谢出生证明和独生子女证、第一胎准生证。
此外，美女程凑巧与一有二胎的同事户口所在地一样，于是，积极借鉴他的经验，了解
到需要准备双方父母的结婚证或婚育证明。这是因为街道需要证明我们的父母们只结了
一次婚，只生了一个孩子。
综合上述情况，美女程积极发动双方父母搞定了他们的结婚证（居然能找到，上面还印
着革委会的章，以及办酒席用的鱼肉票已领的证明）
第二步：个人准备阶段：
美女程充分利用自己和FESCO的关系，迅速搞定了自己的婚育证明以及没有领取独生子
女费。但是档案在海淀人才的谢同学迟迟无法搞定。美女程果断地要求谢同学把自己的
档案转移到FESCO，并因此搞定谢同学的婚育证明以及独生子女费问题。此举证明极其
英明，因为这样在后续无数次要求FESCO盖章的时候，美女程都可以一次性搞定两个人
需要的章。
解决掉存档单位证明问题后，美女程很挠头的就是如何撰写《二胎指标申请书》。根据
同事的说法，街道会无数次刁难，因此美女程希望尽可能地完善准备，减少被挑刺儿的
机会。百度了多次后，选择了网络上可以看到的最完善的一个版本参考写了自己的申请
书。结果发现，最重要的一句话 -- 双方都是独生子女 -- 压根没有体现在模板中。
除了写，就是大量的复印。所以你能想到的文件都要复印。
第三步：初次提交：
美女程她娘受托带着厚厚的材料跑了街道办事处。办事处说这事情要先回居委会。只有
居委会审批通过后才上报街道。亲爱的娘带着材料来到了居委会，居委会说二胎事宜必
须有指定居委会办理。亲爱的娘再次奔波到了指定居委会。太佩服亲爱的娘了，这么偏
僻的地方她都能找得到。
指定居委会说：材料复印方式不对，必须要A4纸竖着印，复印材料退回。双方父母光有
结婚证不行，谁知道他们有没有离婚未登记啊。所以需要双方父母4个人的单位的人事
部门出具初婚证明且说明只生了一个孩子。感谢政府感谢党，幸好4位的单位都还健在
，要不然我不知道应该怎么开这个证明。指定居委会说，怎么没有填写专用申请表呢？
（靠，我都百度那么久，就是没有找到所谓的专用申请表，压根就是你们没有贴出来嘛
，凭啥challenge我？）亲爱的娘热情地找人要了好多份回来。幸亏要了好多份，要不
然以后就惨了。还有还有，指定居委会说：“两个孩子年两差距不到5岁，与规定不符
！”幸亏我对我娘进行了充分的宣传。亲爱的娘理直气壮地回答：“俺闺女过30了，符
合规定！”指定居委会从此在这个问题上沉默了。
第四步：再次提交：
根据指定居委会的意见，美女程迅速展开修复工作，在两周之内按要求搞定了所有文件
以及复印件。材料之多，俺的1.8米双人床都铺满了
指定居委会继续挑刺：这个女方父亲怎么能用一代身份证呢？这个男方母亲的户口本页
面不平整，有涂改嫌疑，还是让派出所证明一下吧！另外，专用申请表上夫妻两个既然
只有一个孩子，就不用把孩子的信息填两遍了！（那为什么设计表格的时候不加个说明
啊！）那个夫妻作为申请人怎么没有在每一页材料上签字啊？（靠，不是你说的，要等
你在每页材料上盖章以后我才能签字吗？而且日期还要按照你说的签）
第五步：第三次提交：
美女程继续改进，终于准备好了所有材料，要去指定居委会正式提交。指定居委会大姐
说她忙，不一定在，预约也不一定在。这个时候，守株待兔是个好方法。亲爱的娘和美
女程在指定居委会大姐上班前40分钟到了她的办公室门口候着，终于在那个穿金戴银的
大姐上班的时候逮到了她。大姐这次实在挑不出毛病，只好登记造册接收。大姐说：“
要过年了，都很忙，等通知吧。正常30个工作日。你怎么不早点办啊？你这样医院能接
收你？现在规定没有指标不能产检！”美女程满脸堆笑：“慢慢来，您别急。产检的事
情我自己搞定就好。”
第六步：出其不意地提前被批准：
周一，指定居委会给亲爱的娘打电话，说批完了，年前来拿吧。哇咔咔，政府效率很高
嘛。从周一开始，小龙女阿当同志终于有了合法身份了。为了这一天，回想过去那次次
准备，就当是个纪念吧。幸亏我们的父母们东西保存得好，幸亏他们的单位都在，要不
然这个指标是绝对办不下来滴。
最后综述所有材料清单：
夫妻双方准备：户口本、结婚证、身份证、本人独生子女证、单位出具初婚证明、独生
子女费未领取或退还证明、二胎指标申请书（个人拟）x1、二胎指标申请表（居委会给
）x2、一胎准生证（政府收回）、一胎出生证、一胎独生子女证（政府收回）。特别说
明，如果一胎独生子女证丢失，一胎独生子女证夫妻双发申请表可以作为证明
夫妻双方父母准备：结婚证、身份证、户口本、单位出具的初婚未离且只生育一个子女
的证明
上述所有文件为原件，必须配套复印件。提交材料时，原件与复印件必须同时提交。待
原件审核通过后，复印件加盖审核通过章，申请人（夫妻其中一方）亲笔签字，并按照
要求签署日期
f*4
3 楼
应该没有吧
假设存在O(nlgn)，则有
T(n) = 2T(n/2)+f(n)
需要f(n) = O(n)
考虑2n+1个数
n个1， n个3
3 3 3 3...3 1 1 1 1...1 2
用reverse()改成
1 1 1 1...1 2 3 3 3 3...3
需要 f(n) = n + n*( (n+1)+n) = O(n^2)
最后需要的run time 是O(n^2)
假设存在O(nlgn)，则有
T(n) = 2T(n/2)+f(n)
需要f(n) = O(n)
考虑2n+1个数
n个1， n个3
3 3 3 3...3 1 1 1 1...1 2
用reverse()改成
1 1 1 1...1 2 3 3 3 3...3
需要 f(n) = n + n*( (n+1)+n) = O(n^2)
最后需要的run time 是O(n^2)
a*2
4 楼
可能average是O(nlogn)就可以了吧
我当时给的解法就是O(n^2)
对i找到1到i里面最大的值arr[j]然后reverse(j),reverse(i)
明显他不满意，后来说quicksort，选第一个或者最后一个做pivot好像不行，如果题目
改成reverse(i,j)就好了
我当时给的解法就是O(n^2)
对i找到1到i里面最大的值arr[j]然后reverse(j),reverse(i)
明显他不满意，后来说quicksort，选第一个或者最后一个做pivot好像不行，如果题目
改成reverse(i,j)就好了
f*4
5 楼
reverse(i,j){
reverse(j);
reverse(i);
reverse(j);
}
谁来分析一下avg？
【在 a**********2 的大作中提到】
: 可能average是O(nlogn)就可以了吧
: 我当时给的解法就是O(n^2)
: 对i: 找到1到i里面最大的值arr[j]然后reverse(j),reverse(i)
: 明显他不满意，后来说quicksort，选第一个或者最后一个做pivot好像不行，如果题目
: 改成reverse(i,j)就好了
reverse(j);
reverse(i);
reverse(j);
}
谁来分析一下avg？
【在 a**********2 的大作中提到】
: 可能average是O(nlogn)就可以了吧
: 我当时给的解法就是O(n^2)
: 对i: 找到1到i里面最大的值arr[j]然后reverse(j),reverse(i)
: 明显他不满意，后来说quicksort，选第一个或者最后一个做pivot好像不行，如果题目
: 改成reverse(i,j)就好了
d*d
6 楼
这里的reverse是算O(n)呢还是算O(1)呢?
h*3
7 楼
到底是reverse还是排序阿?我糊涂了
f*1
8 楼
exchange(i,j){
reverse(i,j);
reverse(i+1,j-1);
}
so nlogn ?
【在 f****4 的大作中提到】
: reverse(i,j){
: reverse(j);
: reverse(i);
: reverse(j);
: }
: 谁来分析一下avg？
reverse(i,j);
reverse(i+1,j-1);
}
so nlogn ?
【在 f****4 的大作中提到】
: reverse(i,j){
: reverse(j);
: reverse(i);
: reverse(j);
: }
: 谁来分析一下avg？
f*4
9 楼
给的是
reverse(i); // 0~i reverse
除非说是 reverse(i) O(1)
不然很怀疑有 nlgn
【在 f*********1 的大作中提到】
: exchange(i,j){
: reverse(i,j);
: reverse(i+1,j-1);
: }
: so nlogn ?
reverse(i); // 0~i reverse
除非说是 reverse(i) O(1)
不然很怀疑有 nlgn
【在 f*********1 的大作中提到】
: exchange(i,j){
: reverse(i,j);
: reverse(i+1,j-1);
: }
: so nlogn ?
m*t
10 楼
这个就是Bill Gates上大一的时候发表的一篇数学论文，关于翻松饼次数的上下界，其
实就是这种reverse排序次数的分析。有兴趣者可以找来读一下。
实就是这种reverse排序次数的分析。有兴趣者可以找来读一下。
m*t
11 楼
查了一下，这个问题叫做pancake sorting，在数学上来说并不简单，已经研究了几十
年。现在最好的结果是需要执行reverse的次数介于(15/14)n 和 (18/11)n之间。
http://en.wikipedia.org/wiki/Pancake_sorting
年。现在最好的结果是需要执行reverse的次数介于(15/14)n 和 (18/11)n之间。
http://en.wikipedia.org/wiki/Pancake_sorting
q*x
12 楼
这里假定reverse(1)和reverse(100)代价相同？
【在 m****t 的大作中提到】
: 查了一下，这个问题叫做pancake sorting，在数学上来说并不简单，已经研究了几十
: 年。现在最好的结果是需要执行reverse的次数介于(15/14)n 和 (18/11)n之间。
: http://en.wikipedia.org/wiki/Pancake_sorting
【在 m****t 的大作中提到】
: 查了一下，这个问题叫做pancake sorting，在数学上来说并不简单，已经研究了几十
: 年。现在最好的结果是需要执行reverse的次数介于(15/14)n 和 (18/11)n之间。
: http://en.wikipedia.org/wiki/Pancake_sorting
f*4
13 楼
学习了～
【在 m****t 的大作中提到】
: 查了一下，这个问题叫做pancake sorting，在数学上来说并不简单，已经研究了几十
: 年。现在最好的结果是需要执行reverse的次数介于(15/14)n 和 (18/11)n之间。
: http://en.wikipedia.org/wiki/Pancake_sorting
【在 m****t 的大作中提到】
: 查了一下，这个问题叫做pancake sorting，在数学上来说并不简单，已经研究了几十
: 年。现在最好的结果是需要执行reverse的次数介于(15/14)n 和 (18/11)n之间。
: http://en.wikipedia.org/wiki/Pancake_sorting
相关阅读
数学教育 一家之言 III: 中美比较花生酱能用来做什么？女儿7岁半了，还兜尿布哪里有卖亲子装的？转载：How to raise a bilingual child碰到一个对我说,我儿子只会说no的妈妈请推荐三岁孩子用的电动牙刷转一个shutterfly free calendar code 换包子紧急求助，女儿头上长虱子了!Melissa & Doug 多少折扣算deal？我也贴贴娃的lego生日party那些装饰的和goody bag都到哪里买啊？关于英语对算术能力的负面影响(3)大家给孩子报名上学的时候都怎么填语言那项的支原体感染英文怎么说孝应该是optional的,而不是required200伪币，求shutterfly FREE SHIPPING code小朋友几岁可以看电视？我儿子为我们长脸了 (转载)大家都怎么清洗杯子里的吸管的？