SCOI2015

这周各种头疼，一直睡觉+发呆，啥子都没干。

就补一下之前的东西。

d1t1小凸玩矩阵

一开始脑子抽写了最小费用最大流，不知道自己怎么想的。

第k大最小，明显的二分，又是二分图，二分第k大值，把小于它的边权值设为1，大于它的权值设为0跑最大流即可，也可以直接用匈牙利。

//Achen

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<vector>

#include<cstdio>

#include<queue>

#include<cmath>

const int N=;

typedef long long LL;

using namespace std;

int s,t,n,m,k,a[N][N],is[N][N],vis[N],pr[N],l=1e9,r=;

template<typename T>void read(T &x)  {

    char ch=getchar(); x=; T f=;

    while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

    if(ch=='-') f=-,ch=getchar();

    for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

}

int find(int x) {

    for(int i=;i<=m;i++) if(!vis[i]&&is[x][i]) {

        vis[i]=;

        if(pr[i]==-||find(pr[i])) {

            pr[i]=x;

            return ;

        }

    }

    return ;

}

int ok(int x) {

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++) {

            if(a[i][j]>x) is[i][j]=;

            else is[i][j]=;

        }

    int rs=;

    memset(pr,-,sizeof(pr));

    for(int i=;i<=n;i++) {

        memset(vis,,sizeof(vis));

        rs+=find(i);

    }

    return rs>n-k;

}

int main() {

#ifdef DEBUG

    freopen(".in","r",stdin);

    freopen(".out","w",stdout);

#endif

    read(n); read(m); read(k);

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++) {

            read(a[i][j]);

            l=min(l,a[i][j]);

            r=max(r,a[i][j]);

        }

    int ans=r;

    while(l<=r) {

        int mid=((l+r)>>);

        if(ok(mid)) ans=mid,r=mid-;

        else l=mid+;

    }

    printf("%d\n",ans);

    return ;

}

d1t2国旗计划

传送门

先倍长破环为链。

记每个区间的nx，为左端点在这个区间左端点之后，右端点之前的，右端点最靠右的区间。那么每个区间的答案就是一直沿着nx跳直到覆盖的长度超过环长。

找nx,可以先把每个区间拆成左右端点，按pos排序，pos相同先排左端点。从左往右扫，扫到一个左端点就更新当前可以到达的右端点的最右值，扫到一个右端点就更新当前区间的答案。

扫一遍也就可以把第一个区间为起点的答案求出来了，记为k。

那么其他区间的答案肯定是k，k+1或者k-1。

把每个区间的nx设为它的父亲，建出一颗以第2*n个区间为根的树，那么每个区间的答案就是，判断它的第k个、第k-1个，第k+1个父亲到它能不能覆盖整个环长，选最近的父亲更新答案。

这个在dfs过程中把访问到的点都放进栈里就好了。

//Achen

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<vector>

#include<cstdio>

#include<queue>

#include<cmath>

const int N=1e6+;

typedef long long LL;

using namespace std;

int n,m,k=1e9+,l[N],r[N],ans[N],cnt,fa[N];

template<typename T>void read(T &x)  {

    char ch=getchar(); x=; T f=;

    while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

    if(ch=='-') f=-,ch=getchar();

    for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

}

struct node {

    int f,id;

    LL pos;

    node(){}

    node(LL pos,int f,int id):pos(pos),f(f),id(id){}

    friend bool operator <(const node &A,const node &B) {

        return A.pos<B.pos||(A.pos==B.pos&&A.f<B.f);

    }

}p[N];

int ecnt,fir[N],nxt[N],to[N];

void add(int u,int v) {

    nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v;

}

int que[N],top=;

void dfs(int x) {

    que[++top]=x;

    if(top&&top>=k-) {

        if(top>k&&r[que[top-k]]-l[x]>=m) ans[x]=min(ans[x],k+);

        if(top>k-&&r[que[top-k+]]-l[x]>=m) ans[x]=min(ans[x],k);

         if(top>k-&&r[que[top-k+]]-l[x]>=m) ans[x]=min(ans[x],k-);

    }

    for(int i=fir[x];i;i=nxt[i])

        dfs(to[i]);

    top--;

}

