首页 > 代码库 > ACM--South Pacific 2012
ACM--South Pacific 2012
题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=584
A:UVAlive 6161 Decision Making
题意：给出01字符串，判断中间两位是否相同，相同就输出Do-it，否者输出Do-it-Not。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 #define inf 0x7fffffff 8 using namespace std; 9 const int maxn=1000000+100;10 char str[maxn];11 int main()12 {13 int t;14 cin>>t;15 while (t--)16 {17 memset(str,0,sizeof(str));18 scanf("%s",str+1);19 int len=strlen(str+1);20 if (str[len/2]==str[len/2+1]) cout<<"Do-it"<<endl;21 else cout<<"Do-it-Not"<<endl;22 }23 return 0;24 }
B：UVAlive 6162 Log Books
题意：一个人学习练车，如果练车时间累加达到50个小时（包括夜晚练车时间10个小时）的话，就通过考核。在每天的练车时间中，不能超过2小时，题目输入中每行给出4个时刻，分别是日升、日落、练车开始时刻、练车结束时刻。如果在日落后或者在日升前练车的话，这段时间就算作夜晚的练车时间。如果整个练车时间里有超过一半的时间在夜晚练车时间，那么整个时间都算作夜晚练车时间。
解法：水题一类，按照题意模拟，注意细节处理就可以了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 #define inf 0x7fffffff 8 using namespace std; 9 int n;10 int main()11 {12 int n;13 int a,b,c,d,e,f,g,h;14 int total=0,night=0;15 while (cin>>n,n)16 {17 total=night=0;18 int ok=0;19 for (int i=1 ;i<=n ;i++)20 {21 scanf("%d:%d %d:%d %d:%d %d:%d",&a,&b,&c,&d,&e,&f,&g,&h);22 int num1=a*60+b;23 int num2=c*60+d;24 int num3=e*60+f;25 int num4=g*60+h;26 if (num4-num3>120) ok=1;27 total += num4-num3;28 if (num3<num4 && num4<=num1) night += num4-num3;29 else if (num3<=num1&&num4<=num2) night += num1-num3;30 else if (num3<=num1&&num2<=num4) night += num1-num3+num4-num2;31 else if (num1<num3&&num3<=num2&&num2<num4) night += num4-num2;32 else if (num2<=num3) night += num4-num3;33 }34 if (ok) cout<<"NON"<<endl;35 else if (total>=50*60 && night>=10*60) cout<<"PASS"<<endl;36 else cout<<"NON"<<endl;37 }38 return 0;39 }
C：UVAlive 6163 Myth Busters
题意：给出很多组的数字串，每组数字串由4个数字组成。对于每组数字串来说，你可以在每个数字前面加上+,-,*,/,(,),使其每组数字串之和为10，就让我们每组数字串的和是否都有可能为10。
解法：由于只有4个数字，我们可以先把其中两个数字合并在一起，就只有3个数字了，接下来又在3个数字中选择其中2个合并起来，这样就成了2个数字的运算了。
通过枚举运算符号和括号、next_permutation函数就可以实现上面说的方法了。
注意一点：这道题里面如果把减号放在一个数前面，不能把它整体看成负数来处理。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 #define inf 0x7fffffff 8 using namespace std; 9 int n; 10 int cmp(int i,int j) {return i<j; } 11 int main() 12 { 13 int an[5]; 14 char str[5]; 15 while (cin>>n,n) 16 { 17 int count=0; 18 int bn[5],cn[5]; 19 for (int k=1 ;k<=n ;k++) 20 { 21 for (int j=1 ;j<=4 ;j++) {cin>>str[j];an[j]=str[j]-‘0‘;} 22 sort(an+1,an+4+1,cmp); 23 int cnt=0; 24 int flag=1; 25 do { 26 for (int i=1 ;i<=4 ;i++) { 27 if (i==1) bn[1]=an[1]+an[2]; 28 else if (i==2) bn[1]=an[1]-an[2]; 29 else if (i==3) bn[1]=an[1]*an[2]; 30 else if (i==4 && an[2]) bn[1]=an[1]/an[2]; 31 //else if (i==5) bn[1]=-an[1]+an[2]; 32 //else if (i==6) bn[1]=-an[1]-an[2]; 33 //else if (i==7) bn[1]=(-an[1])*an[2]; 34 //else if (i==8 && an[2]) bn[1]=(-an[1])/an[2]; 35 bn[2]=an[3]; 36 bn[3]=an[4]; 37 sort(bn+1,bn+4,cmp); 38 do 39 { 40 for (int j=1 ;j<=4 ;j++) { 41 if (j==1) cn[1]=bn[1]+bn[2]; 42 else if (j==2) cn[1]=bn[1]-bn[2]; 43 else if (j==3) cn[1]=bn[1]*bn[2]; 44 else if (j==4 && bn[2]) cn[1]=bn[1]/bn[2]; 45 //else if (j==5) cn[1]=-bn[1]+bn[2]; 46 //else if (j==6) cn[1]=-bn[1]-bn[2]; 47 //else if (j==7) cn[1]=(-bn[1])*bn[2]; 48 //else if (j==8 && bn[2]) cn[1]=(-bn[1])/bn[2]; 49 cn[2]=bn[3]; 50 sort(cn+1,cn+3,cmp); 51 do 52 { 53 int sum=cn[1]+cn[2];if (sum==10) {flag=0;break; } 54 sum=cn[1]-cn[2];if (sum==10) {flag=0;break; } 55 sum=cn[1]*cn[2];if (sum==10) {flag=0;break; }if (cn[2]) 56 sum=cn[1]/cn[2];if (sum==10) {flag=0;break; } 57 //sum=(-cn[1])+cn[2];if (sum==10) {flag=0;break; } 58 //sum=(-cn[1])-cn[2];if (sum==10) {flag=0;break; } 59 //sum=(-cn[1])*cn[2];if (sum==10) {flag=0;break; }if (cn[2]) 60 //sum=(-cn[1])/cn[2];if (sum==10) {flag=0;break; } 61 62 }while(next_permutation(cn+1,cn+3) && flag); 63 } 64 65 }while (next_permutation(bn+1,bn+4) && flag); 66 sort(bn+1,bn+4,cmp); 67 do 68 { 69 for (int j=1 ;j<=4 ;j++) { 70 if (j==1) cn[1]=bn[2]+bn[3]; 71 else if (j==2) cn[1]=bn[2]-bn[3]; 72 else if (j==3) cn[1]=bn[2]*bn[3]; 73 else if (j==4 && bn[3]) cn[1]=bn[2]/bn[3]; 74 //else if (j==5) cn[1]=-bn[2]+bn[3]; 75 //else if (j==6) cn[1]=-bn[2]-bn[3]; 76 //else if (j==7) cn[1]=(-bn[2])*bn[3]; 77 //else if (j==8 && bn[3]) cn[1]=(-bn[2])/bn[3]; 78 cn[2]=bn[1]; 79 sort(cn+1,cn+3,cmp); 80 do 81 { 82 int sum=cn[1]+cn[2];if (sum==10) {flag=0;break; } 83 sum=cn[1]-cn[2];if (sum==10) {flag=0;break; } 84 sum=cn[1]*cn[2];if (sum==10) {flag=0;break; }if (cn[2]) 85 sum=cn[1]/cn[2];if (sum==10) {flag=0;break; } 86 //s/um=(-cn[1])+cn[2];if (sum==10) {flag=0;break; } 87 //sum=(-cn[1])-cn[2];if (sum==10) {flag=0;break; } 88 //sum=(-cn[1])*cn[2];if (sum==10) {flag=0;break; }if (cn[2]) 89 //sum=(-cn[1])/cn[2];if (sum==10) {flag=0;break; } 90 91 }while(next_permutation(cn+1,cn+3) && flag); 92 } 93 94 }while (next_permutation(bn+1,bn+4) && flag); 95 96 } 97 }while (next_permutation(an+1,an+5) && flag); 98 if (flag==0) {count++; } 99 }100 if (count==n) cout<<"TRUE"<<endl;101 else cout<<"BUSTED"<<endl;102 }103 return 0;104 }
G：UVAlive 6167 Fridge Lock
题意：有一个密码锁，有k层密码组成，每一层有一些数字，然后从k层中每层选出一个数来构成一个方程组，题目给出这样的k组方程式的系数和运算结果，要你在k层中找到这样的解满足这k组方程。
解法：高斯消元解方程组。然后判断解出的解x1,x2,x3....xk是否在k层密码数字中（x1是否在k1这一层数字中，x2是否在k2这一层中...）
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<cstdlib> 6 #include<algorithm> 7 #define inf 0x7fffffff 8 #define eps 1e-10 9 using namespace std; 10 typedef long long LL; 11 int n; 12 int an[11][55]; 13 bool free_x[60]; ///判断是否是不确定的变元 14 double x[60]; ///解集 15 int sign(double x){ return (x>eps) - (x<-eps);} 16 int Gauss(double A[][60]) 17 { 18 int i,j; 19 int row,col,max_r; 20 for(row=0,col=0; row<n&&col<n; row++,col++) 21 { 22 max_r = row; 23 for(i = row+1; i < n; i++) ///找到当前列所有行中的最大值(做除法时减小误差) 24 { 25 if(sign(fabs(A[i][col])-fabs(A[max_r][col]))>0) 26 max_r = i; 27 } 28 if(max_r != row) ///将该行与当前行交换 29 { 30 for(j = row; j < n+1; j++) 31 swap(A[max_r][j],A[row][j]); 32 } 33 if(sign(A[row][col])==0) ///当前列row行以下全为0(包括row行) 34 { 35 row--; 36 continue; 37 } 38 for(i = row+1; i < n; i++) 39 { 40 if(sign(A[i][col])==0) 41 continue; 42 double ta = A[i][col]/A[row][col]; 43 for(j = col; j < n+1; j++) 44 A[i][j] -= A[row][j]*ta; 45 } 46 } 47 for(i = row; i < n; i++) ///col=n存在0...0,a的情况,无解 48 { 49 if(sign(A[i][col])) 50 return -1; 51 } 52 if(row < n) ///存在0...0,0的情况,有多个解,自由变元个数为n-row个 53 { 54 memset(free_x,true,sizeof(free_x)); 55 for(i = row-1; i >=0; i--) 56 { 57 int free_num = 0; ///自由变元的个数 58 int free_index; ///自由变元的序号 59 for(j = 0; j < n; j++) 60 { 61 if(sign(A[i][j])!=0 && free_x[j]) 62 free_num++,free_index=j; 63 } 64 if(free_num > 1) continue; ///该行中的不确定的变元的个数超过1个,无法求解,它们仍然为不确定的变元 65 ///只有一个不确定的变元free_index,可以求解出该变元,且该变元是确定的 66 double tmp = A[i][n]; 67 for(j = 0; j < n; j++) 68 { 69 if(sign(A[i][j])!=0 && j!=free_index) 70 tmp -= A[i][j]*x[j]; 71 } 72 x[free_index] = tmp/A[i][free_index]; 73 free_x[free_index] = false; 74 } 75 return n-row; 76 } 77 ///有且仅有一个解,严格的上三角矩阵(n==m) 78 for(i = n-1; i >= 0; i--) 79 { 80 double tmp = A[i][n]; 81 for(j = i+1; j < n; j++) 82 if(sign(A[i][j])!=0) 83 tmp -= A[i][j]*x[j]; 84 x[i] = tmp/A[i][i]; 85 } 86 return 0; 87 } 88 //void gauss_elimination(double A[][60],int n) 89 //{ 90 // int i,j,k,r; 91 // for (i=0 ;i<n ;i++) 92 // { 93 // r=i; 94 // for (j=i+1 ;j<n ;j++) 95 // if (fabs(A[j][i])>fabs(A[r][i])) r=j; 96 // if (r!=i) for (j=0 ;j<=n ;j++) swap(A[r][j],A[i][j]); 97 // for (k=i+1 ;k<n ;k++) 98 // { 99 // double f=A[k][i]/A[i][i];100 // for (j=i ;j<=n ;j++) A[k][j] -= f*A[i][j];101 // }102 // }103 // for (i=n-1 ;i>=0 ;i--)104 // {105 // for (j=i+1 ;j<n ;j++)106 // A[i][n] -= A[j][n]*A[i][j];107 // A[i][n] /= A[i][i];108 // }109 //}110 int main()111 {112 while (cin>>n,n)113 {114 int a;115 char c;116 getchar();117 char str[111];118 for (int i=0 ;i<n ;i++)119 {120 int sum=0;121 int cnt=0;122 memset(str,0,sizeof(str));123 gets(str);124 int len=strlen(str);125 for (int j=0 ;j<len ;j++)126 {127 if (str[j]==‘ ‘)128 {129 an[i][cnt++]=sum;130 sum=0;131 }132 else sum=sum*10+str[j]-‘0‘;133 if (j==len-1) an[i][cnt++]=sum;134 }135 an[i][cnt]=-1;136 }137 double bn[11][60];138 for (int i=0 ;i<n ;i++)139 {140 for (int j=0 ;j<n ;j++) cin>>bn[i][j];141 scanf(" = %lf",&bn[i][n]);142 }143 // for (int i=0 ;i<n ;i++)144 // {145 // for (int j=0 ;j<=n ;j++) cout<<bn[i][j]<<" ";146 // cout<<endl;147 // }148 int h=Gauss(bn);149 //gauss_elimination(bn,n);150 // for (int i=0 ;i<n ;i++)151 // {152 // for (int j=0 ;j<=n ;j++) cout<<bn[i][j]<<" ";153 // cout<<endl;154 // }155 if (h)156 {157 for (int i=0 ;i<h ;i++) cout<<x[i]<<" ";158 for (int i=h ;i<n ;i++) cout<<an[i][0]<<" ";159 cout<<endl;160 }161 else162 {163 for (int i=0 ;i<n ;i++) cout<<x[i]<<" ";164 cout<<endl;165 }166 }167 return 0;168 }
I:UVAlive 6169 Class Packing
题意：学校有幼儿园和小学一到六个年级，一个班对应一个老师，现在每个年级有一批学生，幼儿园到二年级每个班最多容纳20个人，三到四年级每个班最多容纳25个人，五到六年级一个班最多30人，每个年级的同学如果人数没有达到上限，可以从相邻的年级凑人数，比如三年级的人数不够的话，只能从二年级和四年级中找同学来凑。现在问最少需要多少个老师。
解法：贪心。我们先从幼儿园开始，幼儿园组成几个班后，如果人数不够的话，就从一年级学生中找来；接着处理一年级的人数，如果有空缺，就从三年级中找同学来；按此方法接着四年级、五年级。最后处理六年级，如果六年级人数不够的话，就不用填补了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 #define inf 0x7fffffff 8 using namespace std; 9 //20 20 20 25 25 30 3010 int main()11 {12 int an[7];13 while (cin>>an[0]>>an[1]>>an[2]>>an[3]>>an[4]>>an[5]>>an[6])14 {15 if (!an[0] && !an[1] && !an[2] && !an[3] && !an[4] && !an[5] && !an[6]) break;16 int count=0;17 if (an[0]%20)18 {19 count += an[0]/20+1;20 an[1] -= (20-(an[0]%20));21 }22 else count += an[0]/20;23 if (an[1]<=0) {}24 else if (an[1]%20)25 {26 count += an[1]/20+1;27 an[2] -= (20-(an[1]%20));28 }29 else count += an[1]/20;30 if (an[2]<=0) {}31 else if (an[2]%20)32 {33 count += an[2]/20+1;34 an[3] -= (20-(an[2]%20));35 }36 else count += an[2]/20;37 if (an[3]<=0) {}38 else if (an[3]%25)39 {40 count += an[3]/25+1;41 an[4] -= (25-(an[3]%25));42 }43 else count += an[3]/25;44 if (an[4]<=0) {}45 else if (an[4]%25)46 {47 count += an[4]/25+1;48 an[5] -= (25-(an[4]%25));49 }50 else count += an[4]/25;51 if (an[5]<=0) {}52 else if (an[5]%30)53 {54 count += an[5]/30+1;55 an[6] -= (30-(an[5]%30));56 }57 else count += an[5]/30;58 if (an[6]<=0) {}59 else if (an[6]%30) count += an[6]/30+1;60 else count += an[6]/30;61 cout<<count<<endl;62 }63 return 0;64 }
J：UVAlive 6170 Esspe-Peasee
题意：给出一个foom、food和twob的值，要求是否有这样一组解，满足x个foom 和 y个food 等于1个twob的值，如果有满足，输出x+y最小的一组。
解法：扩展欧几里德算法。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 #define inf 0x7fffffff 8 using namespace std; 9 typedef long long LL;10 LL x,y,z;11 LL q;12 LL u,v,w;13 LL gcd(LL a,LL b)14 {15 if (!b) return a;16 return gcd(b,a%b);17 }18 void exgcd(LL a,LL b)19 {20 if (!b) {x=1 ;y=0 ;q=a; }21 else22 {23 exgcd(b,a%b);24 LL temp=x ;x=y ;y=temp-a/b*y;25 }26 }27 int main()28 {29 while (cin>>u>>v>>w)30 {31 if (!u && !v && !w) break;32 LL d=gcd(u,v);33 if (w%d)34 {35 cout<<"Unquibable!"<<endl;36 continue;37 }38 LL c=w/d;39 //u /= d ;v /= d;40 exgcd(u,v);41 x=((((x%(v/d)+(v/d))%(v/d))*(c%(v/d))+(v/d))%(v/d));42 y=(w-u*x)/v;43 if (y<0)44 {45 cout<<"Unquibable!"<<endl;46 continue;47 }48 // x *= c ;y *= c;49 // x=(x%v+v)%v;50 // y=(y%u+u)%u;51 // int flag=0;52 // for (LL k=-100 ;k<100 ;k++)53 // {54 // LL x1=x+k*(v/d);55 // LL y1=y-k*(u/d);56 // if (x1>=0 && y1>=0 && x1*u<y1*v)57 // {58 //59 // if (x1+y1<x+y)60 // {61 // flag=1;62 // x=x1 ;y=y1 ;63 // }64 // }65 // }66 // if (!flag) {cout<<"Unquibable!"<<endl;continue;}67 cout<<x<<" foom";68 if (x!=1) cout<<"s";69 cout<<" and "<<y<<" foob";70 if (y!=1) cout<<"s";71 cout<<" for a twob!"<<endl;72 73 }74 return 0;75 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。