A.特別行動隊

n<=1000000

看了數據范圍和題目感覺就像是斜率優化，然后瞎推了一波式子，沒想到A了。

sij表示i+1到j的權值和。

j比k優秀? $$fj+a*sij^{2}+b*sij+c>fk+a*sik^{2}+b*sik+c$$

然后亂整理$$2*a*si<\frac{fj-fk}{sj-sk}+a*(sj+sk)-b$$

si遞增，維護上凸。

#include<iostream> #include<cstdio> #define ll long long #define ld long double #define MN 1000000 using namespace std; inline int read() {int x = 0 , f = 1; char ch = getchar();while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f; }ll f[MN+5],s[MN+5],a,b,c; int top=0,tail=0,q[MN+5]; int n;ll calc(ll x){return a*x*x+b*x+c;}ld solve(int x,int y) {return (ld)(f[x]-f[y])/(s[x]-s[y])+(ld)a*(s[x]+s[y])-(ld)b; }void ins(int x) {while(top>tail&&solve(x,q[top])>solve(q[top],q[top-1])) top--;q[++top]=x; }int get(ll x) {while(top>tail&&solve(q[tail+1],q[tail])>x) tail++;return q[tail]; }int main() {n=read();a=read();b=read();c=read();for(int i=1;i<=n;i++) s[i]=s[i-1]+read();for(int i=1;i<=n;i++){int from=get(1LL*2*a*s[i]);f[i]=f[from]+calc(s[i]-s[from]);ins(i);}cout<<f[n]; return 0; }

?B.巡邏

n<=100000

題解：yy一下可以發現，k=1找的是最長鏈，答案是(n-1)*2+1-長度

k=2的時候，我們把最長鏈上的邊改成-1，然后再跑最長鏈就行啦。答案是(n-1)*2+2-長度之和。

我一開始yy了很牛逼的樹形dp，然后寫了半天還是有一個點過不了。。。百度一下題解，真的妙

#include<iostream> #include<cstdio> #define MN 100000 using namespace std; inline int read() {int x = 0 , f = 1; char ch = getchar();while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f; }struct edge{int to,next,w;}e[MN*2+5]; int head[MN+5],cnt=0,n; int f[MN+5],w1[MN+5],f1[MN+5],mx[MN+5],mx2[MN+5],ans=0,K,from; void solve(int x,int fa) {int from1=0,from2=0;mx[x]=mx2[x]=f[x]=0;for(int i=head[x];i;i=e[i].next)if(e[i].to!=fa){solve(e[i].to,x);if(f[e[i].to]+e[i].w>mx[x]) mx2[x]=mx[x],mx[x]=f[e[i].to]+e[i].w,from2=from1,from1=e[i].to;else if(f[e[i].to]+e[i].w>mx2[x]) mx2[x]=f[e[i].to]+e[i].w,from2=e[i].to;}if(mx[x]+mx2[x]>ans) ans=mx[x]+mx2[x],from=x;f[x]=mx[x];mx[x]=from1;mx2[x]=from2; }void relabel(int x) {for(int i=head[x];i;i=e[i].next)if(e[i].to==mx[x])e[i].w=-1,relabel(e[i].to); }void ins(int f,int t) {e[++cnt]=(edge){t,head[f],1};head[f]=cnt;e[++cnt]=(edge){f,head[t],1};head[t]=cnt; }int main() {n=read();K=read();for(int i=1;i<n;i++) ins(read(),read());solve(1,0);if(K==1)return 0*printf("%d",2*n-1-ans);n=n*2-ans;ans=0;for(int i=head[from];i;i=e[i].next)if(e[i].to==mx[from]||e[i].to==mx2[from])e[i].w=-1,relabel(e[i].to);solve(1,0);printf("%d\n",n-ans);return 0; }

?3.signaling? 信號覆蓋

?

題意：給定平面上n個點，滿足沒有三個點共線，沒有四個點共圓。你現在隨意選出三個點，求這三個點的外接圓內包含的點的期望個數。? $n\leqslant 1500$

題解：對于每一個三個點包含一個點的情況，我們都能抽象成一個四邊形。我們發現凸四邊形有兩種方法蓋住四個點，而凹多邊形只有一種方法，所以凸多邊形的貢獻是2，凹的是1，他們的個數相加是C(n,4),所以我們只要計算凸多邊形或者凹多邊形的個數就行了。我們枚舉凹多邊形的凹點，然后按照極角排序，然后枚舉一個點，找出最遠的點使得他們之間的夾角不超過平角，通過組合算出個數，最后除以總的方案數C(n,3)?。

復雜度$n^{2}logn$

#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #define MN 1500 #define ll long long using namespace std; inline int read() {int x = 0 , f = 1; char ch = getchar();while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f; }struct P {double x,y,alpha;void getAlpha(double xx,double yy){alpha=atan2(x-xx,y-yy);}friend double cross(P a,P b){return a.x*b.y-a.y*b.x;}bool operator == (P b){return x==b.x&&y==b.y;}bool operator < (const P &b) const {return alpha<b.alpha;}P operator - (P b){return (P){x-b.x,y-b.y};}void print(){cout<<x<<" "<<y<<" "<<alpha<<endl;} }p[MN+5],pt[MN+5];int n,top; double ans=0;ll work(P th) {ll sum=1LL*(n-3)*(n-1)*(n-2)/6;int num=0;top=2;for(int i=1;i<n;i++,--num){while(cross(p[i]-th,p[top]-th) <= 0){top=top%(n-1)+1,num++;if(top==i) break;}sum-=1LL*(num)*(num-1)/2; }return sum; }int main() {n=read();if(n==3) return 0*puts("3");for(int i=1;i<=n;i++) pt[i].x=p[i].x=read(),pt[i].y=p[i].y=read();for(int i=1;i<=n;i++){for(int j=1;j<n;j++){if(pt[i]==p[j]) swap(p[j],p[n]);p[j].getAlpha(pt[i].x,pt[i].y); }sort(p+1,p+n);ans+=work(pt[i]);}double A=1LL*n*(n-1)*(n-2)/6,B=1LL*n*(n-1)*(n-2)*(n-3)/24;printf("%.6lf\n",(ans+2*(B-ans))/A+3);return 0; }

?

轉載于:https://www.cnblogs.com/FallDream/p/apio2010.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的[APIO2010]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。