[ACM] POJ 1173 解题报告, DP, 逐位确定

我表示是跟着黄伟牛混的.. 他写的报告难以称作报告.. 题目一抄写两句话代码一贴万事, 自己琢磨了好久, 记录一下, 我记性不好喜欢写的详细一点以后自己可以查.. (拓展阅读: 刘未鹏牛的<为什么你应该(从现在开始就)写博客> )

快放假了, ACM + GRE 加油, 不拼命的下场只有一个, 平庸.. 哞

第一问 total number of symbols in BC(n,k,m) 比较容易, 简单DP

dp[n][k][m]=∑dp[n-i][k-1][m]     , i∈[1,m]

第二问 yzhw口口声声“经典的逐位确定方法”..

也就是说, 我们来看 “1111010”(从0位到6位), 简单的讲从高位(0)到低位(6)每一位如果有1, 那么就看, 如果这一位是0, (继承前面的高位后) 低位能形成多少种组合, 把这个组合数加到rank中.
流程是 1[0xxxxx]能有多少组合 即求0xxxxx符合k-1和m的组合(直接用前面求出的dp数组即可, 虽然前面求的是1xxxxx, 但是和0xxxxx数量是一样的), 然后11[0xxxx]能有多少种, 遇到0跳过, 最后看11110[0x]

但是这样并不完全缜密, 我们考虑”10011000″的情况, 按上面的算法进行到第3位的时候, 100[0xxxx], 这个0xxxx是可能产生00011这种组合的, 而放入原文就变成了10000011, 0的长度就超过了. 所以我们想出来的办法是把 0-1 (不包括1到0) 交界处的那个1单独考虑, 看前面有多少位0然后详细说明. 比如100[0xxxx], xxxx只能是以1开头的, 10[0xxx], xxx只能是1xx或者01x, (11x到哪去了? 11x不是在这里的 [特殊情况] 内考虑的, 好好想一下.. 没法讲的太清楚)

代码如下, 写的时候很有自己的想法, 多推敲推敲最后的产品和yzhw的也八九不离十了.. 这个代码还是很精简很漂亮的


#include <stdio.h>
#include <string.h>
#include <algorithm>

int main() {
	int dp[34][34][34];
	memset(dp,0,sizeof(dp));
	//DP
	for(int m=1;m<=33;m++) {
		for(int i=1;i<=m;i++)
			dp[i][1][m]=1;
		for(int k=1;k<33;k++)
			for(int n=k;n<33;n++) {
				if(!dp[n][k][m])
					break;
				for(int i=1;i<=m;i++) {
					if(n+i>33)
						break;
					dp[n+i][k+1][m]+=dp[n][k][m];
				}
			}
	}

	int n,k,m;
	scanf("%d%d%d",&n,&k,&m);
	printf("%d\n",dp[n][k][m]);

	int N;
	scanf("%d",&N);
	while(N--) {
		char a[34];
		scanf("%s",a);
		char color='1';
		int rank=0;
		int kRemain=k;
		int head=0;
		for(int p=0;a[p]!='\0';p++) {
			if(color==a[p])
				continue;
			if(color=='1') {
				color='0';
				kRemain--;
				for(int i=head+1;i<p;i++)
					rank+=dp[n-i][kRemain][m];
			}
			else {
				color='1';
				kRemain--;
				for(int i=std::min(n-1,head+m);i>p;i--)
					rank+=dp[n-i][kRemain][m];
			}
			head=p;
		}
		printf("%d\n",rank);
	}

	return 0;
}

[ACM] POJ 1727 解题报告, 二分+贪心

思路和yzhw牛一样

