以后不好意思放报告就在这记一下心得啦

POJ1083

http://wenku.baidu.com/view/98287f0c844769eae009edf9.html 这个说此题是DP, 我琢磨了一下贪心不就行嘛, 再看了下discuss连贪心都不用.. 将路线的线段压扁后, 设最多的地方有n层, 那么最优解显然不会n, 可以推出必然总是存在至少一个点上有m条线段, 因为每一个点上有多少条线段都是常数, 这显然也是不成立的..
STL好好用 =D swap() max_element()

#include <stdio.h>
#include <algorithm>
#include <string.h>

using namespace std;

int main() {
    int T,N;
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&N);

        int s,t,press[200];
        memset(press,0x00,sizeof(press));

        for(int i=0;i<N;i++) {
            scanf("%d%d",&s,&t);
            if(s>t)
                swap(s,t);
            for(int k=(s-1)>>1;k<=(t-1)>>1;k++)
                press[k]++;
        }

        printf("%d\n",*max_element(press,press+200)*10);
    }

    return 0;
}

POJ1456

又是DP list上的题目想了想用贪心做了.. 算法没啥难度细节挺恶心, 数据结构又用了位, 感觉思维复杂度和struct差不多, 打出来酷一点..
恶心了有两小时.. 大概是有点困了

#include <stdio.h>
#include <stdlib.h>

int __comp1(const void *a,const void *b) {
    return (*(int *)a&((1<<14)-1)) - (*(int *)b&((1<<14)-1));
}

int __comp2(const void *a,const void *b) {
    return (*(int *)a>>14) - (*(int *)b>>14);
}

int seqMax(int a[],int from,int to) {
    int p=from;
    for(int i=from+1;i<=to;i++) {
        if((a[p]>>14)<(a[i]>>14))
            p=i;
    }
    int r=(a[p]>>14);
    a[p]=a[to];
    return r;
}

int main() {
    int a[10001],n;
    while(1) {
        if(scanf("%d",&n)==EOF)
            break;
        for(int i=0;i<n;i++) {
            scanf("%d",a+i);
            a[i]<<=14;
            int temp;
            scanf("%d",&temp);
            a[i]+=temp;
        }

        qsort(a,n,sizeof(int),__comp1);

        int edge=-1;
        int head=n-1;
        int result=0;
        for(int i=n-1;i>=0 && head >=0;) {
            for(;head>0;head--)
                if((a[head-1]&((1<<14)-1))!=edge)
                    break;
            int days=(a[head]&((1<<14)-1))-(head==0?0:(a[head-1]&((1<<14)-1)));
            //qsort(a+head,i-head+1,sizeof(int),__comp2);       too much time cost, according to the test data
            int cut=(i-head+1)<days?(i-head+1):days;
            for(int j=0;j<cut;j++)
                result+=seqMax(a,head,i--);
            head--;
        }

        printf("%d\n",result);

    }
    return 0;
}

POJ 1730

*pow()以后就用double pow(double a,double b)不要多想
*接上面, 算一个数的开房, 可以b=1/n. 需要注意的是a是负数时即使n是奇数, 函数值也是NaN
*判断NaN可以 a!=a 或使用
中的isnan() . a!=a是因为所有带有NaN的逻辑表达式值都为false, a!=a就是!(a==a)
*这道囧题说”The value of x will have magnitude at least 2″(绝对值>=2, 有可能是负的), 重点是”and be within the range of a (32-bit) int”, 但是当时是ISO C90的标准，那时候2^31还是在int型以内的.. 所以2^31要单独考虑或者用long long.. 太囧了阿..

#include <stdio.h>
#include <math.h>

int main() {
    while(1) {
        long long n;
        scanf("%lld",&n);
        if(!n)
            break;
        int max=1;
        for(int i=31;i>=2;i--) {
            if(n<0 && !(i%2))
                continue;
            long long __n=(long long)fabs((double)n);
            double m=pow((double)__n,(double)1/i);
            if(m-(int)m<1E-12||(int)m+1-m<1E-12) {
                max=i>max?i:max;
                break;
            }
        }
        printf("%d\n",max);
    }
    return 0;
}

POJ 1953

就是Fibonacci数列, 推了一下发现a[i] = sum(a[k])+1, k=1..i-2

#include <stdio.h>

int main() {
    int dp[46][2];
    dp[0][0]=1;
    dp[0][1]=0;
    for(int i=1;i<=45;i++) {
        dp[i][0]=dp[i-1][0]+dp[i-1][1];
        dp[i][1]=dp[i-1][0];
    }

    int N;
    scanf("%d",&N);
    for(int i=1;i<=N;i++) {
        int a;
        scanf("%d",&a);
        printf("Scenario #%d:\n%d\n\n",i,dp[a+1][0]);
    }

    return 0;
}