[EC-Final 2017H]Mr. Panda and Birthday Song

Link

Solution

两次dp,一次尽量符合要求,一次尽量不符合要求,即一次让连续的元音、辅音尽量长,一次让连续的辅音元音尽量短,判断判断就能转移出来了。

Code

const int XN=1e6+11,INF=0x1f1f1f1f;

int main() {
    int T;fin>>T;
    const char *Ans[]={"LIKE","SURPRISE","DISLIKE"};
    std::set<char> vowels({'a','e','i','o','u'});
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d: ",ks);
        static char s[XN];
        int x,y;
        fin>>(s+1)>>x>>y;//x vow y non-vow
        int n=strlen(s+1);
        static int f[XN][2];
        int type=0;
        for(int i=1;i<=n;++i) {
            f[i][0]=f[i][1]=-1;
            if(s[i]=='?') {
                if(~f[i-1][0])
                    f[i][1]=1;
                else
                    f[i][1]=f[i-1][1]+1;
                if(~f[i-1][1])
                    f[i][0]=1;
                else
                    f[i][0]=f[i-1][0]+1;
            } else if(vowels.count(s[i])) {
                if(~f[i-1][0])
                    f[i][1]=1;
                else
                    f[i][1]=f[i-1][1]+1;
            } else {
                if(~f[i-1][1])
                    f[i][0]=1;
                else
                    f[i][0]=f[i-1][0]+1;
            }
            if(f[i][0]==y)
                f[i][0]=-1;
            if(f[i][1]==x)
                f[i][1]=-1;
            if(f[i][0]==-1 && f[i][1]==-1) {
                type=2;
                break;
            }
        }
        if(type!=2) {
            for(int i=1;i<=n;++i) {
                f[i][0]=f[i][1]=-1;
                if(s[i]=='?') {
                    if(f[i-1][1]!=-1)
                        f[i][1]=f[i-1][1]+1;
                    else
                        f[i][1]=1;
                    if(f[i-1][0]!=-1)
                        f[i][0]=f[i-1][0]+1;
                    else
                        f[i][0]=1;
                } else if(vowels.count(s[i])) {
                    if(f[i-1][1]!=-1)
                        f[i][1]=f[i-1][1]+1;
                    else
                        f[i][1]=1;
                } else {
                    if(f[i-1][0]!=-1)
                        f[i][0]=f[i-1][0]+1;
                    else
                        f[i][0]=1;
                }
                if(f[i][0]==y || f[i][1]==x) {
                    type=1;
                    break;
                }
            }
        }
        puts(Ans[type]);
    }
    return 0;
}

[ECL-Final 2017D]Mr. Panda and Geometric Sequence

Link

Solution

x划分出的前三项为a[1],a[2],a[3],则a[1]a[2]a[3]=a[2]^3\le x\le 10^{15}a[2]\le 10^5

Code

std::vector<long long> nums;
void Prep() {
    const int N=1e5;
    const long long UP=1e15;
    //k*p*q
    auto Join=[](long long a,long long b)->long long {
        for(long long x=b;x;x/=10)
            if((a*=10)>UP)
                return UP+1;
        return a+=b;
    };

    for(long long p=1;p<=N;++p)
        for(long long q=p+1;p*q<=N;++q)
            if(std::__gcd(p,q)==1) {
                for(long long k=1;k*p*q<=N;++k) {
                    long long x=Join(Join(k*p*p,k*p*q),k*q*q),a=k*q*q;
                    while(x<=UP) {
                        nums.push_back(x);
                        if(a*q%p)
                            break;
                        else
                            x=Join(x,a=a*q/p);
                    }
                }
            }
    std::sort(nums.begin(),nums.end());
    nums.erase(std::unique(nums.begin(),nums.end()),nums.end());
}

int main() {
    Prep();
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d: ",ks);
        long long l,r;fin>>l>>r;
        auto Solve=[&](long long x) {
            return std::upper_bound(nums.begin(),nums.end(),x)-nums.begin();
        };

        fout<<Solve(r)-Solve(l-1)<<'\n';
    }
    return 0;
}

