[CLYZ2017]day10
圆圈游戏
solution
60分
记每个圆的最小的包含它的那个圆为父亲,那么图就是森林.
再用一个无穷大的圆包含它们,那么图就是一棵树.
选了父亲就不能选孩子.
\(f[i]\)表示以\(i\)为根的子树的最大价值.
\(f[i]=max(w[i],\sum{f[k]}),k\)为\(i\)的孩子.
直接枚举找父亲,\(O(n^2)\).
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 100005
using namespace std;
typedef long long ll;
struct circle{
int x,y,r,w;
}a[N],b[N];
struct graph{
int nxt,to;
}e[N];
int f[N],g[N],fa[N],n,cnt;
inline int read(){
int ret=0;char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
ret=(ret<<1)+(ret<<3)+c-'0';
c=getchar();
}
return ret;
}
inline void addedge(int x,int y){
e[++cnt]=(graph){g[x],y};g[x]=cnt;
}
inline ll sqr(int k){
return 1ll*k*k;
}
inline ll dis(int i,int j){
return sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y);
}
//j包含i
inline bool chk(int i,int j){
return a[j].r>a[i].r&&sqr(a[j].r-a[i].r)>dis(i,j);
}
inline void dfs(int u){
for(int i=g[u];i;i=e[i].nxt){
dfs(e[i].to);
f[u]+=f[e[i].to];
}
f[u]=max(f[u],a[u].w);
}
inline void Aireen(){
n=read();
for(int i=1;i<=n;++i)
a[i]=(circle){read(),read(),read(),read()};
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(chk(i,j)){
if(!fa[i]) fa[i]=j;
else if(a[j].r 100分
考虑扫描线.
将圆按圆上最左边的点排序,将圆分为上下两半弧.
在圆的最左点将圆插入,在圆的最右点将圆删去.
插入一个圆之前,先找到第一个在它上面的半弧,如果是下半弧,为它的兄弟;如果是上半弧,为它的父亲.均可知它的父亲.
用\(set\)维护,\(O(nlogn)\)
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 100005
#define eps 1e-13
using namespace std;
typedef long long ll;
struct graph{
int nxt,to;
}e[N];
int f[N],g[N],x[N],y[N],r[N],w[N],fa[N],n,m,cx,cnt;
struct circle{
int n,k;
};
inline ll sqr(int k){
return 1ll*k*k;
}
bool operator < (circle a,circle b){
double ya,yb;
ya=y[a.n]+sqrt(sqr(r[a.n])-sqr(cx-x[a.n]))*a.k;
yb=y[b.n]+sqrt(sqr(r[b.n])-sqr(cx-x[b.n]))*b.k;
if(fabs(ya-yb)>eps) return ya s;
inline int read(){
int ret=0;char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
ret=(ret<<1)+(ret<<3)+c-'0';
c=getchar();
}
return ret;
}
inline void addedge(int x,int y){
e[++cnt]=(graph){g[x],y};g[x]=cnt;
}
inline void dfs(int u){
for(int i=g[u];i;i=e[i].nxt){
dfs(e[i].to);
f[u]+=f[e[i].to];
}
f[u]=max(f[u],w[u]);
}
struct point{
int p,k,n;
}p[N<<1];
inline bool cmp(point a,point b){
if(a.p!=b.p) return a.p0) fa[p[i].n]=j.n;
else fa[p[i].n]=fa[j.n];
s.insert(tmp1);s.insert(tmp2);
}
}
for(int i=1;i<=n;++i)
addedge(fa[i],i);
dfs(0);
printf("%d\n",f[0]);
}
int main(){
freopen("circle.in","r",stdin);
freopen("circle.out","w",stdout);
Aireen();
fclose(stdin);
fclose(stdout);
return 0;
}
划分序列
solution
60分
二分答案\(ans\).
元素均为非负数
贪心判断即可.
nK不超过几千万时
\(f[i][j]\)表示前\(i\)个数分\(k\)段的最小值
\(f[i][j]=min\{f[i-1][j],0(\)若\(f[i-1][j-1]\leq{ans})\}+a_i\)
判断\(f[n][k]\)是否\(\leq{ans}\)即可.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define K2 15
#define K1 105
#define N 50005
#define M 1000000000
#define INF 1500000000
#define min(x,y) xmx){
++cnt;sum=a[i];
}
else sum+=a[i];
return cnt<=k;
}
inline bool cmp2(){
for(int i=1;i<=n;++i)
if(a[i]>0) return false;
return true;
}
inline bool chk2(int mx){
int cnt=1,sum=a[1];
for(int i=2;i<=n;++i)
if(sum+a[i]>mx){
++cnt;sum=a[i];
}
else sum+=a[i];
return cnt<=k;
}
inline bool chk3(int mx){
for(int i=1;i<=n;++i)
for(int j=0;j<=k;++j)
f1[i][j]=INF+1;
f1[1][1]=a[1];
for(int i=2;i<=n;++i){
for(int j=1;j<=k;++j){
f1[i][j]=min(f1[i][j],f1[i-1][j]+a[i]);
if(f1[i-1][j-1]<=mx) f1[i][j]=min(f1[i][j],a[i]);
}
}
return f1[n][k]<=mx;
}
inline bool chk4(int mx){
for(int i=1;i<=n;++i)
for(int j=0;j<=k;++j)
f2[i][j]=INF+1;
f2[1][1]=a[1];
for(int i=2;i<=n;++i){
for(int j=1;j<=k;++j){
f2[i][j]=min(f2[i][j],f2[i-1][j]+a[i]);
if(f2[i-1][j-1]<=mx) f2[i][j]=min(f2[i][j],a[i]);
}
}
return f2[n][k]<=mx;
}
inline void Aireen(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
if(n<=100){
l=-INF;r=INF;
while(l>1);
if(chk3(mid)) r=mid;
else l=mid+1;
}
printf("%d\n",l);
return;
}
if(k<=10){
l=-INF;r=INF;
while(l>1);
if(chk4(mid)) r=mid;
else l=mid+1;
}
printf("%d\n",l);
return;
}
if(cmp1()){
r=INF;
while(l>1);
if(chk1(mid)) r=mid;
else l=mid+1;
}
printf("%d\n",l);
return;
}
}
int main(){
freopen("divide.in","r",stdin);
freopen("divide.out","w",stdout);
Aireen();
fclose(stdin);
fclose(stdout);
return 0;
}
100分
设\(l\)为最少合法划分段数,\(r\)为最多合法划分段数.
若\(l\leq{ans}\leq{r}\),则可行.
\(f[i]\)表示前\(i\)个数最少划分段数,\(g[i]\)表示前\(i\)个数最多划分段数.
\(f[i]=min\{f[j]\}+1\;(s[i]-s[j]\leq{ans})\)
\(g[i]=max\{g[j]\}+1\;(s[i]-s[j]\leq{ans})\)
找到\(i\)能延伸到的最左端\(lef\),询问\([lef,i-1]\)的最值,树状数组维护前缀最大值即可.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define K2 15
#define K1 105
#define N 50005
#define M 1000000000
#define INF 1500000000
#define min(x,y) x>1);
if(chk(mid)) r=mid;
else l=mid+1;
}
printf("%d\n",l);
}
int main(){
freopen("divide.in","r",stdin);
freopen("divide.out","w",stdout);
Aireen();
fclose(stdin);
fclose(stdout);
return 0;
}