POJ1019

思路:
1. i属于哪个区间[10^(k-1),10^k-1], 也就是n那个区间有几位数
long long map[]={0,45,9045,1395495,189414495,(long long)(2E31-1)};
我另外写了个程序算出来的..汗

2. i<=map[k], 纸上算出来一个式子, 根据h可以得出map[k]某个区间里第h行的末尾是第n个digits, 比如
123..9899100
123..9899100101
123..9899100101102
123..9899100101102103
当h=4时(第4行), n等于([103的3]到开始[123的1]有多少位digits)
反过来可以由已知的n求出h
这个h不一定是整数, 但是由于函数n=f(h)是递增的, 所以根据h的整数位可以得出要求的digit在哪一行内

h=sqrt(2*n/k+(0.5+map2[k-1]/k)^2-0.5-map2[k-1]/k
map2[k]存放了 1234..k个9有多少位数

3. 根据行数算出要求的digit是哪一行的第几位, 现在问题简化成求123..9899100..这个数列中的第几位数, 很简单了

细节:
注意第2步中
开方下来h如果是整数需要特别判断一下, 我在这磨了好久.. 因为开始试图用(int)(h-0.00001)这种方式判断整数纠缠不清.. 非常傻. 就想不起来直接判断

(实验了一下math.h的sqrt()函数对于整数的开方没有误差25.0000开方就是5.0000, 可以直接if(5==5.0000)这样)

代码用C++WA G++AC, 不知缘何

//  Calculate using another program to achieve the array;
//  i of 9,99,999,9999
#include <stdio.h>
#include <math.h>

long long pow10(long long n) {
    long long a;
    a=1;
    while(n--)
        a*=10;
    return a;
}

int main() {
    long long map[]={0,45,9045,1395495,189414495,(long long)(2E31-1)};
    long long map2[]={0,9,189,2889,38889};  //how many digits does {1 2 3 4 ... 99...9} have
    long long N;
    long long n,k,x,l,number,result,digit,k_;
    double h;
/*  bool newline;
    FILE *fp;
    char tt;
    fp=fopen("E:\\a.out","wt");
    l=0; */
    scanf("%lld",&N);
    while(N--) {
/*  if(newline)
    fputc('\n',fp);
    newline=false;
    l++;    */
        scanf("%lld",&l);
        for(k=1;l>map[k];k++);
        n=l-map[k-1];
        h=sqrt((double)2*n/k+(0.5+(double)map2[k-1]/k)*(0.5+(double)map2[k-1]/k))-0.5-(double)map2[k-1]/k;

        if(h==(long long)h)
            x=(long long)h;
        else
            x=(long long)h+1;
/*  if(h==x)
        newline=true;   */
        n=n-map2[k-1]*(x-1)-(x-1)*x/2*k;
        for(k_=1;map2[k_]<n;k_++);   //area's number of digits
        n-=map2[k_-1];
        number=pow10(k_-1)+(n-1)/k_;
        digit=k_-(n-1)%k_;
        result=number/pow10(digit-1)%10;
        printf("%lld\n",result);
//fputc(result+'0',fp);
    }
    return 0;
}

POJ 1015

最优化原理 Principle of Optimality, 马克一下有空看看
还有这个

DP算法是Google出来的.. 都是这个算法, 不重复发言了..

虽然AC了(125ms) 还是有个疑问, 为什么每次S(J)(辩控和)必须最大? 是不是有可能S(J)不是最大的情况下因为V(J)(辩控差)的原因正好可以选一个s[i]很大的人这样在后面的过程中S(J)反而更大, 而因为每次都取最优反而埋没了这个解呢… 事实证明这不可能, 但是为什么? 等等再想这个问题.. 马克一下

细节:
1. path我用了三维空间.. 每一个状态我附上了完整的路径, 省得每次找某人有没有被选中还要回溯搜一遍.

2. 众所周知..这个数组序号不可以是负的比较麻烦, 我加了 #define A(x) (x+400) 这样定义int f[21][A(401)]; 使用的时候很方便了 f[21][A(-400)] 即可 多打几个符号看着顺心, 我有检查强迫症, 总是+400我会很困扰的..

3. memset()一般只能把int初始化为0, 其实-1也可以的, 参考补码的知识, -1=0xff, int是4字节, 连一起是0xffffffff, 还是-1 =P

4.freopen(“in.txt”, “r”, stdin); freopen(“out.txt”, “w”, stdout); 有in文件可以用一下, 方便对比

代码: (这种东西真是只给自己看的..)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define A(x) (x+400)
#define MAX(x,y) (x>y?x:y)

int sort_function(const void *a,const void *b) {
    return *(int *)a-*(int *)b;
}

int main() {
    int p[201],d[201],v[201],s[201];
    int f[21][A(401)],path[21][A(401)][21];
    int n,m;
    int N,i,j,k,l,h;
    int D,P;

    N=0;
    while(1) {
        scanf("%d %d",&n,&m);
        if(!n&&!m)
            break;
        N++;
        for(i=1;i<=n;i++) {
            scanf("%d %d",p+i,d+i);
            v[i]=p[i]-d[i];
            s[i]=p[i]+d[i];
        }

        memset(f,0xff,21*A(401)*sizeof(int));   //f[i][A(j)]=0xffffff=-1;
                                                //开始忘*sizeof(int)了, int占4字节, 导致m稍微大一点就出错
        f[0][A(0)]=0;
        for(i=1;i<=m;i++)
            for(j=-i*20;j<=i*20;j++)
                for(k=MAX(-(i-1)*20,j-20);k<=j+20 && k<=(i-1)*20;k++) {
                    if(f[i-1][A(k)]==-1)
                        continue;
                    for(l=1;l<=n;l++) {
                        if(v[l]==j-k && f[i-1][A(k)]+s[l]>f[i][A(j)]) {
                            for(h=1;h<=i-1;h++)
                                if(path[i-1][A(k)][h]==l)
                                    break;
                            if(h>i-1) {     //这里有个细节, 开始我写的h==i,其实不一定 如果上面是for(h=2..
                                            //h==2,i==1,直接跳出, 那么就不对了, 写成h<=i-1的补集最好, 严密一点
                                f[i][A(j)]=f[i-1][A(k)]+s[l];
                                path[i][A(j)][i]=l;
                                for(h=1;h<i;h++)
                                    path[i][A(j)][h]=path[i-1][A(k)][h];
                            }
                        }
                    }
                }

        printf("Jury #%d\n",N);
        for(i=0;i<=20*m;i++) {
            if(f[m][A(i)]==-1&&f[m][A(-i)]==-1)
                continue;
            j=f[m][A(i)]>f[m][A(-i)]?1:-1;
            P=(i*j+f[m][A(i*j)])/2;
            D=f[m][A(i*j)]-P;
            printf("Best jury has value %d for prosecution and value %d for defence:\n",P,D);
            qsort((void *)(path[m][A(i*j)]+1),m,sizeof(int),sort_function);
            for(k=1;k<=m;k++)
                printf(" %d",path[m][A(i*j)][k]);
            printf("\n\n");
            j=-1;
            i=400;
        }
    }
    return 0;
}