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

P1000 A+B Problem
#include <iostream>
using namespace std;
int main()
{
int a,b;
cin>>a>>b;
cout<<a+b;
return 0;
}

P1001 谁拿了最多奖学金
#include <iostream>
#include <cstring>
using namespace std;
struct student
{
string name;
int testScore;
int classScore;
bool moniter;
bool westStudent;
int paperAmount;
int prize;
};
student stu[100];
int maxx=0,maxx_i,totalPrize=0;
void in(int i)
{
char s;
cin>>stu[i].name>>stu[i].testScore>>stu[i].classScore;
cin>>s;
if(s=='Y')stu[i].moniter=true;
else stu[i].moniter=false;
cin>>s;
if(s=='Y')stu[i].westStudent=true;
else stu[i].westStudent=false;
cin>>stu[i].paperAmount;
}
void award(int i)
{
stu[i].prize=0;
if(stu[i].testScore>80&&stu[i].paperAmount>0)stu[i].prize+=8000;
if(stu[i].testScore>85&&stu[i].classScore>80)stu[i].prize+=4000;
if(stu[i].testScore>90)stu[i].prize+=2000;
if(stu[i].testScore>85&&stu[i].westStudent)stu[i].prize+=1000;
if(stu[i].classScore>80&&stu[i].moniter)stu[i].prize+=850;
if(stu[i].prize>maxx){maxx=stu[i].prize;maxx_i=i;}
totalPrize+=stu[i].prize;
}
int main()
{
int i,n;
char s;
cin>>n;
for(i=0;i<n;i++)
{
in(i);
award(i);
}
cout<<stu[maxx_i].name<<endl;
cout<<stu[maxx_i].prize<<endl;
cout<<totalPrize;
return 0;
}

P1002 过河
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int l,m,s,t;
int a[100];
int dp[40000];
bool d[40000];
int main()
{
cin>>l>>s>>t>>m;
int i,j,k;
for(i=0;i<m;i++)cin>>a[i];
sort(a,a+m);
if(s==t)
{
i=0;
j=0;
int sum=0;
for(i=0;i<=m;i++)
{
if(i==0)
{
k=a[i]-a[i]%s;
for(j=0;j<m;j++)a[j]-=k;
l-=k;
}
if(a[i]-a[i-1]>2*s)
{
k=a[i]-a[i-1]-(a[i]-a[i-1])%s;
for(j=i;j<m;j++)a[j]-=k;
l-=k;
}
if(i==m)
{
k=l-a[i-1]-(l-a[i-1])%s;
l-=k;
}
}
i=0;j=0;
while(i<l)
{
i+=s;
while(i>a[j]&&i<l)j++;
while(i==a[j++])sum++;
if(i==a[j])j++;
}
cout<<sum;
return 0;
}
fill(dp,dp+40000,10000);
memset(d,0,sizeof(d));
dp[0]=0;
for(i=0;i<=m;i++)
{
if(i==0&&a[i]>300)
{
k=a[i]-300;
for(j=0;j<m;j++)a[j]-=k;
l-=k;
}
else if(i==m&&l-a[i-1]>300)l=a[i-1]+300;
else if(a[i]-a[i-1]>300)
{
k=a[i]-a[i-1]-300;
for(j=i;j<m;j++)a[j]-=k;
l-=k;
}
}
for(i=0;i<m;i++)d[a[i]]=true;
for(i=s;i<l+t;i++)
for(j=s;j<=t;j++)
if(i-j>=0)if(dp[i-j]+d[i]<dp[i])dp[i]=dp[i-j]+d[i];
int minn=100000;
for(i=l;i<l+t;i++)if(dp[i]<minn)minn=dp[i];
cout<<minn;
return 0;
}

P1007 绕钉子的长绳子
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
double x[1000],y[1000];
int main()
{
double r,c=0,t1,t2;
int i,j,n;
cin>>n>>r;
for(i=0;i<n;i++)cin>>x[i]>>y[i];
for(i=0;i<n;i++)
{
if(i==n-1)
{
t1=abs(y[i]-y[0]);t2=abs(x[i]-x[0]);
if(x[i]==x[0])c+=t1;
else if(y[i]==y[0])c+=t2;
else c+=sqrt(t1*t1+t2*t2);
break;
}
t1=abs(y[i]-y[i+1]);t2=abs(x[i]-x[i+1]);
if(x[i]==x[i+1])c+=t1;
else if(y[i]==y[i+1])c+=t2;
else c+=sqrt(t1*t1+t2*t2);
}
c+=r*2*3.1415926;
printf("%.2f",c);
return 0;
}

