The 14th Beihang University Collegiate Programming Contest Online Solutions

给北航出题人点赞!期待后天的现场赛!

A

b-a\le 50,那么容易得出,当a较大时,给两个人的时间段数必须相同,否则不可能和相等。
粗略估计可以得到一个界2500a<2500时暴力DP,a\ge 2500时,将每个时间长度-a,然后状态里再计一下给两个人段数的差值,然后就可以DP了。

const int XN=50+11;

int main() {
    //freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int T;std::cin>>T;
    while(T--) {
        int n,a,b;std::cin>>n>>a>>b;
        static int t[XN];
        for(int i=1;i<=n;++i)
            std::cin>>t[i];
        if(a>2500) {
            for(int i=1;i<=n;++i)
                t[i]-=a;
            static const int N=50,H=2500;
            static int f[2][2*N+1][2*H+1];
            memset(f[0],127,sizeof(f[0]));
            f[0][N][H]=0;
            for(int i=1,sum=0,o=1;i<=n;sum+=t[i++],o^=1) {
                memset(f[o],127,sizeof(f[o]));
                for(int j=-(i-1);j<=(i-1);++j)
                    for(int k=-sum;k<=sum;++k) {
                        int x=f[o^1][N+j][H+k];
                        if(k+t[i]<=H)
                            Reduce(f[o][N+j+1][H+k+t[i]],x);
                        if(k-t[i]>=-H)
                            Reduce(f[o][N+j-1][H+k-t[i]],x);
                        Reduce(f[o][N+j][H+k],x+1);
                    }
            }
            std::cout<<f[n&1][N][H]<<'\n';
        } else {
            static const int H=50*2500;
            static int f[2][2*H+1];
            memset(f[0],127,sizeof(f[0]));
            f[0][H]=0;
            for(int i=1,o=1,sum=0;i<=n;sum+=t[i++],o^=1) {
                memset(f[o],127,sizeof(f[o]));
                for(int j=-sum;j<=sum;++j) {
                    int x=f[o^1][H+j];
                    if(j+t[i]<=H)
                        Reduce(f[o][H+j+t[i]],x);
                    if(j-t[i]>=-H)
                        Reduce(f[o][H+j-t[i]],x);
                    Reduce(f[o][H+j],x+1);
                }
            }
            std::cout<<f[n&1][H]<<'\n';
        }
    }
    return 0;
}

C

使用点分治。在一层中,统计以根为端点的所有链的边权和and边权异或和。考虑如何统计答案。
把式子(a_1+a_2)(b_1{\rm\ xor\ }b_2)展开一下,最后可以转化成求a_i(\sum b_j{\rm\ xor\ }b_i)的和。考虑到xor的位独立性,可以一位位地统计。

const int XN=1e5+11,P=1e9+7,INF=0x1f1f1f1f;

struct Edge {
    int to;
    unsigned int v;
};

std::vector<Edge> G[XN];

namespace StaticVertexBasedDC {
    bool ud[XN];
    int size[XN];

    int GetSize(int pos,int fa) {
        size[pos]=1;
        for(auto &e : G[pos]) {
            int u=e.to;
            if(!ud[u] && u!=fa)
                size[pos]+=GetSize(u,pos);
        }
        return size[pos];
    }

    int Centre(int pos) {
        GetSize(pos,0);
        int tot=size[pos];
        bool found;
        do {
            found=0;
            for(auto &e : G[pos])
                if(!ud[e.to] && size[e.to]<size[pos] && size[e.to]*2>=tot) {
                    pos=e.to;
                    found=1;
                    break;
                }
        } while(found);
        return pos;
    }

    long long Calc(std::pair<long long,unsigned int> a[],int n,std::array<int,32> const &xs) {
        long long res=0;
        for(int i=1;i<=n;++i) {
            long long sum=0;
            for(int b=31;b>=0;--b)
                (sum+=(long long)(a[i].second>>b&1?n-xs[b]:xs[b])*(1u<<b))%=P;
            (res+=a[i].first*sum)%=P;
        }
        return res;
    }

