涼心的比賽(一)補題

目錄

• • D*Well played!
  • G*法法非法是朋友

題目連結

D*Well played!

題意：有n個物品，能進行a次操作一和b次操作二，每個物品有一個hp和damage，操作一為把某個物品的hp變為原來的兩倍，操作二為把某個物品的hp指派給它的damage，問這n個物品的damage的總和最大是多少。

思路：證明出來a操作應該都使用給同一個物品最優，然後按b操作的最優方案排序，枚舉使用a操作

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<map>
#include<algorithm>
#include<queue>
#include<math.h>
#include<vector>
using namespace std;
#define Inf 0x7fffffff
typedef long long ll;
const int N=220000;
int n,a,b;
struct node{
	ll hp,dmg,x;
}f[N];
ll ans,s;
int cmp(node x,node y){return x.x>y.x;}
	
int main(){
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&f[i].hp,&f[i].dmg);
		f[i].x=f[i].hp-f[i].dmg;
	}
	sort(f+1,f+1+n,cmp);
	ll sum=0;
	for(int i=1;i<=b;i++)sum+=max(f[i].hp,f[i].dmg);
	for(int i=b+1;i<=n;i++)sum+=f[i].dmg;
	ans=sum;
	for(int i=1;i<=b;i++)ans=max(ans,sum-max(f[i].hp,f[i].dmg)+(f[i].hp<<a)); 
	sum=sum-max(f[b].hp,f[b].dmg)+f[b].dmg;
	for(int i=b+1;i<=n&&b;i++)ans=max(ans,sum-f[i].dmg+(f[i].hp<<a));
	cout<<ans;
}
           

G*法法非法是朋友

題意：通過圓心坐标(x1,y1)和半徑R給定一個大的圓形範圍和一個點(x2,y2),找一個圓形範圍使其不包含點(x2,y2)和大圓外任意點。

思路：找内切圓，半徑為 dis[(x1,y1),(x2,y2)]+R

注意：若(x1,y1)和(x2,y2)重合，不包含點(x2,y2)的最大内切圓的半徑隻能為R/2

#include<bits/stdc++.h>
using namespace std;
#define Inf 0x7fffffff
typedef long long ll;
double x1,x2,y1_,y2_,R,r,x,y;
double dis(double x1,double y1_,double x2,double y2_){
	return sqrt((x1-x2)*(x1-x2)+(y1_-y2_)*(y1_-y2_));
}
int main(){
	cin>>R>>x1>>y1_>>x2>>y2_;
	double d=dis(x1,y1_,x2,y2_);
	if(d>=R){
		//cout<<x1<<" "<<y1_<<" "<<R;
		printf("%.1lf %.1lf %.1lf",x1,y1_,R);
		return 0;
	}
	if(d==0){
		printf("%.16lf %.16lf %.16lf",x1+R/2,y1_,R/2);
		return 0;
	}
	r=d+R;
	x=x2+(x1-x2)/d*r;
	y=y2_+(y1_-y2_)/d*r;
	x=(x+x2)/2;y=(y+y2_)/2;
	r/=2;
	printf("%.16lf %.16lf %.16lf",x,y,r);
}