百练 2816 红与黑 递归水题

这题貌似搞了好一阵子。。。囧~明明是很简单的题目好不好。。。。
代码能力还是太差。。。好像还做复杂了点 = =！！
或者不需要另外开一个int数组。。。不过算了 = =
本来认为应该是DP的。。。其实感觉DP的思想也是可以的吧。。。
开始的时候没有考虑到四个角的情况，走到边上就return了 = =
后来发现不行，就增大了数组，每条边外面都加一行吧。。。
越看越觉得傻X了。。。囧~





#include“cstdio”
int num[25][25];
char table[25][25];
int x,y;
void get(int a,int b)
{
num[a][b] = 1;    //标记
if(a < 1 || b < 1 || a > y || b > x)return;
if(table[a-1][b] == '.' && num[a-1][b] != 1)get(a - 1,b);
if(table[a+1][b] == '.' && num[a+1][b] != 1)get(a + 1,b);
if(table[a][b-1] == '.' && num[a][b-1] != 1)get(a,b - 1);
if(table[a][b+1] == '.' && num[a][b+1] != 1)get(a,b + 1);
}
int main()
{
int t1,t2,t = 0;
while(scanf("%d%d",&x,&y) && x){
for(int i = 1;i <= y;i ++)
scanf("%s",&table[i][1]);    //输入数据，从[1]开始。。。
for(int i = 1;i <= y;i ++)
for(int j = 1;j <= x;j ++){
num[i][j] = 0;
if(table[i][j] == '@'){t1 = i;t2 = j;}    //清零顺便记录起始位置
}
get(t1,t2);
for(int i = 1;i <= y;i ++)
for(int j = 1;j <= x;j ++)
if(num[i][j])t++;
printf("%d\n",t);
t = 0;
}
return 0;
}


标程就是标程 = =！！
/*
int f(int x, int y){
if(x < 0 || x >= W || y < 0 || y >= H)return 0; // 如果走出矩阵范围
if(z[x][y] == '#')return 0;
else{
z[x][y] = '#'; // 将走过的瓷砖做标记
return 1 + f(x - 1, y) + f(x + 1, y) + f(x, y - 1) + f(x, y + 1);
}
}
*/

POJ 1664 放苹果 递归水题

开始不知道处理M个苹果放N个碟子没有空的问题，和同学讨论了一下，这样可以理解为先在每个碟子上放一个苹果，这样就剩下M - N个苹果，可以在N个碟子上任意放。。。递归了 = =
想清楚了就真的水了。。。。囧~
所以说有时候递归的思路真的蛮清晰的= =！！



#include“cstdio”
int f(int a,int b)
{
if(b == 1 || a == 0)return 1;     //注意a为0的情况
if(b == 2)return 1 + a / 2;    //这里优化了一下 = =
if(a < b)return f(a,a);          //这里wa了一次，无语 = =
return f(a,b - 1) + f(a - b,b);    //分两种情况，有空盘和没有空盘的
}
int main()
{
int n,x,y;
scanf("%d",&n);
while(n --){
scanf("%d%d",&x,&y);
printf("%d\n",f(x,y));
}
return 0;
}

百练 2694 逆波兰表达式 递归

这道题确实很能启发递归的思路啊。。。

但还是要吐槽下百练OJ，明明上面提示人家用cmath，结果G++不认介个。。CE = =

然后改cstdlib过了 = =

难道要用GCC？ = =！！

#include"cstdio"

#include"cstdlib"

double func()

{

char s[20];

double a,b;

scanf("%s",s);

switch(s[0]){

case '+': return func() + func();

case '-': return func() - func();

case '*': return func() * func();

case '/': a = func(),b = func();

if(b) return a / b;

else return -1;    //这里return什么好。。。好像-1也不妥= =

default : return atof(s);

}

}

int main()

{

printf("%lf\n",func());

}

关于子函数的一些思考

前天和海天说起关于编程能力的问题。其实对于编程这东西，从来都是熟能生巧。自从开始做题以后，才慢慢发掘编程基本功真的好重要。简单的说，就是一种思维，或者说是条件反射。当你遇到一个问题，你很自然的会将之细分化，分隔成若干个过程，也就是子函数。这样你就只需要关心子函数的参数输入和返回值。对于整个main函数的流程构成是相当有帮助的。即使是debug的时候也可以很有针对性的进行调试。思路也要比之前只有一个主函数的时候清晰很多。

