ZJT's Blog

大変に気分がいい~

集训队作业之AGC069-F

2017-12-11 19:122017-12-11 19:12
集训队作业AtCoder二分答案2-SAT

传送门

二分答案之后可以转成2-SAT模型,然后可以用线段树优化建模,把边数复杂度降到$O(n\log n)$。

#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
#define MAXN 1000010
using namespace std;

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[10000000];

int n,sizew,nump,numw;
int g[MAXN],nume;
pair<int,int> a[MAXN];
int dfn[MAXN],low[MAXN];
int last[MAXN];
int p[MAXN][2];
stack<int> S;
bool instack[MAXN];
int c[MAXN],numc;

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
}

void build(int x,int cl,int cr,int l,int r,int src){
    if(l<=cl && cr<=r){
        addEdge(p[sizew+src-1][1],p[x][0]);
        addEdge(p[x][1],p[sizew+src-1][0]);
        return;
    }
    int mid=(cl+cr)>>1;
    if(l<=mid) build(x<<1,cl,mid,l,r,src);
    if(r>mid) build(x<<1|1,mid+1,cr,l,r,src);
}

void tarjan(int x){
    S.push(x);
    instack[x]=1;
    dfn[x]=low[x]=++numw;
    for(int i=g[x];~i;i=e[i].next)
        if(!dfn[e[i].to]){
            tarjan(e[i].to);
            if(low[e[i].to]<low[x]) low[x]=low[e[i].to];
        }else if(instack[e[i].to]){
            if(dfn[e[i].to]<low[x]) low[x]=dfn[e[i].to];
        }
    if(dfn[x]==low[x]){
        ++numc;
        while(S.top()!=x){
            instack[S.top()]=0;
            c[S.top()]=numc;
            S.pop();
        }
        instack[S.top()]=0;
        c[S.top()]=numc;
        S.pop();
    }
}

bool check(int lim){
    memset(g,-1,sizeof g);
    nump=nume=0;
    for(sizew=1;sizew<n;sizew<<=1);
    for(int i=1;i<=2*sizew-1;i++) p[i][0]=++nump;
    for(int i=1;i<=2*sizew-1;i++) p[i][1]=++nump;
    for(int i=sizew-1;i;i--){
        addEdge(p[i<<1][1],p[i][1]);
        addEdge(p[i<<1|1][1],p[i][1]);
        addEdge(p[i][0],p[i<<1][0]);
        addEdge(p[i][0],p[i<<1|1][0]);
    }
    memset(last,0,sizeof last);
    for(int i=1;i<=n;i++)
        if(last[a[i].second]){
            int j=last[a[i].second];
            addEdge(p[sizew+i-1][0],p[sizew+j-1][1]);
            addEdge(p[sizew+j-1][0],p[sizew+i-1][1]);
            addEdge(p[sizew+i-1][1],p[sizew+j-1][0]);
            addEdge(p[sizew+j-1][1],p[sizew+i-1][0]);
        }else last[a[i].second]=i;
    for(int i=n-1;i;i--)
        if(a[i+1].first-a[i].first<lim){
            int l=i+1,r=n;
            while(l<r){
                int mid=(l+r+1)>>1;
                if(a[mid].first-a[i].first<lim) l=mid;
                else r=mid-1;
            }
            build(1,1,sizew,i+1,l,i);
        }
    memset(dfn,0,sizeof dfn);
    numc=numw=0;
    for(int i=1;i<=nump;i++)
        if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;i++)
        if(c[p[sizew+i-1][0]]==c[p[sizew+i-1][1]]) return 0;
    return 1;
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int t1,t2;
        scanf("%d%d",&t1,&t2);
        a[i*2-1]=make_pair(t1,i);
        a[i*2]=make_pair(t2,i);
    }
    n*=2;
    sort(a+1,a+n+1);
    int l=0,r=a[n].first-a[1].first;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    printf("%d\n",l);
    return 0;
}

查看详细内容

[CF 853D]Michael and Charging Stations

2017-10-18 19:562017-10-18 19:56
Codeforces结论题二分答案

传送门

最近一直在不务正业,没怎么做AtCoder。打了几场cf的vp,状态都不怎么好,基本都是卡一题卡1h多都没做出来,赛后仔细想想就突然会做了。感觉还是场上心态不对,尤其是cf这种时间紧的比赛,看来还是要多打现场比赛才行。

这几天打的所有题卡我卡得最久的应该就是这题了,这题场上就有一堆人过了,然而我场上一直在瞎找结论,找了一些没什么用的结论,然后一直在想怎么dp,结果也没刚出来。赛后仔细想了想,发现有几个很明显的结论我场上都直接无视了,有这些结论就好做很多了。

