转载

[BZOJ1911][BZOJ1912][BZOJ1913]APIO2010解题报告

 1 /**************************************************************  2     Problem: 1911  3     User: mjy0724  4     Language: C++  5     Result: Accepted  6     Time:1688 ms  7     Memory:24248 kb  8 ****************************************************************/  9   10 #include<cstdio> 11 #include<cstdlib> 12 #include<cstring> 13 const int maxn=1000010;long long INF=10000000000000007; 14 long long n,a,b,c,sum[maxn],opt[maxn],f[maxn]; 15 long long g(int j,int k){ 16     if (2*a*(sum[j]-sum[k])==0) 17     { 18         if (f[j]+a*sum[j]*sum[j]-b*sum[j]-(f[k]+a*sum[k]*sum[k]-b*sum[k])>0) return INF; 19         else return -INF; 20     } 21     return (f[j]+a*sum[j]*sum[j]-b*sum[j]-(f[k]+a*sum[k]*sum[k]-b*sum[k]))/(2*a*(sum[j]-sum[k])); 22 } 23   24 int main(){  25     scanf("%lld",&n); 26     scanf("%lld%lld%lld",&a,&b,&c); 27     for (int i=2;i<=n+1;i++) scanf("%lld",∑[i]),sum[i]+=sum[i-1]; 28     int head=1,tail=1;opt[1]=1;f[1]=0; 29     for (int i=2;i<=n+1;i++){ 30         if (a>=0) while (head<tail&&g(opt[head],opt[head+1])>sum[i]) head++;        31         else while (head<tail&&g(opt[head],opt[head+1])<sum[i]) head++;    32         int j=opt[head]; 33         f[i]=f[j]+a*(sum[i]-sum[j])*(sum[i]-sum[j])+b*(sum[i]-sum[j])+c;     34         if (a>=0) while (head<tail&&g(opt[tail-1],opt[tail])<g(opt[tail],i)) tail--; 35         else while (head<tail&&g(opt[tail-1],opt[tail])>g(opt[tail],i)) tail--; 36         opt[++tail]=i; 37     } 38     printf("%lld/n",f[n+1]); 39     return 0; 40 }

patrol 巡逻

Description

首先对于k=1的情况，稍微观察就可以看出来，假设连上这条边之后原图形成了一个由n个点组成的环

原先经过这些点的边数为2（n-1）,如今为n，所以减少的路径为（n-2）

如果是再连一条边的话，如果不与第一条形成的环相交（指有边重合），那么显然规律不变

如果有边重叠了，设重叠的边数为x，那么原先经过这些点的边数为2（n--1-x），如今为n，所以减少的路径为n-2-2x

也就是相对于第一种规律，每重叠一条边，减少的路径数-2

那么我们不妨令每条边初始边权为1，第一问可以通过求树的直径得到

对于第一问经过的路径，边权改为-1，也就实现了每重叠一条边，减少的路径数-2的效果

 1 /**************************************************************  2     Problem: 1912  3     User: mjy0724  4     Language: C++  5     Result: Accepted  6     Time:708 ms  7     Memory:5288 kb  8 ****************************************************************/  9   10 #include<cstdio> 11 #include<cstdlib> 12 #include<cstring> 13 const int maxn=100010,maxm=200010; 14 int n,k,e,link[maxn],next[maxm],fa[maxm],pos1[maxn],pos2[maxn],w[maxm],ans,sum,s; 15 void add(int x,int y){ 16     fa[++e]=y;next[e]=link[x];link[x]=e;w[e]=1; 17     fa[++e]=x;next[e]=link[y];link[y]=e;w[e]=1; 18 } 19   20 int dfs(int p,int fat){ 21     int max1=0,max2=0; 22     for (int i=link[p];i;i=next[i]) if (fa[i]!=fat){ 23         int tmp=dfs(fa[i],p)+w[i]; 24         if (tmp>max1){ 25             max2=max1;max1=tmp;pos2[p]=pos1[p];pos1[p]=i; 26         }else if (tmp>max2) max2=tmp,pos2[p]=i; 27     } 28     if (max1+max2>ans) { 29         ans=max1+max2;s=p; 30     } 31     return max1; 32 } 33   34 int main(){ 35     scanf("%d%d",&n,&k); 36     int e=0,x,y; 37     for (int i=1;i<n;i++) scanf("%d%d",&x,&y),add(x,y); 38     dfs(1,0);sum=ans; 39     if (k==1){printf("%d/n",2*(n-1)-(ans-1));return 0;} 40     for (int i=pos1[s];i;i=pos1[fa[i]]) w[i]=-1; 41     for (int i=pos2[s];i;i=pos1[fa[i]]) w[i]=-1; 42     ans=0;dfs(1,0); 43     printf("%d/n",2*(n-1)-(ans-1)-(sum-1)); 44     return 0; 45 }

