这一篇的看点PKU1088、PKU1012。
PKU1008
分析：先按H历法算出总天数，再模T历法一年的天数的到T历法的年，
但T历法没月的概念，只是两个独立循环的组合，所以分别模20和13就能得到结果。
数据4. uayet 259应输出13 ahau 364。
代码 #include < stdio.h > #include < string .h > int main() { char HM[ 19 ][ 10 ] = { " pop " , " no " , " zip " , " zotz " , " tzec " , " xul " , " yoxkin " , " mol " , " chen " , " yax " , " zac " , " ceh " , " mac " , " kankin " , " muan " , " pax " , " koyab " , " cumhu " , " uayet " }; char TD[ 20 ][ 10 ] = { " imix " , " ik " , " akbal " , " kan " , " chicchan " , " cimi " , " manik " , " lamat " , " muluk " , " ok " , " chuen " , " eb " , " ben " , " ix " , " mem " , " cib " , " caban " , " eznab " , " canac " , " ahau " }; int i,j,n,Hyear,Hday,Tyear,tds; // tds是totaldays总天数 char Hmonth[ 10 ]; scanf( " %d " , & n); printf( " %d\n " ,n); for (i = 1 ;i <= n;i ++ ) { tds = 0 ; scanf( " %d.%s %d " , & Hday,Hmonth, & Hyear); tds += 365 * Hyear + Hday; // 按Haab历计算总天数 for (j = 0 ;j < 19 ;j ++ ) // 循环累加求一年里的天数 if (strcmp(HM[j],Hmonth) == 0 ) { tds += j * 20 ; break ; } Tyear = tds / 260 ; tds = tds % 260 ; printf( " %d %s %d\n " ,tds % 13 + 1 ,TD[tds % 20 ],Tyear); // 要加1 } return 0 ; }
PKU1163
分析：这是老师给的动态规划课件里面的一道例题，即数塔问题。和HDU2084题目一样，要是不懂题意可以去那里看中文。动态规划思想，从数塔下面往上面动态最优求和。
代码 #include < stdio.h > int ma( int n, int m){ return n > m ? n:m;} int main(){ int n,a[ 102 ][ 102 ]; int i,j; while (scanf( " %d " , & n) != EOF) { for (i = 0 ;i < n;i ++ ) for (j = 0 ;j <= i;j ++ ) scanf( " %d " , & a[i][j]); for (i = n - 2 ;i >= 0 ;i -- ) for (j = 0 ;j <= i;j ++ ) a[i][j] = ma(a[i][j] + a[i + 1 ][j],a[i][j] + a[i + 1 ][j + 1 ]); printf( " %d\n " ,a[ 0 ][ 0 ]); } return 0 ;}
PKU1088
求一个二维数组的最长递减序列的长度（一个点滑向上下左右相邻四个点之一）,对每个点都作为起点搜一次。
如果用常规的广度优先搜索方法，重复的子问题太多。对于其中的每个值都要广度搜索一次，找出其能够搜出的最大搜索次数，然后找出所有点的最大搜索次数的最大值。
用记忆化搜索，添加一个二维表，记忆每个搜索过的点的最大递归次数，当下一次搜索到该点时，就可以直接从二维表中直接取出来用就可以了。
代码 #include < stdio.h > #include < string .h > int r,c,map[ 102 ][ 102 ],f[ 102 ][ 102 ]; int dir[ 4 ][ 2 ] = {{ - 1 , 0 },{ 1 , 0 },{ 0 , 1 },{ 0 , - 1 }}; bool ok( int x, int y){ return (x >= 0 && x < r && y >= 0 && y < c);} int find( int x, int y){ int i,fx,fy; if (f[x][y] > 0 ) return f[x][y]; for (i = 0 ;i < 4 ;i ++ ) { fx = x + dir[i][ 0 ]; fy = y + dir[i][ 1 ]; if (ok(fx,fy) && map[x][y] > map[fx][fy] && f[x][y] < find(fx,fy) + 1 ) f[x][y] = find(fx,fy) + 1 ; } return f[x][y];} int main(){ int i,j,mediate,max; while (scanf( " %d%d " , & r, & c) != EOF) { for (i = 0 ;i < r;i ++ ) for (j = 0 ;j < c;j ++ ) scanf( " %d " , & map[i][j]); memset(f, 0 , sizeof (f)); max = 0 ; for (i = 0 ;i < r;i ++ ) for (j = 0 ;j < c;j ++ ) { mediate = find(i,j); if (max < mediate) max = mediate; } printf( " %d\n " ,max + 1 ); } return 0 ;}
PKU2027
太水了，不多说了。
PKU1012
约瑟夫问题，我先查到了位置坐标公式：f[i]=(f[i-1]+m-1)%(n-i+1);然后看了discuss上《总结三点》帖子
1.要kill的人的位置公式p=(p+m-1)%rest+1
2.kill的位置<k就break，此时剩下的人rest等于k就成功
3.m不要递增，m是k+1的整数倍或者k+1的整数倍加1，这样会提高不少
第三点不明白，就让m递增了，超时。
后又查找第三点的原因，在ericxieforever的专栏找到了答案。
另外这一题要把结果打表后再输出，不然还会超时。
分析：先引入Joseph递推公式，设有n个人（0,...,n-1），数m，则第i轮出局的人为f(i)=(f(i-1)+m-1)%(n-i+1),f(0)=0;
依次我们可以来做测试，只要前k轮中只要有一次f(i)<k则此m不符合题意。
接下来我们考察一下只剩下k+1个人时候情况，那么依题意则这一轮出局的人要么在上一轮出局人的左边，要么就在右边，则必有m%(k+1)==0或1
代码 #include < stdio.h > int main(){ int k,m,i; int f,t,a[ 14 ]; for (k = 1 ;k < 14 ;k ++ ){ t = 0 ; for (m = 1 ; ;m += ((t ++ ) % 2 ? 1 :k)){ f = 0 ; for (i = 1 ; ;i ++ ){ f = (f + m - 1 ) % ( 2 * k - i + 1 ); if (f < k){ break ; } } if (i == k + 1 ) break ; } a[k] = m; } while (scanf( " %d " , & k),k) printf( " %d\n " ,a[k]); return 0 ;}
PKU1046
对16以后的每个点从16个三维坐标中找距离最近的点形成映射。
挺简单，就贴代码了。
代码 #include < stdio.h > #include < math.h > const int SIZE = 100 ; int pos[ 100 ]; // 记录对应的最小值所在位置 struct RGB{ int red,green,blue;}colors[SIZE]; double distance(RGB * color1,RGB * color2){ double r = color1 -> red - color2 -> red; double g = color1 -> green - color2 -> green; double b = color1 -> blue - color2 -> blue; return sqrt(r * r + g * g + b * b);} int main( void ){ double dist,min; int count = 0 , r,g,b,i,j,k; while (scanf( " %d%d%d " , & r, & g, & b),r + g + b !=- 3 ) { colors[count].red = r; colors[count].green = g; colors[count].blue = b; count ++ ; } k = 0 ; for (i = 16 ;i < count; ++ i) { min = 0xfffffff ; for (j = 0 ;j < 16 ; ++ j) { dist = distance( & colors[i], & colors[j]); if (dist < min) { min = dist; pos[k] = j; } } k ++ ; } for (i = 16 ,k = 0 ;i < count; ++ i, ++ k) { printf( " (%d,%d,%d) maps to (%d,%d,%d)\n " ,colors[i].red,colors[i].green,colors[i].blue,colors[pos[k]].red,colors[pos[k]].green,colors[pos[k]].blue); } return 0 ;}PKU1050
二维数组找子矩形的最大和。（枚举+DP）
i从0到n-1循环，j从i到n-1循环，对i和j所指的行和其中间的行求和，得到一个一维数组，每次都求出这个一维数组的最大连续子序列，最大值即为结果。
代码 #include < stdio.h > #include < string .h > int map[ 100 ][ 100 ],n,temp[ 100 ],maxNum; void findmaxNum(){ int i,m = 0 ; for (i = 0 ;i < n;i ++ ) { if (m >= 0 ) m += temp[i]; else m = temp[i]; if (m > maxNum) maxNum = m; }} int main(){ int i,j,k; scanf( " %d " , & n); maxNum = - 222222222 ; for (i = 0 ;i < n;i ++ ) for (j = 0 ;j < n;j ++ ) scanf( " %d " , & map[i][j]); for (i = 0 ;i < n;i ++ ) { memset(temp, 0 , sizeof (temp)); for (j = i;j < n;j ++ ) { for (k = 0 ;k < n;k ++ ) temp[k] += map[j][k]; findmaxNum(); } } printf( " %d\n " ,maxNum); return 0 ;}PKU1207
暴力0MS过的
代码 #include < stdio.h > int len( int a){ int t = 1 ; while (a != 1 ) { if (a % 2 ) a = 3 * a + 1 ; else a /= 2 ; t ++ ; } return t;} int main(){ int i,a,b,aa,bb,t,max; while (scanf( " %d%d " , & a, & b) != EOF) { aa = a; bb = b; if (a > b) { t = a; a = b; b = t; } max = 0 ; for (i = a;i <= b;i ++ ) { t = len(i); if (max < t) max = t; } printf( " %d %d %d\n " ,aa,bb,max); } return 0 ;}
转载于:https://www.cnblogs.com/DreamUp/archive/2010/07/22/1783275.html
相关资源：POJ、HDU、ZOJ、SOJ水题过滤器