可以说，子函数就是一种解决问题的思想。对于如何快速的写出各种子函数，这就是考验编程能力的时候了。而main函数则是整个问题的基本思路。这样一道题的代码敲出来就要好看很多了。。。。

个人感觉这里面是有点面向对象的思想....不过想想也是，对象调用的成员函数不正是子函数的一种么？ = =

百练 2755 二叉树 递归水题

常规思路 = =
直接打表出来，两个for找到最先相同的值。。。


#include“cstdio”
int a[20],b[20];
int main()
{
int x,y;
scanf("%d%d",&x,&y);
for(int i = 0;x + y;i ++){
if(x){a[i] = x;x /= 2;}
if(y){b[i] = y;y /= 2;}
}
for(int i = 0;a[i];i ++)
for(int j = 0;b[j];j ++)
if(a[i] == b[j]){
printf("%d\n",a[i]);
return 0;
}
return 0;
}




递归思路：



#include“cstdio”
int common(int x,int y)
{
if(x == y)return x;
if(x > y)return common(x / 2,y);
return common(x,y / 2);
}
int main()
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",common(a,b));
return 0;
}




数据太弱的情况，时间上看不出什么分别，但貌似递归的思路是比较巧妙的。。。。

POJ 1222 EXTENDED LIGHTS OUT 暴力不水。。

喵的各种debug啊~这题从下午2点开始弄到晚上10点，加起来差不多5个多小时 T_T
总是卡在全0和全1的数据上面，我就奇怪了。。。 = =
然后查来查去，tmp数组没重置 = =
我勒个去。。。。wa了3次
细节问题很多啊，代码能力迫切需要提高 = =！！
想清楚题目的思路是一回事，实现起来是另一回事，感觉上很多题思路很清晰但是敲起代码来很困难，这题感觉上是可以写的更简洁些的，但是模拟能力不好啊。。。开始看了题目很久才想明白怎么回事。。。原来是枚举第一行的情况，确实巧妙。。。囧~
看discuss用高斯消元，高级东西矣 = =
线代没学好，翻翻书才行。。。

#include“cstdio”
#include“cstring”


int num[7][8],res[7][8],num2[7][8];


void change(int a,int b)
{
if(!num2[a][b])num2[a][b] = 1;else num2[a][b] = 0;
if(!num2[a-1][b])num2[a-1][b] = 1;else num2[a-1][b] = 0;
if(!num2[a+1][b])num2[a+1][b] = 1;else num2[a+1][b] = 0;
if(!num2[a][b-1])num2[a][b-1] = 1;else num2[a][b-1] = 0;
if(!num2[a][b+1])num2[a][b+1] = 1;else num2[a][b+1] = 0;
}


