【幾何/分治】【最短路】【數學期望】Day 10.24

1、斜率

可以證明如果兩點之間還有一點的話那么原來的兩個點連線一定不會是最大斜率

然后我就寫了個沙茶分治…………

其實根據上面的推論只用枚舉相鄰的兩個點，掃一遍就可以了

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
typedef pair<int,int> P;
int n,a,b;
P p[500001];
double ans;
void solve(int l,int r)
{
    if (l>=r) return;
    int mid=(l+r)/2;
    for (int i=l;i<=r;i++) if (i!=mid)
    {
        ans=max(ans,double(p[mid].second-p[i].second)/(p[mid].first-p[i].first));
    }
    solve(l,mid-1);solve(mid+1,r);
}
int main()
{
    freopen("slope.in","r",stdin);
    freopen("slope.out","w",stdout); 
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d",&a,&b);
        p[i]=P(a,b);
    }
    sort(p+1,p+n+1);
    ans=double(p[2].second-p[1].second)/(p[2].first-p[1].first); 
    solve(1,n);
    printf("%.3f",ans);
} 

?

2、最優路徑

這不就是原來做的過路費嗎……

#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
#define ll long long
using namespace std;
typedef pair<int,int> P;
struct E{
    int next,to,w;
}e[250001];
priority_queue<P,vector<P>,greater<P> > que;
int n,m,a,b,c,sz=0,head[501],v[501],reg[501],f[501];
ll w[501][501];
void insert(int a,int b,int w)
{
    sz++;
    e[sz].next=head[a];
    head[a]=sz;
    e[sz].to=b;
    e[sz].w=w;
}
void dijkstra(int s)
{
    memset(reg,0,sizeof(reg));
    memset(f,0x7f,sizeof(f));
    f[s]=1;
    que.push(P(0,s));
    while(!que.empty())
    {
        int x=que.top().second;que.pop();
        if (reg[x]) continue;
        reg[x]=1;
        for (int i=head[x];i;i=e[i].next)
        {
            if (v[e[i].to]<=v[s]&&f[e[i].to]>max(f[x],e[i].w))
            {
                f[e[i].to]=max(f[x],e[i].w);
                que.push(P(f[e[i].to],e[i].to));
            }
        }
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (reg[i]&&reg[j]) w[i][j]=min(w[i][j],(ll)max(f[i],f[j])*v[s]);
}
int main()
{
    freopen("path.in","r",stdin);
    freopen("path.out","w",stdout);
    ios::sync_with_stdio(false); 
    memset(w,0x7f,sizeof(w));
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>v[i];
    for (int i=1;i<=m;i++)
    {
        cin>>a>>b>>c; 
        insert(a,b,c);insert(b,a,c);
    }
    for (int i=1;i<=n;i++) dijkstra(i);
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            if (i==j){
                cout<<0<<" ";
            }else{
                if (w[i][j]==w[0][0])
                    cout<<-1<<" ";
                else
                    cout<<w[i][j]<<" ";
            }
        }
        cout<<endl;
    }
} 

3、小G的線段樹

如果一個點上存在賦值語句，只有最后一個賦值語句會起作用，所以所有賦值語句的期望就是操作數的平均數

k個賦值操作把序列分割成了k+1個空位，注意到所有加法操作的位置都是等效的，由于加法操作只會在最后一個空位起作用，所以所有加法語句的期望就是操作數的總和乘上起作用的概率1/(k+1)

賦值語句的期望加上加法語句的期望就是所求的答案，然后在整個序列上差分即可

因為空間開成100001，當n=100000時右邊界差分會訪問越界，所以我決定以后都用const int N=所需空間+10的方式開空間

#include <cstdio>
typedef double db;
typedef long long ll;
using namespace std;
const int N=100010;
int n,m,q,c,l,r,x,a[N];
ll s1[N],s2[N],z2[N],w1=0,w2=0,w3=0;
db ans[N];
int main()
{
    freopen("segment.in","r",stdin);
    freopen("segment.out","w",stdout);
    scanf("%d%d%d",&n,&m,&q);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&c,&l,&r,&x);
        if (c==1)
            s1[l]+=x,s1[r+1]-=x;
        else
            s2[l]+=x,s2[r+1]-=x,z2[l]++,z2[r+1]--;
    }
    for (int i=1;i<=n;i++)
    {
        w1+=s1[i],w2+=s2[i],w3+=z2[i];
        if (w3==0)
            ans[i]=ans[i-1]+a[i]+w1;
        else
            ans[i]=ans[i-1]+1.0*w2/w3+1.0*w1/(w3+1);
    }
    for (int i=1;i<=q;i++)
    {
        scanf("%d%d",&l,&r);
        printf("%.3lf\n",ans[r]-ans[l-1]);
    }
}

?