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

Re: [轉錄]Re: [代碼] GCJ

看板Prob_Solve (計算數學 Problem Solving)作者Lucemia (生の直感、死の予感)時間16年前 (2008/08/03 04:30)推噓5(5推 0噓 1→)

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

※ 引述《scan33scan33 (亨利喵)》之銘言： : 又來獻醜了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以下的質數轉貼我看到據說是b的 O(1) 解 if(A > N*M) printf("Case #%d: IMPOSSIBLE\n", cnum+1, res); else if(A == N*M) { printf("Case #%d: 0 0 %d 0 0 %d\n", cnum+1, N, M); } else if(A % N == 0) { printf("Case #%d: 0 0 %d 0 0 %d\n", cnum+1, N, A/N); } else if(A % N) { printf("Case #%d: 0 0 %d 1 %d %d\n", cnum+1, N, (N*M-A)%N, 1+A/N); } } : 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) : ) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.24.134