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

[Lucemia (生の直感、死の予感)]

※ 引述《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
推 scan33scan33:好難理解這樣有沒有所有case@@...
推 wacca:當然沒有呀 沒考慮到A可能是質數的情況
→ wacca:sorry誤會了 但後面那個似乎應該是 (N*M-A)%N, (A+N-1)/N
推 Arton0306:那個code是對的 是第一名的人寫的 可以下載
推 ferng1021:to 3F 他已經把A%N==0的情況分開討論 所以那樣寫沒問題
推 powertodream:唔...這麼神奇...