ZJT's Blog

大変に気分がいい~

集训队作业之AGC007-C

2017-12-19 17:542017-12-19 17:54
集训队作业AtCoder结论题

传送门

结论题,可以发现每次推一个球之后,剩下的相邻两项的期望距离还是一个等差数列,所以递归下去算就行了。每次是$O(1)$的,所以总复杂度是$O(n)$的。

#include <cstdio>
#include <cstring>

long double solve(int n,long double a,long double d){
    if(!n) return 0;
    long double res=a+d*(2*n-1)/2;
    long double a1=(a*(n-1)*2+(a+2*d)+(3*a+3*d))/(2*n);
    long double a2=((a+d)*(2*(n-1)-1)+(a+3*d)*2+(3*a+6*d))/(2*n);
    return res+solve(n-1,a1,a2-a1);
}

int main(){
    int n;
    double a,d;
    scanf("%d%lf%lf",&n,&a,&d);
    printf("%.20lf\n",(double)solve(n,a,d));
}

查看详细内容

集训队作业之AGC018-F

2017-12-18 17:312017-12-18 17:31
集训队作业AtCoder构造二分图

传送门

首先我们可以直接根据每个点的儿子个数来确定这个点权值的奇偶性。如果某个点在两棵树里的奇偶性不一样,则显然无解。否则,我们可以通过以下方法构造出一组解,使得权值为偶数的点全部取$0$,剩下的点要么是$1$要么是$-1$。

对于每棵树,我们可以把所有奇数的点两两配对(由于奇数点的数量是奇数,所以会剩下一个点不参与配对),使得对于每棵子树,设子树中的奇数点有$2k+1$个,我们都可以在子树中找出$k$对配对的奇数点(还有一个点没有在子树内部配对)。则我们可以钦定每对点一个取$1$,一个取$-1$,这样每个子树的权值和的绝对值就是$1$了。

我们把两棵树的配对情况都拿出来连边,这样建出来的图显然是不含奇环的,所以是个二分图。我们直接把二分图左边的点赋成$1$,右边的点赋成$-1$,就能满足条件了。

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

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

int n,root;
int g[MAXN],nume;
int e2[MAXN][2],nume2;
int d[MAXN],d0[MAXN];
int c[MAXN];

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

int dfs(int x){
    int cnt=0;
    int last=0;
    for(int i=g[x];~i;i=e[i].next){
        cnt^=1;
        int temp=dfs(e[i].to);
        nume2++;
        if(last){
            e2[nume2][0]=last;
            e2[nume2][1]=temp;
            last=0;
        }else last=temp;
    }
    if(!last) last=x;
    d[x]^=cnt;
    d0[x]=cnt;
    return last;
}

void dfs2(int x){
    for(int i=g[x];~i;i=e[i].next)
        if(!c[e[i].to]){
            c[e[i].to]=-c[x];
            dfs2(e[i].to);
        }
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    scanf("%d",&n);
    memset(g,-1,sizeof g);
    nume=0;
    for(int i=1;i<=n;i++){
        int t;
        scanf("%d",&t);
        if(t!=-1) addEdge(t,i);
        else root=i;
    }
    dfs(root);
    memset(g,-1,sizeof g);
    nume=0;
    for(int i=1;i<=n;i++){
        int t;
        scanf("%d",&t);
        if(t!=-1) addEdge(t,i);
        else root=i;
    }
    dfs(root);
    for(int i=1;i<=n;i++)
        if(d[i]){
            puts("IMPOSSIBLE");
            return 0;
        }
    memset(g,-1,sizeof g);
    nume=0;
    for(int i=1;i<=nume2;i++)
        addEdge(e2[i][0],e2[i][1]),addEdge(e2[i][1],e2[i][0]);
    for(int i=1;i<=n;i++)
        if(!d0[i] && !c[i]){
            c[i]=1;
            dfs2(i);
        }
    puts("POSSIBLE");
    for(int i=1;i<=n;i++)
        if(d0[i]) printf("0 ");
        else printf("%d ",c[i]);
}

查看详细内容

集训队作业之ARC071-F

2017-12-18 17:202017-12-18 17:20
集训队作业AtCoderDP

传送门

容易发现只要有两个非1的数排在一起,后面的数就会一直重复了。所以只要枚举最后一个1的位置,然后分类讨论一下就做完啦。

哦对了要DP预处理一下最后一个1位于第$i$位时,第$i$位以前的方案数。转移用前缀和搞一下就行了。

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

const LL P=1000000007;

