作者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)