P1011 清帝之惑之顺治
#include <iostream>
#include <cstring>
using namespace std;
struct arr
{
int x;
int y;
};
long a[1001][1001],maxx[1001][1001];
int r,c;
arr q[100000];
void search(int x,int y)
{
int head=1,tail=1;
if(maxx[x][y]==0)maxx[x][y]=1;
q[head].x=x;
q[head].y=y;
while(head<=tail)
{
x=q[head].x;
y=q[head].y;
if(x>0&&a[x-1][y]<a[x][y]&&maxx[x-1][y]<maxx[x][y]+1)
{
tail++;
q[tail].x=x-1;
q[tail].y=y;
maxx[x-1][y]=maxx[x][y]+1;
}
if(y>0&&a[x][y-1]<a[x][y]&&maxx[x][y-1]<maxx[x][y]+1)
{
tail++;
q[tail].x=x;
q[tail].y=y-1;
maxx[x][y-1]=maxx[x][y]+1;
}
if(x<r-1&&a[x+1][y]<a[x][y]&&maxx[x+1][y]<maxx[x][y]+1)
{
tail++;
q[tail].x=x+1;
q[tail].y=y;
maxx[x+1][y]=maxx[x][y]+1;
}
if(y<c-1&&a[x][y+1]<a[x][y]&&maxx[x][y+1]<maxx[x][y]+1)
{
tail++;
q[tail].x=x;
q[tail].y=y+1;
maxx[x][y+1]=maxx[x][y]+1;
}
head++;
}
}
int main()
{
memset(maxx,0,sizeof(maxx));
int i,j;
long m=0;
cin>>r>>c;
for(i=0;i<r;i++)
for(j=0;j<c;j++)
cin>>a[i][j];
for(i=0;i<r;i++)
for(j=0;j<c;j++)
search(i,j);
for(i=0;i<r;i++)
for(j=0;j<c;j++)
if(maxx[i][j]>m)m=maxx[i][j];
cout<<m;
return 0;
}

P1016 北京2008的挂钟
#include <iostream>
#include <cstring> using namespace std;
int effect[9][5]={{1,2,4,5,0},{1,2,3,0,0},{2,3,5,6,0},{1,4,7,0,0},{2,4,5,6,8},{3,6,9,0,0},{4,5,7,8,0},{7,8,9,0,0},{5,6,8,9,0}};
int size[9]={4,3,4,3,5,3,4,3,4};
int a[10];
int clocks[10];
int t[10];
void print()
{
for(int i=0;i<9;i++)
for(int j=0;j<a[i];j++)cout<<i+1<<" ";
}
bool check()
{
int i,j,k,c;
for(i=0;i<9;i++)t[i]=clocks[i];
for(i=0;i<9;i++)
{
if(a[i]==0)continue;
for(j=0;j<a[i];j++)
{
for(k=0;k<size[i];k++)
{
t[effect[i][k]-1]=(t[effect[i][k]-1]+3)%12;
}
}
}
for(i=0;i<9;i++)if(t[i]!=0&&t[i]!=12)return false;
print();
return true;
}
int main()
{
int i;
for(i=0;i<9;i++){cin>>clocks[i];clocks[i]*=3;}
for(a[8]=0;a[8]<4;a[8]++)
for(a[7]=0;a[7]<4;a[7]++)
for(a[6]=0;a[6]<4;a[6]++)
for(a[5]=0;a[5]<4;a[5]++)
for(a[4]=0;a[4]<4;a[4]++)
for(a[3]=0;a[3]<4;a[3]++)
for(a[2]=0;a[2]<4;a[2]++)
for(a[1]=0;a[1]<4;a[1]++)
for(a[0]=0;a[0]<4;a[0]++)
if(check())return 0;
return 0;
}

