hdu 1423 最长上升公共子序列 LCIS 模板题

累死我了。

开始的时候我因为题目没有看清楚，没有注意到计算结果超出了int，提交一直wa。看了别人的代码，意识到了精度的问题，但是提交还是一直wa。沉默良久，想到了是在qsort排序的时候，在排序函数内部的值也会超出int，大喜，修改之后提交，依然wa……用sort函数排序，提交ac。

我很疑惑，不明白为什么用sort提交通过，用qsort提交就wa。在编译的时候，编译器报警，我看了一下警告信息，突然意识到了qsort的比较函数是默认的返回int值，下面就知道怎么处理了，跟double一样，返回值不是int，那就换一种方式将int表示出来。

修改之后提交ac。

用sort提交的代码：

?#include<stdio.h>  
#include<string.h>  
#include<stdlib.h>  
#include<iostream>  
#include <algorithm>  
using namespace std; 
#define N 100005  
struct node 
{ 
    long long x; 
    long long y; 
} a[N]; 
bool operator < (const node &a, const node &b) 
{ 
    return a.x * b.y <a.y * b.x; 
} 
int main() 
{ 
    int n; 
    int m=365*24*60*60; 
    while(scanf("%d",&n),n) 
    { 
        int i; 
        for(i=0; i<n; i++) 
            scanf("%I64d%I64d",&a[i].x,&a[i].y); 
        sort(a,a+n); 
        long long sum; 
        sum=0; 
        for(i=0; i<n; i++) 
        { 
            sum+=sum*a[i].y+a[i].x; 
            sum%=m; 
        } 
        printf("%I64d\n",sum); 
    } 
    return 0; 
} 

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include <algorithm>
using namespace std;
#define N 100005
struct node
{
    long long x;
    long long y;
} a[N];
bool operator < (const node &a, const node &b)
{
    return a.x * b.y <a.y * b.x;
}
int main()
{
    int n;
    int m=365*24*60*60;
    while(scanf("%d",&n),n)
    {
        int i;
        for(i=0; i<n; i++)
            scanf("%I64d%I64d",&a[i].x,&a[i].y);
        sort(a,a+n);
        long long sum;
        sum=0;
        for(i=0; i<n; i++)
        {
            sum+=sum*a[i].y+a[i].x;
            sum%=m;
        }
        printf("%I64d\n",sum);
    }
    return 0;
}

用qsort提交的代码：

#include<stdio.h>  
#include<string.h>  
#include<stdlib.h>  
#include<iostream>  
#include <algorithm>  
using namespace std; 
#define N 100005  
struct node 
{ 
    long long x; 
    long long y; 
} a[N]; 
int cmp(const void *a,const void *b) 
{ 
    return (*(node *)a).x*(*(node *)b).y>(*(node *)b).x*(*(node *)a).y?1:-1; 
} 
int main() 
{ 
    int n; 
    int m=365*24*60*60; 
    while(scanf("%d",&n),n) 
    { 
        int i; 
        for(i=0; i<n; i++) 
            scanf("%I64d%I64d",&a[i].x,&a[i].y); 
        qsort(a,n,sizeof(a[0]),cmp); 
        long long sum; 
        sum=0; 
        for(i=0; i<n; i++) 
        { 
            sum+=sum*a[i].y+a[i].x; 
            sum%=m; 
        } 
        printf("%I64d\n",sum); 
    } 
    return 0; 
} 

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include <algorithm>
using namespace std;
#define N 100005
struct node
{
    long long x;
    long long y;
} a[N];
int cmp(const void *a,const void *b)
{
    return (*(node *)a).x*(*(node *)b).y>(*(node *)b).x*(*(node *)a).y?1:-1;
}
int main()
{
    int n;
    int m=365*24*60*60;
    while(scanf("%d",&n),n)
    {
        int i;
        for(i=0; i<n; i++)
            scanf("%I64d%I64d",&a[i].x,&a[i].y);
        qsort(a,n,sizeof(a[0]),cmp);
        long long sum;
        sum=0;
        for(i=0; i<n; i++)
        {
            sum+=sum*a[i].y+a[i].x;
            sum%=m;
        }
        printf("%I64d\n",sum);
    }
    return 0;
}

补充：软件开发 , C++ ,