Tag Archives: Number Theory

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

Speak

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

快放假了, 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的也八九不离十了.. 这个代码还是很精简很漂亮的

[cpp]

#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;
}
[/cpp]

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

Speak

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

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

5 Replies

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

理论基础

首先需要了解的是..
序理论(中文) 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’ 的极小元, 过程如下

[cpp]
(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)
[/cpp]

因为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 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即可
[cpp]
#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;
}
[/cpp]

[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:
[cpp]
#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;
}
[/cpp]