题目链接：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。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define inf 0x7fffffff
using namespace std;
const int maxn=+;
char str[maxn];
int main()
{
int t;
cin>>t;
while (t--)
{
memset(str,,sizeof(str));
scanf("%s",str+);
int len=strlen(str+);
if (str[len/]==str[len/+]) cout<<"Do-it"<<endl;
else cout<<"Do-it-Not"<<endl;
}
return ;
}
题意：一个人学习练车，如果练车时间累加达到50个小时（包括夜晚练车时间10个小时）的话，就通过考核。在每天的练车时间中，不能超过2小时，题目输入中每行给出4个时刻，分别是日升、日落、练车开始时刻、练车结束时刻。如果在日落后或者在日升前练车的话，这段时间就算作夜晚的练车时间。如果整个练车时间里有超过一半的时间在夜晚练车时间，那么整个时间都算作夜晚练车时间。
解法：水题一类，按照题意模拟，注意细节处理就可以了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define inf 0x7fffffff
using namespace std;
int n;
int main()
{
int n;
int a,b,c,d,e,f,g,h;
int total=,night=;
while (cin>>n,n)
{
total=night=;
int ok=;
for (int i= ;i<=n ;i++)
{
scanf("%d:%d %d:%d %d:%d %d:%d",&a,&b,&c,&d,&e,&f,&g,&h);
int num1=a*+b;
int num2=c*+d;
int num3=e*+f;
int num4=g*+h;
if (num4-num3>) ok=;
total += num4-num3;
if (num3<num4 && num4<=num1) night += num4-num3;
else if (num3<=num1&&num4<=num2) night += num1-num3;
else if (num3<=num1&&num2<=num4) night += num1-num3+num4-num2;
else if (num1<num3&&num3<=num2&&num2<num4) night += num4-num2;
else if (num2<=num3) night += num4-num3;
}
if (ok) cout<<"NON"<<endl;
else if (total>=* && night>=*) cout<<"PASS"<<endl;
else cout<<"NON"<<endl;
}
return ;
}
题意：给出很多组的数字串，每组数字串由4个数字组成。对于每组数字串来说，你可以在每个数字前面加上+,-,*,/,(,),使其每组数字串之和为10，就让我们每组数字串的和是否都有可能为10。
解法：由于只有4个数字，我们可以先把其中两个数字合并在一起，就只有3个数字了，接下来又在3个数字中选择其中2个合并起来，这样就成了2个数字的运算了。
通过枚举运算符号和括号、next_permutation函数就可以实现上面说的方法了。
注意一点：这道题里面如果把减号放在一个数前面，不能把它整体看成负数来处理。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define inf 0x7fffffff
using namespace std;
int n;
int cmp(int i,int j) {return i<j; }
int main()
{
int an[];
char str[];
while (cin>>n,n)
{
int count=;
int bn[],cn[];
for (int k= ;k<=n ;k++)
{
for (int j= ;j<= ;j++) {cin>>str[j];an[j]=str[j]-'';}
sort(an+,an++,cmp);
int cnt=;
int flag=;
do {
for (int i= ;i<= ;i++) {
if (i==) bn[]=an[]+an[];
else if (i==) bn[]=an[]-an[];
else if (i==) bn[]=an[]*an[];
else if (i== && an[]) bn[]=an[]/an[];
//else if (i==5) bn[1]=-an[1]+an[2];
//else if (i==6) bn[1]=-an[1]-an[2];
//else if (i==7) bn[1]=(-an[1])*an[2];
//else if (i==8 && an[2]) bn[1]=(-an[1])/an[2];
bn[]=an[];
bn[]=an[];
sort(bn+,bn+,cmp);
do
{
for (int j= ;j<= ;j++) {
if (j==) cn[]=bn[]+bn[];
else if (j==) cn[]=bn[]-bn[];
else if (j==) cn[]=bn[]*bn[];
else if (j== && bn[]) cn[]=bn[]/bn[];
//else if (j==5) cn[1]=-bn[1]+bn[2];
//else if (j==6) cn[1]=-bn[1]-bn[2];
//else if (j==7) cn[1]=(-bn[1])*bn[2];
//else if (j==8 && bn[2]) cn[1]=(-bn[1])/bn[2];
cn[]=bn[];
sort(cn+,cn+,cmp);
do
{
int sum=cn[]+cn[];if (sum==) {flag=;break; }
sum=cn[]-cn[];if (sum==) {flag=;break; }
sum=cn[]*cn[];if (sum==) {flag=;break; }if (cn[])
sum=cn[]/cn[];if (sum==) {flag=;break; }
//sum=(-cn[1])+cn[2];if (sum==10) {flag=0;break; }
//sum=(-cn[1])-cn[2];if (sum==10) {flag=0;break; }
//sum=(-cn[1])*cn[2];if (sum==10) {flag=0;break; }if (cn[2])
//sum=(-cn[1])/cn[2];if (sum==10) {flag=0;break; } }while(next_permutation(cn+,cn+) && flag);
} }while (next_permutation(bn+,bn+) && flag);
sort(bn+,bn+,cmp);
do
{
for (int j= ;j<= ;j++) {
if (j==) cn[]=bn[]+bn[];
else if (j==) cn[]=bn[]-bn[];
else if (j==) cn[]=bn[]*bn[];
else if (j== && bn[]) cn[]=bn[]/bn[];
//else if (j==5) cn[1]=-bn[2]+bn[3];
//else if (j==6) cn[1]=-bn[2]-bn[3];
//else if (j==7) cn[1]=(-bn[2])*bn[3];
//else if (j==8 && bn[3]) cn[1]=(-bn[2])/bn[3];
cn[]=bn[];
sort(cn+,cn+,cmp);
do
{
int sum=cn[]+cn[];if (sum==) {flag=;break; }
sum=cn[]-cn[];if (sum==) {flag=;break; }
sum=cn[]*cn[];if (sum==) {flag=;break; }if (cn[])
sum=cn[]/cn[];if (sum==) {flag=;break; }
//s/um=(-cn[1])+cn[2];if (sum==10) {flag=0;break; }
//sum=(-cn[1])-cn[2];if (sum==10) {flag=0;break; }
//sum=(-cn[1])*cn[2];if (sum==10) {flag=0;break; }if (cn[2])
//sum=(-cn[1])/cn[2];if (sum==10) {flag=0;break; } }while(next_permutation(cn+,cn+) && flag);
} }while (next_permutation(bn+,bn+) && flag); }
}while (next_permutation(an+,an+) && flag);
if (flag==) {count++; }
}
if (count==n) cout<<"TRUE"<<endl;
else cout<<"BUSTED"<<endl;
}
return ;
}
题意：有一个密码锁，有k层密码组成，每一层有一些数字，然后从k层中每层选出一个数来构成一个方程组，题目给出这样的k组方程式的系数和运算结果，要你在k层中找到这样的解满足这k组方程。
解法：高斯消元解方程组。然后判断解出的解x1,x2,x3....xk是否在k层密码数字中（x1是否在k1这一层数字中，x2是否在k2这一层中...）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define inf 0x7fffffff
#define eps 1e-10
using namespace std;
typedef long long LL;
int n;
int an[][];
bool free_x[]; ///判断是否是不确定的变元
double x[]; ///解集
int sign(double x){ return (x>eps) - (x<-eps);}
int Gauss(double A[][])
{
int i,j;
int row,col,max_r;
for(row=,col=; row<n&&col<n; row++,col++)
{
max_r = row;
for(i = row+; i < n; i++) ///找到当前列所有行中的最大值(做除法时减小误差)
{
if(sign(fabs(A[i][col])-fabs(A[max_r][col]))>)
max_r = i;
}
if(max_r != row) ///将该行与当前行交换
{
for(j = row; j < n+; j++)
swap(A[max_r][j],A[row][j]);
}
if(sign(A[row][col])==) ///当前列row行以下全为0(包括row行)
{
row--;
continue;
}
for(i = row+; i < n; i++)
{
if(sign(A[i][col])==)
continue;
double ta = A[i][col]/A[row][col];
for(j = col; j < n+; j++)
A[i][j] -= A[row][j]*ta;
}
}
for(i = row; i < n; i++) ///col=n存在0...0,a的情况,无解
{
if(sign(A[i][col]))
return -;
}
if(row < n) ///存在0...0,0的情况,有多个解,*变元个数为n-row个
{
memset(free_x,true,sizeof(free_x));
for(i = row-; i >=; i--)
{
int free_num = ; ///*变元的个数
int free_index; ///*变元的序号
for(j = ; j < n; j++)
{
if(sign(A[i][j])!= && free_x[j])
free_num++,free_index=j;
}
if(free_num > ) continue; ///该行中的不确定的变元的个数超过1个,无法求解,它们仍然为不确定的变元
///只有一个不确定的变元free_index,可以求解出该变元,且该变元是确定的
double tmp = A[i][n];
for(j = ; j < n; j++)
{
if(sign(A[i][j])!= && j!=free_index)
tmp -= A[i][j]*x[j];
}
x[free_index] = tmp/A[i][free_index];
free_x[free_index] = false;
}
return n-row;
}
///有且仅有一个解,严格的上三角矩阵(n==m)
for(i = n-; i >= ; i--)
{
double tmp = A[i][n];
for(j = i+; j < n; j++)
if(sign(A[i][j])!=)
tmp -= A[i][j]*x[j];
x[i] = tmp/A[i][i];
}
return ;
}
//void gauss_elimination(double A[][60],int n)
//{
// int i,j,k,r;
// for (i=0 ;i<n ;i++)
// {
// r=i;
// for (j=i+1 ;j<n ;j++)
// if (fabs(A[j][i])>fabs(A[r][i])) r=j;
// if (r!=i) for (j=0 ;j<=n ;j++) swap(A[r][j],A[i][j]);
// for (k=i+1 ;k<n ;k++)
// {
// double f=A[k][i]/A[i][i];
// for (j=i ;j<=n ;j++) A[k][j] -= f*A[i][j];
// }
// }
// for (i=n-1 ;i>=0 ;i--)
// {
// for (j=i+1 ;j<n ;j++)
// A[i][n] -= A[j][n]*A[i][j];
// A[i][n] /= A[i][i];
// }
//}
int main()
{
while (cin>>n,n)
{
int a;
char c;
getchar();
char str[];
for (int i= ;i<n ;i++)
{
int sum=;
int cnt=;
memset(str,,sizeof(str));
gets(str);
int len=strlen(str);
for (int j= ;j<len ;j++)
{
if (str[j]==' ')
{
an[i][cnt++]=sum;
sum=;
}
else sum=sum*+str[j]-'';
if (j==len-) an[i][cnt++]=sum;
}
an[i][cnt]=-;
}
double bn[][];
for (int i= ;i<n ;i++)
{
for (int j= ;j<n ;j++) cin>>bn[i][j];
scanf(" = %lf",&bn[i][n]);
}
// for (int i=0 ;i<n ;i++)
// {
// for (int j=0 ;j<=n ;j++) cout<<bn[i][j]<<" ";
// cout<<endl;
// }
int h=Gauss(bn);
//gauss_elimination(bn,n);
// for (int i=0 ;i<n ;i++)
// {
// for (int j=0 ;j<=n ;j++) cout<<bn[i][j]<<" ";
// cout<<endl;
// }
if (h)
{
for (int i= ;i<h ;i++) cout<<x[i]<<" ";
for (int i=h ;i<n ;i++) cout<<an[i][]<<" ";
cout<<endl;
}
else
{
for (int i= ;i<n ;i++) cout<<x[i]<<" ";
cout<<endl;
}
}
return ;
}
题意：学校有幼儿园和小学一到六个年级，一个班对应一个老师，现在每个年级有一批学生，幼儿园到二年级每个班最多容纳20个人，三到四年级每个班最多容纳25个人，五到六年级一个班最多30人，每个年级的同学如果人数没有达到上限，可以从相邻的年级凑人数，比如三年级的人数不够的话，只能从二年级和四年级中找同学来凑。现在问最少需要多少个老师。
解法：贪心。我们先从幼儿园开始，幼儿园组成几个班后，如果人数不够的话，就从一年级学生中找来；接着处理一年级的人数，如果有空缺，就从三年级中找同学来；按此方法接着四年级、五年级。最后处理六年级，如果六年级人数不够的话，就不用填补了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define inf 0x7fffffff
using namespace std;
//20 20 20 25 25 30 30
int main()
{
int an[];
while (cin>>an[]>>an[]>>an[]>>an[]>>an[]>>an[]>>an[])
{
if (!an[] && !an[] && !an[] && !an[] && !an[] && !an[] && !an[]) break;
int count=;
if (an[]%)
{
count += an[]/+;
an[] -= (-(an[]%));
}
else count += an[]/;
if (an[]<=) {}
else if (an[]%)
{
count += an[]/+;
an[] -= (-(an[]%));
}
else count += an[]/;
if (an[]<=) {}
else if (an[]%)
{
count += an[]/+;
an[] -= (-(an[]%));
}
else count += an[]/;
if (an[]<=) {}
else if (an[]%)
{
count += an[]/+;
an[] -= (-(an[]%));
}
else count += an[]/;
if (an[]<=) {}
else if (an[]%)
{
count += an[]/+;
an[] -= (-(an[]%));
}
else count += an[]/;
if (an[]<=) {}
else if (an[]%)
{
count += an[]/+;
an[] -= (-(an[]%));
}
else count += an[]/;
if (an[]<=) {}
else if (an[]%) count += an[]/+;
else count += an[]/;
cout<<count<<endl;
}
return ;
}
题意：给出一个foom、food和twob的值，要求是否有这样一组解，满足x个foom 和 y个food 等于1个twob的值，如果有满足，输出x+y最小的一组。
解法：扩展欧几里德算法。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define inf 0x7fffffff
using namespace std;
typedef long long LL;
LL x,y,z;
LL q;
LL u,v,w;
LL gcd(LL a,LL b)
{
if (!b) return a;
return gcd(b,a%b);
}
void exgcd(LL a,LL b)
{
if (!b) {x= ;y= ;q=a; }
else
{
exgcd(b,a%b);
LL temp=x ;x=y ;y=temp-a/b*y;
}
}
int main()
{
while (cin>>u>>v>>w)
{
if (!u && !v && !w) break;
LL d=gcd(u,v);
if (w%d)
{
cout<<"Unquibable!"<<endl;
continue;
}
LL c=w/d;
//u /= d ;v /= d;
exgcd(u,v);
x=((((x%(v/d)+(v/d))%(v/d))*(c%(v/d))+(v/d))%(v/d));
y=(w-u*x)/v;
if (y<)
{
cout<<"Unquibable!"<<endl;
continue;
}
// x *= c ;y *= c;
// x=(x%v+v)%v;
// y=(y%u+u)%u;
// int flag=0;
// for (LL k=-100 ;k<100 ;k++)
// {
// LL x1=x+k*(v/d);
// LL y1=y-k*(u/d);
// if (x1>=0 && y1>=0 && x1*u<y1*v)
// {
//
// if (x1+y1<x+y)
// {
// flag=1;
// x=x1 ;y=y1 ;
// }
// }
// }
// if (!flag) {cout<<"Unquibable!"<<endl;continue;}
cout<<x<<" foom";
if (x!=) cout<<"s";
cout<<" and "<<y<<" foob";
if (y!=) cout<<"s";
cout<<" for a twob!"<<endl; }
return ;
}