    std::pair<long long,unsigned int> all[XN],sub[XN];
    std::array<int,32> aset,sset;
    int allc,subc;
    void DFS(int pos,int fa,long long len,unsigned int xs) {
        sub[++subc]={len,xs};
        for(auto &e : G[pos])
            if(!ud[e.to] && e.to!=fa)
                DFS(e.to,pos,(len+e.v)%P,xs^e.v);
    }

    int rec;

    long long DC(int pos) {

        static int cc;
        ++cc;
        Enlarge(rec,cc);

        ud[pos]=1;
        allc=0;
        long long res=0;
        for(int i=0;i<32;aset[i++]=0);
        for(auto &e : G[pos]) {
            int u=e.to;
            if(!ud[u]) {
                for(int i=0;i<32;sset[i++]=0);
                subc=0;

                DFS(e.to,pos,e.v,e.v);
                for(int i=1;i<=subc;++i)
                    for(int b=31;b>=0;--b)
                        sset[b]+=sub[i].second>>b&1;

                (res-=Calc(sub,subc,sset))%=P;
                for(int b=31;b>=0;--b)
                    aset[b]+=sset[b];
                std::copy(sub+1,sub+1+subc,all+allc+1);
                allc+=subc;
            }
        }
        (res+=Calc(all,allc,aset))%=P;
        for(int i=1;i<=allc;++i)
            (res+=all[i].first*all[i].second%P)%=P;
        for(auto &e : G[pos]) {
            int u=e.to;
            if(!ud[u])
                (res+=DC(Centre(u)))%=P;
        }

        --cc;

        return res;
    }
}

void Work() {
    int n;std::cin>>n;
    using namespace StaticVertexBasedDC;
    for(int i=1;i<=n;++i) {
        ud[i]=0;
        std::vector<Edge>().swap(G[i]);
    }
    for(int i=1;i<=n-1;++i) {
        int x,y;unsigned int v;
        std::cin>>x>>y>>v;
        G[x].push_back({y,v});
        G[y].push_back({x,v});
    }

    rec=0;

    int Ans=DC(Centre(1));

//  std::cerr<<rec<<':'<<'\n';

    Ans<0  && (Ans+=P);
    std::cout<<Ans<<'\n';
}
int main() {
    //freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int T;std::cin>>T;
    while(T--)
        Work();
    return 0;
}

E

从大到小枚举d,然后用枚举d的倍数,并查集判断是否已经联通。
要先把相同的数字合并成一个,复杂度就是标准O(n\log n)了。

const int XN=1e5+11,V=1e5;

int dsu[XN];
int Root(int x) {
    return dsu[x]?dsu[x]=Root(dsu[x]):x;
}

void Work() {
    int n;std::cin>>n;
    static int cnt[XN];
    for(int i=1;i<=V;++i)
        cnt[i]=dsu[i]=0;
    long long Ans=0;
    for(int i=1;i<=n;++i) {
        int x;std::cin>>x;
        cnt[x]++;
    }
    for(int i=1;i<=V;++i)
        if(cnt[i])
            Ans+=(long long)(cnt[i]-1)*i;
    for(int d=V;d>=1;--d) {
        std::vector<int> v;
        for(int x=d;x<=V;x+=d)
            if(cnt[x])
                v.push_back(x);
        for(size_t i=0;i+1<v.size();++i)
            if(Root(v[i])!=Root(v[i+1])) {
                dsu[Root(v[i])]=Root(v[i+1]);
                Ans+=d;
            }
    }
    std::cout<<Ans<<'\n';
}

int main() {
    //freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int T;std::cin>>T;
    while(T--)
        Work();
    return 0;
}

G

对于每个if[i][k]表示以i为结尾的所有上升子序列的\sum x^k是多少。转移的时候,对于a[j] < a[i],则a[i]可以接在以j为结尾的子序列后面,使得子序列长度+1。将(x+1)^k用二项式定理展开,就可以求出来\sum (x+1)^k了。
然后加上一个树状数组维护就好了

