作者scan33scan33 (亨利喵)
标题[转录]Re: [代码] GCJ
时间Sun Aug 3 04:02:22 2008
又来献丑了XD
每次看了大家的想法都觉得焕然一新呀！
所以又来抛砖引玉了
※ [本文转录自 scan33scan33 信箱]
作者: scan33scan33 (负け组み) 看板: grosmil
标题: Re: [代码] GCJ
时间: Sun Aug 3 03:56:51 2008
http://code.google.com/codejam/contest/dashboard?c=agdjb2RlamFtchALEghjb250ZXN0cxiL4AYM
我只有写两题a,b：
a.
给一颗tree，leaves有value，internal node是AND,OR gate，뜊|evaluate下面两个value的&,|值(皆是bool)，问你怎样可以改变最少的
internal node，让root evaluate成V(0 or 1)
就单纯tree dp，从下面做上来。
dp table长这样：
dp[node编号][node的值] = 最小改变数
b.
这题就是给正整数A求
是否找的到在一个grid上3个皆为grid points的triangle面积为A/2
grid大小为n*n (n=10000)
A最大是10^8
观察一：
如果存在，一定有一个从(0,0)开始的三角形符合以上条件。
证明想法：旋转＋平移。
观察二：
固定(0,0)以後，假设其他两点是(a,b),(c,d)。A = |ad - bc|
let ad > bc： A = ad -bc
因此对grid所有格子做a,d的search
因为ad - A = bc，所以就对每个求出的ad做(ad-A)的因数分解，
看看有没有办法弄出一个bc在grid上。
注意：如果ad-A = 0，那直接随便assign一个valid的b,c给他,
where b*c = 0 <-- 这条害我吃了WA
时间复杂度是O(n^2*p(1000)),where p是1000以下的质数
d.
有种encoding方法，就是给一个k,一个string s
k个k个一组做permutation，把s map到一个 string t。
(Ex:
base = 开始分段的点
permu[] = {0~k}的一种排列;
for(int i=0;i<k;i++) t[i+base] = s[permu[i]+base];
这样叫做一种permutation
)
问你under some permutation
，t有最少有几组连续字母的substring？
(
Ex:
aaabbbccc
是三组(a,b,c)
)
--
※ 发信站: 批踢踢兔(ptt2.cc)
◆ From: 119.14.139.216
※ 编辑: scan33scan33 来自: 119.14.139.216 (08/03 04:15)