分类存档：默认分类

SRM 614

250

三次方枚举卡住左方，下方，以及右方/上方，再一个for计算矩形内的点，n^4暴力。

其实枚举前两个之后，每个点要求的len是固定的，按这个sort能达到n^3 lg n的复杂度。

525

这题比赛的时候没有过是很不应该的……就是一个很典型的dp。回忆一下这场SRM的过程，总结了一下为什么写这种计数自己经常会写但写得很慢。得出以下几点：

  1. 我想的过程中，经常会陷入局部情况或者说特例的求解，这样弄得最后整个代码就非常混乱，往往写出很多种情况，而这会极大的降低编码的效率。
  2. 组合计数问题，对独立的步骤进行划分是尤为重要的。而不同情况下每个步骤的操作都是类似的。把类似的过程统一处理往往能得到事半功倍的效果。
  3. 总得来看，其实这是architecture上的失败和大局观上的失败。

既然意识到了这个问题，那就在以后练习/比赛的时候注意提高吧。

算法大致是分小环和大环dp。

小环通过一个函数统一处理：count(int x, int y, int n, bool o)。这个函数返回的是，在小环上，一个接口在x号点，另一个接口在y号点，整个环的人数是n，x接口和y接口的颜色是否相等时的方案数。这个conut可以通过递推进行预处理(只和两条独立的链有关)。

然后在大环上，用g[i][j]表示处理完前i个小环，给下面的接口的颜色和“第0个环给第n-1个环的颜色”是否相等。再次递推。

最后输出g[n-1][0]即可。

1000

这题就是给定N, M, goalX, goalY求下面这个函数……

  1. 当i = goalX, j = goalY, f(i, j) = 0
  2. 其他情况 f(i, j) = (f((i + 1) % N, j) + f(i, (j + 1) % M)) / 2 + 1

输出f(0, 0)即可。

规模有100，迭代是可行的一个做法。

但是这样的迭代是过不了的……

        clr(f, 0);
        rep (it, 10000) {
            rep (i, N) rep (j, M) {
                if (i != goalX || j != goalY) {
                    int ni = (i + 1) % N, nj = (j + 1) % M;
                    f[i][j] = 1 + (f[ni][j] + f[i][nj]) / 2;
                }
            }
        }

这是因为顺序不科学导致的……因为(goalX, goalY)才是不动点，这样盲目地走看上去就很悲剧。
假设现在我在goalX, goalY，那么我影响到的路线应当是沿着-1方向过来的。
所以改成下面这样迭代顺序就过了。

        clr(f, 0);
        rep (it, 10000) {
            rep (_i, N) rep (_j, M) {
                int i = goalX - _i, j = goalY - _j;
                if (i < 0) i += N;
                if (j < 0) j += M;
                if (i != goalX || j != goalY) {
                    int ni = (i + 1) % N, nj = (j + 1) % M;
                    f[i][j] = 1 + (f[ni][j] + f[i][nj]) / 2;
                }
            }
        }

除了迭代以外，对于这种互相依赖的关系，迭代矩阵的又是满秩的，高斯消元解方程也是一个选择。那么假设M+N-1个未知量，其中M个在同一行，N个在同一列(为了方便，最好把不动点放在交错的位置)。这样其它的所有函数值都可以表示为这N+M-1个未知量的线性组合。绕了一圈一个，就可以得到M+N级别个方程，而M+N只有200，高斯消元是没有压力的。

但是zYc大师说好像有问题，等下写个代码看看能不能过。

更新
这个高斯消元算法是可以AC的。
代码在此

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，别的强盗数值不变。代码如下：

#include 
#include 
#include 
using namespace std;

int main(){
	int m,n;
	scanf("%d%d",&m,&n);
	vector u;
	u.push_back(n);
	for(int i=2;i< =m;i++){
		int c=i/2,sum=0;
		vector v=u;
		sort(v.begin(),v.end());
		for(int j=0;jn){
			u.insert(u.begin(),-1);
		}else{
			v.swap(u);
			u.insert(u.begin(),n-sum);
		}
	}
	printf("%d\n",u[0]);
}

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

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

#include 
#include 
#include 
using namespace std;

int main(){
    int m,n;
    scanf("%d%d",&m,&n);
    vector u;
    u.push_back(n);
    for(int i=2;i< =m;i++){
        int c=i/2,sum=0;
        vector v=u;
        sort(v.begin(),v.end());
        for(int j=0;j 0 && c < i - 1 && v[ c - 1 ] == v[ c ]) c--;
        for(int j=0;jn){
            u.insert(u.begin(),-1);
        }else{
            v.swap(u);
            u.insert(u.begin(),n-sum);
        }
    }
    printf("%d\n",u[0]);
}

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

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

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

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

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

至此，该题得到了解决。

注重积累

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

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

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