int C[21][21];
std::array<int,21> AddOne(std::array<int,21> const &a) {
    std::array<int,21> res;
    for(int i=0;i<=20;++i) {
        res[i]=0;
        for(int j=0;j<=i;++j)
            (res[i]+=(long long)C[i][j]*a[j]%P)%=P;
    }
    return res;
}

std::array<int,21> &operator +=(std::array<int,21> &a,std::array<int,21> const &b) {
    for(int i=0;i<=20;++i)
        (a[i]+=b[i])%=P;
    return a;
}

std::array<int,21> bit[XN];int n;
std::array<int,21> Sum(int pos) {
    std::array<int,21> res;
    for(int i=0;i<=20;res[i++]=0);
    for(;pos;pos-=pos & -pos)
        res+=bit[pos];
    return res;
}

void Add(int pos,std::array<int,21> const &v) {
    for(;pos<=n;pos+=pos & -pos)
        bit[pos]+=v;
}

std::pair<int,int> p[XN];
std::vector<int> num;

int main() {
    //freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    C[0][0]=1;
    for(int i=1;i<=20;++i) {
        C[i][0]=1;
        for(int j=1;j<=i;++j)
            C[i][j]=C[i-1][j-1]+C[i-1][j];
    }
    int T;std::cin>>T;
    while(T--) {
        std::vector<int>().swap(num);
        int n,k;std::cin>>n>>k;
        long long Ans=0;
        for(int i=1;i<=n;++i) {
            std::cin>>p[i].first>>p[i].second;
            num.push_back(p[i].first);
        }
        std::sort(num.begin(),num.end());
        num.erase(std::unique(num.begin(),num.end()),num.end());
        for(int i=1;i<=(int)num.size()+1;++i)
            for(int j=0;j<=20;bit[i][j++]=0);
        ::n=num.size()+1;
        Add(1,{1});
        for(int i=1;i<=n;++i) {
            p[i].first=std::lower_bound(num.begin(),num.end(),p[i].first)-num.begin()+2;
            auto res=Sum(p[i].first-1),
                 v=AddOne(res);
            for(int j=0;j<=20;++j)
                v[j]=(long long)v[j]*p[i].second%P;
            (Ans+=v[k])%=P;
            Add(p[i].first,v);
        }
        std::cout<<Ans<<'\n';
    }
    return 0;
}

J

感觉这次写的不错,留个模板

const int XN=20;

int Pow(long long base,long long v,int P) {
    long long res=1;
    for(base%=P;v;v>>=1,(base*=base)%=P)
        if(v&1)
            (res*=base)%=P;
    return res;
}

int Inverse(long long a,int P) {
    return Pow(a,P-2,P);
}

long long Mul(long long x,long long y,long long P) {
    long long res=0;
    for(x%=P;y;y>>=1,(x*=2)%=P)
        if(y&1)
            (res+=x)%=P;
    return res;
}

struct Lucas {
    int P;
    std::vector<int> fact,ifact;

    Lucas(int P):P(P),fact(P),ifact(P) {
        fact[0]=1;
        for(int i=1;i<P;++i)
            fact[i]=(long long)fact[i-1]*i%P;
        ifact[P-1]=Inverse(fact[P-1],P);
        for(int i=P-2;i>=0;--i)
            ifact[i]=(long long)ifact[i+1]*(i+1)%P;
    }

    int C(int n,int m) {
        return n<m?0:(long long)fact[n]*ifact[m]%P*ifact[n-m]%P;
    }

    int operator ()(long long n,long long m) {
        long long res=1;
        while(n && m) {
            (res*=C(n%P,m%P))%=P;
            n/=P,m/=P;
        }
        return res;
    }
};

struct MultiLucas {
    std::vector<Lucas> c;
    std::vector<int> p,t;
    std::vector<long long> r;
    long long P;

    MultiLucas(std::vector<int> const &p):p(p),t(p.size()),r(p.size()) {
        P=1;
        c.reserve(p.size());
        for(size_t i=0;i<p.size();++i) {
            P*=p[i];
            c.emplace_back(p[i]);
        }

        for(size_t i=0;i<p.size();++i) {
            r[i]=P/p[i];
            t[i]=Inverse(r[i],p[i]);
        }
    }

