回复：【信息】vijos共54题AC代码 秋枫 2013.6.25

P1104 采药
#include <iostream>
#include <cstring>
using namespace std;
int dp[101][1001];
int c[1000],t[1000];
int max1=0,m,time1;
void search(int n,int wn,int tn)
{
if(dp[n][tn]>=wn)return ;
dp[n][tn]=wn;
if(n>=m){if(wn>max1){max1=wn;}return ;}
if(time1>=tn+t[n])search(n+1,wn+c[n],tn+t[n]);
search(n+1,wn,tn);
return ;
}
int main()
{
memset(dp,-1,sizeof(dp));
int i;
cin>>time1>>m;
for(i=0;i<m;i++)cin>>t[i]>>c[i];
search(0,0,0);
cout<<max1;
return 0;
}

P1113 不高兴的津津
#include <stdio.h>
int main()
{
int a[7]={0};
int i,j,k,max=0,max_i;
for(i=0;i<7;i++)
{
scanf("%d",&k);
a[i]+=k;
scanf("%d",&k);
a[i]+=k;
}
for(i=0;i<7;i++)
if(a[i]>max){max=a[i];max_i=i+1;}
if(max>8)
printf("%d",max_i);
else printf("0");
return 0;
}

P1114 FBI树
#include <iostream>
#include <cstring>
using namespace std;
char s[3000];
int tree[3000][20];
int size,layer;
char ans[3000][20];
void search(int n)
{
int i,j=0,k=1;
for(i=0;i<n;i++)k*=2;
for(i=0;i<size;i+=k)
tree[j++][n]=s[i]-'0';
if(n==layer)return ;
search(n+1);
}
void print()
{
int i,j,k;
for(i=0;i<size;i++)
{
if(tree[i][0]==0)ans[i][0]='B';
if(tree[i][0]==1)ans[i][0]='I';
k=i+1;
for(j=1;j<=layer;j++)
{
if(k%2!=0)k++;
if(k>1)k/=2;
if(ans[k-1][j]=='B'){if(tree[i][0]==1)ans[k-1][j]='F';}
else if(ans[k-1][j]=='I'){if(tree[i][0]==0)ans[k-1][j]='F';}
else if(ans[k-1][j]!='F')
{
if(tree[i][0]==0)ans[k-1][j]='B';
if(tree[i][0]==1)ans[k-1][j]='I';
}
}
}
for(i=1;i<=size;i++)
{
cout<<ans[i-1][0];
j=0;
k=i;
while(k%2==0)
{
j++;
cout<<ans[k/2-1][j];
k/=2;
}
}
}
int main()
{
cin>>layer;
if(layer==0)
{
cin>>s;
if(s[0]=='0')cout<<"B";
else cout<<"I";
return 0;
}
cin>>s;
size=strlen(s);
search(0);
print();
return 0;
}

P1116 一元三次方程求解
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
double a,b,c,d,j,i;
cin>>a>>b>>c>>d;
for(j=-10000;j<10000;j++)
{
i=j/100;
if(a*i*i*i+b*i*i+c*i+d<0.0001&&a*i*i*i+b*i*i+c*i+d>-0.0001)
printf("%.2f ",i);
}
return 0;
}

P1117 数的划分
#include <iostream>
#include <cstring>
using namespace std;
int q[501][501];
bool d[501][501];
int m,n;
int main()
{
memset(d,false,sizeof(d));
int i,j,k;
//int t1,t2;
cin>>n>>m;
q[0][0]=1;
d[0][0]=true;
for(i=1;i<=n;i++)
for(j=0;j<=n;j++)
for(k=0;k<=m;k++)
if(d[j][k]&&j+i<=n&&k+1<=m)
{
d[j+i][k+1]=true;
q[j+i][k+1]+=q[j][k];
}
cout<<q[n][m];
return 0;
}

P1121 马拦过河卒
#include <iostream>
#include <cstring>
using namespace std;
bool s[100][100];
int m,n,sum=0;
void search(int x,int y)
{
if(x==m&&y==n){sum++;return ;}
if(x<m&&s[x+1][y])search(x+1,y);
if(y<n&&s[x][y+1])search(x,y+1);
return ;
}
int main()
{
memset(s,true,sizeof(s));
int mx,my;
cin>>m>>n>>mx>>my;
s[mx][my]=false;
if(mx>0)
{
if(my>1)s[mx-1][my-2]=false;
s[mx-1][my+2]=false;
}
if(mx>1)
{
if(my>0)s[mx-2][my-1]=false;
s[mx-2][my+1]=false;
}
if(my>0)
{
if(my>1)s[mx+1][my-2]=false;
s[mx+2][my-1]=false;
}
s[mx+2][my+1]=false;
s[mx+1][my+2]=false;
if(!s[m][n]){cout<<0;return 0;}
search(0,0);
cout<<sum;
return 0;
}

P1123 均分纸牌
#include <iostream>
using namespace std;
int a[10000];
int main()
{
int i,j,n,sum=0,t=0;
cin>>n;
for(i=0;i<n;i++)
{
cin>>a[i];
sum+=a[i];
}
sum/=n;
for(i=0;i<n-1;i++)
{
if(a[i]!=sum)
{
a[i+1]+=a[i]-sum;
t++;
}
}
cout<<t;
return 0;
}

P1127 级数求和
#include <iostream>
using namespace std;
int main()
{
int i=1,k;
double sum=1;
cin>>k;
while(sum<=k)
{
i++;
sum+=1/double (i);
}
cout<<i;
return 0;
}