第一个结论就是一定存在一个最优解,使得所有攒的积分都被用完。因为如果最后剩下的积分大于等于200,则随便把之前攒了积分的某天改成用积分,最后剩下的积分一定会减少,且答案不会变劣。如果最后只剩下100的积分,且前面存在某天攒了100积分,就可以把这天改成用积分,这样就不存在剩余积分了。否则,前面一定只要攒了积分就是攒200,这样的话根本不会出现剩100分(因为每次用都是200的倍数),这就矛盾了。

第二个结论是一定存在一个最优解,使得某个前缀里面每天都攒积分,并且这个前缀之后肯定只有连续且花费相等的一段是在攒积分,而其他时间都在用积分。这个的证明就是如果后面有两段,就根据前面的位置关系,可以把最后那一段的某个位置挪到前面去,然后就减少了最后一段的长度,直到把最后那些多出来的段删完为止。

有了这两个结论,我们直接枚举前缀的长度,然后二分后面那段的长度,看看能把积分用完的情况下最多能积多少分,然后就做完啦。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 300010
using namespace std;

int n;
int a[MAXN],s[MAXN];
int f1[MAXN];
int next1[MAXN],next2[MAXN];
int ans=0;

int getS(int l,int r){ return s[r]-s[l-1]; }

void pre_gao(){
    int last1=n+1,last2=n+1;
    for(int i=n;i>=1;i--){
        next1[i]=last1;
        next2[i]=last2;
        if(a[i]==1) last1=i;
        else last2=i;
    }
}

void update(int x){
    if(x>ans) ans=x;
}

void gao(int x){
    if(getS(x+1,n)*10>=getS(1,x)) update(s[x]);
    if(next1[x]<=n){
        int s1=s[x],s2=getS(x+1,next1[x]-1);
        int s3=max(s1-10*s2,0);
        int l=next1[x],r=next2[next1[x]]-1;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(getS(mid+1,n)*10>=s3+getS(next1[x],mid)) l=mid;
            else r=mid-1;
        }
        if(getS(l+1,n)*10>=s3+getS(next1[x],l))
            update(s1+getS(next1[x],l));
    }
    if(next2[x]<=n){
        int s1=s[x],s2=getS(x+1,next2[x]-1);
        int s3=max(s1-10*s2,0);
        int l=next2[x],r=next1[next2[x]]-1;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(getS(mid+1,n)*10>=s3+getS(next2[x],mid)) l=mid;
            else r=mid-1;
        }
        if(getS(l+1,n)*10>=s3+getS(next2[x],l))
            update(s1+getS(next2[x],l));
    }
}

int main(){
#ifdef DEBUG
    freopen("D.in","r",stdin);
#endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        a[i]/=1000;
        s[i]=s[i-1]+a[i];
    }
    pre_gao();
    for(int i=1;i<=n;i++)
        gao(i);
    ans=s[n]*10-ans;
    printf("%d00\n",ans);
    return 0;
}

查看详细内容

集训队作业之AGC006-D

2017-10-16 15:482017-10-16 15:48
集训队作业AtCoder二分答案

传送门

其实一点日语都不会的话,也大概能差不多看懂日语题面?

首先这种大小比来比去的题显然得二分答案,把小于等于答案的数都看做1,否则看作0,然后底层就只有0和1啦。考虑最终答案的结构,如果底层的两个0或者两个1挨在一起了,那么这两个位置的值全程都不会改变,可以看作是一个隔板,把两边的值隔开。考虑两个隔板之间的值,肯定是01交错的形式,如果两个隔板上的数一样,那么最终这些数都会变成隔板上的数。如果两边的数不一样,则最后会左右对半分别取两个隔板上的数。

然后暴力二分答案然后跑出最中间是0还是1就行啦。

#include <cstdio>
#include <cstring>
#define MAXN 200010

int n;
int a[MAXN],b[MAXN];

int calc(){
    int last=1;
    a[n+1]=a[n];
    for(int i=2;i<=n+1;i++)
        if(a[i]==a[i-1]){
            if(a[last]==a[i]){
                for(int j=last+1;j<i-1;j++)
                    a[j]=a[i];
            }else{
                for(int j=last+1;j<i-1;j++)
                    if(j-last<i-1-j) 
                        a[j]=a[last];
                    else 
                        a[j]=a[i];
            }
            last=i;
        }
    return a[(n+1)/2];
}