    long long operator ()(long long n,long long m) {
        long long res=0;
        for(size_t i=0;i<p.size();++i)
            (res+=Mul((long long)c[i](n,m)*t[i]%P,r[i],P))%=P;
        return res;
    }
};

void Work() {
    int n,k;
    long long m;
    std::cin>>n>>m>>k;
    std::vector<int> p(k);
    static long long v[XN];
    long long all=0;
    for(int i=0;i<n;++i) {
        std::cin>>v[i];
        all+=v[i];
    }
    long long P=1;
    for(int i=0;i<k;++i) {
        std::cin>>p[i];
        P*=p[i];
    }
    MultiLucas C(p);
    long long Ans=0;
    for(int S=0;S<(1<<n);++S) {
        int cnt=0;long long sum=0;
        for(int i=0;i<n;++i)
            if(S>>i&1) {
                cnt++;
                sum+=v[i]+1;
            }
        if(sum<=m) {
            (Ans+=Mul(cnt&1?P-1:1,C(m-sum+n-1,n-1),P))%=P;
        }
    //  std::cerr<<S<<'\n';
    }
    std::cout<<Ans<<'\n';
}

int main() {
    //freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int T;std::cin>>T;
    while(T--)
        Work();
    return 0;
}

[ICPC 2018 Shenyang Onsite D][Gym 101955D]Diameter of a tree

Link

感觉很有意思,非常想A掉这道题,但是找了好久都没有任何的题解或者AC代码。无奈看到过掉这道题的一位KUT小哥哥CF在线,于是讨教了一发,朝鲜小哥哥马上就回给我了AC代码!心里有点小激动
KUT小哥哥的function对象用的实在6…感觉这样写特别紧凑易读!

Solution

任何一个边数为c边权和为w的路径,在x点的值就是cx+w
问题可以转化为一堆直线,求x点处最高的直线的纵坐标。
半平面交可以转化为凸包,因此维护一个全局凸包就行了。
点分治,对于分出来的子树的凸包,需要求出从不同子树选出两点加和产生新点集的凸包。
为了保证复杂度,KUT小哥哥用了类似线段树一样的分治思想。
这是这道题的精华部分,然而我现在还是不懂为什么KUT小哥哥AddHull这么做是对的。先A了过几天再看看吧。

Code

const int XN=2e5+11;

struct Point {
    long long x,y;

    long long operator ()(int a) {
        return x*a+y;
    }

    friend Point operator +(Point const &a,Point const &b) {
        return Point{a.x+b.x,a.y+b.y};
    }   

    friend Point operator -(Point const &a,Point const &b) {
        return Point{a.x-b.x,a.y-b.y};
    }   

    friend long long Outer(Point const &a,Point const &b) {
        return a.x*b.y-a.y*b.x;
    }

    friend bool operator <(Point const &a,Point const &b) {
        return a.x<b.x || (a.x==b.x && a.y<b.y);
    }
};

std::vector<Point> ConvexHull(std::vector<Point> a) {
    if(!std::is_sorted(a.begin(),a.end()))
        std::sort(a.begin(),a.end());
    std::vector<Point> hull;
    for(Point p : a) {
        while(hull.size()>1 && Outer(hull.back()-hull[hull.size()-2],p-hull.back())>=0)
            hull.pop_back();
        hull.push_back(p);
    }
    return hull;
}

std::vector<Point> MergeHull(std::vector<Point> const &a,std::vector<Point> const &b) {
    std::vector<Point> c(a.size()+b.size());
    std::merge(a.begin(),a.end(),b.begin(),b.end(),c.begin());
    return ConvexHull(c);
}

std::vector<Point> AddHull(std::vector<Point> const &v1,std::vector<Point> const &v2) {
    std::vector<Point> hull;
    for(size_t p1=0,p2=0;p1<v1.size() && p2<v2.size();) {
        hull.push_back(v1[p1]+v2[p2]);
        if(p1+1<v1.size() && p2+1<v2.size()) {
            if(Outer(v1[p1+1]-v1[p1],v2[p2+1]-v2[p2])<0)
                ++p1;
            else
                ++p2;
        } else if(p1+1<v1.size())
            ++p1;
        else
            ++p2;
    }
    return hull;
}