[ECL-Final 2017 G]Image Recognition

Link

Solution

最开始的想法是,把每次的询问中相邻两个串找到一个不同的位置就能区分开。然而,“不同”关系不具有传递性。如何才能让A、B不同,B、C不同,那么A、C就不同?考虑把01串排序,也将询问的串排序。那么设A、B第一个不同的位置为i。由于A<B,则A[i]=0,B[i]=1,C[i]=1,由此推出了A、C不同。

Code

暴力的实现:

const int XN=2e3+11,XM=4e5+11;

struct BitSet {

    static int BW;

    unsigned long long s[(XM>>6)+1];

    void Set(unsigned int pos,bool val) {
        val==0?(s[pos>>6]&=~(1ull<<(pos&63))):(s[pos>>6]|=1ull<<(pos&63));
    }

    static int XorFirst1(BitSet const &a,BitSet const &b) {
        for(int i=0;i<BW;++i) {
            unsigned long long x=a.s[i]^b.s[i];
            if(x)
                return 64*i-1+__builtin_ffsll(x);
                    //(x&(-1u)?__builtin_ffs(x&(-1u)):__builtin_ffs(x>>32)+32);
        }
        return -1;
    }

    void Reset() {
        for(int i=0;i<BW;++i)
            s[i]=0;
    }
}b[XN];
int BitSet::BW;

int main() {
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d:\n",ks);
        int n,m,q;fin>>n>>m>>q;
        BitSet::BW=(m>>6)+1;
        static std::pair<std::string,int> c[XN];
        for(int i=0;i<n;i++){
            std::cin>>c[i].first;
            c[i].second=i;
        }
        std::sort(c,c+n);
        static int ref[XN];
        for(int i=0;i<n;++i) {
            ref[c[i].second]=i;
            b[i].Reset();
            for(int j=0;j<m;j++)
                b[i].Set(j,c[i].first[j]=='1');
        }
        while(q--) {
            int cnt;fin>>cnt;
            static int a[XN];
            for(int i=0;i<cnt;++i) {
                fin>>a[i];
                a[i]=ref[a[i]];
            }
            std::sort(a,a+cnt);
            static int Ans[XN];
            for(int i=0;i<cnt-1;++i)
                Ans[i]=BitSet::XorFirst1(b[a[i]],b[a[i+1]]);
            std::sort(Ans,Ans+cnt-1);
            int ac=std::unique(Ans,Ans+cnt-1)-Ans;
            fout<<ac<<' ';
            for(int i=0;i<ac;++i)
                fout<<Ans[i]<<' ';
            fout<<'\n';
        }
    }
    return 0;
}

Hash+二分
从CF上学来的做法。注意这是01串,可以将字符串的hash转化成集合的hash。

const int XN=2e3+11,XM=4e3+11;

int main() {
    srand(233);
    static unsigned long long h[XM];
    for(int i=0;i<XM;++i)
        h[i]=(unsigned long long)rand()<<32|rand();
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d:\n",ks);
        int n,m,q;fin>>n>>m>>q;
        static unsigned long long hash[XN][XM];
        static char s[XN][XM];
        static int seq[XN],rank[XN];
        for(int i=0;i<n;++i) {
            fin>>s[i];
            hash[i][0]=s[i][0]=='1'?h[0]:0;
            for(int j=1;j<m;++j)
                hash[i][j]=hash[i][j-1]^(s[i][j]=='1'?h[j]:0);
            seq[i]=i;
        }
        auto First=[&](int x,int y)->int {
            if(hash[x][0]!=hash[y][0])
                return 0;
            else {
                int L=0,R=m-2;
                while(L!=R) {
                    int M=(L+R+1)/2;
                    if(hash[x][M]==hash[y][M])
                        L=M;
                    else
                        R=M-1;
                }
                return L+1;
            }
        };
        std::sort(seq,seq+n,[&](int x,int y)->bool {return s[x][First(x,y)]=='0'; });
        for(int i=0;i<n;++i)
            rank[seq[i]]=i;
        while(q--) {
            int cnt;fin>>cnt;
            static int a[XN];
            for(int i=0;i<cnt;++i)
                fin>>a[i];
            std::sort(a,a+cnt,[&](int x,int y)->bool { return rank[x]<rank[y]; });
            static int Ans[XN];
            for(int i=0;i<cnt-1;++i)
                Ans[i]=First(a[i],a[i+1]);
            std::sort(Ans,Ans+cnt-1);
            int ac=std::unique(Ans,Ans+cnt-1)-Ans;
            fout<<ac<<' ';
            for(int i=0;i<ac;++i)
                fout<<Ans[i]<<' ';
            fout<<'\n';
        }
    }
    return 0;
}