1. 每一个event它对应的可能的cause是这个event点下面的三角形区域(这个区域是无穷大的)
2. 问 “the latest time at which the earliest cause could have occurred” 就相当于用一条平行于x轴的直线 t=t0 把这些三角形区域拦腰切断(当然, 此线必须在所有event下面), 只准在腰以上的三角形里放cause. 然后用二分求到一个恰好不能再往上移了的直线, 就成了.
3. 可行性判断, 用贪心. 三角形们和直线相交的那个区间就可以代表这个三角形, 因为放在直线以上的cause都可以垂直投影到直线上, 效果更佳.
4. 在这些所有的区间中, 要找出最少的cause个数n, 使得每个区间内都能包含至少一个的cause. 如果这个n<=m, 那么这条直线ok, 否则不ok.
5. 怎么判断呢, 引用yzhw “以区间右端点为第一关键字,左端点为第二关键字进行排序,然后每次贪心的选择当前区间的右端点作为子区间,统计要导出全部区间需要子区间的个数num。” (其实第二关键字是不用排序的, 无所谓).
6. 对应5, 举个例子

---------(A)
   ------
  -------
     --------
        -------
    ------------
                 -----(B)
.....           ......

按照右边界升序排序, 123行显然要放一个点在他们区间里, 放哪呢, “不妨”(这个词表达能力太强了)放在最右边, 即点A处. 然后我们下面所有的左边界< =A的都可以ban掉了, 因为右边界是升序排序的. 这个操作后得到的问题是最优子结构的. 然后到了第7行, A不给力了, "不妨"取一个B. 这些操作整合一下就是维护一个变量rightEdge, 一旦rightEdge不给力就取一个当前区间最右边的点, 同时更新rightEdge至这个点. 之前的错误: 对应6的例子, 我以前是按左边界优先于右边界升序排序的, 那样虽然也对但是无法处理一个区间包含另一个区间的情况, 需要filter一下, filter的过程能写成O(n), 我比较愚钝写的n^2一个case要算2分钟 - -.. 总之这个贪心记住了, 求最小覆盖数 代码点下面: Read More

[ACM] POJ 1065 POJ 3636 解题报告, 数论, 贪心, 偏序集, Dilworth定理

这两道题用的理论都是一样的, 贪心算法很简单, 关键是怎么证明:

理论基础

首先需要了解的是..
序理论(中文) http://zh.wikipedia.org/zh-sg/%E5%BA%8F%E7%90%86%E8%AE%BA
偏序集(中文) http://zh.wikipedia.org/zh-sg/%E5%81%8F%E5%BA%8F%E5%85%B3%E7%B3%BB
Dilworth’s Theorem(wiki没中文) http://en.wikipedia.org/wiki/Dilworth’s_theorem

Dilworth的对偶定理的证明我看的lambda2fei牛这里写的, 英文太长实在是没法看..
Dilworth本身的证明我还没有看.. TODO. 但是lamb牛写的chain(链)和antichain(反链)的转换我一看就明了, 通过这种转换可以很容易的使用Dilworth定理, 同样也可以证明Dilworth定理, 我还没看原本怎么证明的..(稍后update) 这种方法已经很牛逼了感觉

为了文章完整性引用一下他的证明

Dilworth定理说的是:对于一个偏序集,其最少链划分数等于其最长反链的长度。
Dilworth定理的对偶定理说的是:对于一个偏序集,其最少反链划分数等于其最长链的长度。
Dilworth定理先不证,有空再不上来,其对偶定理证明如下:

设一个偏序集S的最少反链划分数是p,最长链长度是r。
1.先证p≥r。这是显然的,因为最长链长度是r,r个元素中的任意两个都可以比较,因此它们必定两两属于不同的反链,因此反链个数≥r,即p≥r。
2.再证r≥p。设X1=S。找出X1的所有极小元组成集合Z1,将其从X1删之,得到X2,再找出X2的所有极小元组成集合Z2(特别注意Z2中的任何元素a2,在X1中必然存在一个元素a1使得a1≤a2,否则a2可以放到X1中,这与X1的选取矛盾),再将Z2从X2中删除,得到X3,……这样一直下去,总存在一个k使得XK不空但X(K+1)为空。这样便得到一条链a1,a2,a3,……,ak,其中ai属于Xi。由于r是最长链长度,因此r≥k。另一方面,我们也得到了一个反链划分,即X1,X2,X3,……,XK。由于p是最少反链划分,因此k≥p。因此有r≥p。证毕。