struct Edge {
    int to,v;
    Edge *pre;
    void *operator new(size_t flag) {
        static Edge *pool=(Edge*)malloc(XN*2*sizeof(Edge)),*mem;
        return flag?mem++:mem=pool;
    }
}*G[XN];

void AddEdge(int x,int y,int v) {
    G[x]=new Edge{y,v,G[x]};
    G[y]=new Edge{x,v,G[y]};
}

long long mxw[XN];

bool ud[XN];

void DC(int pos=1) {
    static int size[XN];
    std::function<int(int)> Centroid=[&](int pos) {
        std::function<void(int,int)> GetSize=[&](int pos,int fa) {
            size[pos]=1;
            for(Edge *e=G[pos];e;e=e->pre)
                if(fa!=e->to && !ud[e->to]) {
                    GetSize(e->to,pos);
                    size[pos]+=size[e->to];
                }
        };
        GetSize(pos,0);
        int tot=size[pos];
        bool found;
        do {
            found=0;
            for(Edge *e=G[pos];e;e=e->pre)
                if(!ud[e->to] && size[e->to]<size[pos] && size[e->to]*2>=tot) {
                    pos=e->to;
                    found=1;
                    break;
                }
        } while(found);
        return pos;
    };

    static std::vector<Point> v[XN];

    ud[pos=Centroid(pos)]=1;
    std::vector<std::vector<Point>> all;
    for(Edge *e=G[pos];e;e=e->pre)
        if(!ud[e->to]) {
            v[e->to].clear();
            std::function<void(int,int,std::vector<Point>&,int,long long)> DFS=
                [&](int pos,int fa,std::vector<Point> &v,int dep,long long length) {
                Enlarge(mxw[dep],length);
                v.push_back({dep,length});
                for(Edge *e=G[pos];e;e=e->pre)
                    if(e->to!=fa && !ud[e->to])
                        DFS(e->to,pos,v,dep+1,length+e->v);
            };
            DFS(e->to,pos,v[e->to],1,e->v);
            all.push_back(ConvexHull(v[e->to]));
        }

    std::function<void(int,int,int)> Solve=[&](int pos,int L,int R) {
        static std::vector<Point> T[XN*4];
        if(L==R)
            T[pos]=all[L];
        else {
            int M=(L+R)/2;
            Solve(pos<<1,L,M);Solve(pos<<1|1,M+1,R);
            T[pos]=MergeHull(T[pos<<1],T[pos<<1|1]);
            std::vector<Point> sum=AddHull(T[pos<<1],T[pos<<1|1]);
            for(auto p : sum)
                Enlarge(mxw[p.x],p.y);
        }
    };

    if(all.size())
        Solve(1,0,all.size()-1);

    for(Edge *e=G[pos];e;e=e->pre)
        if(!ud[e->to])
            DC(Centroid(e->to));
}

void Work() {
    int n,m;
    fin>>n>>m;
    Edge::operator new(0);
    for(int i=1;i<=n;++i) {
        G[i]=0;
        mxw[i]=-1;
        ud[i]=0;
    }
    for(int i=1;i<=n-1;++i) {
        int x,y,v;fin>>x>>y>>v;
        AddEdge(x,y,v);
    }
    DC();
    std::vector<Point> poly;
    for(int i=1;i<=n-1;++i)
        if(mxw[i]>=0)
            poly.push_back({i,mxw[i]});
    poly=ConvexHull(poly);

    for(int q=1;q<=m;++q) {
        int x;fin>>x;
        int L=0,R=poly.size()-1;
        while(R-L>2) {
            int M1=(L*2+R)/3,M2=(L+R*2)/3;
            if(poly[M1](x)>poly[M2](x))
                R=M2;
            else
                L=M1;
        }
        long long Ans=0;
        for(int i=L;i<=R;++i)
            Enlarge(Ans,poly[i](x));
        fout<<Ans<<'\n';
    }
}

int main() {
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d:\n",ks);
        Work();
    }
    return 0;
}