int n;
LL g[MAXN],sg[MAXN];

inline void update(LL &x,LL y){ x=(x+y)%P; }

int main(){
    scanf("%d",&n);
    g[0]=1;
    sg[0]=1;
    for(int i=1;i<=n;i++){
        g[i]=g[i-1];
        if(i>=3) g[i]=(g[i]+sg[i-3])%P;
        sg[i]=(sg[i-1]+g[i])%P;
    }
    LL ans=0;
    //a[n]=1
    update(ans,g[n-1]);
    for(int i=2;i<=n;i++){
        int j=n-i-1;
        if(j<0) j=0;
        update(ans,sg[n-2]-(j?sg[j-1]:0));
    }
    //a[n-1]=1
    update(ans,g[n-1]*(n-1));
    //else
    for(int i=0;i<=n-2;i++)
        update(ans,g[i]*(n-1)%P*(n-1));
    ans=(ans+P)%P;
    printf("%lld\n",ans);
}

查看详细内容

集训队作业之ARC077-E

2017-12-18 2:172017-12-18 2:17
集训队作业AtCoder差分

传送门

推一下发现每一段的代价是个关于$x$的分段一次函数,然后随便差分维护一下一次项系数和常数项,然后扫一遍就能知道$x$在每个位置时的总步数。

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

int n,m;
LL v[MAXN];
LL d[MAXN][2];

void add(int l,int r,LL x1,LL x2){
    d[l][0]+=x1;
    d[l][1]+=x2;
    d[r+1][0]-=x1;
    d[r+1][1]-=x2;
}

int main(){
#ifdef DEBUG
    freopen("E.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",v+i);
    LL s0=0;
    for(int i=1;i<n;i++){
        LL a=v[i],b=v[i+1];
        if(a<b){
            add(a+1,b,-1,a+1);
            s0+=b-a;
        }else{
            if(a<m) add(a+1,m,-1,a+1);
            add(1,b,-1,a-m+1);
            s0+=b+m-a;
        }
    }
    LL t0=0,t1=0;
    LL ans=1LL<<60;
    for(int i=1;i<=m;i++){
        t0+=d[i][0]; t1+=d[i][1];
        LL s=s0+t0*i+t1;
        if(s<ans) ans=s;
    }
    printf("%lld\n",ans);
}

查看详细内容

集训队作业之ARC063-F

2017-12-18 2:102017-12-18 2:10
集训队作业AtCoder分治单调队列

传送门

问题可以转化成选一个周长最长的矩形使其内部不包含任何点。

首先答案有一个性质就是一定穿过横竖两条中线之一。因为如果两条都不穿过,即缩整个矩形的四分之一里,是没有选$\max(H,W)$再加一条长度为1的边组成的矩形优的。我们先只考虑穿过竖中线的情况,横中线的情况可以把所有东西旋转九十度后转化成竖中线。

在穿过竖中线的同时,我们再对纵坐标分治,每次分治到纵坐标在$[y_l,y_r]$的区间时,我们选最中间的点的纵坐标$y_m$,先递归算出纵坐标在$[y_l,y_m]$或$[y_m,y_r]$中的答案,剩下的就只用考虑同时穿过$x=x_m=W/2$和$y=y_m$两条直线的矩形了。

我们从右往左枚举矩形左边那条边的横坐标$x_l$,并对每个$x_l$处理出所有横坐标在$[x_l,x_m]$且纵坐标在$[y_l,y_m]$中的点的最大的纵坐标$y_1$,以及所有横坐标在$[x_l,x_m]$且纵坐标在$[y_m,y_r]$中的点的最小的纵坐标$y_2$。最终的矩形底边一定在$y_1$上方,顶边一定在$y_2$下方。同样,我们也枚举右边的横坐标$x_r$,并处理出意义相同的$y_1$和$y_2$。这样,两个$x_l$和$x_r$围出来的矩形的底边就是两个$y_1$的较大值,顶边就是$y_2$的较小值。考虑对每个$x_l$找出最优的$x_r$,我们发现可以把右边的所有$x_r$分成三段,第一段的$[y_1,y_2]$完全包含$x_l$的$[y_1,y_2]$;第二段不完全包含,但不被$x_l$的$[y_1,y_2]$包含;第三段则完全被$x_l$的$[y_1,y_2]$包含。第一段的答案很好处理,直接取最靠右的$x_r$就行了,后两段也能通过分别维护单调队列来进行统计(其中第二段还要分为上下两种情况)。这样,在把横坐标排好序之后,我们可以线性地统计出同时穿过$x_m$和$y_m$的答案。排序也可以用归并排序来做到线性,这样总复杂度就是$O(n\log n)$了。

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

