最后一波期末考马上就要来临，这个半周主要补了一下题目。整理几道印象深刻的题目吧。
Hello 2018 C. Party Lemonade
题意：给出n，L。下面c1,c2,,,cn。表示1升花费c1，2升花费c2，4升花费c3，2^(n-1)升花费cn，求买L升最少花费多少。我看许多题解都是用一种位运算处理的，我没怎么看懂，最后是听一位大佬的做法补的题。
其实就是用贪心的方法，因为是最小花费，所以还是先求出所有方案的性价比，按照性价比从大到小排序，然后深搜依次判断，取出性价比最高的方案，比较用此方案买>=L升，和买剩余L/(2^(n-1))升，余数部分用其余方案处理。深搜最后得到最小花费。 还是看代码解释吧。
ll n,L;
struct node
{
ll a;//价格
ll b;//2^(n-1)升
double c;//性价比
}q[35];
bool cmp(node x,node y)
{
return x.c<y.c;
}
ll ans;
ll dfs(int i,ll val)
{
if(i>n||val<=0) return 999999;
ll k=val/q[i].b;
ll h=k*q[i].b;
if(h==val)//恰好用最高性价比买够
{
ll e;
e=q[i].a*k;
return e;
}
else
{
ll e;
e=(k+1)*q[i].a;//用此方案买完
ll p=dfs(i+1,val-k*q[i].b);//余下来的用后面的方案处理掉
e=min(e,p+k*q[i].a);//比较下那种花费小
return e;
}
}
int main()
{
ll s=1;
cin>>n>>L;
for(int i=1;i<=n;i++)
{
cin>>q[i].a;
q[i].c=1.0*q[i].a/s;
q[i].b=s;
s=s*2;
}
sort(q+1,q+1+n,cmp);//性价比高的排前面
s=dfs(1,L);//从第一个开始取
cout<<s<<endl;
}
Hello 2018 D. Too Easy Problems
你要从n个题目中选出一些题目来，使得你得分最多，且耗时不能超过T得分规则：如果你选了k道题，那么其中 分数>=k的那部分题目每个得1分。最后输出得分，和选中的题目。
其实这道题就是二分处理。。。
#define N 220000
using namespace std;
int n,T,a[N],t[N],q[N];
struct node
{
int id,t;
}s[N];
bool cmp(node a,node b)
{
return a.t<b.t;
}
bool check(int mid)
{
int num=0;
int cnt=0;
for (int i=1;i<=n;i++)
{
if(a[i]>=mid)
q[++num]=t[i];
}
sort(q+1,q+num+1);
if(num<mid) return 0;
int time=0;
for (int i=1;i<=num;i++)
{
if(time+q[i]>T) break;
++cnt;
time+=q[i];
if (cnt>=mid) return 1;
}
return cnt>=mid;
}
int main()
{
scanf("%d%d",&n,&T);
for (int i=1;i<=n;i++) cin>>a[i]>>t[i];
int l=0,r=n;
while(l<=r)
{
int mid=(l+r)/2;
if (check(mid)) l=mid+1;//找出合适的时间
else r=mid-1;
}
cout<<r<<endl;
cout<<r<<endl;
int num=0;
for (int i=1;i<=n;i++)
{
if (a[i]>=r)
{
s[++num].t=t[i];
s[num].id=i;
}
}
sort(s+1,s+num+1,cmp);
for (int i=1;i<=r;i++)
cout<<s[i].id<<" ";
return 0;
}
Good Bye 2017 C. New Year and Curling
题意：给出n，r。就是下面给出n个数x[i]，代表依次按照在x[i]上扔下去半径为r的圆，只要碰到其他圆或y=0的边就停止。输出最后这几个圆的坐标。
这其实就是一道计算几何的水题，(2r)^2-(x1-x2)*(x1-x2)=y^2。依次对比找两圆的关系，求得最大的y值保存。
double a[1100],x[1100],y[1100];
int main()
{
int n,r;
cin>>n>>r;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
x[0]=0;
y[0]=0;
for(int i=1;i<=n;i++)
{
double maxn=0;
for(int j=1;j<i;j++)//依次和前面圆做比较，确定位置，找最大y值
{
double ret=r*r*4;
ret-=(a[i]-x[j])*(a[i]-x[j]);
ret=sqrt(ret);
ret+=y[j];
maxn=max(maxn,ret);
}
if(maxn==0)
{
x[i]=a[i];
y[i]=r;
}
else
{
y[i]=maxn;
x[i]=a[i];
}
}
for(int i=1;i<=n;i++)
{
printf("%.12lf ",y[i]);
}
}
LightOJ 1265 Island of Survival
题目大意：孤岛上有t只老虎,d只鹿,1个人(你)。每天会有两种动物相遇。那么
1.老虎和人相遇,人必败;
2.老虎和鹿相遇,鹿必败;
3.老虎和老虎相遇,双方都得死;
4.鹿和鹿相遇,什么也不发生;
5.人和鹿相遇,人必定不败,鹿未必;
求人（你）活下来的概率，冷静分析就可以知道，鹿对结果没有任何影响，鹿不管怎样都得死光。那么想要生存下来最后肯定老虎要全死，如果老虎是奇数，那么人必死，只有虎是偶数是有可能生还，也就是计算t只老虎依次全部两两相遇的概率。这样就不难了。
int main()
{
int t,d,Case=0;
int T;
cin>>T;
while(T--)
{
scanf("%d%d",&t,&d);//鹿没影响
cout<<"Case "<<++Case<<": ";
if(t&1)//虎奇数，人必死
{
cout<<"0"<<endl;
}
else
{
if(t==0)
{
cout<<"1"<<endl;
}
else
{
double ans=1;
while(t!=0)//依次求出选出两虎的概率相乘
{
ans=ans*(t-1)*1.0/(t+1)*1.0;
t-=2;
}
cout<<ans<<endl;
}
}
}
return 0;
}