非标准库的一些好用的东西

Bit Opearation Built-in Functions

int __builtin_ffs (int x)
//Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero. 
int __builtin_clz (unsigned int x)
//Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined. 
int __builtin_ctz (unsigned int x)
//Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined. 
int __builtin_clrsb (int x)
//Returns the number of leading redundant sign bits in x, i.e. the number of bits following the most significant bit that are identical to it. There are no special cases for 0 or other values.
int __builtin_popcount (unsigned int x)
//Returns the number of 1-bits in x.
int __builtin_parity (unsigned int x)
//Returns the parity of x, i.e. the number of 1-bits in x modulo 2.

[CF1088E]Ehab and a component choosing problem

Link

Solution

答案的值等于整棵树的点权最大联通块,可以用一次树形DP求出来。
接下来就求最多有多少个点权和等于所求答案的联通块。
有一个贪心是,凑出顶点深度更深的联通块一定不会比凑出顶点深度更浅的联通块更优。因此第二次DFS的时候如代码所示再DP一遍。

Code

const int XN=3e5+11;

std::vector<int> G[XN];
int a[XN];

long long f[XN],g[XN],res;

void DP(int pos,int fa) {
    f[pos]=a[pos];
    for(int u : G[pos]) if(u!=fa) {
        DP(u,pos);
        f[pos]+=std::max(f[u],0ll);
    }
}

int cnt=0;

void DFS(int pos,int fa) {
    g[pos]=a[pos];
    for(int u : G[pos]) if(u!=fa) {
        DFS(u,pos);
        g[pos]+=std::max(g[u],0ll);
    }
    if(g[pos]==res) {
        cnt++;
        g[pos]=0;
    }
}