int w,h,n,w0;
pair<int,int> a[MAXN];
deque<int> S1,S2,S3;

bool cmp2(pair<int,int> x,pair<int,int> y){
    return x.second<y.second;
}

int gao(int l,int r,int y0,int y1){
    if(l==r) return max(max(w+a[l].second-y0,w+y1-a[l].second),max(y1-y0+a[l].first,y1-y0+w-a[l].first));
    int mid=(l+r)>>1;
    int ymid=a[mid].second;
    int res1=gao(l,mid,y0,a[mid].second);
    int res2=gao(mid+1,r,a[mid+1].second,y1);
    sort(a+l,a+r+1);
    int mid2=l-1;
    while(mid2<r && a[mid2+1].first<=w0) mid2++;
    static int s1[MAXN][3],s2[MAXN][3];
    int ls1=0,ls2=0;
    int t0=y0,t1=y1;
    for(int i=mid2;i>=l;i--){
        s1[++ls1][0]=t0;
        s1[ls1][1]=t1;
        s1[ls1][2]=a[i].first;
        if(a[i].second<=ymid && a[i].second>t0) t0=a[i].second;
        if(a[i].second>ymid && a[i].second<t1) t1=a[i].second;
    }
    s1[++ls1][0]=t0;
    s1[ls1][1]=t1;
    s1[ls1][2]=0;
    t0=y0; t1=y1;
    for(int i=mid2+1;i<=r;i++){
        s2[++ls2][0]=t0;
        s2[ls2][1]=t1;
        s2[ls2][2]=a[i].first;
        if(a[i].second<=ymid && a[i].second>t0) t0=a[i].second;
        if(a[i].second>ymid && a[i].second<t1) t1=a[i].second;
    }
    s2[++ls2][0]=t0;
    s2[ls2][1]=t1;
    s2[ls2][2]=w;
    S1.clear();
    S2.clear();
    S3.clear();
    int now1=1,now2=1;
    for(int i=1;i<=ls2;i++){
        while(!S3.empty() && s2[S3.front()][1]-s2[S3.front()][0]+s2[S3.front()][2]<s2[i][1]-s2[i][0]+s2[i][2])
            S3.pop_front();
        S3.push_front(i);
    }
    int res=0;
    for(int i=1;i<=ls1;i++){
        while(now1<=ls2 && s2[now1][0]<=s1[i][0]){
            while(!S1.empty() && s2[S1.front()][1]+s2[S1.front()][2]<s2[now1][1]+s2[now1][2])
                S1.pop_front();
            S1.push_front(now1++);
        }
        while(now2<=ls2 && s2[now2][1]>=s1[i][1]){
            while(!S2.empty() && s2[S2.front()][2]-s2[S2.front()][0]<s2[now2][2]-s2[now2][0])
                S2.pop_front();
            S2.push_front(now2++);
        }
        while(!S1.empty() && s2[S1.back()][1]>=s1[i][1]) S1.pop_back();
        while(!S2.empty() && s2[S2.back()][0]<=s1[i][0]) S2.pop_back();
        while(!S3.empty() && (s2[S3.back()][0]<=s1[i][0] || s2[S3.back()][1]>=s1[i][1])) S3.pop_back();
        res=max(res,s1[i][1]-s1[i][0]+s2[min(now1-1,now2-1)][2]-s1[i][2]);
        if(!S1.empty()) res=max(res,s2[S1.back()][1]-s1[i][0]+s2[S1.back()][2]-s1[i][2]);
        if(!S2.empty()) res=max(res,s1[i][1]-s2[S2.back()][0]+s2[S2.back()][2]-s1[i][2]);
        if(!S3.empty()) res=max(res,s2[S3.back()][1]-s2[S3.back()][0]+s2[S3.back()][2]-s1[i][2]);
    }
    res=max(res,max(res1,res2));
    return res;
}

int solve(){
    w0=w/2;
    sort(a+1,a+n+1,cmp2);
    return gao(1,n,0,h);
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    scanf("%d%d%d",&w,&h,&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].first,&a[i].second);
    int ans1=solve()*2;
    swap(w,h);
    for(int i=1;i<=n;i++) swap(a[i].first,a[i].second);
    int ans2=solve()*2;
    printf("%d\n",max(ans1,ans2));
    return 0;
}

查看详细内容