SRM 613

250

枚举分隔的位置,左边的一起向左,右边的一起向右。统计答案即可。

500

看了WJMZBMR的代码才明白过来T_T,容斥太弱了。算出区间内每个数包含的素因子。然后因为要gcd变为1,所以可以看成不能包含素因子Pi这若干个条件的与。接着就可以用容斥原理了。

900

看了芒果的代码才明白过来。首先是不能一行一行来填,这样dp的状态太难表示。

然后考虑一列一列来填。

  1. 假如只有left的话,就可以f[i][j]来表示填好前i列,其中有j列还没分配的时候的方案数。然后这个j其实蕴含了前面有j列是要填东西的,但是还没决定填在哪些行这么个意思。然后遇到left的结束端点,就可以拿这些数目去分配。大致就是乘个A几几的组合数。
  2. 现在如果有right的话,可以按left反过来那样处理,但是现在要统一起来,只能考虑从左往右填。由于一个行进入可填范围就不会变没了,所以f[i][j]表示填好前i列,还有j行没搞定。于是每次可以选择(或者不选)一个行,用当前列来填上。
  3. 最后把前两种dp合起来,f[i][j][k]转移一下就好了。

2014年的春游

本来今天打算做opencup的,结果早上一起来发现猛犸半夜发了条消息说今天出题。于是屁颠屁颠地跑去参加东莞帮的春游了。

首先是订的餐厅正门在装修,绕了几百米才进到去。我只能说十分感动……然后饭桌上miffy说要玩我是间谍。我表示从来没玩过,但是还是作为大菜鸟加入了这个游戏。但是我没有想到我的信誉就在这个游戏中破产了……

首先是大家抽到“女人”,学妹抽到“小三”。我第一个说,直接就说了麦当劳N年前的广告词“我就喜欢”。结果第一轮就被投死了(这是说明小伙伴都认为我是gay吗 )……然后后来学妹说“男人都挺喜欢的”,我当时就十分感动,终于有学妹同意我的观点了。结果最后发现学妹一直以为我说的是我喜欢小三。我立马感觉膝盖中了一枪……

后来有一次我抽到“爱做”,大家抽到“做*爱”。然后大家都说这词太坑爹不玩,我还不知道自己是卧底,大声说这回我可以说我就喜欢了吧!然后发现大家眼神不对劲……

后来跟着大队去逛西湖和太子湾。我说这是我第一次去太子湾,然后被学妹鄙视成马。

逛完以后发现坐公交回不来了,步行了很长一段时间以后遇到一个车10块一个人载到黄龙。大家都犹豫上不上……由于我记得那段路长得简直坑爹,于是直接就说了不管你们上不上,反正我是要上了。于是大家也一起上了,然后顺利回到玉泉正门。回来以后我跟阿龟老莫介绍了正门的波霸奶茶,于是一起去喝了一杯,我们都表示大颗的珍珠十分给力,下次还来……

Andrew Stankevich Contest #13 Problem B 海盗分金问题

题目地址
Problem B Bandits

ASC是质量很高的一套题目,在codeforces的gym上开放了第1~30套。

其中多为智商题。这也就意味着,如果一题不会做,你可能想很久,查阅了很多资料,还是不会做。前几套的题解可以在shi哥的博客上找到。后面的好像就没什么题解了。当然codeforces上的红色账号可以看到标程。可是既然是智商题,本来不会做的,看了标程也往往是不明白的……

随着我们team备战ACMICPC World Finals 2014,ASC 16-30都被我们训练过了,网络上又缺乏题解,于是考虑陆陆续续写一些我们team在训练时候没有想出来的题的题解。因为学校课程/实习面试/训练/英语课等原因,我自己时间也不是特别多,于是不可能像shi哥那样一套一套地完整写了。但是我写的题对于没有达到Topcoder Codeforces双红的算法竞赛选手大概还是很有意义的。

这个海盗分金是个经典问题,但是其实不容易想对。而且条件变一下策略也要跟着变化。这题题意是这样的:

有n个海盗和m块钱(1 ≤ n, m ≤ 2000),他们要分这些钱。

分钱流程如下:先给每个强盗依次记上编号1~n。然后1号强盗提出一个钱的分配方案(也就是指定每个人获得多少钱)。剩下的人(包括1号强盗本身)对这个方案进行投票,如果支持提案的人数严格大于半数人,那么这个方案被通过,大家按数目分钱;而如果不通过,则大家把1号强盗杀掉。剩下的强盗编号都减一,人数减一,再次分钱。

