poj1000-1009小结
poj1000-1009小结
蒟蒻一枚，开始从poj做起。废了n久时间且参考有些参考大神博客才写完poj10题。但总算是写完了，小结一下。
poj1000 A+B
经典题目，不解释，过。
poj1001 Exponentiation
- 大意
- 求R的n次方。
- 忽略小数点前的前导0，小数点的后导0输出。如0.50输出为:
.5
- 算法
- 高精度乘以int
- 代码
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
char s[10];
int a,n,p_cnt;
struct bign{
int a[140];
int p_cnt;
void set(int a0,int p_cnt0)
{
int i;
p_cnt=p_cnt0;
for(i=0;a0;i++) {
a[i]=a0%10;
a0/=10;
}
for(;i<140;i++) a[i]=0;
}
struct bign operator *(int b)
{
int i,t;
bign c;
for(t=i=0;i<140;i++) {
t=a[i]*b+t;
c.a[i]=t%10;
t/=10;
}
return c;
}
void p()
{
int i,j;
for(i=140-1;i>=p_cnt;i--)
if(a[i]) break;
for(j=0;j<p_cnt;j++)
if(a[j]) break;
if(i<p_cnt&&j>=p_cnt)
puts("0");
else {
for(;i>=p_cnt;i--)
printf("%d",a[i]);
if(j<p_cnt) putchar('.');
for(i=p_cnt-1;i>=j;i--)
printf("%d",a[i]);
printf("\n");
}
}
}r,ans;
int init()
{
if(cin>>s>>n) {
char *p=strchr(s,'.');
p_cnt=s+strlen(s)-p-1;
strcpy(p,p+1);
sscanf(s,"%d",&a);
return 1;
} else {
return 0;
}
}
void cal()
{
int nn=n;
r.set(a,p_cnt);
ans.set(1,0);
while(n--)
ans=ans*a;
ans.p_cnt=p_cnt*nn;
}
int main()
{
while(init()){
r.set(a,p_cnt);
cal();
ans.p();
}
}poj1002
- 大意
- 公司为了便于记忆电话号码，采取了不同的分隔方法和把字母映射为某一个数字
- 算法
- 直接把输入搞成一个7位数，暴力开数组记录出现次数，最后按标准格式输出。
- 代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int n;
int num_cnt[10000001],num,ans_cnt;
char s[100],c,p[8];
void get_std(char p[],char s[])
{
int i,j;
for(j=i=0;s[i];i++) {
if(s[i]>='0'&&s[i]<='9') p[j++]=s[i];
switch(s[i]) {
case 'Q':
case 'Z':
case '-':break;
case 'A':
case 'B':
case 'C':p[j++]='2';break;
case 'D':
case 'E':
case 'F':p[j++]='3';break;
case 'G':
case 'H':
case 'I':p[j++]='4';break;
case 'J':
case 'K':
case 'L':p[j++]='5';break;
case 'M':
case 'N':
case 'O':p[j++]='6';break;
case 'P':
case 'R':
case 'S':p[j++]='7';break;
case 'T':
case 'U':
case 'V':p[j++]='8';break;
case 'W':
case 'X':
case 'Y':p[j++]='9';break;
}
}
}
int main()
{
int i;
scanf("%d\n",&n);
memset(num_cnt,0,sizeof(num_cnt));
while(n--){
gets(s);
get_std(p,s);
sscanf(p,"%d",&num);
num_cnt[num]++;
}
ans_cnt=0;
for(i=0;i<=10000000;i++)
if(num_cnt[i]>1) {
ans_cnt++;
printf("%03d-%04d %d\n",i/10000,i%10000,num_cnt[i]);
}
if(ans_cnt==0) puts("No duplicates.");
}poj1003
题目已经给了公式，直接计算出，然后计算即可。
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
double a[1000];
int ans[521];
int main()
{
int i,j;
int x,y;
a[1]=0.50;
for(i=2;a[i-1]<5.20;i++)
a[i]=a[i-1]+1.0/(i+1);
//printf("%d\n",i);
for(i=1,j=1;j<521;j++) {
while(a[i]<j/100.0) i++;
ans[j]=i;
}
do{
scanf("%d.%d",&x,&y);
if(x==0&&y==0)
break;
printf("%d card(s)\n",ans[x*100+y]);
}while(1);
return 0;
}poj1004 Financial Management
其实就是求12个数的平均数，保留两位小数。
但是我wa了很多次。根源在于浮点数的精度原因。
wa 1
#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
double a[12],sum,ans;
int i;
for(i=0;i<12;i++) cin>>a[i];
for(sum=i=0;i<12;i++) sum+=a[i];
ans=sum/12;
printf("$%.02lf\n",ans);
return 0;
}wa 2
#include<cstdio>
using namespace std;
int main()
{
int i;
double tmp,sum;
sum=0.0;
for (i=0;i<12;i++)
{
scanf("%lf", &tmp);
sum+=tmp;
}
printf("$%.2lf\n",sum/12);
return 0;
}然后找了一个大神的程序发现大神输出使用cout的格式化输出的，而我并不会cout.大神是这样子的
cout<<fixed<<setprecision(2)<<'$'<<sum/12.0<<endl;
用大神的代码提交了一下,A了。然后我就觉得，一定要用printf写出来。然后各种百度。期间wa了无数次。又说printf格式化输出就是四舍五入的，又说是截断的，又说根据程序运行结果来看不是截断是四舍五入的。最后看到有人说设计的是想四舍五入的，但是因为实型的存储机制blablabla的导致有些并不是四舍五入的。然后又有各种版本的四舍五入的正确输出方法的。有这样说的（注：我是用sum存储的平均数，逃）
version1
sum=(int)(sum*100+0.5)/100.0;
printf("$%.2lf\n",sum);version2
sum+=0.005;
printf("$%.2lf\n",sum);最后我是这么干的A掉了
ans=(int)round(sum*100.0);
printf("$%d.%02d",ans/100,ans%100);经验
实型精度问题要注意，四舍五入不简单。
poj1005
大意
一个半圆每年扩充面积值50.给出点的坐标，问第几年会被覆盖。保证点不会在某一年的圆的边界上。
代码
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
using namespace std;
const double pi=atan(1)*4;
const double k=2*50/pi;
int l,r,m;
int main(void)
{
int n;
double x,y;
cin>>n;
for(int i=1;i<=n;i++) {
cin>>x>>y;
x=x*x+y*y;
/*l=0; r=20000000; while(r-l>1) { m=(l+r)/2; if (k*m>x) r=m; else l=m; }*/
r=1+(int)floor(x/k);
cout<<"Property "<<i<<": This property will begin eroding in year "<<r<<"."<<endl;
}
cout<<"END OF OUTPUT."<<endl;
return 0;
}poj1006
大意
人有三种巅峰，周期性出现，周期数题面说了，给出这三种巅峰的各自出现的一天。问第t天后至少过多少天会出现三种巅峰在同一天出现。
数论题
中国剩余定理
代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
using namespace std;
int e_gcd(int a,int b,int &x,int &y)
{
if(b==0) {
x=1; y=0;
return a;
}
int ans=e_gcd(b,a%b,x,y);
int tmp=x;
x=y; y=tmp-a/b*y;
}
int crt(int r[],int m[],int n)
{
int M=1,ans=0;
for(int i=0;i<n;i++) M*=m[i];
for(int i=0;i<n;i++) {
int x,y,mi=M/m[i];
e_gcd(mi,m[i],x,y);
ans=(ans+mi*x*r[i])%M;
}
if(ans<0) ans+=M;
return ans;
}
int main()
{
int p,e,i,d,t=1,k=21252;
int a[3],m[3];
do{
cin>>p>>e>>i>>d;
if(p==-1&&e==-1&&i==-1&&d==-1) break;
a[0]=p; a[1]=e; a[2]=i;
m[0]=23; m[1]=28; m[2]=33;
int ans=crt(a,m,3);
ans-=d;
if(ans<=0) ans+=21252;
cout<<"Case "<<t++<<": the next triple peak occurs in "<<ans<<" days."<<endl;
}while(1);
return 0;
}poj1007
大意
给出若干等长的DNA序列，按照序列中的逆序对个数从少到多排序后输出。
算法
归并排序并求逆序对个数。最后按照逆序对个数排序。
源码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define array_len 1000
int merge_tmp[array_len];
void merge_cnt(int a[],int l,int r,int &cnt,int tmp[])
{
int m=(l+r)/2,i=l,j=m+1,k=l;
while(i<=m&&j<=r) {
if(a[i]>a[j]) {
tmp[k++]=a[j];
cnt+=m+1-i;
j++;
} else {
tmp[k++]=a[i];
i++;
}
}
while(i<=m) tmp[k++]=a[i++];
while(j<=r) tmp[k++]=a[j++];
while (l<=r) {
a[l]=tmp[l];
l++;
}
}
void merge_srt_cnt(int a[],int l,int r,int &cnt,int tmp[])
{
if(l<r) {
int m=(l+r)/2;
merge_srt_cnt(a,l,m,cnt,tmp);
merge_srt_cnt(a,m+1,r,cnt,tmp);
merge_cnt(a,l,r,cnt,tmp);
}
}
void merge_cnt(char a[],int l,int r,int &cnt,char tmp[])
{
int m=(l+r)/2,i=l,j=m+1,k=l;
while(i<=m&&j<=r) {
if(a[i]>a[j]) {
tmp[k++]=a[j];
cnt+=m+1-i;
j++;
} else {
tmp[k++]=a[i];
i++;
}
}
while(i<=m) tmp[k++]=a[i++];
while(j<=r) tmp[k++]=a[j++];
while (l<=r) {
a[l]=tmp[l];
l++;
}
}
void merge_srt_cnt(char a[],int l,int r,int &cnt,char tmp[])
{
if(l<r) {
int m=(l+r)/2;
merge_srt_cnt(a,l,m,cnt,tmp);
merge_srt_cnt(a,m+1,r,cnt,tmp);
merge_cnt(a,l,r,cnt,tmp);
}
}
struct dna{
char s[52];
int invrsn;
bool operator <(dna b)
{
if(invrsn!=b.invrsn)
return invrsn<b.invrsn;
else
return strcmp(s,b.s)<0;
}
}a[100];
char s[52];
char tmps[52];
int main()
{
int n,m,i;
cin>>n>>m;
for(i=0;i<m;i++) {
cin>>s;
strcpy(a[i].s,s);
a[i].invrsn=0;
merge_srt_cnt(s,0,n-1,a[i].invrsn,tmps);
}
sort(a,a+m);
for(i=0;i<m;i++) cout<<a[i].s<<endl;
return 0;
}poj1008
模拟水题，不解释
#include<stdio.h>
#include<string.h>
char p[20][15]={"pop","no","zip","zotz","tzec","xul","yoxkin","mol","chen",
"yax","zac","ceh","mac","kankin","muan","pax","koyab","cumhu",
"uayet"};
char q[20][15]={"imix","ik","akbal","kan","chicchan","cimi","manik","lamat",
"muluk","ok","chuen","eb","ben","ix","mem","cib","caban",
"eznab","canac","ahau"};
int get_mnth_ind(char *m)
{
int i;
for(i=0;i<19;i++)
if(strcmp(m,p[i])==0)
return i;
return -1;
}
int main()
{
int n,mnth_day,mnth_ind,year,day;
char s[15];
scanf("%d",&n);
printf("%d\n",n);
while(n--){
scanf("%d. %s %d",&mnth_day,s,&year);
mnth_ind=get_mnth_ind(s);
day=year*365+mnth_ind*20+mnth_day;
//printf("day=%d\n",day);
year=day/260; day%=260;
mnth_day=day%13+1; mnth_ind=day%20;
printf("%d %s %d\n",mnth_day,q[mnth_ind],year);
}
return 0;
}poj1009
大意
图片有很多像素，不直接存储每个图片的像素值，而是以RLE，即
像素值V 长度L
表示连续L个像素的值是V。用这种RLE存储方式以节约空间。现在需要计算每个像素与周围8个格子的最大像素差（取绝对值）取代原来的像素值以生成一副新图。新图的输出格式与输入格式相同。
图的像素很多，10^9级别的。
RLE对数输入数据保证最多1000对。
算法
自己画了几张图，发现只有变化的那个起点及起点周围8个点才回因为有这个变化的点出现导致最大像素差可能改变，而其他的新像素值应该和前面一个（最左边的前一个点是上一行最后一个点）像素点相同。然后又画了图形式的证明了一下，发现的确是这样。然后按照这种方法写。
故事
一开始怕有大量test cases而超时，还用了二分查找确定像素值。
然而wa了。于是先改成直接扫描查找确保查找确定像素值没错，然而还是wa.思考了许久还是不解，然后百度，然后发现我的思路和大神思路差不多。然后阅读代码，觉得和大神的是等价的。然后整个人就不好了。
自己写了个数据生成器，用大神和自己的对拍。发现了一个很大的错误数据，调试了n久，表示数据太大，调试好累，调试了一个小时无果。
最后躺床上，早上突然醒来看到那张自己画的形式的证明的图，脑袋中过了一下证明的过程，发现自己的证明有一个bug，图片的终结最后一行的后一行是没有的，这个就和前面的不一样，要特殊考虑或者把这个特殊处理使其符合前面形式证明的条件一样。然后我就把原来的输入的RLE对增加了一队
-1 width
或者直接增加一个起始变化点
total val
其中total是图的总像素点，val随便什么无所谓
源码
//WA
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
struct node{
int pos;
int val;
void set(int p,int v){pos=p;val=v;}
bool operator <(node b){return pos<b.pos;}
}a[2005],b[16500];
int width,total,height,pos,acnt,bcnt;
int get_val(int pos)
{
int i;
for(i=0;i<acnt;i++)
if(pos>=a[i].pos&&pos<a[i+1].pos)
return a[i].val;
}
void cal(int pos)
{
int r,c,j,k,tpos,val,tval=0;
val=get_val(pos);
r=pos/width; c=pos%width;
for(j=-1;j<=1;j++) {
if((c==0&&j==-1)||(c==width-1&&j==1)) continue;
for(k=-1;k<=1;k++) {
if((r==0&&k==-1)||(r==height-1&&k==1)) continue;
tpos=(r+k)*width+c+j;
tval=max(tval,abs(val-get_val(tpos)));
}
}
b[bcnt++].set(pos,tval);
}
int main()
{
int r,c,j,k,i;
int val,l;
while(1) {
scanf("%d",&width);
if(width==0) break;
acnt=bcnt=pos=total=0;
while(1) {
scanf("%d%d",&val,&l);
if(val==0&&l==0) break;
a[acnt++].set(pos,val);
pos+=l;
}
a[acnt].set(pos,val);//AC版本修改这里，修改为acnt++.但是一开始这样写并不是疏忽落了++，而是一开始之时为了增加这个节点来让查找更方便，未考虑到把这个变成一个起始变化点
total=pos; height=total/width;
for(i=0;i<acnt;i++) {
r=a[i].pos/width; c=a[i].pos%width;
for(j=-1;j<=1;j++) {
if((c==0&&j==-1)||(c==width-1&&j==1)) continue;
for(k=-1;k<=1;k++) {
if((r==0&&k==-1)||(r==height-1&&k==1)) continue;
cal((r+k)*width+c+j);
}
}
}
b[bcnt].set(total,-1);
sort(b,b+bcnt);
printf("%d\n",width);
pos=0;
for(i=0;i<bcnt;i=j) {
for(j=i+1;j<bcnt;j++)
if(b[j].val!=b[i].val) break;
printf("%d %d\n",b[i].val,b[j].pos-b[i].pos);
}
printf("0 0\n");
}
printf("0\n");
return 0;
}//AC
/*上面改了，增加一个起始变化点。同时因为这个点的增加，修改了判断是否点是否合法的判断条件。毕竟原来的判断是基于起始变化点是合法点。
*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
struct node{
int pos;
int val;
void set(int p,int v){pos=p;val=v;}
bool operator <(node b){return pos<b.pos;}
}a[2005],b[16500];
int width,total,height,pos,acnt,bcnt;
int get_val(int pos)
{
int i;
for(i=0;i<acnt;i++)
if(pos>=a[i].pos&&pos<a[i+1].pos)
return a[i].val;
}
void cal(int pos)
{
int r,c,j,k,tpos,val,tval=0;
val=get_val(pos);
r=pos/width; c=pos%width;
for(j=-1;j<=1;j++) {
if((c+j<0)||(c+j>=width)) continue;
for(k=-1;k<=1;k++) {
if((r+k<0)||(r+k>=height)) continue;
tpos=(r+k)*width+c+j;
tval=max(tval,abs(val-get_val(tpos)));
}
}
b[bcnt++].set(pos,tval);
}
int main()
{
int r,c,j,k,i;
int val,l;
while(1) {
scanf("%d",&width);
if(width==0) break;
acnt=bcnt=pos=total=0;
while(1) {
scanf("%d%d",&val,&l);
if(val==0&&l==0) break;
a[acnt++].set(pos,val);
pos+=l;
}
a[acnt++].set(pos,val);//这里修改了
total=pos; height=total/width;
for(i=0;i<acnt;i++) {
r=a[i].pos/width; c=a[i].pos%width;
for(j=-1;j<=1;j++) {
if((c+j<0)||(c+j>=width)) continue;
for(k=-1;k<=1;k++) {
if((r+k<0)||(r+k>=height)) continue;
cal((r+k)*width+c+j);
}
}
}
b[bcnt].set(total,-1);
sort(b,b+bcnt);
printf("%d\n",width);
pos=0;
for(i=0;i<bcnt;i=j) {
for(j=i+1;j<bcnt;j++)
if(b[j].val!=b[i].val) break;
printf("%d %d\n",b[i].val,b[j].pos-b[i].pos);
}
printf("0 0\n");
}
printf("0\n");
return 0;
}经验
边界是特殊的，最好多考虑，看是否和普通的一样，能否特判断或者能否转化程普通的。
腾讯成长空间 449人发布