P1128 选数
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int a[100];
bool t[6000001];
int n,k,sum=0;
void search(int m,int r,int s)
{
if(r==k) {if(t[s])sum++;/*cout<<s<<endl;*/return ;}
if(m>=n)return ;
search(m+1,r+1,s+a[m]);
search(m+1,r,s);
}
int main()
{
memset(t,true,sizeof(t));
int i,j;
cin>>n>>k;
for(i=0;i<n;i++)cin>>a[i];
for(i=2;i<5000000;i++)
{
if(t[i])
{
for(j=2;j<=5000000/i;j++)
t[i*j]=false;
}
}
search(0,0,0);
cout<<sum;
return 0;
}

P1130 数的计数
#include <stdio.h>
int add(int n);
int main()
{
int n;
scanf("%d",&n);
printf("%d",add(n));
return 0;
}
int add(int n)
{
int i,sum=1;
if(n==1)return sum;
else
for(i=1;i<=n/2;i++)
sum+=add(i);
return sum;
}

P1131 最小公倍数和最大公约数问题
#include <iostream> using namespace std;
bool check(int m,int n)
{
int i,k;
if(m>n)k=n;
else k=m;
for(i=2;i<=k;i++)
if(m%i==0&&n%i==0)return false;
return true;
}
int main()
{
int x,y;
cin>>x>>y;
if(x==y){cout<<1;return 0;}
if(x>y||y%x!=0){cout<<0;return 0;}
int i,j,n=y/x,sum=2;
for(i=2;i<n;i++)
{
if(n%i==0)
{
j=n/i;
if(check(i,j))sum++;
}
}
cout<<sum;
return 0;
}

P1132 求二叉树的先序序列
#include <iostream>
#include <cstring>
using namespace std; char pre[10],in[10],post[10]; void search(int pof,int pol,int inf,int inl)
{
cout<<post[pol];
if(pol==pof)return ;
int i,j,k,maxx=0,minn=100;
for(i=inf;i<=inl;i++)if(in[i]==post[pol])break;
for(j=inf;j<i;j++)
{
for(k=pof;k<=pol;k++)if(in[j]==post[k])break;
if(k>maxx)maxx=k;
if(k<minn)minn=k;
}
if(minn<=maxx)
search(minn,maxx,inf,i-1);
maxx=0;minn=100;
for(j=i+1;j<=inl;j++)
{
for(k=pof;k<=pol;k++)if(in[j]==post[k])break;
if(k>maxx)maxx=k;
if(k<minn)minn=k;
}
if(minn<=maxx)
search(minn,maxx,i+1,inl);
return ;
}
int main()
{
cin>>in>>post;
int l=strlen(in)-1;
search(0,l,0,l);
return 0;
}

P1133 装箱问题
#include <iostream>
#include <cstring>
using namespace std;
bool dp[31][20001];
int size[31];
int totalSize,n,maxx=1;
void search(int l,int c)
{
if(l==n)
{
if(c>maxx)maxx=c;
return ;
}
if(!dp[l][c])return ;
dp[l][c]=false;
search(l+1,c);
if(c+size[l]<=totalSize)
search(l+1,c+size[l]);
}
int main()
{
memset(dp,true,sizeof(dp));
int i;
cin>>totalSize>>n;
for(i=0;i<n;i++)cin>>size[i];
search(0,0);
cout<<totalSize-maxx;
return 0;
}

P1141 最小非负值
#include <iostream>
#include <stdlib.h>
#include <cstring>
using namespace std;
char s1[10000],s2[10000];
int a[10000],b[10000],c[1000000];
int main()
{
int i,j,k=0;
cin>>s1;
strcpy(s2,s1);
strrev(s1);strrev(s2);
s2[0]++;
memset(c,0,sizeof(c));
int la=strlen(s1),lb=strlen(s2),lc;
for (i=0;i<la;i++) a[i]=s1[i]-48;
for (i=0;i<lb;i++) b[i]=s2[i]-48;
for (i=0;i<la;i++)
for (j=0;j<lb+1;j++)
{
c[i+j]+=a[i]*b[j]+k;
k=c[i+j]/10;
c[i+j]%=10;
}
lc=la+lb+10;
while (c[lc]==0) lc--;
for(i=lc;i>=0;i--)
{
if(c[i]%2==1&&i>0)
c[i-1]+=10;
if(i==0&&c[i]%2==1){cout<<1;system("pause");return 0;}
c[i]/=2;
}
cout<<c[0]%2;
return 0;
}

P1211 生日日数
#include <iostream>
using namespace std;
int a[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check(int n)
{
if(n%4==0&&(n%100!=0||n%400==0))return true;
return false;
}
int main()
{
int year,month,day;
int i,j,m;
cin>>year>>month>>day;
m=(year-1949)*365;
for(i=1949;i<year;i++)if(check(i))m++;
for(i=1;i<month;i++)
{
m+=a[i];
if(i==2&&check(year))m++;
}
m+=day;
m+=10000;
i=1949;
while(m>365&&(m>366||!check(i)))
{
m-=365;
if(check(i))m--;
i++;
if(m==0){cout<<i<<"-"<<1<<"-"<<1;}
}
cout<<i<<"-";
j=i;i=1;
while(m>a[i]&&(m>29||!(i==2&&check(j))))
{
m-=a[i];
if(i==2&&check(j))m--;
i++;
if(m==0)cout<<i<<"-"<<1;
}
cout<<i<<"-"<<m;
return 0;
}