P1034 家族
#include <iostream> using namespace std;
int father[5001];
int getFather(int x)
{
if(father[x]==x)return x;
return getFather(father[x]);
}
int main()
{
int n,m,p;
int i,j,k;
int t1,t2,t3,t4;
cin>>n>>m>>p;
for(i=1;i<=n;i++)father[i]=i;
for(i=0;i<m;i++)
{
cin>>t1>>t2;
t3=getFather(t1);
t4=getFather(t2);
if(t3!=t4)father[t4]=t3;
}
for(i=0;i<p;i++)
{
cin>>t1>>t2;
if(getFather(t1)==getFather(t2))cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}

P1035 贪婪的送礼者
#include <iostream>
#include <cstring>
using namespace std;
char name[11][20];
char s[20];
int n;
int money[11],people[11];
int ans[11];
int main()
{
memset(ans,0,sizeof(ans));
cin>>n;
int i,j,k,p;
for(i=0;i<n;i++)cin>>name[i];
for(i=0;i<n;i++)
{
cin>>s;
for(j=0;j<n;j++)if(strcmp(s,name[j])==0)break;
cin>>money[j]>>people[j];
ans[j]+=money[j];
if(people[j]==0)continue;
for(k=0;k<people[j];k++)
{
cin>>s;
for(p=0;p<n;p++)if(strcmp(s,name[p])==0)break;
ans[p]+=money[j]/people[j];
}
ans[j]-=money[j]/people[j]*people[j];
}
for(i=0;i<n;i++)cout<<name[i]<<" "<<ans[i]-money[i]<<endl;
return 0;
}

P1041 神风堂人数
#include <iostream>
using namespace std;
int main()
{
int i;
double p,q,j;
cin>>p>>q;
for(i=1;1;i++)
if(int(q*i/100-0.0000000001)-int(p*i/100+0.0000000001)>=1)
{
cout<<i;
return 0;
}
}

P1051 送给圣诞夜的极光
#include<iostream>
#include<string.h>
#include <stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
bool c[102][102];
char a[102][102];
int i,j,k,s=0,n,m,b1,b2;
int f(int x,int y)
{
if(!c[x][y])return 0;
if(c[x][y]==true){
c[x][y]=false;
if(x>0)f(x-1,y);
if(x>0&&y>0)f(x-1,y-1);
if(x>1)f(x-2,y);
if(x<n-1)f(x+1,y);
if(x<n-1&&y<m-1)f(x+1,y+1);
if(x>0&&y<m-1)f(x-1,y+1);
if(x<n-2)f(x+2,y);
if(x<n-1&&y>0)f(x+1,y-1);
if(y>1)f(x,y-2);
if(y>0)f(x,y-1);
if(y<m-1)f(x,y+1);
if(y<m-2)f(x,y+2);
}
}
int main()
{
cin>>n>>m;
for(i=0;i<n;i++)
for(j=0;j<m;j++){
cin>>a[i][j];
if(a[i][j]=='#'){
c[i][j]=true;
}
else c[i][j]=false;
}
for(i=0;i<n;i++)
for(j=0;j<m;j++){
if(c[i][j]){
f(i,j);
s++;
}
}
cout<<s<<endl;
return 0;
}

P1096 津津的储蓄计划
#include <iostream> using namespace std;
int main()
{
int i,n,m=0,l=0;
for(i=1;i<=12;i++)
{
cin>>n;
m=m+300-n;
if(m<0){cout<<"-"<<i;return 0;}
else
{
l+=m/100*100;
m%=100;
}
}
cout<<m+l*1.2;
return 0;
}

P1097 合并果子
#include <iostream>
#include <cstring>
using namespace std;
int a[ 20001 ];
int ta[ 65537 ];
int tt[ 20001];
void jisort(int N)
{
int i,j,k;
memset( ta, 0, sizeof( ta ) );
for (int i = 0; i < N; i++ ) ta[ a[i] & 0xffff ] ++;
for (int i = 0; i < 65535; i++ ) ta[ i + 1 ] += ta[ i ];
for (int i = 0; i < N; i++ ) tt[ -- ta[ a[i] & 0xffff ] ] = a[i];
memset( ta, 0, sizeof( ta ) );
for (int i = 0; i < N; i++ ) ta[ tt[i] >> 16 ] ++;
for (int i = 0; i < 65535; i++ ) ta[ i + 1 ] += ta[ i ];
for (int i = N - 1; i >= 0; i-- ) a[ -- ta[ tt[i] >> 16 ] ] = tt[i];
}
int main()
{
memset(a,10000000,sizeof(a));
int i,j,k,t,n;
long sum=0;
cin>>n;
for (i=0;i<n;i++) cin>>a[i];
jisort(n);
for (i=0;i<n-1;i++)
{
a[0]+=a[1];
sum+=a[0];
j=2;
while(a[0]>a[j]&&j<n-i)j++;
if(j>2)
{
t=a[0];
for(k=0;k<j-2;k++)
a[k]=a[k+2];
a[j-2]=t;
}
for(k=j-1;k<n-i-1;k++)
a[k]=a[k+1];
}
cout<<sum;
return 0;
}

P1102 陶陶摘苹果
#include <iostream>
using namespace std;
int main()
{
int a[10];
int i,n,sum=0;
for(i=0;i<10;i++)cin>>a[i];
cin>>n;
n+=30;
for(i=0;i<10;i++)
if(a[i]<=n)sum++;
cout<<sum;
return 0;
}

P1103 校门外的树
#include <iostream>
#include <cstring>
using namespace std;
bool a[10001];
int main()
{
memset(a,true,sizeof(a));
int i,j,n,m,l,r,sum=0;
cin>>n>>m;
for(i=0;i<m;i++)
{
cin>>l>>r;
for(j=l;j<=r;j++)a[j]=false;
}
for(i=0;i<=n;i++)if(a[i])sum++;
cout<<sum;
return 0;
}