※ 引述《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