1065详解

要求的就是集合的chain的划分最小数目.
对于题目中给出的关系P={l <= l’ and w <= w’}, 我们定义关系P’={l < l’ and w > w’} (并不是l<=l’), 那么对于原来关于 P 可比较的两个元素, 关于 P’ 则不能比较, 原来不能比较关于 P’ 就可比较. 相应的 P 的 chain/antichain 就成为 P’ 的 antichain/chain .
这样定义后, 就可以放下原题, 题目变成找一堆元素中的最少antichain数目, 根据Dilworth定理对偶定理的证明过程(如上), 每次剥离出 Xi 中的所有极小元, 直到 Xi 为空, 剥离的次数就是答案 .

剥离的次数 == k== 关于 P’ 的最长chain的长度(对偶定理) == 关于P的最长antichain的长度(chain转换) == 关于P的chain的最少划分数(Dilworth)

有点绕.. 但比看上去简单

实例:
考虑元素集 (1,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,5) (4,1) (5,2) (6,1) (6,7) (7,1)
每次取出关于 P’ 的极小元, 过程如下

(1,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,5) (4,1) (5,2) (6,1) (6,7) (7,1)
                  (3,1) (3,2) (3,3)       (4,1) (5,2) (6,1)       (7,1)
                                          (4,1) (5,2) (6,1)       (7,1)
                                                      (6,1)       (7,1)

因为P’是严格的偏序关系, 每次取出的最小元 x 就要满足找不到 y 使 y P’ x (如果是不严格的偏序就要考虑自反的情况)
怎样取极小元呢, P’ 的极小元是 “在 l 比它小的元素中, 找不到 w 比它大的元素”, 按照代码中的 comp() 排序以后(先l后w), 以这个条件找极小元的集合, 等价于从第一个元素开始找, 后一个元素的w’>=前一个元素的w, 的元素集合. 比如(1,2) (2,3) (2,4) (3,5) (6,7), 满足2<=3<=4<=5<=7, 这样贪心就很简单了

3636详解

和1065基本一样, 有了上面的理论就很好做了. 关键在于 P => P’ 的转换

P={w1<w2 && h1<h2} (大于小于无所谓)
所以 P的”可比较”关系 Pc = {w<w2 && h1<h2 || w1>w2 && h1>h2}
所以 P’c= {w1<w2 && w1>=h2 || w1>w2 && h1<=h2 || w1==w2}
所以 P’= {w1<=w2 && h1>=h2}

这里 P’ 是具有自反性和反对称性的非严格偏序关系.
这里就有一个问题: 集合内元素具有互异性, 但是题目中的元素有可能存在两两相同的, 怎么办?
我们可以想像我们上面讨论的集合是题目中的元素”只保留相同元素中的一个”后的集合, 这个集合中的元素a包含了n个题目中的相同元素, 就有两种处理的方法:

方法一: 把这n个元素看作一个a来”剥离”(取最小元), 1065就是这样, (1,2)(1,2)(1,2)在一起剥离是可以的, 因为1<=1,2<=2, 符合P的比较条件
方法二: 剥离a后a还存在于后来的Xi中, 并且n-=1, 直到n==0 a消失, 3636就要这么干, (1,2)(1,2)是不能放在一起的, 不符题意(P), 可以证明这样干是最优的(如果不取这个最小元, 这次执行后得到的Xi要比取的元素多一个, 不取白不取)

经过思考, 这道题最终要做的贪心是: 先按照w排序, w的互异值从小到大为w1,w2..wk, 然后在w==w1的元素里找到h最大的元素取出, 再在w2中找h最大的元素取出, 并且这些h需要满足条件:比前一个取出的元素的h大, 取完一次result++, 直到取空

代码点下面:
Read More

[ACM] POJ 1183 解题报告

a = (b*c-1)/(b+c) 令m = b+c => c = m-b
推得 m = – (b^2 + 1)/(a – b)
做一下多项式除法后 m = (b – a) + (a^2 + 1)/(b – a) + 2a
所以令k=b – a (由arctan()的函数图像知k>0)

=> m = k + (a^2 + 1)/k + 2a
根据函数图像知道 (0 , 根号(a^2 + 1)]内递减, [根号(a^2 + 1), +∞)内递增, 所以我们需要求两个区间上最靠近根号(a^2 + 1)的使m为整数的k
设 i>=根号(a^2 + 1) 则对于此情况下要求的mi = i + (a^2 + 1)/i + 2a 有 j = (a^2 + 1)/i 使
mi = (a^2 + 1)/j + j + 2a
而 j<=根号(a^2 + 1) 所以右边区间满足情况的i在左边都能找到对应的j, 所以只要搜索左边就行了

k=n..1
找出最先使 (a*a+1)%k==0的k即可

#include <stdio.h>
int main() {
    int a;
    scanf("%d",&a);
    int k=a;
    long long foo=(long long)a*a+1;
    while(foo%k)
        k--;
    printf("%d\n",k+foo/k+2*a);
    return 0;
}

[ACM] POJ1067解题报告, Beatty贝蒂数列

无意看到的题目.. 因为是中文的就猫了一眼, 觉得挺水就做做, 结果一做就是一下午.. NOI还有点名堂

开始觉得就是博弈+简单DP, 右图每一个格子 (a, b) , 玩家一次取石子以后能变成的状态是 (a-i, b) , (a, b-i) , 或者 (a-i, b-i) , 只要路线上存在lose, 赋值为win, 否则赋值lose. 整个表格是对称的. 自底向上DP就可以解决.

然后看了discuss, 存在O(1) 的算法..

Beatty sequence Wiki 讲解 , 看一下就了了..

The positive irrational number r\, generates the Beatty sequence

\mathcal{B}_r = \lfloor r \rfloor, \lfloor 2r \rfloor, \lfloor 3r \rfloor,... = ( \lfloor nr \rfloor)_{n\geq 1}

If r > 1 \,, then s = r/(r-1)\, is also a positive irrational number. They naturally satisfy

\frac1r + \frac1s = 1 \,

and the sequences

\mathcal{B}_r = ( \lfloor nr \rfloor)_{n\geq 1} and
\mathcal{B}_s = ( \lfloor ns \rfloor)_{n\geq 1}

form a pair of complementary Beatty sequences.

For r = the golden mean, we have s = r + 1. In this case, the sequence ( \lfloor nr \rfloor), known as the lower Wythoff sequence, is

  • 1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, … (sequence A000201 in OEIS).

and the complementary sequence ( \lfloor ns \rfloor), the upper Wythoff sequence, is

  • 2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41, 44, 47, … (sequence A001950 in OEIS).

上下两个数列整好组成 lose 状态的坐标 (1,2) (3,5) (4,7) … 至于为什么等我有空会思考update一下 =D 好神奇阿

其中r是黄金分割律, 即 (1+sqrt(5))/2

则如果m在第一个数列里,则

m=[nr]=nr-x
m/r=n-x/r

其中x属于[0,1) , 先求出n再判断m/r是否在等式右边的区间里即可. 再返回n判断输入的b是否在二队列中相应的位置

Code:

#include <stdio.h>
#include <math.h>
#include <algorithm>

//return num in Beatty sequence(r=golden mean), -1 if not belong to
int Br(int m) {
    static const double P=(1+sqrt(5.0))/2;
    double foo=m/P;
    int n=(int)foo;
    if(foo-n>0.999999)
        n++;
    n++;
    if(foo>(n-1/P))
        return n;
    else
        return -1;
}

int main() {
    int a,b;
    while(scanf("%d%d",&a,&b)!=EOF) {
        if(a>b)
            std::swap(a,b);
        int foo=Br(a);
        bool win=true;
        if(foo!=-1)
            if(a+foo==b)
                win=false;
        if(win)
            printf("1\n");
        else
            printf("0\n");
    }
    return 0;
}