PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[轉錄]Re: [代碼] GCJ

看板Prob_Solve (計算數學 Problem Solving)作者scan33scan33 (亨利喵)時間16年前 (2008/08/03 04:02)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串1/2 (看更多)

又來獻醜了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)