int main(){
    scanf("%d",&n);
    n=n*2-1;
    for(int i=1;i<=n;i++)
        scanf("%d",b+i);
    int l=1,r=n;
    while(l<r){
        int mid=(l+r)>>1;
        for(int i=1;i<=n;i++)
            a[i]=(b[i]<=mid?1:0);
        if(calc()==1) r=mid;
        else l=mid+1;
    }
    printf("%d\n",l);
    return 0;
}

查看详细内容

集训队作业之AGC013-C

2017-9-27 18:342017-9-27 18:34
集训队作业AtCoder二分答案

传送门

容易算出如果两只蚂蚁相撞之后方向不变继续行走的话,最终每只蚂蚁的位置在哪。我们只需要知道相撞后转向的情况下,每只蚂蚁最终位于不转向情况下哪只蚂蚁的位置。这个直接对每只蚂蚁二分,看他总共会转多少次向,然后就能得到他实际的位置啦。

不过我的做法好像比正常做法复杂很多,好像代码比他们长几倍。。。感觉是我傻逼了。

代码:

#include <cstdio>
#include <cstring>
#define MAXN 1000010
#define LL long long

int n;
LL L,T;
LL pos[MAXN],dir[MAXN];
LL d1[MAXN],d2[MAXN];
LL sd1[MAXN],sd2[MAXN];
LL p1[MAXN],p2[MAXN];
int id1[MAXN],id2[MAXN];
int target1[MAXN],target2[MAXN],target[MAXN];
int n1,n2;

LL getD1(int x,int l){
    if(l<=x) return sd1[x]-sd1[x-l];
    LL res=sd1[x];
    l-=x;
    res+=sd1[n1]*(l/n1);
    res+=sd1[n1]-sd1[n1-l%n1];
    return res;
}

LL getD2(int x,int l){
    if(l<=n2-x+1) return sd2[x+l-1]-sd2[x-1];
    LL res=sd2[n2]-sd2[x-1];
    l-=n2-x+1;
    res+=sd2[n2]*(l/n2);
    res+=sd2[l%n2];
    return res;
}

int find1(int x1,int x2,LL t){
    int l=0,r=t;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(getD1(x1,mid)+getD2(x2,mid)<=t) l=mid;
        else r=mid-1;
    }
    t-=getD1(x1,l)+getD2(x2,l);
    x1=((x1-l-1)%n1+n1)%n1+1;
    x2=(x2+l-1)%n2+1;
    if(t<d1[x1]) return id2[x2];
    else return id1[(x1-2+n1)%n1+1];
}

int find2(int x1,int x2,LL t){
    int l=0,r=t;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(getD1(x1,mid)+getD2(x2,mid)<=t) l=mid;
        else r=mid-1;
    }
    t-=getD1(x1,l)+getD2(x2,l);
    x1=((x1-l-1)%n1+n1)%n1+1;
    x2=(x2+l-1)%n2+1;
    if(t<d2[x2]) return id1[x1];
    else return id2[x2%n2+1];
}

int main(){
#ifdef DEBUG
    freopen("C.in","r",stdin);
#endif
    scanf("%d%lld%lld",&n,&L,&T);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",pos+i,dir+i);
        if(dir[i]==1){
            p1[++n1]=pos[i];
            id1[n1]=i;
        }else{
            p2[++n2]=pos[i];
            id2[n2]=i;
        }
    }
    for(int i=1;i<=n1;i++){
        d1[i]=(p1[i]-p1[(i-2+n1)%n1+1]+L)%L;
        if(!d1[i]) d1[i]=L;
        sd1[i]=sd1[i-1]+d1[i];
    }
    for(int i=1;i<=n2;i++){
        d2[i]=(p2[i%n2+1]-p2[i]+L)%L;
        if(!d2[i]) d2[i]=L;
        sd2[i]=sd2[i-1]+d2[i];
    }
    T*=2;
    int now=1;
    for(int i=1;i<=n1;i++){
        if(!n2){
            target[i]=i;
            continue;
        }
        while(now<=n2 && p1[i]>p2[now]) now++;
        int x=(now-1)%n2+1;
        LL delta=(p2[x]-p1[i]+L)%L;
        if(delta>T) target1[i]=id1[i];
        else target1[i]=find1(i,x,T-delta);
        target[id1[i]]=target1[i];
    }
    now=n1;
    for(int i=n2;i>=1;i--){
        if(!n1){
            target[i]=i;
            continue;
        }
        while(now && p2[i]<p1[now]) now--;
        int x=(now-1+n1)%n1+1;
        LL delta=(p2[i]-p1[x]+L)%L;
        if(delta>T) target2[i]=id2[i];
        else target2[i]=find2(x,i,T-delta);
        target[id2[i]]=target2[i];
    }
    T/=2;
    for(int i=1;i<=n;i++){
        int x=target[i];
        if(dir[x]==1) printf("%lld\n",(pos[x]+T)%L);
        else printf("%lld\n",((pos[x]-T)%L+L)%L);
    }
    return 0;
}