signaling 信号覆盖

Description

[BZOJ1911][BZOJ1912][BZOJ1913]APIO2010解题报告

我们考虑四边形

[BZOJ1911][BZOJ1912][BZOJ1913]APIO2010解题报告

如果是凸的四边形，当对角和>180度的时候能够信号覆盖4个，也就是一个凸四边形能带来2种答案为4的取法

凹多边形只要取外面的3个点可以带来1种答案为4的取法剩下的情况答案都为3

凹多边形的取法与凸多边形的取法是已知一个可以计算出另一个的

于是我们可以先考虑计算凹多边形的取法

先枚举位于中间的点，容易看出，剩下三个点构成的三角形能够包含中间点

相反的，不能包含的就是不能构成凹多边形的，于是我们可以计算这些不包含的方案数

对所有的点按照中间点进行极角排序，然后单调队列维护每个点能够到达的最远点，使得两点间的所有点的极角差都在180度之间

可以用叉积简化运算

最后注意一些乘法加法运算的细节就可以了

 1 /**************************************************************  2     Problem: 1913  3     User: mjy0724  4     Language: C++  5     Result: Accepted  6     Time:1996 ms  7     Memory:1356 kb  8 ****************************************************************/  9   10 #include<cstdio> 11 #include<cstdlib> 12 #include<cstring> 13 #include<cmath> 14 #include<algorithm> 15 #include<iostream> 16 #define ll long long 17 #define maxn 1510 18 struct point{ 19     ll x,y; 20     double angle;    21 }; 22 ll n,an,b; 23 point p[maxn],a[maxn]; 24 ll cross(point p0,point p1,point p2){ 25     return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); 26 } 27 void sortf(int l,int r){ 28     int i=l,j=r;double mid=p[(l+r) >> 1].angle; 29     do{ 30         while (i<r&&p[i].angle<mid) i++; 31         while (l<j&&p[j].angle>mid) j--; 32         if (i<=j){ 33             point tmp=p[i];p[i]=p[j];p[j]=tmp; 34             i++;j--; 35         } 36     }while (i<=j); 37     if (i<r) sortf(i,r); 38     if (l<j) sortf(l,j); 39 } 40 ll calc(int x){ 41     int tot=0; 42     for (int i=1;i<=n;i++) {if (i!=x) p[++tot]=a[i];else p[0]=a[i];} 43     for (int i=1;i<=tot;i++) p[i].angle=atan2(p[i].y-p[0].y,p[i].x-p[0].x); 44     sortf(1,tot); 45     ll ans=(n-1)*(n-2)*(n-3)/6;  46     ll tail=2,t=0; 47     for (int i=1;i<=tot;i++){     48         while (cross(p[0],p[i],p[tail])>=0) {tail=tail%tot+1;t++;if (tail==i) break;}         49         ans-=t*(t-1)/2;t--;  50     }    51     return ans; 52 } 53   54 int main(){ 55     scanf("%lld",&n);    56     for (int i=1;i<=n;i++) scanf("%lld%lld",&a[i].x,&a[i].y);     57     ll an=0;for (int i=1;i<=n;i++) an+=calc(i);   58     ll b=n*(n-3)*(n-2)*(n-1)/24-an,c=2*b+an,d=(n-2)*n*(n-1)/6; 59     printf("%lf",(double)(c*4+(d-c)*3)/d); 60     return 0; 61 }