int main() {

#ifdef DEBUG

    freopen(".in","r",stdin);

    freopen(".out","w",stdout);

#endif

    memset(ans,,sizeof(ans));

    read(n); read(m);

    for(int i=;i<=n;i++) {

        read(l[i]); read(r[i]);

        if(r[i]<=l[i]) r[i]+=m;

        p[++cnt]=node(l[i],,i);

        p[++cnt]=node(r[i],,i);

        l[i+n]=l[i]+m; r[i+n]=r[i]+m;

        p[++cnt]=node(l[i+n],,i+n);

        p[++cnt]=node(r[i+n],,i+n);

    }

    sort(p+,p+cnt+);

    int s=-,now=,mx=,mxid,t,rt;

    for(int i=;i<=cnt;i++) {

        if(p[i].f==) {

            if(s==-) {

                s=p[i].id; now=s; t=; mxid=p[i].id;

            }

            if(r[p[i].id]>mx) mx=r[p[i].id],mxid=p[i].id;

        }

        else {

            if(p[i].id==now) { t++; now=mxid; }

            fa[p[i].id]=mxid;

        }

        if(r[now]-l[s]>=m) k=min(k,t);

    }

    for(int i=;i<=*n;i++) {

        if(fa[i]!=i) add(fa[i],i);

        else rt=i;

    }

    dfs(rt);

    for(int i=;i<=n;i++) printf("%d ",ans[i]);

    return ;

}

d1t3小凸想跑步

传送门

半平面交的模板题。

把需要的三角形面积小于其他每个三角形的式子列出来，就是一坨半平面的式子，直接半平面交求面积即可。

计算几何，模板打错最为致命。

//Achen

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<vector>

#include<cstdio>

#include<queue>

#include<cmath>

typedef long long LL;

typedef double db;

using namespace std;

const int N=3e5+;

const db eps=1e-;

int n,cnt,tot;

db ans;

template<typename T>void read(T &x)  {

    char ch=getchar(); x=; T f=;

    while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

    if(ch=='-') f=-,ch=getchar();

    for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

}

struct pt {

    db x,y;

    pt(){}

    pt(db x,db y):x(x),y(y){}

}p[N],T0,T1,T2,T3;

pt operator + (pt A,pt B) { return pt(A.x+B.x,A.y+B.y); }

pt operator - (pt A,pt B) { return pt(A.x-B.x,A.y-B.y); }

pt operator * (pt A,db p) { return pt(A.x*p,A.y*p); }

pt operator / (pt A,db p) { return pt(A.x/p,A.y/p); }

db dot(pt A,pt B) { return A.x*B.x+A.y*B.y; }

db cross(pt A,pt B) { return A.x*B.y-A.y*B.x; }

db length(pt A) { return sqrt(dot(A,A)); }

db dcmp(db x) { return (fabs(x)<eps)?:(x<?-:); }

struct Line {

    pt a,b;

    db slop;

    friend bool operator <(const Line&A,const Line&B) {

        return (A.slop<B.slop)||(A.slop==B.slop&&cross(A.b-A.a,B.b-A.a)<);

    }

}L[N],a[N];

db get_Area(int n) {

    if(n<) return ;

    db res=; p[n+]=p[];

    for(int i=;i<=n;i++) res+=cross(p[i],p[i+]);

    return fabs(res)/2.0;

}

pt inter(Line A,Line B) {

    pt rs;

    db k1=cross(B.b-A.a,A.b-A.a);

    db k2=cross(A.b-A.a,B.a-A.a);

    db t=k1/(k1+k2);

    rs.x=B.b.x+(B.a.x-B.b.x)*t;

    rs.y=B.b.y+(B.a.y-B.b.y)*t;

    return rs;

}