假设强盗们都绝顶聪明,并且他们都认为彼此绝顶聪明。

一个强盗会反对投票,当且仅当他知道当前这个人被投死了以后,他一定会存活下来,并且获得至少和当前提案相当的金币。

现在,请你回答第一个强盗最多能提案分配给自己多少钱而不被杀。如果无论如何都会被杀,输出-1。

很容易想到倒着推,每个强盗用一个数值表示他在最坏情况下能获得的钱。可能死则用-1表示。然后每次在前面加入一个强盗,他就可以收买那些最容易收买的人。把后面的强盗的数值从小到大排序,给这些人的数值加一块钱,就能得到他的支持,用这种方式收集够票数以后,剩下的钱就是自己的了,于是把被他收拢的强盗的数值都加1,没被他收拢的强盗数值都设为0;而如果钱不够……那这个强盗就死定了,直接填入一个-1,别的强盗数值不变。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(){
	int m,n;
	scanf("%d%d",&m,&n);
	vector<int> u;
	u.push_back(n);
	for(int i=2;i< =m;i++){
		int c=i/2,sum=0;
		vector<int> v=u;
		sort(v.begin(),v.end());
		for(int j=0;j<c ;j++) sum+=++v[j];
		for(int j=c;j<i-1;j++) sum+=v[j]=0;
		if(sum>n){
			u.insert(u.begin(),-1);
		}else{
			v.swap(u);
			u.insert(u.begin(),n-sum);
		}
	}
	printf("%d\n",u[0]);
}
</c></int></algorithm></vector></cstdio>

然后你就会得到Wrong Answer on 36……问题出在哪里呢?

下面给出AC的代码可以先思考一下为什么。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(){
    int m,n;
    scanf("%d%d",&m,&n);
    vector<int> u;
    u.push_back(n);
    for(int i=2;i< =m;i++){
        int c=i/2,sum=0;
        vector<int> v=u;
        sort(v.begin(),v.end());
        for(int j=0;j<c ;j++) sum+=v[j] + 1;
        while (c > 0 && c < i - 1 && v[ c - 1 ] == v[ c ]) c--;
        for(int j=0;j<c;j++) ++v[j];
        for(int j=c;j<i-1;j++) v[j]=0;
        if(sum>n){
            u.insert(u.begin(),-1);
        }else{
            v.swap(u);
            u.insert(u.begin(),n-sum);
        }
    }
    printf("%d\n",u[0]);
}
</c></int></algorithm></vector></cstdio>

可以看到,后面的代码和前面的差别在于对数值相等的强盗的变化进行了一些处理。

但是为什么是这样?我们甚至可以发现海盗算当前分配方案的时候sum值的计算和v值的修改是不对应的。可以先想一想而不急着看下文。

其实关键是:当前的这个海盗的选择具有任意性。

首先解决第一个问题,为何sum值和之前的计算一样?答案是当前强盗作出的决策必须能够收买超过半数人。

再来第二个问题,为何v值的变化要把和vc等值的被收买的强盗的v值也设为0?答案是这些强盗不知道当前强盗会不会选到自己,所以他们的最坏情况下得到的金币是0。

至此,该题得到了解决。

Dreyfus模型

Dreyfus模型将学习的过程分为五个不同的阶段或水平:

1.新手(Novice)需要详细的指导——要手把手地教。新手不知道这些指导是否有效,或者哪些指导更加重要;因为没有上下文知识可供他们使用进行评估。因此,新手需要频繁迅速的成就感和有规律的反馈。一本好的入门指导书籍要提供有足够多的图画和充足的可靠信息。

2.高级初学者(Advanced Beginner)对基本步骤——单独的任务——已经熟悉了,而且可以把它们进行有机的组合。高级初学者仍然在很大程度上是面向任务而不是面向目标的,不过他们已经开始有些概念了。这也是一个学习者最危险的阶段——他们知道自己学到的已经不少了,但是这还不足以让他们远离麻烦!刚学走路的孩子在很多方面都是高级初学者。有了足够的经验,高级初学者就能拥有足够的能力以胜任某些工作。

