[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++, 直到取空

代码点下面:
Continue reading →

[ACM] POJ 1161 解题报告, 图论, 几何

Speak

好繁的一道题.. 看走眼了 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

代码点下面 (没有任何可读性可言..)
Continue reading →

[ACM] POJ 1183 解题报告

Speak

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

[Geek Power] 脑力训练之怎样忘记

Speak

本文遵循署名-非商业性使用-相同方式共享协议2.5 转载请注明译者http://axlarts.com 及原文地址
原文http://www.increasebrainpower.com/how-to-forget.html
因为一些事情探究.. 总之这是Google搜”how to forget”的第一篇, 觉得不错译一下..

(概念有点容易混淆，“想法”thought 和“记忆”memory 虽然是不同的概念，但是想法是由记忆产生的，就像你深夜对鬼的恐惧这个thought，是你的记忆综合作用的效果，如果你的记忆中没有鬼这玩意，就不会有这种恐惧，顶多怕个入室抢劫啥的。并且本文探讨的thought显然是不断出现的thought，也就成为了memory，所以某种程度上通用。 –译者的YY)

怎样忘记？一般来说我关于记忆的探讨都是关于提高记忆能力的，但是一名脑力通讯(Brainpower Newsletter, 就是这网站. 译者注..) 的读者写信问我能否写一篇关于如何忘记一些东西的文章。他有一些念头不断浮现以至于他干什么都不能集中。

显然，任何”想要忘记”的直接尝试一般来讲都不会有用。如果我让你现在不要去想一只和房子一样大的红色气球 (在中国你要想像一只比房子大的多的气球. 译者注..)，你阻止自己去想这个飘在空中的气球的一切努力最终都会生成一幅栩栩如生的蓝天白云红气球的画面 :)。只要你还在告诉自己“别想这个了！”，它就会一直飘在你的思维里。

同样的无论你阻止自己去想什么都会这样。“别去想X”让你的注意力无法从X上移开。于是抛开某个念头就需要一些内在的技巧。

注意力是有限的。你只能同时注意有限的东西，你提供给某个事物的注意力越少，它就会越快的淡出你的脑海。所以忘记的关键在于转移注意。

别想你能推倒一段记忆。它几乎能存在于——嗯，你的余生。但是如果每当它闪出来，你都有意的转移你的注意到别的什么上去，它就会逐渐丧失能量，会越来越少的出现，变的虚弱无力…

贴标签是个好办法，就像一些人在思考时做的。举个例子，假设一个不受欢迎的念头开始形成并且干扰了你的精神力场。你可以给它打上标签，“记忆碎片”，或者 “感觉”，或者“反应”。并且可以在此基础上细化，像“只是出于恐惧的胡思乱想－－人在恐惧的时候容易胡思乱想”。然后你能立即把注意力转移到更高产的方面。做足够多这样的工作，不想要的想法和思维”噪音“能够被更快的排除。

另一个可能有帮助的技巧是，把这些破门而入的想法写在 to-do list 上，无论它们是记忆还是以后的计划还是一些担心还是别的什么东西。比如，你可以在黑莓手机上标记某个需要在这周五处理的记忆。这种对记忆的作为“在周五处理”的“分类”让大脑此刻放下它变的更合理、容易。当然，如果它只是不必要的钻牛角尖，当周五来临你猫了眼自己的list，扫过这一项也许会直接在旁边注 “没必要啦”…

这两个技巧的作用程度会根据你的心理偏好变化，但是关键在于记住，你是自己注意力的MASTER！虽然严格来讲本文没有真的讲怎样忘掉一段记忆，但是，你的记忆并不是问题， (虽说这也不是绝对的，但是确实，恐惧本身并不可怕，对恐惧持续的阴影才是可怕的; 而我此刻面临的悲伤情绪，它带来的负面影响比悲伤本身厉害多了。–译者注) 只要它们被放在了正确的位置。也就是说把你的注意力放在正确的地方－－你选择的领域。

失恋的朋友们，我这有一打“记忆碎片”和“再想也没屌用”的标签，有要的么？ 😉

[ACM] POJ2353 POJ3612解题报告

Speak

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)求通过某点的入口-出口路径, 这两个题每一个状态都是可以表示成从两个状态比较来. 以后遇到类似的题目要警觉一下.. 或许还有三向之类的衍生..

代码:
Continue reading →

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

Speak

无意看到的题目.. 因为是中文的就猫了一眼, 觉得挺水就做做, 结果一做就是一下午.. 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] 水题tips集合

6 Replies

以后不好意思放报告就在这记一下心得啦

Continue reading →

[ACM] POJ1159解题报告, LCS

Speak

引用大牛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;
}

无光驱安装win7很给力的途径..

Speak

试了半天在dos下用loadISO加载光盘镜像, 然后有各种问题, ntfs格式不兼容什么的最讨厌了..

然后发现用虚拟光驱就可以.. 之前觉得不行是重启以后虚拟光驱就不挂载了, 但是原来不需要, 只在第一次重启之前才用到CD, 之后需要的文件就被copy到硬盘上了.

1. 制作U盘启动盘, 挂上winPE系统.
2. 安装虚拟光驱, 载入ISO.
3. run setup.exe 就成了..

我原来XP直接2了 winPE没试但是没有不行的理由吧~~

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

Speak

思路和网上的都差不多, 我另外开了程序算出每一行可能的情况直接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]}

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

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 )

Continue reading →

Asher.GG

git gud together

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

理论基础

1065详解

3636详解

[ACM] POJ 1161 解题报告, 图论, 几何

[ACM] POJ 1183 解题报告

[Geek Power] 脑力训练之怎样忘记

[ACM] POJ2353 POJ3612解题报告

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

[ACM] 水题tips集合

[ACM] POJ1159解题报告, LCS

无光驱安装win7很给力的途径..

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

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