int main() {
    int n;fin>>n;
    for(int i=1;i<=n;++i)
        fin>>a[i];
    for(int i=1;i<=n-1;++i) {
        int x,y;fin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    DP(1,0);
    res=*std::max_element(f+1,f+1+n);
    DFS(1,0);
    fout<<res*cnt<<' '<<cnt<<'\n';
    return 0;
}

[CF1043E]Make It One

Link

Solution

将找最小值变成求是否可行,而求是否可行的方法又是容斥计数判断是否为0,这波操作666
f[i][j]表示选i个数字\gcdj的方案数目,答案就是最小的i使得f[i][1]\not=0
f[i][j]=\binom {i}{c[j]}-\sum_{k=2}f[i][j*k]c[j]表示所有数字中整除j的个数。

Code

const int XN=3e5+11,P=1e9+7;

int Add(int x,int const &y) {
    return (x+=y)>=P?x-P:x;
}

int Minus(int x,int const &y) {
    return (x-=y)<0?x+P:x;
}

int Mul(long long x,int const &y) {
    return x*y%P;
}

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

int main() {
    static int f[8][XN],a[XN],fact[XN],ifact[XN],cnt[XN],c[XN];
    int n,m=0;fin>>n;

    fact[0]=1;
    for(int i=1;i<=n;++i)
        fact[i]=Mul(fact[i-1],i);
    ifact[n]=Pow(fact[n],P-2);
    for(int i=n-1;i>=0;--i)
        ifact[i]=Mul(ifact[i+1],i+1);

    auto C=[](int n,int m) { return n>=m?Mul(fact[n],Mul(ifact[n-m],ifact[m])):0; };

    for(int i=1;i<=n;++i) {
        fin>>a[i];
        f[1][a[i]]=1;
        Enlarge(m,a[i]);
        cnt[a[i]]++;
    }
    for(int i=1;i<=m;++i)
        for(int j=1;i*j<=m;++j)
            c[i]+=cnt[i*j];
    for(int i=2;i<=7;++i) {
        for(int j=m;j>=1;--j) {
            f[i][j]=C(c[j],i);//整除j的个数
            for(int k=2;k*j<=m;++k)
                f[i][j]=Minus(f[i][j],f[i][k*j]);
        }
    }
    int Ans=-1;
    for(int i=1;i<=7;++i)
        if(f[i][1]) {
            Ans=i;
            break;
        }
    fout<<Ans<<'\n';
    return 0;
}

[ICPC 2018 Shenyang Onsite L][Gym 101955L]Machining Disc Rotors

Link

Solution

最远点对一定出现在一对交点处,或者交点和它的未被覆盖的对称点处。考虑弦长变化的单调性即可证明。

Code

const int XN=2e2+11;
const double eps=1e-10,pi=acos(-1);

int sgn(double const &x) {
    return (x>-eps)-(x<eps);
}

struct Point {
    double x,y;

    double Length() const {
        return sqrt(x*x+y*y);
    }

    Point Normal() const {
        return Point{-y,x};
    }

    Point Unit() const {
        double len=Length();
        return Point{x/len,y/len};
    }

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

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

    friend Point operator *(const Point &a,const double &k) {
        return Point{a.x*k,a.y*k};
    }

    friend Point operator /(const Point &a,const double &k) {
        return Point{a.x/k,a.y/k};
    }

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

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

double Dist(const Point &a,const Point &b) {
    return (a-b).Length();
}

void Work() {
    int n,R;fin>>n>>R;
    Point o{0,0};
    auto Atan2=[](double const &y,double const &x) { double r=atan2(y,x); return r<0?r+pi*2:r; };
    bool flag=0;
    auto Calc=[&](Point p,int r)->std::vector<Point> {
        int d1=sgn(Dist(o,p)-R-r),d2=sgn(Dist(o,p)-fabs(R-r));
        if(d1==0)
            return {p/(R+r)*R};
        else if(d1<0 && d2==0) {
            return {p/(R-r)*R};
        } else if(d1<0 && d2>0) {
            double d=Dist(o,p),x=(R*R-r*r+d*d)/(2*d),h=sqrt(R*R-x*x);
            Point v=(p-o).Unit(),n=v.Normal();
            return {v*x-n*h,v*x+n*h};
        } else
            return {};
    };

    std::vector<Point> cross;
    std::vector<std::pair<double,double> > ranges;
    for(int i=1;i<=n;++i) {
        int x,y,r;
        fin>>x>>y>>r;
        std::vector<Point> nc=Calc(Point{(double)x,(double)y},r);
        for(Point &p : nc)
            cross.push_back(p);
        if(nc.size()==1) {
            double x=Atan2(nc[0].y,nc[0].x);
            ranges.push_back({x,x});
        } else if(nc.size()==2)
            ranges.push_back({Atan2(nc[0].y,nc[0].x),Atan2(nc[1].y,nc[1].x)});
    }
    std::sort(ranges.begin(),ranges.end());
    double Ans=0;
    for(size_t i=0;i<cross.size();++i) {
        for(size_t j=i+1;j<cross.size();++j)
            Enlarge(Ans,Dist(cross[i],cross[j]));
        double ang=Atan2(-cross[i].y,-cross[i].x);
        auto Cover=[&](std::pair<double,double> const &x,double const &y)->bool {
            if(x.first<=x.second)
                return x.first<=y && y<=x.second;
            else
                return x.first<=y || y<=x.second;
        };
        auto iter=std::upper_bound(ranges.begin(),ranges.end(),std::pair<double,double>(ang,ang));
        if(iter!=ranges.begin())
            flag|=!Cover(*--iter,ang) && !Cover(ranges.back(),ang);
        else
            flag|=!Cover(ranges.back(),ang);
        if(flag)
            break;
    }
    if(flag)
        Ans=R*2;
    fout<<Ans<<'\n';
}

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

[ICPC 2018 Shenyang Onsite K][Gym 101955K]Let the Flames Begin

Link

Solution

求步长为k的约瑟夫游戏中第m个出圈的人。
n\le 10^{18},\min{m,k}\le 10^6

The Initial Josephus Problem Solution

f[n]表示n个人围成一圈玩约瑟夫最后剩下的人的标号。
由于删掉一个人之后就会变成n-1的问题,只需要考虑删掉这一个人对于n-1问题的影响。可以发现,删掉第k个人的影响只是n-1问题中的第一个人变成大问题中的第k+1个人,也就是所有人的标号都增加了k
因此f[n]=(k+f[n-1])\mod n(从0开始标号)

This Enhanced Problem Solution

类似的思路
f[n][m]表示n个人第m个出圈的是谁,那么根据前面的分析f[n][m]=(k+f[n-1][m-1])\mod n
边界条件f[n][1]=m-1,在m小的时候直接递推过去就行了。
km大的时候,核心思想是优化递推式。由于kn大,所以走很多步才会被膜一次,那么就算一下会走几步被膜,把k乘上次数去算,一次走多步。
假设当前递推值为p,当前总人数为tx步之后需要mod,则有下式
p+xk\ge t+x。根据此式就能解出x了。

Code

int main() {
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d: ",ks);
        long long n,m,k;fin>>n>>m>>k;
        long long Ans=(k-1)%(n-m+1);
        if(m<k) {
            for(int i=2;i<=m;++i)
                Ans=(Ans+k)%(n-m+i);
            ++Ans;
        } else {
            if(k==1)
                Ans=m;
            else {
                long long tot,p,x;
                for(tot=n-m+1,p=(k-1)%(n-m+1);
                        tot+(x=(tot-p)/(k-1)+((tot-p)%(k-1)!=0))<=n;
                        (p+=k*x)%=(tot+=x));
                p+=(n-tot)*k;
                Ans=++p;
            }
        }
        fout<<Ans<<'\n';
    }
    return 0;
}

[ICPC 2018 Shenyang Onsite E][Gym101955E]The Kouga Ninja Scrolls

Link

Solution

曼哈顿转切比雪夫之后x,y独立了。
问题变成从区间中选取两个颜色不同的数字使得差值最大。
维护区间最大次大、最小次小值,满足最大次大、最小次小值分别是不同的颜色,最大差值一定来源于这四个数字。枚举合法情况判一判就好了。

Code

const int XN=1e5+11;
const long long INF=1e18;

struct SegTree {

    struct Data {
        std::pair<long long,int> mn[2],mx[2];

        Data() {
            mn[0]=mn[1]=std::pair<long long,int>(INF,-1);
            mx[0]=mx[1]=std::pair<long long,int>(-INF,-1);
        }

        long long Solve() {
            long long res=0;
            for(int i=0;i<2;++i)
                for(int j=0;j<2;++j)
                    if(mn[i].second!=mx[j].second)
                        Enlarge(res,mx[j].first-mn[i].first);
            return res;
        }

        friend Data Merge(Data const &a,Data const &b) {
            Data res;
            auto Update=[&](Data const &x) {
                for(int i=0;i<2;++i) {
                    if(x.mn[i].first<res.mn[0].first) {
                        if(x.mn[i].second!=res.mn[0].second)
                            res.mn[1]=res.mn[0];
                        res.mn[0]=x.mn[i];
                    } else if(x.mn[i].first<res.mn[1].first && x.mn[i].second!=res.mn[0].second)
                        res.mn[1]=x.mn[i];

                    if(x.mx[i].first>res.mx[0].first) {
                        if(x.mx[i].second!=res.mx[0].second)
                            res.mx[1]=res.mx[0];
                        res.mx[0]=x.mx[i];
                    } else if(x.mx[i].first>res.mx[1].first && x.mx[i].second!=res.mx[0].second)
                        res.mx[1]=x.mx[i];

                }
            };
            Update(a);Update(b);
            return res;
        }
    };

    struct Node {
        Node *son[2];
        Data v;
        Node(std::pair<long long,int> const &x) {
            v.mn[0]=v.mx[0]=x;
        }

        void *operator new(size_t flag) {
            static Node *pool=(Node*)malloc(XN*10*sizeof(Node)),*mem=0;
            return flag?mem++:mem=pool;
        }

        void Up() {
            v=Merge(son[0]->v,son[1]->v);
        }
    }*root;

    int L,R;

    SegTree(std::pair<long long,int> a[],int n):L(1),R(n) {
        std::function<void(Node*&,int,int)> Build=
            [&](Node *&pos,int L,int R) {
                pos=new Node(a[L]);
                if(L==R)
                    return;
                else {
                    int M=(L+R)/2;
                    Build(pos->son[0],L,M);
                    Build(pos->son[1],M+1,R);
                    pos->Up();
                }

            };
        Build(root,1,n);
    }

    long long Query(int l,int r) {
        std::function<Data(Node*,int,int)> Query=
            [&](Node *pos,int L,int R) {
                if(l<=L && R<=r)
                    return pos->v;
                else {
                    int M=(L+R)/2;
                    Data res;
                    if(l<=M)
                        res=Merge(res,Query(pos->son[0],L,M));
                    if(M+1<=r)
                        res=Merge(res,Query(pos->son[1],M+1,R));
                    return res;
                }
            };
        return Query(root,L,R).Solve();
    }

    template <class T>
    void Modify(int goal,T F) {
        std::function<void(Node*,int,int)> Modify=
            [&](Node *pos,int L,int R) {
                if(L==R) {
                    F(pos->v.mn[0]);
                    F(pos->v.mx[0]);
                } else {
                    int M=(L+R)/2;
                    goal<=M?Modify(pos->son[0],L,M):Modify(pos->son[1],M+1,R);
                    pos->Up();
                }
            };
        Modify(root,L,R);
    }
};

void Work() {
    SegTree::Node::operator new(0);

    auto Convert=[](int x,int y)->std::pair<int,int> { return std::pair<int,int>(x+y,x-y); };

    int n,m;fin>>n>>m;
    static std::pair<long long,int> cx[XN],cy[XN];
    for(int i=1;i<=n;++i) {
        int x,y,c;fin>>x>>y>>c;
        std::tie(cx[i].first,cy[i].first)=Convert(x,y);
        cx[i].second=cy[i].second=c;
    }

    SegTree segX(cx,n),segY(cy,n);

    for(int q=1;q<=m;++q) {
        int op;fin>>op;
        switch(op) {
            case 1 : {
                int id,x,y;fin>>id>>x>>y;
                std::tie(x,y)=Convert(x,y);
                segX.Modify(id,[&](std::pair<long long,int> &a) { a.first+=x; });
                segY.Modify(id,[&](std::pair<long long,int> &a) { a.first+=y; });
            } break;
            case 2 : {
                int id,c;fin>>id>>c;
                auto Change=[&](std::pair<long long,int> &a) { a.second=c; };
                segX.Modify(id,Change);
                segY.Modify(id,Change);
            } break;
            case 3 : {
                int l,r;fin>>l>>r;
                fout<<std::max(segX.Query(l,r),segY.Query(l,r))<<'\n';
            } break;
        }
    }
}

int main() {
    int T;fin>>T;

    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d:\n",ks);
        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;
}