查看详细内容

集训队作业之AGC007-E

2017-9-25 21:392017-9-25 21:39
集训队作业AtCoder二分答案启发式合并

传送门

首先显然要二分答案。为了判断答案是否可行,我们直接对每棵子树维护一些点对$(u_i,v_i)$,表示可以在第一个点深度为$u_i$,最后一个点深度为$v_i$的情况下走完整棵子树。然后合并两个儿子的时候,用启发式的思想,直接考虑较小的子树中每个点作为起点或终点的情况。这样做的话,每个点维护点对的数量,就是两个儿子中较小的数量乘以2。根据启发式合并的性质,这样做一次是$O(nlogn)$,加上二分答案就是两个log了。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define MAXN 200010
using namespace std;

int n;
int pre[MAXN],ch[MAXN][2];
int size[MAXN],sf[MAXN];
LL v[MAXN],lim;
pair<LL,LL> *f[MAXN];

void dfs(int x){
    if(ch[x][0]){
        dfs(ch[x][0]);
        dfs(ch[x][1]);
        if(size[ch[x][0]]>size[ch[x][1]]) swap(ch[x][0],ch[x][1]);
        size[x]=size[ch[x][0]]<<1;
    }else{
        size[x]=1;
    }
    f[x]=new pair<LL,LL>[size[x]+1];
}

int join(pair<LL,LL> *fs,pair<LL,LL> *f0,pair<LL,LL> *f1,int sf0,int sf1){
    int now0=1,now1=1;
    int sfs=0;
    while(now0<=sf0 || now1<=sf1){
        if(now1>sf1){
            if(!sfs || fs[sfs].second>f0[now0].second)
                fs[++sfs]=f0[now0];
            now0++;
        }else if(now0>sf0){
            if(!sfs || fs[sfs].second>f1[now1].second)
                fs[++sfs]=f1[now1];
            now1++;
        }else if(f0[now0].first<f1[now1].first){
            if(!sfs || fs[sfs].second>f0[now0].second)
                fs[++sfs]=f0[now0];
            now0++;
        }else{
            if(!sfs || fs[sfs].second>f1[now1].second)
                fs[++sfs]=f1[now1];
            now1++;
        }
    }
    return sfs;
}

bool gao(int x){
    if(!ch[x][0]){
        sf[x]=1;
        f[x][1]=make_pair(0,0);
        return 1;
    }
    int c0=ch[x][0],c1=ch[x][1];
    if(!gao(c0)) return 0; 
    if(!gao(c1)) return 0;
    LL delta=v[c0]+v[c1];
    static pair<LL,LL> f0[MAXN],f1[MAXN];
    int sf0=0,sf1=0;
    int now=sf[c1];
    for(int i=sf[c0];i>=1;i--){
        while(now && f[c0][i].second+f[c1][now].first+delta>lim) now--;
        if(!now) break;
        f0[++sf0]=make_pair(f[c0][i].first+v[c0],f[c1][now].second+v[c1]);
    }
    for(int i=1;i<=sf0;i++)
        if(i<sf0-i+1)
            swap(f0[i],f0[sf0-i+1]);
    now=1;
    for(int i=1;i<=sf[c0];i++){
        while(now<=sf[c1] && f[c0][i].first+f[c1][now].second+delta>lim) now++;
        if(now>sf[c1]) break;
        f1[++sf1]=make_pair(f[c1][now].first+v[c1],f[c0][i].second+v[c0]);
    }
    sf[x]=join(f[x],f0,f1,sf0,sf1);
    return sf[x];
}

bool check(LL _lim){
    lim=_lim;
    return gao(1);
}

int main(){
#ifdef DEBUG
    freopen("E.in","r",stdin);
#endif
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        scanf("%d%lld",pre+i,v+i);
        if(!ch[pre[i]][0]) ch[pre[i]][0]=i;
        else ch[pre[i]][1]=i;
    }
    dfs(1);
    LL l=0,r=131072LL*131072LL;
    while(l<r){
        LL mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    printf("%lld\n",l);
    return 0;
}

查看详细内容