int ck(Line A,Line B,Line P) {

    pt t=inter(A,B);

    return cross(t-P.a,P.b-P.a)>;

}

db solve(int n) {

    sort(L+,L+n+);

    tot=;

    for(int i=;i<=n;i++)

        if(i==||L[i].slop!=L[i-].slop) a[++tot]=L[i];

    cnt=; int ql=,qr=;

    L[++qr]=a[]; L[++qr]=a[];

    for(int i=;i<=tot;i++) {

        while(qr>ql&&ck(L[qr-],L[qr],a[i])) qr--;

        while(qr>ql&&ck(L[ql+],L[ql],a[i])) ql++;

        L[++qr]=a[i];

    }

    while(qr>ql&&ck(L[qr-],L[qr],L[ql])) qr--;

    while(qr>ql&&ck(L[ql+],L[ql],L[qr])) ql++;

    L[qr+]=L[ql];

    for(int i=ql;i<=qr;i++)

        p[++cnt]=inter(L[i],L[i+]);

    return get_Area(cnt);

}

int main() {

#ifdef DEBUG

    freopen(".in","r",stdin);

    freopen(".out","w",stdout);

#endif

    read(n);

    for(int i=;i<=n;i++) {

        read(p[i].x); read(p[i].y);

    }

    p[n+]=p[]; ans=get_Area(n);

    for(int i=;i<=n;i++) {

        L[++cnt].a=p[i]; L[cnt].b=p[i+];

        L[cnt].slop=atan2(L[cnt].b.y-L[cnt].a.y,L[cnt].b.x-L[cnt].a.x);

    }

    T0=p[]; T1=p[];

    for(int i=;i<=n;i++) {

        T2=p[i]; T3=p[i+];

        db a=T0.y-T1.y-T2.y+T3.y;

        db b=T1.x-T0.x-T3.x+T2.x;

        db c=cross(T2,T3)-cross(T0,T1);

        db xx,yy;

        if(a==&&b==) continue;

        if(b==) { xx=c/a; yy=;}

        else if(a==) { xx=; yy=c/b; }

        else xx=,yy=(c-a*xx)/b;

        L[++cnt].a=pt(xx,yy);

        if(b==) { xx=c/a; yy=;}

        else if(a==) { xx=; yy=c/b; }

        else xx=,yy=(c-a*xx)/b;

        L[cnt].b=pt(xx,yy);

        if(b==) xx=xx+;

        else if(a==) yy=yy+;

        else yy=yy+; 

        pt tp=pt(xx,yy);

        if(a*xx+b*yy-c<) {

            if(cross(L[cnt].b-L[cnt].a,tp-L[cnt].a)<) swap(L[cnt].a,L[cnt].b);

        }

        else {

            if(cross(L[cnt].b-L[cnt].a,tp-L[cnt].a)>) swap(L[cnt].a,L[cnt].b);

        }

        L[cnt].slop=atan2(L[cnt].b.y-L[cnt].a.y,L[cnt].b.x-L[cnt].a.x);

    }

    ans=solve(cnt)/ans;

    printf("%.4lf\n",ans);

    return ;

}

/*

5

1 8

0 7

0 0

8 0

8 8

*/

d2t1小凸玩密室

传送门

奥妙重重的树形dp

容易想到最基础的dp,dp[i][j]表示点亮了x的整颗子树，最后一个点亮的是j的方案数。

尝试优化这个dp,对于一个有父亲的x来说，要么是先点亮它的父亲再点它，再点它兄弟，要么是先点它，再点它父亲，再点它兄弟（它兄弟先的两种情况对称）。

也就是要么它要对他父亲负责，要么它要对他父亲的另一个儿子负责。

那么对于每一个叶子节点，要么它要对它的某个祖先负责，要么它要对某个祖先的儿子负责。

g[x][i]表示点亮x后点亮x的第i个祖先需要的最小代价，f[x][i]表示点亮x后点亮x的第i个祖先的另一个儿子的最小代价。

