本篇看点PKU1011、PKU1013。
PKU2000
模拟题，没用公式，暴力0MS过了
代码 #include < stdio.h > int main(){ int i,n,c,sum,pay; while (scanf( " %d " , & n),n) { sum = 0 ; pay = 1 ; c = 0 ; for (i = 1 ;i <= n;i ++ ) { sum += pay; c ++ ; if (c == pay) { c = 0 ; pay ++ ; } } printf( " %d %d\n " ,n,sum); } return 0 ;}
PKU1218
又是模拟题，题意：监狱门原本都锁着，经过n次题述操作后，看有多少监狱门是开着的。
代码 #include < stdio.h > #include < string .h > int main(){ int i,j,n,a[ 102 ],cas,sum; scanf( " %d " , & cas); while (cas -- ) { scanf( " %d " , & n); memset(a, 0 , sizeof (a)); for (i = 1 ;i <= n;i ++ ) { for (j = 0 ;j <= n;j += i) a[j] ++ ; } sum = 0 ; for (i = 1 ;i <= n;i ++ ) if (a[i] % 2 ) sum ++ ; printf( " %d\n " ,sum); } return 0 ;}PKU1664
思想：
①最少的盘子放了一个，这样每个盘子至少一个，n个盘子先放上n个，剩下的m-n个可以随便放
②最少的盘子没有放，这样剩下的n-1个盘子还是随便放m个
代码 #include < iostream > using namespace std; int find( int m, int n){ if (m < 0 ) return 0 ; if (m == 0 || n == 1 ) return 1 ; return find(m - n,n) + find(m,n - 1 );} int main(){ int t,m,n; scanf( " %d " , & t); while (t -- ) { scanf( " %d%d " , & m, & n); printf( " %d\n " ,find(m,n)); } return 0 ;}网上搜的解题报告：
看到这道题立即想到了递归的经典案例：整数划分问题。
将正整数n表示成一系列正整数之和：n=n1+n2+…+nk， 其中n1≥n2≥…≥nk≥1，k≥1。 正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。 例如正整数6有如下11种不同的划分： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。
将最大加数x不大于m的划分个数记作q(n,m) 有 1 n=1 || m=1 q(n,m) = { q(n,n) n<m 1+q(n,n-1) n=m q(n,m-1)+q(n-m,m) n>m>1 重点在n>m>1的情况。 呵呵，当时我还花了好些功夫才理解到哦，真是精妙。有了这一点经验，放苹果的问题就容易了，我们也有递归式 将在m个盘中放n个苹果记作fun(m,n)，且不能有空盘。（题目中的可以有空盘 不方便递归，我们循环累加） 对于fun(m,n) 1 n=1||m=n resulut = 0 n<m ∑ fun(n-m,i) n>=m , i=1..n 当n>=m时，是不是方法和整数划分问题的n>m>1时很像呢？呵呵
PKU1011,PKU1013清华大学的《程序设计导引及在线实践》书上有详细讲解，这里就不多说了……
PKU1013枚举
代码 #include < stdio.h > #include < string .h > char left[ 3 ][ 7 ],right[ 3 ][ 7 ],result[ 3 ][ 5 ]; bool isLight( char x){ int i; for (i = 0 ;i < 3 ;i ++ ){ switch (result[i][ 0 ]){ case ' u ' : if (strchr(right[i],x) == NULL) return false ; break ; case ' e ' : if (strchr(left[i],x) != NULL || strchr(right[i],x) != NULL) return false ; break ; case ' d ' : if (strchr(left[i],x) == NULL) return false ; break ; } } return true ;} bool isHeavy( char x){ int i; for (i = 0 ;i < 3 ;i ++ ){ switch (result[i][ 0 ]){ case ' u ' : if (strchr(left[i],x) == NULL) return false ; break ; case ' e ' : if (strchr(right[i],x) != NULL || strchr(left[i],x) != NULL) return false ; break ; case ' d ' : if (strchr(right[i],x) == NULL) return false ; break ; } } return true ;} int main(){ int n; char c; scanf( " %d " , & n); while (n -- ){ for ( int i = 0 ;i < 3 ;i ++ ) scanf( " %s%s%s " ,left[i],right[i],result[i]); for (c = ' A ' ;c <= ' L ' ;c ++ ){ if (isLight(c)){ printf( " %c is the counterfeit coin and it is light.\n " ,c); break ; } if (isHeavy(c)){ printf( " %c is the counterfeit coin and it is heavy.\n " ,c); break ; } } } return 0 ;}PKU1011递归
代码 #include < stdio.h > #include < stdlib.h > int cmp( const void * a, const void * b){ return * ( int * )b - * ( int * )a;} int n,sti[ 100 ],used[ 100 ]; int slove( int k, int left, int len){ int i; if (k == 0 && left == 0 ) return 1 ; if (left == 0 ) left = len; for (i = 0 ;i < n;i ++ ) { if (used[i] == 1 ) continue ; if (sti[i] > left) continue ; used[i] = 1 ; if (slove(k - 1 ,left - sti[i],len)) return 1 ; used[i] = 0 ; if (sti[i] == left || left == len) // 重点理解 break ; } return 0 ;} int main(){ while (scanf( " %d " , & n),n) { int i,sum = 0 ,minlen,len; for (i = 0 ;i < n;i ++ ) { used[i] = 0 ; scanf( " %d " , & sti[i]); sum += sti[i]; } qsort(sti,n, sizeof (sti[ 0 ]),cmp); minlen = sti[ 0 ]; for (len = minlen;len <= sum;len ++ ) { if (sum % len != 0 ) continue ; if (slove(n, 0 ,len)) { printf( " %d\n " ,len); break ; } } } return 0 ;}
转载于:https://www.cnblogs.com/DreamUp/archive/2010/07/22/1783278.html
相关资源：POJ、HDU、ZOJ、SOJ水题过滤器