[ACM] POJ 3274 Gold Balanced Lineup 解题报告, 对数组Hash

算法很简单, 就是记录各个feature的累积和数组, 数组稍作处理, 只要能够比较 [让能够相减得出答案的两个数组] 的”形状”.
比如

111      111      000
110      221<=    110
111      332      110
010      342      120
001      342      120
100      443<=    110
010      453      120

中间一列的221和443的”形状”一样, 也就是相减能得到答案, 所以稍作处理都减去最右边的数即可, 方便比较.
问题是者离散化以后也有100000的数据怎么记录, 好吧我开始用的二叉树后来发现想错了..
无耻的Google以后发现对数组Hash的方法.. 很汗颜 太洋气了.. 跑2xxMS

代码:
Read More

[ACM] POJ 3277 City Horizon 解题报告, 线段树+离散化

第一道线段树.. 略难。 引用忘了哪看的一句话“10亿的的数据规模是任何数据结构都无能为力的,所以必须离散化”。因为略复杂我用class写的…yzhw牛说“线段树编程复杂度太高,一般用树狀数组或者STL set。不要class,class运行爆慢” 但是哥就是用class和链表过了,怎样!! 1200ms.. 不过后来看了一下Google到用Pascal的蒟蒻牛的代码,发现树狀数组果然好用!

hw给了我篇论文,我发现现在的程度知道了一个数据结构的意思&&一些优化比如“lazy”,写出来的东西details上面大家都差不多的。比如这道题目的lazy我也是加了个-1作标签说明下面的节点需要递归确认,即这一块不是一大块一样的

优化有二:
1. compress()  每次插入完一个building以后沿着树往下看有没有标记为-1但是左右子树height(toLoad)相等的,如果有合并左右子树。实践证明这个优化对这题的数据用处不大,反而拖到了1800ms…
2. 这个厉害了,没它我算5000的数据都要跑半分钟,而还有两组40000的数据,加了这优化4w的秒出。也是刚刚那篇里提到的“观察发现,线段树的建树、统计操作已难以再优化,但插入操作却任可以优化。由于一开始房子的高度无序,所以每次插入如果全部包含不能直接赋值,还需要向下递归左右子树。其实我们可以先将房子的高度排序,然后再依次插入,这样一旦全部包含就可以直接赋值,程序的效率大大提高。这样这道题就可以AC了。”

代码:

Read More

[ACM] POJ 2133 Cow Imposters, easy DP + BFS

简单DP + BFS
牌子之间两两组合出新牌子, 新产生的牌子只需与原始的号码两两组合即可,即,不用考虑两个新牌子组合的情况,因为两个新牌子组合的结果必然等价与一个新牌子和原始牌子组合的结果, 否则会超时。

很自然的就可以用类似BFS里的队列来做, 我由此引发的思考是, 这种新牌子和原始牌子组合到达新point, 和BFS的思想是十分一致的, 我可以把每一个原始牌子看作一个方向, 牌子号码的每一位是一维空间。 比如 01001 这个原始牌子, 对应了一个五维空间, 这个原始牌子的方向就是 ( 0, 1, 0, 0, 1 ) 。 题目就能抽象为, 给出一个B维的空间和可以走的E个方向, 问你能到达离某个点最近的维度
Read More

[ACM] POJ 1205, 简单DP

DP就是每次在原序列右边加一个city的时候 (此时n个city) 只要看前一个状态 (n-1个city) 最右边的city的情况
也就是记录n个city时的三个状态 xxxV xxx> xxx<
xxxV 和 xxx< 的数量和就是要求的结果, xxx>是记录一下如果允许向右流水那么方案的数量
状态转移即为右图
然后dp[100]结果超过long long, 于是用BigInteger, 写这个报告的原因也是第一次用Java交OJ..

代码:


import java.math.*;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		BigInteger dp[][]=new BigInteger[101][2];
		dp[1][0]=BigInteger.ONE;
		dp[1][1]=BigInteger.ZERO;
		for(int i=2;i<=100;i++) {
			dp[i][0]=dp[i-1][0].add(dp[i-1][0]).add(dp[i-1][1]);
			dp[i][1]=dp[i-1][0].add(dp[i-1][1]);
		}
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()) {
			int a=sc.nextInt();
			System.out.println(dp[a][0].add(dp[a][1]));
		}
	}
}

[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 2594 求有向图(允许路径重叠的)最小路径覆盖, Floyd + 匈牙利算法

大飞同学问我这一题, 图论的东西我是一点都没看过, 直接看了discuss
做这题用了得有十个小时.. 我可是连二分图都不知道是什么..
然后什么是二分图匹配

最小覆盖数 == 节点数 – 最大匹配数

为什么呢, 数学归纳一下, 匹配数为0时显然 最小覆盖数 == 节点数, 然后有一个二分图匹配就能把两个覆盖路径合二为一, 很简单. 具体的在ufo008ahw这里有所说明
扩展阅读: Matrix67牛有一篇文章介绍了二分图最大匹配的König定理及其证明

求二分图最大匹配匈牙利算法或者最大流(这个我还没看- -).
有向图转化成二分图很简单, 把每个节点变成两个节点(在二分图两边)一个负责入一个负责出即可

至此我们已经可以解决有向图的最小路径覆盖问题. 允许路径重叠的情况怎么办呢, 明显是要转化成不允许路径重叠的情况来依葫芦画瓢, 想要在求二分图最大匹配的过程中考虑允许重叠的情况我想过.. 没想出来, 难度吹牛逼一样.

怎样转化: 用Floyd求一下传递闭包即可, 这个我想了好久才明白, 我来说明一下
比如有向图G: 1->2->3 4->2->5
解释是: 对于任何的有重复节点的路径, 比如这里的2, 求了传递闭包以后的图就会包含1->3和4->5这两个路径, 实现”跳过去”的走法

Floyd没什么好说的, 关于匈牙利算法(初次接触)的一些细节:

1. 下面这个代码的我是看的这里, 这个数据结构和递归太牛了..做完我整个人都犀利了. 它是只记y指向x不记x指向y, 每次对x搜索可用的y, 而不是记录它们, 整个操作都简单了好多. 原文的注释写的很好
2. 代码中的visited[] 这个验证我列举了各种情况, 是正确的, 有点难度
3. 算法的原理我很清楚了. 但是代码里x和y双重循环, 为什么x和y各循环一遍就ok了我还是没有理解太透彻, 这也是匈牙利算法的精髓吧

代码点下面:
Read More

[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 1887 2533 解题报告, LIS的nlogn算法..

记录到当前位置combo数为k的尾巴的最小值, 比如 1 3 2 6, 则 dp[combo]=tail 罗列为 dp[1]=1, dp[2]=2 (1,2的尾巴比1,3等小), dp[3]=6, combo最大为6. 然后再多加一位就看能不能更新前面combo数对应的tail, 让tail更小; 当然还看combo数能不能+1. 比如1 3 2 6再加个5, dp[3]就=5 (1,2,5的tail比1,2,6的tail小), 不加5加7就多一个dp[4]=7. 因为dp[combo]值相对于combo数是递增的, 所以可以二分查找实现nlogn.

这两个是买一送一的题目.. 1887的二分写的有点蛋疼.. 2533要求不能相等, 就加了个标记每次对二分的两个指针p0,p1, 和中点(p0+p1)/2看一下, 重复就continue, 不重复一样做, 省得麻烦.. 想了一下还可以前面严格<, 后面可以>=, 这样更新tail的时候就不会重复产生影响.

代码点下面:
Read More

[ACM] POJ 2430 解题报告, 状态压缩DP, 奶牛你太懒了..

从左到右DP, 存储哪里有奶牛以后排序, 同一个x坐标的上下奶牛合并.. 0没有 1上 2下 3都有
随着奶牛的位置x从左到右DP, 需要记录的状态是dp[i][p][k], p是在x处的奶牛圈起来的方式, 我记的是 0没圈(这就初始状态可能) 1圈上 2圈下 3两个一起圈 4两个分开圈, 记录每个可能的k和对应的面积最小值
状态转移比较麻烦.. 我是又分两个状态之间的圈圈怎样互相结合来枚举,  0不结合 1上边延伸出去 2下边 3两边一起延伸 4两边分开延伸. 应该还有更巧妙的方法.. 不想再碰这题了
172ms 直接大数组20M内存..代码点下面
Read More

[ACM] POJ 1230 贪心, 数据结构

挺简单的算法我没想出来..

考虑最左边的需要移除墙的列。这列是必定要移除一些墙的。
不妨移除右边界较大的那些墙。
实现的时候,可以用基数排序的方式来找到右边界较大的墙。
开两个数组如下:
map[i][j] = { 第i列中,从该列开始向右延伸,长度为j的墙的数目}
cnt[i] = {第i列中墙的数目}
这样代码比较方便,速度也快。          ——荣誉属于糯米

糯米的这个数据结构非常棒, 我做了一点改进: 糯米记录了右边还有多长的墙, 实际上只要记录右边墙的边界就可以了, 省掉一些计算和思维复杂度
所以我的代码精简一点, 看我的吧 🙂

这种题一眼看上去像DP, 我看了点东西说DP和贪心有很多相似之处, 比如都是找最优子结构. 区别在于贪心从最优子结构里选出一个或几个就行. 具体有什么区别也没太搞清楚, 感觉DP有一个图的延伸, 每个状态都可能被多次使用, 而贪心不会.

代码点下面:
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 1161 解题报告, 图论, 几何

好繁的一道题.. 看走眼了 1061才是数论题..才发现 思路:

区域看作一个Vertex, 对每个区域BFS求出能到达所有club的和最小值. 复杂度N2
Edge的构造:  一个region周围的点集按顺时针是 {p1, p2, p3 .. pk} 那么 (p1, p2) (p2, p3) … (p(k-1), pk) (pk, p1) 就是它的所有border, 其中任何一条边 (p[j], p[(j+1)%n]) 与也只与另外一个region’ 共享,  而region’ 做取边操作的时候, 这条共享边是颠倒的, 即 (p[(j+1)%n], p[j]) , 所以构造一个二维数组p[][], 上下三角形是对称的, 一对对称的元素就代表了相连的两个区域
club就存在所有靠着它的region内, 在这些region里面此club的步数都是0

细节:

以后这种繁题把变量名起的明白一点.. 多写点注释,  不然容易糊涂, 不太好写函数(其实可以.. 懒)

110行, 跑47ms, 还不错的样子..

Update: 这题数据比较弱, 用floyd简便很多, 因为为BFS准备比较麻烦, floyd直接开个数组全∞了事.. 复杂度N3

代码点下面 (没有任何可读性可言..)
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] POJ2353 POJ3612解题报告

POJ2353
穷逼DP时间复杂度O(n*m*m), 我想的就是这个..
牛逼DP时间复杂度O(n*m), 每一个room的状态都只能由左下右三个room决定, 从底向上双向递归..

POJ3612
把dp[i][h]分成两部分求解, 两部分可以分别以O(100)预处理, 求dp[i][h]是O(1), 所以整个复杂度只有O(n*100), 很棒
引用牛kevin0602的讲解(他的博客已经进不去了.. 不知为何)

先分h’大于h和小于h两种情况,这方程可写为f(n, h) = (H[i]-h)^2 + min { -C*h + min { f(n-1, h’)+C*h’ } (for h’ >= h),C*h + min { f(n-1, h’)-C*h’ } (for h’ < h) },这样就把h’放在一起了,现在定义low(n, h) := min over h' >= h { f(n, h’)+C*h’ },high(n, h) := min over h’ < h { f(n, h')-C*h' },则可方程进一步写为f(n, h) = (H[i]-h)^2 + min { -C*h+low(n-1, h), C*h+high(n-1, h) }。在计算第n个电线杆的时候,low(n-1, h)和 high(n-1, h)用双重DP的方法可以在O(100)*3的时间内算出,则总时间复杂度为O(N*100)。

双向DP有点类似双向BFS, 两次BFS后可以O(1)求通过某点的入口-出口路径, 这两个题每一个状态都是可以表示成从两个状态比较来. 以后遇到类似的题目要警觉一下.. 或许还有三向之类的衍生..

代码:
Read More

[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;
}

[ACM] POJ1159解题报告, LCS

引用大牛lnmm的思路

设ch[1]..ch[n]表示字符串1至n位,i为左游标,j为右游标 ,则i从n递减,j从i开始递增。
min[i][j]表示i和j之间至少需要插入多少个字符才能对称,初始置全0 ,我们最终需要得到的值是min[1][n]. 则
if(ch[i]==ch[j])                                    //如果两个游标所指字符相同,向中间缩小范围
min[i][j]=min[i+1][j-1];
else
min[i][j] = 1 +  (min[i+1][j]和min[i][j-1]中的较小值);     //如果不同,典型的状态转换方程

画个图

i\j  1    2    3    4    5
1    0    *    *    *    *
2    0    0    *    *    *
3         0    0    *    *
4              0    0    *
5                   0    0

求右上的三角形即可, 三个方向, 左, 下, 左下, 和算法导论里353页的图思路差不多, 意思不一样而已.
一个自以为比较有意思的空间优化是, 把头顺时针转45度看那个三角形.. 不讲了麻烦, 上代码..

404K 344MS G++

#include <stdio.h>

int main()
{
    int n;
    char a[5010];
    scanf("%d",&n);
    while(getchar()!='\n');
    scanf("%s",a);

    int c[10010];
    for(int i=2;i<=2*n;i++) {
        c[i]=0;
    }

    for(int x=1;x<=n-1;x++)
        for(int i=1;i<=n-x;i++) {
            int j=i+x;
            char ai=a[i-1],aj=a[j-1];
            if(ai==aj)
                continue;
            c[i+j]=c[i+j-1]<c[i+j+1]?c[i+j-1]:c[i+j+1];
            c[i+j]++;
        }
    printf("%d\n",c[1+n]);

    return 0;
}

[ACM] POJ1185解题报告 状态压缩DP

思路和网上的都差不多, 我另外开了程序算出每一行可能的情况直接copy进 stack[] 中..耍流氓.. 看起来直观点
引用一下大牛BYVoid的思路, 不自己写了

较难看出的动态规划问题。注意到数据范围N≤100;M≤10,发现每行的宽度都不大,所以可以考虑把一行看成一个状态,表示该行的布置方案。每行的布置方案可以预先处理出,由数学知识可以算出,每行最多的布置方案数也不过60个而已。

状态设定

F[i,a,b]为前i行,第i行的方案为A[a],第i-1行的方案为A[b]的最大炮兵数。

状态转移方程

  • F[i,a,b]=Max{ F[i-1,b,c] + P[a] }

其中c为i-2行的布置方案,a,b,c应保证互不冲突,即放置方案中炮兵都在平地上,且不会互相攻击到。

目标结果

  • Ans=Max{F[N,a,b]}

中间进行过一次错误的优化, 认为如果, 比如
画个图..

    HHPH
    PPPP
    PPPP
    HHPH  (红色代表有炮)

1001比1101少了一个1, 那么1101得出的结果至少不会比1001差, 可以剪掉1001. 比如上图的第三行, 没有炮的情况就可以省去,.我当时的想法是如果省掉第三行的炮, 放在第四行唯一的P上(其他情况也是相似),  第四行以下面临的情况就会比之前更加严峻, 从而不会得出更好的结果, 顶多一样.

但是我并没有考虑第三行能对第一行也产生影响 (造成这个错误的原因是状态压缩DP只记录近两行. 虽然没有明面上写, 但是情况已经记录在得分中了). 第三行的P不放炮, 则第一行和第四行都能放, 结果就更好了.

遗留问题, 如何才能在类的定义中实现二维数组的动态分配?

我写成这样

public:
    int *(a[60]);
    State (int m=0) {
        M=m;
        for(int i=0;i<stackN;i++) {
            a[i]=new int[stackN];
            memset(a[i],0xff,sizeof(int)*stackN);
        }
    }

能够compile, 在另开的程序里也没有问题, 但是在题目中答案就不一样, 我跟踪了, 在 s[i].dp(s[i-1]) 的过程中 s[i-1].a[][] 会莫名发生改变, 实际上又没有对它进行任何操作. 值得一提的是release和debug得出的答案不一样, 根据经验应该是内存的什么问题.. 也有可能是类里动态分配内存就不对头, 因为在类中定义变量不能用new..  开学去问问看

Code: (其实是我第一次用类.. 这个问题有点绕, 于是尝试封装=D )

Read More

[ACM] POJ3295解题报告

这是所谓的二叉树么.. 算法很简单, 只是因为第一次用这种结构体封装, 还是试了很多次才摸索出来的.. 很好用诶! 记一下

细节.. 地址和变量不要搞混了.. fw?fw->v():false 我写成了fw->v()? 错了好久

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

struct Orz {
	Orz *fw,*fx;
	bool (*f)(bool w,bool x);
	bool v() {
		return (*f)(fw?fw->v():false,fx?fx->v():false);
	};

bool p[5];
char sb[]={'K','A','C','E','N','p','q','r','s','t'};
char input[201];
int count;

bool fK(bool w,bool x) {	return w&x;		}
bool fA(bool w,bool x) {	return w|x;		}
bool fC(bool w,bool x) {	return !(w&&!x);	}
bool fE(bool w,bool x) {	return !(w^x);		}
bool fN(bool w,bool x) {	return !w;		}
bool fp(bool w,bool x) {	return p[0];	}
bool fq(bool w,bool x) {	return p[1];	}
bool fr(bool w,bool x) {	return p[2];	}
bool fs(bool w,bool x) {	return p[3];	}
bool ft(bool w,bool x) {	return p[4];	}

bool (*f[])(bool w,bool x)={fK,fA,fC,fE,fN,fp,fq,fr,fs,ft};

Orz *proc() {
	char a=input[count++];
	Orz *node=(Orz *)malloc(sizeof(Orz));
	node->fw=node->fx=NULL;

	int type;
	for(type=0;sb[type]!=a;type++);
	node->f=f[type];

	if(type<=4)
		node->fw=proc();
	if(type<4)
		node->fx=proc();
	return node;

}

int pow2(int n) {
	int r=1;
	for(int i=0;i<n;i++)
		r*=2;
	return r;
}

int main() {
	while(1) {
		gets(input);
		if(input[0]=='0')
			break;
		count=0;
		Orz *bigBang=proc();

		short tester;
		for(tester=0x0000;tester<=0x001f;tester++) {
			for(int i=0;i<5;i++)
				p[i]=tester/pow2(i)%2;
			if(bigBang->v()!=true)
				break;
		}

		if(tester==0x0020)
			printf("tautology\n");
		else
			printf("not\n");
	}

	return 0;
}

[ACM] POJ1837解题报告, 背包..

求严格背包, 这次要求是所有物品都必须使用, 问有多少种填满的方法(具体看题)

如果只问能否填满(这样看来又不能把v=重量*杠杆长度看成物品了, 不是传统背包..好难归纳) 那只要用bool型数组记录, 因为不能不用 所以用两个数组更替(a0[i]==true doesn’t mean a1[i]==true, so.)

问有多少种方法把bool换成计数器即可

2010/08/05 Update:
在”能不能放满”(或者填满特定容量) 这种题型中, 以下三种情况是可以让我们求”符合要求的组合有多少种”
1. 一个物品具有多种可选的体积. 比如在本题中是”在物品体积可变, 并且能够为负的情况下, 能不能使占用空间恰为0(平衡)”
2. 物品可以选择不用
3. 1&&2
原因很简单, 上面三种情况的补集是”物品体积固定并且必须全用”, 这种情况最后占用的容积是常数, 逆否命题即上面的蓝字部分成立.

细节:
int *a=(int *)malloc(sizeof(int)*20001);  //sizeof(a)==4
int a[20001];  //sizeof(a)==80004;
混淆了一下 导致数组不能初始化, 结果是诡异的3 (答案是2)
debug的时候数组里是非常混乱的 (比如a0[9999]==-265219901)
但是release的时候数组即使不初始化也都为0, 但不一定(诡异的3就是因为某个数==1, 应该初始化为0的, 和内存前面的写入有关吧)

代码:

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

int main() {
    int *a0,*a1;
    int C,G,c[20],g[20];

    a0=(int *)malloc(sizeof(int)*20001);
    memset(a0,0x00,sizeof(int)*20001);
    a0[10000]=1;
    scanf("%d%d",&C,&G);
    for(int i=0;i<C;i++)
        scanf("%d",c+i);
    for(int i=0;i<G;i++)
        scanf("%d",g+i);

    int v;
    for(int i=0;i<G;i++) {
        a1=(int *)malloc(sizeof(int)*20001);
        memset(a1,0x00,sizeof(int)*20001);

        /*/debug
        for(int k=9900;k<=10100;k++)
            if(a0[k])
                printf("a0[%d]=%d, ",k,a0[k]);
        printf("\n");//*/

        for(int j=0;j<C;j++) {
            v=g[i]*c[j];
            for(int i=19000;i>=1000;i--)        //order doesn't make sense.
                a1[i+v]+=a0[i];

            /*/debug
            for(int k=9900;k<=10100;k++)
                if(a1[k])
                    printf("a1[%d]=%d, ",k,a1[k]);
            printf("\n");//*/

        }
        free(a0);
        a0=a1;
    }

    printf("%d\n",a0[10000]);

    return 0;
}