Re: [轉錄]Re: [代碼] GCJ
※ 引述《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
推
08/03 12:35, , 1F
08/03 12:35, 1F
推
08/03 13:26, , 2F
08/03 13:26, 2F
→
08/03 14:01, , 3F
08/03 14:01, 3F
推
08/03 15:47, , 4F
08/03 15:47, 4F
推
08/03 15:54, , 5F
08/03 15:54, 5F
推
08/05 00:27, , 6F
08/05 00:27, 6F
討論串 (同標題文章)
完整討論串 (本文為第 2 之 2 篇)：