[ACM] POJ1015,1019解题报告

101 Replies

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, 不知缘何

[cpp]// 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;
}[/cpp]

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文件可以用一下, 方便对比

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

[cpp]

#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;
}
[/cpp]

101 thoughts on “[ACM] POJ1015,1019解题报告”

Leave a Reply

Your email address will not be published. Required fields are marked *