int main()
{
int n,i,j,k,tmp[8]={0};
scanf("%d",&n);
for(int count = 1;count <= n;count ++){
memset(tmp,0,sizeof(tmp));            //枚举数组忘了重置，debug了N久。。。囧~~
memset(res,0,sizeof(res));            //这个也debug了N久。。。。囧死
for(i = 1;i < 6;i ++){
for(int j = 1;j < 7;j ++)
scanf("%d",&num[i][j]);            //在矩阵中间输入数据

POJ 1543 Perfect Cubes 暴力大水

暴力水题。可优化空间很大 = =
喵的打表还是很有必要的。。。。原来94ms = =
那些个0ms的是怎么回事。。。

164K   47MS    C++    629B







#include“cstdio”
int main()
{
int n,a,b,c,d,i,t[200]={0},cube[101]={0};     //开始数组开小了，白RE了一次 = =
scanf("%d",&n);
for(i = 2;i <= n;i ++)
cube[i] = i * i * i;      //打表优化了一下，节省了一半时间 = =
for(a = 6;a <= n;a ++)
for(b = 2;b < a;b ++)
for(c = 2;c < a;c ++)
for(d = 2;d < a;d ++){
if(cube[a] == cube[b] + cube[c] + cube[d]){
for(i = 0;t[i];i ++)
if(t[i] == b * c * d)break;     //比较乘积，相同就不输出
if(!t[i]){
printf("Cube = %d, Triple = (%d,%d,%d)\n",a,b,c,d);
t[i] = b * c * d;               //不同就加入记录
}
}
else if(cube[a] < cube[b] + cube[c] + cube[d])break;
}
return 0;
}

POJ 1013 Counterfeit Dollar 模拟，暴力 = =

挖一个大坑 = =

这题思路蛮清晰的，就是实现起来好像很麻烦 = =！！

模拟能力还是不够。。。

囧

这奇葩的解法。。。囧~~

#include"iostream"

#include"string"

#include"fstream"

#include"memory.h"

using namespace std;

int main()

{

    int c[12][3];

    int res[3];

    int n, i, j;

    cin>>n;

    while(n--) {

        memset(c, 0, sizeof(c));

        memset(res, 0, sizeof(res));

        string s1, s2, s3;

        for(i=0; i<3; i++){

            cin>>s1>>s2>>s3;

            for(j=0; j

                c[s1[j]-'A'][i] = 1;

                c[s2[j]-'A'][i] = -1;

            }

            if(s3=="even"){

                res[i] = 0;

            }

            else if(s3=="up"){

                res[i] = 1;

            }

            else {

                res[i] = -1;

            }

        }

        for(i=0; i<13; i++) {

            if(c[i][0]==res[0] && c[i][1]==res[1] && c[i][2]==res[2]) {

                cout<

                break;

            }

            else if(c[i][0]==-res[0] && c[i][1]==-res[1] && c[i][2]==-res[2]) {

                cout<

                break;

            }

        }

    }

    return 0;

}

POJ 1006 生理周期 暴力大水

以前做过，那时题目看得半懂不懂的。。。。原来这么水，囧~
运用数论的知识应该还可以优化。但信安数学基础学的不好啊，同余用不上。囧~
貌似用中国剩余定理可以做 = =
程序设计导演上面的解法也是不错的。。。。嘛
16ms = =！！
我的也要94ms....囧死



#include“cstdio”
int main()
{
int p,e,i,d,count = 1;
while(scanf("%d%d%d%d",&p,&e,&i,&d) && p != -1){
int res = 0;
for(int k = 0;k < 700;k ++){
i %= 33;           //这里wa了一次。囧~
res = i + 33 * k;     //取最大的除数33，效率比较高
if(!((res - e) % 28) && !((res - p) % 23) && res > d){
printf("Case %d: the next triple peak occurs in %d days.\n",count,res - d);
count ++;
break;
}
}
}
return 0;
}








优化算法：



while(scanf("%d%d%d%d", &p, &e, &i, &d) && p!=-1){
 for(j=d+1; j<21252; j++)
  if ((j-p)%23 == 0) break;
 for( ; j<21252; j=j+23)
   if ((j-e)%28 == 0) break;
 for( ; j<21252; j=j+23*28)
  if ((j-i)%33 == 0) break;
}




3个for...怎么就快了 = =

POJ 1580 String Matching 模拟，简单DP

思路没什么好说的。简单DP。
囧~开始果断又是想复杂了。折腾好久都没出来。。。原来就三个for。。。晕~
说起来是真没意识到这是动规呢。

164K  0MS   C++   716B

#include"cstdio"
#include"cstring"
char s1[200],s2[200];
int gcd(int a,int b)
{
return b ? gcd(b,a % b) : a;
}
int main()
{
while(scanf("%s",s1) && s1[0] != '-'){
scanf("%s",s2);
if(!strcmp(s1,s2)){printf("appx(%s,%s) = 1\n",s1,s2);continue;}
int max = 0,t = 0;
int len1 = strlen(s1),len2 = strlen(s2);
for(int i = 0;i < len1;i ++){
for(int j = 0;j < len2;j ++){
for(int i1 = i,j1 = j;i1 < len1 && j1 < len2;i1 ++,j1 ++)
if(s1[i1] == s2 [j1])t ++;
if(t > max)max = t;
t = 0;
}
}
if(!max){printf("appx(%s,%s) = 0\n",s1,s2);continue;}
int x = max * 2,y = len1 + len2;
printf("appx(%s,%s) = %d/%d\n",s1,s2,x / gcd(x,y),y / gcd(x,y));
}
return 0;
}

POJ 1833 排列 （纯模拟）

纯模拟题，算法还算清晰。感觉可优化的地方很多，比如搜索大于某数的最小数可用二分。嫌麻烦就没写了。数据水啊 = =
好在一次水过。。。。。


应该还有STL的next_permutation 函数可以水过的，但是想自己练练手~

172K     469MS      C++       968B     2011-11-17 16:07:49 

喵的逼我用双引号，标签你妹啊


#include"cstdio"
#include"cstdlib"
int cmp(const void *elem1,const void *elem2){
return *(int *)elem1 - *(int *)elem2;
}
int main()
{
int m,n,k;
scanf("%d",&m);
while(m --){
scanf("%d%d",&n,&k);
int num[1100] = {0},i,j;
for(int i = 0;i < n;i ++)
scanf("%d",&num[i]);
while(k){
for(i = n - 1;i > 0;i --){
if(num[i] < num[i-1])continue;         //后一个数比前一个数小则继续
else {
for(j = i;j < n;j ++){
if(num[j] < num[i-1]){         //在[i,n-1]的区间找到比num[i-1]大的最小的数，交换之
num[j - 1] ^= num[i - 1];
num[i - 1] ^= num[j - 1];
num[j - 1] ^= num[i - 1];
break;
}
}
if(j == n){                         //没找到则num[i-1]和表尾交换
num[n - 1] ^= num[i - 1];
num[i - 1] ^= num[n - 1];
num[n - 1] ^= num[i - 1];
}
qsort(num + i,n - i,sizeof(int),cmp);  //[i,n-1]排序
k --;
break;
}
}
if(i == 0){qsort(num,n,sizeof(int),cmp);k--;}  //已经是最大的排列，则重新从小到大排列
}
for(int i = 0;i < n;i ++){
if(i == n - 1){printf("%d\n",num[i]);break;}
printf("%d ",num[i]);
}
}
return 0;
}

POJ 1102 LC-Display 纯模拟水题

挺有意思的一道模拟水题，涉及映射


#include
#include
char n1[11] = {"- -- -----"};
char n2[21] = {"|| | | |||| |  |||||"};
char n3[11] = {"  ----- --"};
char n4[21] = {"|| ||  | | ||| ||| |"};
char n5[11] = {"- -- -- --"};
int main()
{
int s,i,j,k;
char n[15];
while(scanf("%d%s",&s,n) && s){
int len = strlen(n);
for(i = 0;i < len;i ++){
printf(" ");
for(j = 0;j < s;j ++)
printf("%c",n1[n[i] - '0']);
printf("  ");
}
printf("\n");             //第一行输出完毕
for(i = 0;i < s;i ++){
for(j = 0;j < len;j ++){
printf("%c",n2[2 * (n[j] - '0')]);
for(k = 0;k < s;k ++)
printf(" ");
printf("%c ",n2[2 * (n[j] - '0') + 1]);
}
printf("\n");
}                          //第二行输出完毕
for(i = 0;i < len;i ++){
printf(" ");
for(j = 0;j < s;j ++)
printf("%c",n3[n[i] - '0']);
printf("  ");
}
printf("\n");              //第三行
for(i = 0;i < s;i ++){
for(j = 0;j < len;j ++){
printf("%c",n4[2 * (n[j] - '0')]);
for(k = 0;k < s;k ++)
printf(" ");
printf("%c ",n4[2 * (n[j] - '0') + 1]);
}
printf("\n");
}                      //第四行
for(i = 0;i < len;i ++){
printf(" ");
for(j = 0;j < s;j ++)
printf("%c",n5[n[i] - '0']);
printf("  ");
}
printf("\n\n");           //第五行,中间空一行
}
return 0;
}

POJ 1528 perfection

#include
#include
int main()
{
int n,flag = 0;
while(scanf("%d",&n) && n){
if(!flag){printf("PERFECTION OUTPUT\n");flag = 1;}
printf("%5d  ",n);      //输出长度
int sum = 0;
for(int i = 2;i <= sqrt(n+0.0);i ++)    //利用对称性求和
if(n % i == 0){
if(i == sqrt(n+0.0))sum += i;
else sum += i + n / i;
}
if(n != 1)sum++;       //特别注意1的sum应该是0，这里wa了一次
if(sum == n)printf("PERFECT\n");
if(sum < n)printf("DEFICIENT\n");
if(sum > n)printf("ABUNDANT\n");
}
printf("END OF OUTPUT\n");
return 0;
}

POJ 1226 substrings

#include
#include
#include
using namespace std;
int main()
{
int t,n;
cin>>t;
while(t --){
cin>>n;
int minsize = 101,min,len,i,j;
string s[101];
for(int i = 0;i < n;i ++){
cin>>s[i];
if(s[i].size() < minsize){minsize = s[i].size();min = i;}    //选最短字符串，从中取子串进行暴搜
}
for(len = minsize;len > 0;len --){     //从长取到短
for(i = 0;i + len <= minsize;i ++){
string subs = s[min].substr(i,len);    //子串
char tmp[101];
strcpy(tmp,subs.c_str());
string subr = _strrev(tmp);    //逆子串
for(j = 0;j < n;j ++)
if(s[j].find(subs) == string::npos && s[j].find(subr) == string::npos)break;
if(j == n){cout<
}
}
cout<<"0\n";
next:continue;
}
return 0;
}




这题开始没想到一个字母也算子串，白wa了一次 = =
网上的解题报告貌似有用kmp算法搜索和后缀数组的。喵的都没听过。可以好好看下- -！
用string类水过的题，不靠谱。。。。

POJ 1517 大水

#include
int main()
{
int i;
double t = 1,sum = 1;
printf("n e\n- -----------\n0 1\n");
for(i = 1;i < 0;i ++){
t *= i;
sum += (1 / t);
printf("%d %.10g\n",i,sum);
}
return 0;
}




关于%g的消零使用，第一次遇见 = =

POJ 1504 字符串处理

感觉这题就是atoi和itoa的重复使用。。。。不过思路还是蛮清晰的
但看了discuss之后发觉弱爆了 = =

char* a[M],b[M],sum[M];存储输入的两个正整数，然后去除a,b中的前导0和后缀0，下标由0开始由低到高带进位相加存放在sum中,再去除sum中的前导0和后缀0，然后输出就行了。因为 反转(反转(a))=a,所以这里就是改变了一下加法的规则。

这题比较好的解法，如果是模拟的话还要考虑数据溢出问题。用这个方法可以直接上高精度。嗯，很好~

还有strrev函数、、、囧，各种方便。。。。



#include
#include
#include
void swap(char *p,int len)
{
for(int i = 0;i < len / 2;i ++){
p[i] ^= p[len - 1 - i];
p[len - 1 - i] ^= p[i];
p[i] ^= p[len - 1 - i];
}
}
int main()
{
int n;
scanf("%d",&n);
while(n --){
char a[15]={'\0'},b[15]={'\0'},sum[15]={'\0'};
int c,d;
scanf("%s%s",a,b);
c = atoi(a);
d = atoi(b);
_itoa(c,a,10);    //用itoa还不行，必须用_itoa
_itoa(d,b,10);
swap(a,strlen(a));
swap(b,strlen(b));
_itoa(atoi(a) + atoi(b),sum,10);
swap(sum,strlen(sum));
printf("%d\n",atoi(sum));
}
return 0;
}

百练2974 字符串处理与映射

开始想用map映射，但只有一对一，没有多对一，囧~
这么算的话还是if的要快点。。。
但是没想到标程的自建map映射这么奇葩，就用一个数组 = =！！
效率是确实要比我的高啊。。。

#include
#include
#include
#include
using namespace std;
string num[100001];
int main()
{
int n;
char t[80];     //喵的这个开小的，然后RE  = =
scanf("%d",&n);
for(int i = 0;i < n;i ++){
scanf("%s",t);
for(int k = 0;k < strlen(t);k ++){
if(t[k] == '-')continue;
if(t[k] >= '0' && t[k] <= '9')num[i]+=t[k];
if(t[k] >= 'A' && t[k] <= 'C')num[i]+='2';
if(t[k] >= 'D' && t[k] <= 'F')num[i]+='3';
if(t[k] >= 'G' && t[k] <= 'I')num[i]+='4';
if(t[k] >= 'J' && t[k] <= 'L')num[i]+='5';
if(t[k] >= 'M' && t[k] <= 'O')num[i]+='6';
if(t[k] >= 'P' && t[k] <= 'S')num[i]+='7';
if(t[k] >= 'T' && t[k] <= 'V')num[i]+='8';
if(t[k] >= 'W' && t[k] <= 'Y')num[i]+='9';
}
}
sort(&num[0],&num[0] + n);
int tmp = 0,flag = 0;
for(int i = 0;i < n;i ++){
if(num[i] == num[i+1])tmp ++;
else if(tmp){
printf("%s-%s %d\n",num[i].substr(0,3).data(),num[i].substr(3).data(),tmp + 1);   //返回子串（string），转成char[]
flag = 1;   //标记已输出
tmp = 0;
}
}
if(!flag)printf("No duplicates.\n");
return 0;
}
//5796kB 710ms


//附标程：1948kB 410ms
/*

POJ 1484 Blowing Fuses

#include
int main()
{
int n,m,c,i,count = 1;
while(scanf("%d%d%d",&n,&m,&c) &&  n){
int dev[21]={0},flag[21]={0},max = 0,sum = 0;
for(i = 1;i <= n;i ++)
scanf("%d",&dev[i]);
while(m --){
scanf("%d",&i);
if(!flag[i]){
flag[i] = 1;
sum += dev[i];
}
else {flag[i] = 0;sum -= dev[i];}
if(sum > max)max = sum;
}
printf("Sequence %d\n",count);
if(max > c)printf("Fuse was blown.\n\n");
else printf("Fuse was not blown.\nMaximal power consumption was %d amperes.\n\n",max);
count ++;
}
return 0;
}

思路清晰，简单明了。模拟水题。。。。。

开一个判断数组，关了的就开，然后累计负载；开了的就关，释放负载，过程中记录最大值。

POJ 1477 Box of Bricks

水到让人情何以堪、、、、、、囧~~~~~

#include
int main()
{
int n,count = 1;
while(scanf("%d",&n) && n){
int a[51]={0},sum = 0,mov = 0;
for(int i = 0;i < n;i ++){
scanf("%d",&a[i]);
sum += a[i];
}
for(int i = 0;i < n;i ++)
if(a[i] > sum / n)mov += a[i] - sum / n;
printf("Set #%d\nThe minimum number of moves is %d.\n\n",count,mov);
count ++;
}
return 0;
}

POJ 1450 Gridland

找规律水题。。。。不过一开始还真是找不到 = =！！！！


#include
int main()
{
int n;
scanf("%d",&n);
for(int i = 1;i <= n;i ++){
int m,n;
scanf("%d%d",&m,&n);
printf("Scenario #%d:\n",i);
if(m & 1 && n & 1)printf("%d.41\n\n",m * n);  //如果m，n都是基数，则要用到一条斜边
else printf("%d.00\n\n",m * n);
}
return 0;
}

POJ 1350 Cabric Number Problem

绝对坑爹的题目 = =

输入数字一定要等于4，大于或者小于都不可以。。。。

还有那个yes，no的大小写问题  = =

直接就贡献了2次WA和OLE。。。囧~

感觉代码还是很水的 = =！！

#include

#include

#include

int less(const void *p1,const void *p2)

{

return *(char*)p1 - *(char*)p2;

}

int greater(const void *p1,const void *p2)

{

return *(char*)p2 - *(char*)p1;

}

int main()

{

char a[5];

while(scanf("%s",a) && a[0] != '-'){

printf("N=%s:\n",a);

if(((a[0] == a[1]) && (a[1] == a[2]) && (a[2] == a[3])) || strlen(a) != 4){    //相同或者长度不是4的

printf("No!!\n");    //大小写。。。。囧

continue;

}

int max,min,t = atoi(a),n = 0;

while(t != 6174 && t){

qsort(a,4,sizeof(char),greater);

max = atoi(a);

qsort(a,4,sizeof(char),less);

min = atoi(a);

t = max - min;

printf("%d-%d=%d\n",max,min,t);

n ++;

if(t == 999){

printf("999-999=0\nOk!! %d times\n",n + 1);

n = 0;

break;

}

for(int i = 3,tmp = t;i >= 0;i --){

a[i] = '0' + tmp % 10;     //int转char要注意+0

tmp /= 10;

}

}

if(t != 999)printf("Ok!! %d times\n",n);

}

return 0;

}

POJ 1338 ugly number

#include

int u[1510];

int main()

{

int t2,t3,t5,i,p2,p3,p5;

u[1] = 1;

p2 = p3= p5 = 1;

for(i = 2;i < 1501;i ++){

t2 = u[p2] * 2;

t3 = u[p3] * 3;

t5 = u[p5] * 5;

u[i] = t2 < t3 ? (t2 < t5 ? t2 : t5) : (t3 < t5 ? t3 : t5);

if(u[i] == t2)p2 ++;

if(u[i] == t3)p3 ++;

if(u[i] == t5)p5 ++;

}

int n;

while(scanf("%d",&n) && n)

printf("%d\n",u[n]);

return 0;

}

开始不理解题意，RE了好几次 = =

后来想了好一阵，才搞明白算法。。。

可以用heap或者PQ来做，原理一样
相对来说，这题还有点意思 = =！！