第一题，开始被输出吓着了，仔细看，水题一道，dfs即可啊
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int p[25][5];
bool v[25];
int m,a,num;
int f[25];
void go(int x,int n)
{
v[x]=1;
f[n]=x;
if(n==20&&(p[x][1]==m||p[x][2]==m||p[x][3]==m))
{
cout<<num++<<": ";
for(int i=1;i<=20;i++)cout<<" "<<f[i];
cout<<" "<<m<<endl;
}
else
{
for(int i=1;i<=3;i++)
{
if(v[p[x][i]]==0)go(p[x][i],n+1);
}
}
v[x]=0;
}
int main()
{
for(int i=1;i<=20;i++)
{
for(int j=1;j<=3;j++)
{
scanf("%d",&a);
p[i][j]=a;
}
}
while(scanf("%d",&m)&&m)
{
num=1;
memset(v,0,sizeof(v));
go(m,1);
}
return 0;
}
第二和第三题，都是dfs的基础题，没什么可讲的。
第四题，函数本身是单调递增的，先确定无解的情况，有解的话再找解。我是先确定大概整数范围，再小范围的找解，这题在精度上吃亏了。。。。。wa了好久
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
double y;
double s(double x)
{
return 8.0*pow(x,4)+7.0*pow(x,3)+2.0*pow(x,2)+3.0*x+6.0;
}
double find()
{
for(double i=0;i<=100;i++)
{
if(s(i)>=y)return (i-1.0);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%lf",&y);
if(y<6||s(100.0)<y)
{
cout<<"No solution!"<<endl;
continue;
}
if(y==6)
{
cout<<"0.0000"<<endl;
continue;
}
double l=find();
while(l<=100)
{
if(s(l)>=y)
{
printf("%.4f\n",l);
break;
}
l+=0.000001;
}
}
return 0;
}
第五题，嗯，有点难度啊，向朱老板请教才得以ac。基本思路就是二进制枚举+位运算。这里先要做一个预处理，我设了个p[][]数组，将num题的所有情况存在p[num]中，然后二分题数，在p中找到符合的情况。
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1<<15
using namespace std;
int n,m,k,f[1005],num,ti,ans;
int p[17][33000],c[16];
char name[50];
int er(int i)
{
int nnn=0;
int j = i;
while(j>0)
{
nnn+=j%2;
j=j/2;
}
return nnn;
}
int main()
{
memset(c,0,sizeof(c));
for(int i=0;i<=32768;i++)
{
int a=er(i);
p[a][c[a]]=i;
c[a]++;
}
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
memset(f,0,4*(n+1));
for(int i=0;i<n;i++)
{
scanf("%s%d",&name,&num);
for(int j=0;j<num;j++)
{
scanf("%d",&ti);
f[i]+=1<<(ti-1);
}
}
ans=0;
int high=m,low=0,mid,count;
while(low<=high)
{
mid=(low+high)/2;
for(int i=0;i<c[mid];i++)
{
count=0;
for(int j=0;j<n;j++)
{
if((f[j]&p[mid][i])==p[mid][i])count++;
}
if(count>=k)
{
if(er(p[mid][i])>ans)ans=er(p[mid][i]);
ans=mid;
low=mid+1;
break;
}
}
if(low<=mid)high=mid-1;
}
cout<<ans<<endl;
}
return 0;
}
第六题，二分时间，子弹反正都是让它最远距离，看mid时间内能否结束狩猎。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
double x,y,x2,y2,lx,ly,vd,vb,l;
int main()
{
while(scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf",&x,&y,&x2,&y2,&lx,&ly,&vd,&vb,&l)&&(x||y||x2||y2||lx||ly||vd||vb||l))
{
double high=1e+9,low=0,mid,len,t=l/vb,ans=1e+9;
while(high-low>0.00000001)
{
mid=(low+high)/2;
len=sqrt((x2-x-lx*mid)*(x2-x-lx*mid)+(y2-y-ly*mid)*(y2-y-ly*mid));
if((mid-t)*vd>=fabs(len - l))
{
high=mid;
if(mid<ans)ans=mid;
}
else low=mid;
}
printf("%.3f %.3f\n",l,ans);
}
return 0;
}
第七题，三分题，先确定体积表达式，再三分高度，得到最小体积时的半径和高。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int t,n;
double x[10005],y[10005],r,l,mid,mmid,ra,rra,a,b;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
l=0;
for(int i=0;i<n;i++)
{
scanf("%lf%lf%lf",&a,&b,&y[i]);
if(y[i]>l)l=y[i];
x[i]=sqrt(a*a+b*b);
}
r=30000;
while(r-l>0.0000000001)
{
mid=(l+r)/2;
mmid=(mid+r)/2;
ra=0;
rra=0;
for(int i=0;i<n;i++)
{
if(x[i]*mid/(mid-y[i])>ra)ra=x[i]*mid/(mid-y[i]);
if(x[i]*mmid/(mmid-y[i])>rra)rra=x[i]*mmid/(mmid-y[i]);
}
if(ra*ra*mid>rra*rra*mmid)l=mid;
else r=mmid;
}
printf("%.3f %.3f\n",l,ra);
}
return 0;
}
第八题，一开始以为是数学问题，但居然也是三分。。。。这里可以三分转过的角度，然后假设车的左侧中间顶在角上，右后顶在墙上，算出凸出的长度，去最大的和y比较，从而判断能否过弯。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define pi 3.1415926535898
using namespace std;
double x,y,l,w,r,lo,mid,mmid,m,mm,ans;
int main()
{
while(scanf("%lf%lf%lf%lf",&x,&y,&l,&w)!=EOF)
{
ans=0;
r=pi/2;
lo=0;
while(r-lo>0.000000001)
{
mid=(lo+r)/2;
mmid=(mid+lo)/2;
m=cos(mid)*(l-(x-w*cos(mid))/sin(mid))+w*sin(mid);
mm=cos(mmid)*(l-(x-w*cos(mmid))/sin(mmid))+w*sin(mmid);
ans=max(ans,max(m,mm));
if(m<mm)r=mid;
else lo=mmid;
}
if(ans>y)printf("no\n");
else printf("yes\n");
}
return 0;
}
第九题，也是三分，三分x，找出各函数的y值取最大的那个，然后找到所以x的时候这些最大值中最小的那个。
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1<<29
using namespace std;
double a[10005],b[10005],c[10005];
int n,t;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%lf%lf%lf",&a[i],&b[i],&c[i]);
double r=1000,l=0,mid,mmid,m,ma,mm,mma;
double ans = maxn;
while(r-l>0.000000001)
{
mid=(r+l)/2;
mmid=(r+mid)/2;
m=-maxn;
mm=-maxn;
for(int i=0;i<n;i++)
{
ma=a[i]*mid*mid+b[i]*mid+c[i];
mma=a[i]*mmid*mmid+b[i]*mmid+c[i];
if(ma>m)m=ma;
if(mma>mm)mm=mma;
}
ans = min(m,mm);
if(m>mm)l=mid;
else r=mmid;
}
printf("%.4f\n",ans);
}
return 0;
}
第十题，=。=！！！！再说吧，有难度啊。。。