1.Sunscreen
传送门
#include<bits/stdc++.h>
using namespace std;
const int N=2510;
pair<int,int>a[N],b[N];
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;++i) cin>>a[i].first>>a[i].second;for(int i=1;i<=m;++i) cin>>b[i].first>>b[i].second;sort(a+1,a+1+n);sort(b+1,b+1+m);int ans=0,j=0;priority_queue<int,vector<int>, greater<int> >q;for(int i=1;i<=m;++i){while(j<=n&&a[j].first<=b[i].first) q.push(a[j].second),++j;while(!q.empty()&&b[i].second>0){int t=q.top();q.pop();if(t<b[i].first) continue;++ans,--b[i].second;}}cout<<ans;return 0;
}2.Stall Reservations
传送门
（1）按照左端点从小到大排序
（2）维护一个优先队列，存储stall的结束时间和编号号。按照结束时间升序。
（3）每一次取队首，如果结束时间小于开始时间，修改它的结束时间。否则需要新开一个。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include<bitset>
#include<list>
#include <algorithm>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pil pair<int,LL>
#define pli pair<LL,int>
#define pdd pair<db,db>
#define se second
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;i<b;++i)
#define per(i,a,b) for (register int i=a;i>b;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=1e9+7;
const int N=50010;
struct node{int id,x,y;
}p[N];
int ans[N],cnt;
bool cmp(node a,node b)
{return a.x<b.x;
}
void solve()
{int n;cin>>n;rep(i,0,n) p[i].id=i,cin>>p[i].x>>p[i].y;sort(p,p+n,cmp);priority_queue<pii,vector<pii>, greater<pii> >q;rep(i,0,n){if(q.empty()){ans[p[i].id]=++cnt;q.push({p[i].y,cnt});continue;}pii t=q.top();if(t.fi<p[i].x){ans[p[i].id]=t.se;q.pop();q.push({p[i].y,t.se});}else{ans[p[i].id]=++cnt;q.push({p[i].y,cnt});}}cout<<cnt<<endl;rep(i,0,n) cout<<ans[i]<<endl;
}
int main()
{
// #ifndef ONLINE_JUDGE
// freopen("title.in","r",stdin);
// freopen("title.out","w",stdout);
// #endif//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;//cin>>_; while(_--){solve();}return 0;
}3.Radar Installation
传送门
转化为用最少的点覆盖线段问题。
#include<bits/stdc++.h>
#define rep(i,a,b) for (register int i=a;i<b;++i)
#define per(i,a,b) for (register int i=a;i>b;--i)
#define pdd pair<db,db>
#define db double
#define pii pair<int,int>
#define se second
#define fi first
#define MEM(a,x) memset(a,x,sizeof(a))
#define endl '\n'
typedef long long LL;
using namespace std;
const int N=1010;
pdd p[N];
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n,d;while(cin>>n>>d){if(n==0&&d==0) break;db x,y;bool f=1;rep(i,0,n){cin>>x>>y;if(y>d) f=0;p[i].fi=x-sqrt((db)d*d-y*y),p[i].se=x+sqrt((db)d*d-y*y);}if(!f){cout<<-1<<endl;continue;}sort(p,p+n);db nw=-1e18;int ans=0;rep(i,0,n){if(nw<p[i].fi) ++ans,nw=p[i].se;else nw=min(nw,p[i].se);}cout<<ans<<endl;}return 0;
}4.国王的游戏
传送门1
传送门2
按照每个大臣左手右手乘积升序排列。
python版本（不用写高精）：
def cmp(x):return x[0]*x[1];
n=int(input())
nw,_=map(int,input().split(' '))
L=[]
for i in range(n):a,b=map(int,input().split(' '))L.append([a,b])
L.sort(key=cmp)
ans=0
for i in L:ans=max(ans,nw//i[1])nw*=i[0]
print(ans)c++版本：
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
static const int BASE=10;
static const int WIDTH=8;
struct node{int l,r;
}mst[N];
bool cmp(node a,node b)
{return a.l*a.r<b.l*b.r;
}
struct BigInt{vector<int>s;BigInt(long long num=0){*this=num;}BigInt operator = (long long num){s.clear();do{s.push_back(num%BASE);num/=BASE;}while(num>0);return *this;}bool operator < (const BigInt& b) const {if(s.size()!=b.s.size()) return s.size()<b.s.size();for(int i=s.size()-1;i>=0;i--){if(s[i]!=b.s[i]) return s[i]<b.s[i];}return false;
}
};
ostream& operator << (ostream &out,const BigInt& x)
{for(int i=x.s.size()-1;i>=0;i--){out<<x.s[i];}return out;
}
void mul(BigInt &a,int b)
{long long t=0;for(int i=0;i<a.s.size();i++){long long res=b*a.s[i]+t;a.s[i]=res%BASE;t=res/BASE;}while(t){a.s.push_back(t%BASE);t/=BASE;}
}
vector<int> dev(BigInt &a,int b)
{vector<int>c;long long r=0;for(int i=a.s.size()-1;i>=0;i--){r=r*10+a.s[i];c.push_back(r/b);r%=b;}reverse(c.begin(),c.end());while(c.size()>1&&c.back()==0) c.pop_back();return c;
}
int main()
{int n,a,b;cin>>n;cin>>a>>b;for(int i=0;i<n;i++) cin>>mst[i].l>>mst[i].r;sort(mst,mst+n,cmp);BigInt pro=1ll*a*mst[0].l,ans=1ll*a/mst[0].r;for(int i=1;i<n;i++){BigInt res;res.s=dev(pro,mst[i].r);if(ans<res) ans=res;mul(pro,mst[i].l);}cout<<ans;return 0;
}5.Color a Tree
传送门
y总的视频讲解，讲得超级超级清楚
1.如果一个点的父节点已经被染色了，下一步一定会选择它子节点中最大的，这两个点的先后次序就被确定了。
2.考虑三个点x,y,z。若x是y的父节点，y是权值最大的子节点，y一定是在x之后染色。现在需要确定x和z的先后顺序。
先染x：s1=x+2y+3z；先染z：s2=z+2*x+3*y。
若先选x最优，即s1-s2<0，需要满足：
推广到两个组的和并：
合并两组的时候只需要将平均值大的放在前面即可。具体做法类似于并查集，先把每个点看成是独立的一组，在考虑把子节点并向父节点，在这个过程当中计算增加的花费。最终并成一个点。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include<bitset>
#include<list>
#include <algorithm>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pil pair<int,LL>
#define pli pair<LL,int>
#define pdd pair<db,db>
#define se second
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;i<b;++i)
#define per(i,a,b) for (register int i=a;i>b;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=1e9+7;
const int N=1010;
struct node{int fa,sz,sum;db avg;
}S[N];
int n,r;
int find()
{db avg=0,res=0;rep(i,1,n+1){if(i!=r&&avg<S[i].avg){avg=S[i].avg;res=i;}}return res;
}
void solve()
{while(cin>>n>>r&&n){int ans=0;rep(i,1,n+1){int val;cin>>val;ans+=val;S[i]={0,1,val,val};}rep(i,0,n-1){int x,y;cin>>x>>y;S[y].fa=x;}rep(i,0,n-1){int p=find(),fa=S[p].fa;ans+=S[p].sum*S[fa].sz;S[p].avg=-1;rep(i,1,n+1) if(S[i].fa==p) S[i].fa=fa;S[fa].sum+=S[p].sum;S[fa].sz+=S[p].sz;S[fa].avg=(db)S[fa].sum/S[fa].sz;}cout<<ans<<endl;}
}
int main()
{#ifndef ONLINE_JUDGEfreopen("title.in","r",stdin);freopen("title.out","w",stdout);#endifios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;//cin>>_; while(_--){solve();}return 0;
}