3.在胜任(competent)水平上,他们就走到面向目标阶段了。他们可以组合一系列任务以达成某个目标。也许任务的组合顺序不是最佳的,但是通常都可以发挥作用。有能力的人希望给定一个目标,然后能够得到别人的信任来达成这个目标。相反,如果要是试图详细告诉他们应该怎么做,这些有能力的人就会觉得很烦躁,就像是汽车里被坐在后面座位的乘客指手画脚的司机一样。大部分人在大部分技能上很难超越“胜任(competent)”水平,即使他们在每天的日常工作中使用这些技能。这是人类的基本特性——一旦有所收获,我们就不想再投入精力了,而且对于大部分活动来说,所谓的收获只不过是把工作做完而已。

注:已经能够分解目标和组合一系列任务来完成目标,这是胜任的关键。

4.在精通(Proficient)水平上,解决方案开始在人的心目中“慢慢浮现”——而且通常已经完全成型。他们已经具备了在直觉中形成解决方案主要部分细节的能力,之后就可以根据自己先前的经验积累来对解决方案进行映射。一个精通的人需要对其行动的上下文有更广阔的了解,并且开始享受隐喻和格言(以及相反的类似内容)带来的乐趣。他们仍然会回头根据接受的基于规则的训练,来验证自己行为的正确性;但在这个阶段他们已经学着相信自己的判断了。从“新手”发展到“胜任”阶段基本上是线性的过程,而到“精通”阶段代表了一个台阶的提升。一个人必须积极选择才能促成这个转变的开始。通过对某件事情重复足够的次数是可以达到“胜任”的,但要变想得“精通”,必须要有明确的心理诉求才行。

注:在精通阶段,从规则(Rule)到直觉(Intuition)的质的变化,已经能够将显性的知识转化为自己的宝贵经验和方法论。在这里是需要明确的心理述求和自我领悟。

5.专家(Expert)水平:正如从“胜任”到“精通”的转变一样,转变为“专家”也是非线性的过程。要想成为某个领域的专家,可能要花费数年的努力才能达成。这些人工作时几乎完全是从直觉自发的状态,而且很少犯错误。专家生活在模糊的世界之中。她以自己的能力为傲,而且喜欢通过与其他专家交流来校正和提高自己的技能。有趣的是,处于初级阶段的人们倾向于过高估计自己的能力,而在较高阶段的人则更加谦逊。

注:完全的融会贯通,自觉自发,形成了自我的解决问题的方法论和模式,往往已经是无招胜有招。

以上内容转自:新浪博客

翻了翻dd学长的twitter看到这个东西,很有感触。

实际上很多时候我们解决问题的方法都是将一些已有知识进行组合。而这个组合的能力,则决定了自己到底处于哪个层次。

在以前,我是很享受那种想出新颖的方法解决某个问题的感觉的。随着后来的成长,我渐渐发现我所谓的新颖方法肯定是借鉴了某些类似的经验或者思想的。有时候所借鉴的思想甚至可以和这个领域看似毫无关系。

这也就是所谓的知识结构。完全逃离自身知识结构的创新我觉得是不太现实的。我感觉即使是很牛的人,能做的往往也是从自己的知识结构体系中取出内容进行组合。

所以结论是我所该做的内容有两个:一是提升知识量的大小;二是提高对知识组合的能力。

个人看法,欢迎讨论。

注重积累

每次回家和父亲聊天都感觉自己实在太弱了。
探寻原因,终究是积累上的差距实在太大。
即使我能很快明白原理,也没办法做和他一样的事情。
概括而言,自己需要注重的积累包括这几个方面:

  1. 专业知识的积累。在实践中注意观察底层的运作方式,知道其中利害。思考的过程中,注意了解相关法律。知悉什么能做,什么不能做,还有就是:什么说不清楚能不能做,又没什么人敢做。
  2. 知识面上的积累。通识上的差距。与各行各业的人均应有交集,遇人需要有共同的话题以及比较独到的见解。
  3. 交际技巧上的积累。首先是礼仪:端茶递水、敬酒、倾听、谈话、问候、祝福、送礼等,其实自己总结来看,就是七个字:不以自我为中心。再者是比较适合交际的活动:高尔夫、桌球、羽毛球、乒乓球、斗地主等。
  4. 经济实力上的积累。无话可说……
  5. 人脉和社会认同程度上的积累。亦即有头有面。在这基础上可以做的事情就太多了。但是这一点是以前面的内容为基础的。没有前面的支撑,一味地追寻人脉,得到的很可能也只是镜花水月吧。

真希望10年后我不再是今日捉襟见肘、纸上谈兵的赵括。
也希望以后我的小孩能接受到至少和我相当的指引和教育。
:Happy: