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。

至此,该题得到了解决。

注重积累

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

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

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

CERC2013 Problem E 勇者斗恶龙

地址:http://codeforces.com/gym/100299(要登录了点进gym才能成功传送)
很有意思的一个Problem。

一棵树上,勇者在1号点,初始血量是0。每个点有一个权值,踩上去血量会加上$$delta_i$$,这个值可正可负。勇者任何时候血量不能低于0。问勇者能否到达某个目标点T。
国际惯例$$1 \leq n \leq 10^5, -10^6 \leq delta_i \leq 10^6$$

看了solution以后才写出来的。
其实看之前已经有一些零零碎碎的idea。就是组织不起来。

  1. 按道理可以把结果组织成带拓扑关系的pair的形式。pair的第一个元素表示至少要多少血量才能进去,第二个元素表示进去以后能增加多少血量。通俗说就是每个血泉的门槛。
  2. 进去以后血量会更亏的地方没有必要走进去
  3. 应该转化成最多能获得多少血量的问题。

先看最后一点,转化的方法是从需要到达的点连一条边到一个新的点,这个新的点值是无穷。最后只要看最多能获得的血量是不是达到无穷就行了。

然后剩下的就是solution最神棍的地方。在求解“最多能获得多少血量”的前提下,因为最优性的原则可以把一棵树化归为一种理想结构:拓扑关系为一条链的pair。并且满足上面提到的第2条(即每对pair里加血总比扣血多),以及依赖越浅的pair,门槛越低。也就是说,把他看成数组的话,门槛递增。

证明分两步。

  1. 证明:假设是一条链的依赖关系,那么可以视作以上提到理想结构。

    1. 显然一条链上相邻的正值和相邻的负值可以合并。于是必然正负交错,可以构成pair。
    2. 依赖关系最深的pair(就是最后一个),如果first >= second,那么可以直接扔掉。因为根据最优性,永远不会选它。
    3. 对于相邻的pair,如果previous.first >= previous.second(扣血比补血多),那么这个pair必然可以和后面一个合并。原因是根据最优化目标的原则,不可能取了previous就不取next。所以previous和next要么同取要么同不取,所以理应合并。
    4. 对于相邻的pair,如果previous.first >= next.first(伤血门槛不递增),那么previous和next必然可以合并。原因是:根据前面两条,所有的pair都满足first < second,所以根据最优性能取都取掉最好。所以都是贪心去取就好了。如果next门槛比previous还低,那么做完previous肯定顺便做掉next。其实这里条件可以更紧一点,取previous.first >= preivous.first – previous.second + next.first作为合并条件也可以AC的,但是前面那个已经足够了。
  2. 证明:假如每个分支下的子树都是链,那么该子树也可以看成链。
    其实就是数学归纳法的意思。然后这个只要把每个分支下的pair按first顺序列成一行就可以了。

综上,用multiset<pair <long long, long long>>维护链就可以了。

#include <cstdio>
#include <vector>
#include <set>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair <ll, ll> PLL;
typedef multiset <PLL> MS;
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define foreach(it,v) for (__typeof((v).end()) it = (v).begin(); it != (v).end(); it++)
const int N = 200005;
const ll INF = 1e15;
int Tc, n, m;
vector <int> E[N];
MS pool[N];
ll a[N];

MS* merge(MS *a, MS *b) {
    if (a->size() < b->size()) swap(a, b);
    foreach (it, *b) a->insert(*it);
    b->clear();
    return a;
}

MS* dfs(int u, int fa) {
    MS *res = &pool[u];
    rep (i, E[u].size())
        if (E[u][i] != fa)
            res = merge(dfs(E[u][i], u), res);
    PLL cur = a[u] > 0 ? PLL(0, a[u]) : PLL(-a[u], 0);
    while (!res->empty() && (cur.second < cur.first || cur.second >= res->begin()->first)) {
        PLL tmp = *res->begin();
        res->erase(res->begin());
        cur = tmp.first > cur.second ? PLL(cur.first - cur.second + tmp.first, tmp.second) : PLL(cur.first, cur.second - tmp.first + tmp.second);
    }
    if (cur.second > cur.first) res->insert(cur);
    return res;
}

int main() {
    scanf("%d", &Tc);
    while (Tc--) {
        scanf("%d%d", &n, &m);
        rep (i, n + 1) E[i].clear();
        rep (i, n) {
            int x;
            scanf("%d", &x);
            a[i] = x;
        }
        rep (i, n - 1) {
            int u, v;
            scanf("%d%d", &u, &v);
            u--; v--;
            E[u].push_back(v);
            E[v].push_back(u);
        }
        --m;
        E[m].push_back(n);
        E[n].push_back(m);
        a[n++] = INF;
        MS *res = dfs(0, -1);
        ll hp = 0;
        bool flag = 0;
        foreach (it, *res) if (hp >= it->first) {
            hp += it->second - it->first;
            if (hp >= INF / 2) flag = 1;
        }
        res->clear();
        puts(flag ? "escaped" : "trapped");
    }
    return 0;
}