就可以直接转移了 (b表示到父亲的边的权值)

g[x][i]=min(b[lc]*v[lc]+f[lc][0]+g[rc][i+1],b[rc]*v[rc]+f[rc][0]+g[lc][i+1]);

f[x][i]=min(b[lc]*v[lc]+f[lc][0]+f[rc][i+1],b[rc]*v[rc]+f[rc][0]+f[lc][i+1]);

然后再枚举从每个点开始点统计答案即可。

//Achen

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<vector>

#include<cstdio>

#include<queue>

#include<cmath>

#define For(i,a,b) for(int i=(a);i<=(b);i++)

#define Rep(i,a,b) for(int i=(a);i>=(b);i--)

const int N=2e5+;

typedef long long LL;

typedef double db;

using namespace std;

int n;

LL v[N],f[N][],g[N][],R[N],ans,b[N];

//f[x][i] 点亮子树x之后点了x的第i个父亲的儿子

//g[x][i] 点亮子树x之后点了x的第i个父亲

template<typename T>void read(T &x)  {

    char ch=getchar(); x=; T f=;

    while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

    if(ch=='-') f=-,ch=getchar();

    for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

}

#define lc x<<1

#define rc (x<<1|1) 

void dfs(int x) {

    R[x]=R[x/]+b[x];

    if(lc>n) {

        int fa=x/,pr=x;

        For(i,,) {

            int son=(pr&)?(fa<<):(fa<<|);

            g[x][i]=(R[x]-R[fa])*v[fa];

            f[x][i]=(R[x]-R[fa]+b[son])*v[son];

            pr=fa; fa/=;

        }

        return;

    }

    dfs(lc); dfs(rc);

    For(i,,) {

        if(rc>n) {

            g[x][i]=b[lc]*v[lc]+g[lc][i+];

            f[x][i]=b[lc]*v[lc]+f[lc][i+];

        }

        else {

            g[x][i]=min(b[lc]*v[lc]+f[lc][]+g[rc][i+],b[rc]*v[rc]+f[rc][]+g[lc][i+]);

            f[x][i]=min(b[lc]*v[lc]+f[lc][]+f[rc][i+],b[rc]*v[rc]+f[rc][]+f[lc][i+]);

        }

    }

}

void calc(int x) {

    LL tp=g[x][];

    int fa=x/,pr=x;

    for(;fa;) {

        int son=(pr&)?(fa<<):(fa<<|);

        tp+=b[son]*v[son]+g[son][];

        pr=fa; fa/=;

    }

    ans=min(ans,tp);

    if(lc>n) return;

    calc(lc); calc(rc);

}

int main() {

#ifdef DEBUG

    freopen(".in","r",stdin);

    freopen(".out","w",stdout);

#endif

    memset(g,/,sizeof(g));

    memset(f,/,sizeof(f));

    ans=g[][];

    read(n);

    For(i,,n) read(v[i]);

    For(i,,n) read(b[i]);

    dfs();

    calc();

    printf("%lld\n",ans);

    return ;

}

d2t2

传送门

没写，就口胡一下。

用一个set存每一段0的区间，每次从一个点开始先暴力修改这个点的值，修改我的set，查完后改回来。

查询的时候就看现在查的在哪个位置，可以把整段区间分成左右两半，小的一半直接找begin或者rbegin即可，大的一半lower_bound ( i+n/2 ) 用左右两个区间更新答案。

需要注意找到的区间若包涵当前查询位置更新的答案为0，还要特判最前最后区间连一起的情况。

d2t3 情报传递

传送门

第一问直接查询lca即可。

第二问，相当于给每个点赋值，询问路径上小于某个值的点的个数。

把赋值操作离线下来排序，查询也离线下来排序，树链剖分即可。

如果你闲的淡疼，也可以写个啥子主席树之类的。

巴特西

SCOI2015

最新文章

热门文章