[ICPC 2018 Beijing Onsite F]The Kth Largest Value

Link

Solution

询问组数极少。。一开始居然没看到。。。。
首先,用bitset维护出每个点能到的点的集合。对于每组询问,二分答案。
二分答案的时候,需要快速地查询bitset里面某段区间1的个数。
对于一个bitset,直接做区间和是O(\frac n{32})的。但是,可以对1的个数做一个前缀和,类似分块一样。这样,单次询问的复杂度就是O(1)了。

Code

const int XN=5e4+11;

std::vector<int> G[XN],C[XN];int n;

const int SIZE=(XN>>6)+1;
struct BitSet {
    unsigned long long b[SIZE];
    int sum[SIZE];

    void Reset() {
        memset(b,0,sizeof(b));
    }

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

    void GetSum() {
        for(int i=0;i<SIZE;++i)
            sum[i]=(i==0?0:sum[i-1])+__builtin_popcountll(b[i]); 
    }

    int Sum(int l,int r) {
        return Sum(r)-Sum(l-1);
    }

    int Sum(int pos) {
        Reduce(pos,n);
        return pos<1?0:((pos>>6?sum[(pos>>6)-1]:0)+__builtin_popcountll(b[pos>>6]&(((__int128)1<<((pos&63)+1))-1)));
    }

    BitSet &operator |=(BitSet const &other) {
        for(int i=0;i<SIZE;++i)
            b[i]|=other.b[i];
        return *this;
    }

    bool Test(unsigned int pos) const {
        return b[pos>>6]>>(pos&63)&1;
    }
}set[XN];

int low[XN],dfn[XN],stack[XN],dfc,cc,belong[XN],size[XN],top;
bool instack[XN];
void DFS(int pos) {
    dfn[pos]=low[pos]=++dfc;
    instack[stack[++top]=pos]=1;
    for(auto u : G[pos])
        if(!dfn[u]) {
            DFS(u);
            Reduce(low[pos],low[u]);
        } else if(instack[u])
            Reduce(low[pos],dfn[u]);
    if(dfn[pos]==low[pos])
        for(size[++cc]=0,set[cc].Reset();stack[top+1]!=pos;top--) {
            int u=stack[top];
            instack[u]=0;
            belong[u]=cc;
            size[cc]++;
            set[cc].Set(u,1);
        }
}

int Sum(int x,int allb) {
    int res=0;
    for(int i=1;i<=n;++i)
        res+=set[belong[i]].Sum((x^i)&(~allb),(x^i)|allb);
    return res;
}

int Query(int k) {
    int res=0;
    for(int b=15;b>=0;--b) {
        int cnt=Sum(res|(1<<b),(1<<b)-1);
        if(k<=cnt)
            res|=1<<b;
        else
            k-=cnt;
    }
    return res;
}

int main() {
    freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int T;std::cin>>T;
    while(T--) {
        int m,q;std::cin>>n>>m>>q;
        dfc=cc=0;
        for(int i=1;i<=n;++i) {
            G[i].clear();
            dfn[i]=0;
        }
        for(int i=1;i<=m;++i) {
            int x,y;std::cin>>x>>y;
            G[x].push_back(y);
        }

        for(int i=1;i<=n;++i)
            if(!dfn[i]) {
                DFS(i);
                assert(top==0);
            }

        static int deg[XN];

        for(int i=1;i<=cc;++i) {
            C[i].clear();
            deg[i]=0;
        }

        for(int i=1;i<=n;++i)
            for(auto u : G[i])
                if(belong[u]!=belong[i])
                    C[belong[i]].push_back(belong[u]);

        for(int i=1;i<=cc;++i) {
            std::sort(C[i].begin(),C[i].end());
            C[i].erase(std::unique(C[i].begin(),C[i].end()),C[i].end());
            for(int u : C[i])
                deg[u]++;
        }

        std::queue<int> Q;

        for(int i=1;i<=cc;++i)
            if(!deg[i])
                Q.push(i);

        while(!Q.empty()) {
            int pos=Q.front();Q.pop();
            for(auto u : C[pos]) {
                set[u]|=set[pos];
                if(--deg[u]==0)
                    Q.push(u);
            }
        }

        for(int i=1;i<=cc;++i)
            set[i].GetSum();

        while(q--) {
            int k;std::cin>>k;
            std::cout<<Query(k)<<'\n';
        }
    }
    return 0;
}

[ICPC 2018 Beijing Onsite J]Rikka with Triangles

Link

Solution

以每个点为原点,将剩下的点排极角序,然后按顺序枚举剩下的点,记录它上方的,以这两点连线为一边的锐角和钝角直角分别的x,y坐标和。就可以用叉积公式算面积了。
这样做,锐角三角形会被3个锐角计入三次,其他三角形会锐角计入2次,那么当作为非锐角被计入时,就减去两倍的面积。
最后剩下的是所有锐角三角形面积和的三倍,/3输出即可。

Code

const int P=998244353;

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

const int XN=2e3+11,inv3=Pow(3,P-2);

struct Point {
    long long x,y;

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

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

    friend __int128 Outer(Point const &a,Point const &b) {
        return (__int128)a.x*b.y-(__int128)a.y*b.x;
    }
}p[XN],g[XN*2];

void Work() {
    int n;std::cin>>n;
    for(int i=0;i<n;++i)
        std::cin>>p[i].x>>p[i].y;
    long long Ans=0;
    for(int c=0;c<n;++c) {
        for(int i=0;i<n;++i)
            g[i]=p[i]-p[c];
        std::swap(g[c],g[0]);
        std::sort(g+1,g+n,[](Point const &a,Point const &b)->bool {
                    auto Quad=[](Point const &a)->int {
                        return a.x>0 && a.y>=0?1:(a.x<=0 && a.y>0?2:(a.x<0 && a.y<=0?3:4));
                    };
                    int qa=Quad(a),qb=Quad(b);
                    return qa==qb?Outer(b,a)<0:qa<qb;
                });
        static long long xs[XN*2],ys[XN*2];
        for(int i=1;i<n;++i)
            g[n+i-1]=g[i];
        for(int i=1;i<2*n-1;++i) {
            xs[i]=(xs[i-1]+g[i].x)%P;
            ys[i]=(ys[i-1]+g[i].y)%P;
        }
        for(int i=1,le=1;i<n;++i) {
            auto FindLast=[&](int L,int R,std::function<bool(Point)> Judge)->int {//Last Satisfies Judge(g[i])
                    while(L!=R) {
                        int M=(L+R+1)/2;
                        if(Judge(g[M]))
                            L=M;
                        else
                            R=M-1;
                    }
                    return L;
                };
            Enlarge(le,i);
            while(Outer(g[i],g[le])==0)
                ++le;
            Point neg={-g[i].x,-g[i].y};
            if(Outer(g[le],neg)>0) {
                int oppo=FindLast(le,i+n-1,[&](Point const &p)-> bool { return Outer(p,neg)>0; });
                Point axis={-g[i].y,g[i].x};
                int mid=Outer(g[le],axis)>0?FindLast(le,oppo,[&](Point const &p)->bool { return Outer(p,axis)>0; }):le-1;
                (Ans+=g[i].x%P*(3*ys[mid]-2*ys[oppo]-ys[le-1])%P-g[i].y%P*(3*xs[mid]-2*xs[oppo]-xs[le-1])%P)%=P;
            }
        }
    }
    Ans<0 && (Ans+=P);
    (Ans*=inv3)%=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;
}

[ICPC 2018 Jiaozuo Onsite B]Ultraman vs. Aodzilla and Bodzilla

Link

Solution

很不错的想法啊……
首先,一个结论是,1…n这些数字,取出一些,能凑出1…\frac {n(n+1)}{2}之间的所有的和。
S(x)是最小的满足\frac {n(n+1)}{2}\ge xn
那么,同时打掉两个怪物所需的最少时间是S(HP_A+HP_B),因为S(HP_A+HP_B)个轮次中可以凑出HP_A或者HP_B,这样其他的轮次用于打另一个怪,在这个时间内肯定可以打完。
枚举先打哪个怪物,所需的时间同样可以计算。设先打x后打y,那么最终的伤害就是S(HP_x)ATK_x+S(HP_A+HP_B)ATK_{y}。枚举一下先打A还是先打B,显然最小的伤害值一定在这两个中间产生,因为伤害值的表达式中的每一个系数都达到了最小值。
现在就考虑如何构造字典序最小的打法。
如果先打A,只有B不够打才需要修改。那么就从后往前找到第一个合法的位置把这一轮次的打A变成打B。这肯定是所有改法中字典序最小的,因为如果不改这个,就需要在前面改两个。同时,由一开始的那个结论,这样位置肯定是存在的。
如果先打B,那么为了让字典序最小,需要把一些尽量靠前的位置从B改成A。那就从前往后枚举,只要改了之后B还够打就改。最后唯一的可能是A还是不够打。那就把最后一个A的位置改回B,然后直接把A还缺的打击值的那一轮改成A。注意,A还缺的那一轮的打击值一定\le n_1,也就是一定是属于B的轮次。因为,即使是初始状态未做任何调整的前提下,A的打击值+n_1就一定> HP_A了。

Code

int Search(int x) {
    int L=1,R=x;
    while(L!=R) {
        long long M=(L+R)/2;
        if(M*(M+1)/2>=x)
            R=M;
        else
            L=M+1;
    }
    return L;
}

std::pair<long long,std::string> Case1(int ha,int hb,int aa,int ab) {
    long long n1=Search(ha),n=Search(ha+hb);
    long long hita=n1*(n1+1)/2,hitb=n*(n+1)/2-hita;
    long long harm=aa*n1+ab*n;
    std::string s;
    for(int i=1;i<=n1;++i)
        s+='A';
    for(int i=n1+1;i<=n;++i)
        s+='B';
    if(hitb<hb) {
        for(int i=n1;i>=1;--i) {
            if(hita-i>=ha && hitb+i>=hb) {
                s[i-1]='B';
                hita-=i;
                hitb+=i;
                break;
            }
        }
    }
    if(!(hita>=ha && hitb>=hb)) throw;
    return {harm,s};
}

std::pair<long long,std::string> Case2(int ha,int hb,int aa,int ab) {
    long long n1=Search(hb),n=Search(ha+hb);
    long long hitb=n1*(n1+1)/2,hita=n*(n+1)/2-hitb;
    long long harm=ab*n1+aa*n;
    std::string s;
    for(int i=1;i<=n1;++i)
        s+='B';
    for(int i=n1+1;i<=n;++i)
        s+='A';
    int last=0;
    for(int i=1;i<=n1;++i)
        if(hitb-i>=hb) {
            hitb-=i;
            hita+=i;
            s[i-1]='A';
            last=i;
        }
    if(hita<ha) {
        s[last-1]='B';
        s[last+ha-hita-1]='A';
        hitb-=ha-hita;
        hita=ha;
    }
    if(!(hita>=ha && hitb>=hb)) for(;;);
    return {harm,s};
}

void Work() {
    int ha,hb,aa,ab;std::cin>>ha>>hb>>aa>>ab;
    auto Ans=std::min(Case1(ha,hb,aa,ab),Case2(ha,hb,aa,ab));
    std::cout<<Ans.first<<' '<<Ans.second<<'\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;
}

[Codeforces 1137C]Museums Tour

Link

这WA的有点难受2333333333333333333333333
一张边权为1的图,从点1处出发,如果走到某个点p经过的路径长度\bmod d的值属于一个特定的集合S_p,那么p点就能对答案做出1的贡献。点可以重复经过,但只能做一次贡献。问所有点的贡献最大和是多少。

Solution

首先把强连通分量缩起来。考虑强连通分量内的点的答案如何计算。
从分量内任意一个点出发BFS,可以得到一个能到达的(p,l\bmod d)二元组集合。为了简单,可以假设到达连通分量内的出发点已经走过的距离,那么对于d种距离,可以得到d个集合。而这d个集合中,(p,l\mod d)二元组的相对关系是不变的,因此一次BFS就可以得到d个集合的元素。
对于这d个集合,求一下每个集合各自有多少个点能产生贡献,然后在后面的DP中,每个集合的所有的点的DP值就是集合中产生贡献的点+集合中二元组的原来DP值的最大值。
求出(p,l\bmod d)的DP值之后,用它去更新后继SCC中的点。最后,在所有二元组的DP值中取max。
注意!由于必须从1开始,所有的合法值都只能从(1,0)二元组来!其他的所有初始值都必须是不合法的极小值!

Code

const int XN=1e5+11;

std::vector<int> G[XN],C[XN],scc[XN],lc[XN];

int low[XN],dfn[XN],stack[XN],dft,cc,belong[XN],top;
bool instack[XN];
void DFS(int u){
    dfn[u]=low[u]=++dft;
    stack[++top]=u;instack[u]=1;
    for(auto v : G[u])
        if(!dfn[v]){
            DFS(v);
            low[u]=std::min(low[u],low[v]);
        }else if(instack[v]){
            low[u]=std::min(low[u],dfn[v]);
        }
    if(dfn[u]==low[u])
        for(++cc;;){
            int x=stack[top--];
            instack[x]=0;
            scc[cc].push_back(x);
            belong[x]=cc;
            if(x==u) break;
        }
}

int d;
std::string status[XN];
auto Level=[&](int cur,int t)->int {
    return ((t-cur)%d+d)%d;
};


std::vector<int> T[XN];
void BFS(int c) {
    static bool ud[XN][55];
    std::queue<std::pair<int,int>> Q;
    Q.push({scc[c].front(),0});
    ud[Q.front().first][0]=1;
    while(!Q.empty()) {
        int pos,t;std::tie(pos,t)=Q.front();
        Q.pop();
        for(auto u : G[pos])
            if(belong[u]==c && !ud[u][(t+1)%d]) {
                ud[u][(t+1)%d]=1;
                Q.push({u,(t+1)%d});
            }
    }
    for(auto u : scc[c]) {
        for(int t=0;t<d;++t)
            if(ud[u][t])
                T[u].push_back(t);
    }
    lc[c].resize(d);
    for(int t=0;t<d;++t) {
        lc[c][t]=0;
        for(auto u : scc[c])
            for(int ut=0;ut<d;++ut)
                if(ud[u][ut] && status[u][(t+ut)%d]=='1') {
                    lc[c][t]++;
                    break;
                }
    }
}

int main() {
    freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n,m;std::cin>>n>>m>>d;
    for(int i=1;i<=m;++i) {
        int x,y;std::cin>>x>>y;
        G[x].push_back(y);
    }
    for(int i=1;i<=n;++i) {
        std::cin>>status[i];
    }
    for(int i=1;i<=n;++i)
        if(!dfn[i])
            DFS(i);
    for(int i=1;i<=n;++i)
        for(auto u : G[i])
            if(belong[u]!=belong[i])
                C[belong[i]].push_back(belong[u]);
    static int f[XN][55],deg[XN];
    for(int i=1;i<=cc;++i) {
        BFS(i);
        std::sort(C[i].begin(),C[i].end());
        C[i].erase(std::unique(C[i].begin(),C[i].end()),C[i].end());
        for(int u : C[i])
            deg[u]++;
    }
    for(int i=1;i<=n;++i)
        for(int t=0;t<d;++t)
            f[i][t]=-1e9;
    f[1][0]=0;
    std::queue<int> Q;
    for(int i=1;i<=cc;++i)
        if(!deg[i])
            Q.push(i);
    while(!Q.empty()) {
        int pos=Q.front();Q.pop();
        std::vector<int> lf(d,-1e9);//写成0最后没过!
        for(auto u : scc[pos])
            for(int t=0;t<d;++t)
                for(auto ut : T[u])
                    Enlarge(lf[Level(ut,t)],f[u][t]+lc[pos][Level(ut,t)]);
        for(auto u : scc[pos])
            for(int t=0;t<d;++t)
                for(auto ut : T[u])
                    Enlarge(f[u][t],lf[Level(ut,t)]);
        for(auto u : scc[pos])
            for(int t=0;t<d;++t)
                for(auto v : G[u]) {
                    if(belong[v]==belong[u])
                        assert(!Enlarge(f[v][(t+1)%d],f[u][t]));
                    Enlarge(f[v][(t+1)%d],f[u][t]);
                }
        for(auto u : C[pos])
            if(--deg[u]==0)
                Q.push(u);
    }
    for(int i=1;i<=cc;++i)
        assert(deg[i]==0);

    int Ans=0;
    for(int i=1;i<=n;++i)
        for(int t=0;t<d;++t)
            Enlarge(Ans,f[i][t]);
    std::cout<<Ans<<'\n';
    return 0;
}

[ICPC 2018 Nanjing Onsite E]Eva and Euro coins

Link

Solution

核心思想就是将连续的k1和连续的k0消掉。。消到最后是否相同。。
训练的时候PY想法是对的,但没想好怎么写,于是我写的十分野蛮,不出意料地TLE了。。。

Code

const int XN=1e6+11;

int n,k;
std::string Do(std::string s) {
    if(k==1)
        return "";
    else {
        static std::pair<char,int> stack[XN];
        int top=0;
        stack[++top]={s[0],1};
        for(int i=1;i<n;++i)
            if(stack[top].first==s[i]) {
                if(++stack[top].second==k)
                    top--;
            } else
                stack[++top]={s[i],1};
        s="";
        for(int i=1;i<=top;++i)
            while(stack[i].second--)
                s+=stack[i].first;
        return s;
    }
}

int main() {
    //freopen("input","r",stdin);
    std::string s,t;
    std::cin>>n>>k>>s>>t;
    std::cout<<(Do(s)==Do(t)?"Yes":"No")<<'\n';
    return 0;
}

大力代码

const int XN=1e6+11;

int n,k;

void Move(std::list<int> &a) {
    while(*a.begin()>k)
        *a.begin()-=k;  
    auto pred=a.begin(),it=pred;
    ++it;
    for(;it!=a.end();pred=it,++it)
        while(*it-*pred>k)
            *it-=k;
}

bool Flip(std::list<int> &a) {
    if(a.empty())
        return 0;
    int len=1;
    auto pred=a.rbegin(),it=pred;
    ++it;
    bool tak=0;
    std::vector<int> del;
    for(;it!=a.rend();pred=it,++it)
        if(*pred-*it==1) {
            if(++len==k) {
                auto x=it;
                for(int t=k;t--;) {
                    del.push_back(*x--);
                }
                std::reverse(&del.back()-k+1,&del.back()+1);
            }
        } else
            len=1;
    std::reverse(del.begin(),del.end());
    if(del.size()==0)
        return 0;
    int i=0;
    for(auto it=a.begin();it!=a.end();)
        if(*it==del[i]) {
            ++i;
            a.erase(it++);
        } else
            ++it;
    return 1;
}

std::list<int> Do(char *a) {
    std::list<int> id;
    for(int i=1;i<=n;++i)
        if(a[i]=='1')
            id.push_back(i);
    if(id.size()) {
        do {
            Move(id);
        } while(Flip(id));
    }
    return id;
}

int main() {
    //freopen("input","r",stdin);
    static char s[XN],t[XN];
    std::cin>>n>>k;
    std::cin>>(s+1)>>(t+1);
    if(k==1)
        std::cout<<"Yes"<<'\n';
    else {
        auto s1=Do(s),t1=Do(t);
        bool tak=s1==t1;//s1.size()==t1.size();
        std::cout<<(tak?"Yes":"No")<<'\n';
    }   
    return 0;
}

[ICPC 2018 Nanjing Onsite B]Tournament

Link

Solution

首先需要知道,用一个stadium覆盖n个位置,肯定建在中间的那个上。
普通的DP,f[i][j]表示前i个放了j个stadium,将前i个都覆盖了的最小代价,然后f[i][j]=\min (f[k][j-1]+cost(k+1,i))。这个cost就是用一个stadium覆盖[k+1,i]的最小代价。虽然这样没有保证被不同的stadium覆盖的地点一定是被离它最近的那个覆盖,但是考虑到最小的答案一定是那样的情况,所以这样DP正确性没有问题。
接着就wqs二分+决策单调性。。会了就是模板了。。
各种决策单调性还要好好学一学……

Code

const int XN=3e5+11;

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    static int a[XN];
    static long long sum[XN];
    int n,m;std::cin>>n>>m;
    for(int i=1;i<=n;++i) {
        std::cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }

    auto DP=[&](long long C)->std::pair<long long,int> {
        static std::pair<long long,int> f[XN];
        auto Cost=[&](int l,int r) {//建站覆盖[l,r]
            int mid=(l+r)/2;
            return sum[r]-2*sum[mid-1]+sum[l-1]+(long long)a[mid]*(2*mid-l-r-1);
        };

        auto Calc=[&](int j,int i)->std::pair<long long,int> {
            return std::make_pair(f[j].first+Cost(j+1,i)+C,f[j].second+1);
        };

        auto Boundary=[&](int k1,int k2)->int {//k2 better than k1 if p>=x
            int L=k2+1,R=n+1;
            while(L!=R) {
                int M=(L+R)/2;
                if(M!=n+1 && Calc(k1,M)<=Calc(k2,M))
                    L=M+1;
                else
                    R=M;
            }
            return L;
        };

        static std::pair<int,int> Q[XN];
        static int head,tail;
        Q[(tail=head=0)++]={0,0};
        for(int i=1;i<=n;++i) {
            while(tail-head>=2 && Calc(Q[head].first,i)>=Calc(Q[head+1].first,i))
                head++;
            f[i]=Calc(Q[head].first,i);
            while(tail-head>=2 && (Q[tail-1].second==n+1 || Calc(Q[tail-1].first,Q[tail-1].second)>=Calc(i,Q[tail-1].second)))
                tail--;
            Q[tail]={i,Boundary(Q[tail-1].first,i)};
            tail++;
        }
        return f[n];
    };

    long long L=0,R=sum[n];
    while(L!=R) {
        long long M=(L+R)/2;
        if(DP(M).second<=m)
            R=M;
        else
            L=M+1;
    }

    long long Ans=DP(L).first-L*m;
    std::cout<<Ans<<'\n';
    return 0;
}

王钦石の二分

Train2012-sol-wqs
奇怪,这么多年居然从没听说过这个东西!
求将n个元素的数组分成k段的最优化分类的问题。
比如,n个元素的数组划分为k段,最小化平方和,那就二分一个常数C,求最小化\sum s_i^2+C需要分成几段。显然,随着C的增大,最优的段数是单调不下降的,就可以找到分为k段的C,然后答案-kC就是最终的答案。

斜率优化

某次比赛中需要斜率优化发现写得极不顺畅。。。总结一个模板化的东西以后照抄。
SDOI2016 征途为例,题目要求的就是将n个数字的数组分成至多m段,使得每一段的和的平方的总和最小。

f[p][i]表示将前i个数字分成p段的和的最小值,转移显然。
斜率优化:对于一个点i,决策点k_1优于决策点k_2(k_1 < k_2 < i)

\begin{aligned}
f[p-1][k_1]+(s[i]-s[k_1])^2 & < f[p-1][k_2]+(s[i]-s[k_2])^2\\
\frac {(f[p-1][k_1]+s^2[k_1])-(f[p-1][k_2]+s^2[k_2])}{s[k_1]-s[k_2]} & > 2s[i]
\end{aligned}

也就是,当上面的不等式中间为\le时,k_1就可以被扔掉,扔掉之后,队首两个元素的斜率应该上升,直到 > 2s[i]
因此按照这个式子,由于s[i]是不下降的,所以维护决策点连线斜率单增的队列,也就是决策点构成的下凸壳,然后维护下凸壳可以用计算几何的方法。。。
如果某个a[i]=0,那么s[i]=s[i-1],也就是ii-1决策点的横坐标相同,那么i点的纵坐标必定\le i-1点的纵坐标。如果纵坐标相等,要注意去掉这个重复点,否则,放在维护下凸壳的算法里,这种情形也能正确处理。

const int XN=3000+11;

int main() {
    freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    static int a[XN],f[XN][XN],sum[XN];
    int n,m;std::cin>>n>>m;
    for(int i=1;i<=n;++i) {
        std::cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        f[1][i]=sum[i]*sum[i];
    }
    for(int p=2;p<=m;++p) {
        static int Q[XN],head,tail;

        Q[head=0]=p-1;tail=1;
        for(int i=p;i<=n;++i) {
            auto Calc=[&](int t)->int {
                return f[p-1][t]+(sum[i]-sum[t])*(sum[i]-sum[t]);
            };

            auto TurnRight=[&](std::array<int,3> id)->bool {
                std::array<long long,3> x,y;
                for(int i=0;i<3;++i) {
                    x[i]=sum[id[i]];
                    y[i]=f[p-1][id[i]]+sum[id[i]]*sum[id[i]];
                }
                return (x[1]-x[0])*(y[2]-y[1])-(x[2]-x[1])*(y[1]-y[0])<=0;
            };

            while(tail-head>=2 && Calc(Q[head])>=Calc(Q[head+1]))
                head++; 

            f[p][i]=Calc(Q[head]);

            while(tail-head>=2 && TurnRight({Q[tail-2],Q[tail-1],i}))
                tail--;
            Q[tail++]=i;
        }
    }
    int Ans=f[m][n]*m-sum[n]*sum[n];
    std::cout<<Ans<<'\n';
    return 0;
}

[Codeforces 1131E]String Multiplication

Link

s\cdot t=t+s_1+t+s_2+…+s_n+t
\prod s_i中最长的连续的相同字符组成的字符串的长度。

Solution

L(s,c)sc字符的最长连续长度,则要求的结果就是\max L(\prod s_i,c),c\in[‘a’,’z’]
实时维护L(\prod s_i,c)。当读入一个t字符串时,分如下情况讨论:
1. t中的字符全部相同,设为x

L(\prod s_i\cdot t,c)=
\begin{cases}
(L(\prod s_i,c)+1)({\rm len}(t)+1)-1,&c=x\\
1,&c\not=x,c\in \prod s_i\\
0,&\text{otherwise}
\end{cases}
  1. t的字符不全部相同
    t的最长相同前缀的长度为p,最长相同后缀为s
    再分情况

    1. {\rm first}(t)={\rm last}(t)=x
      对于c\not=x
    L(\prod s_i\cdot t,c)=
    \begin{cases}
    1,&c\in\prod s_i\\
    0,&\text{otherwise}
    \end{cases}

    对于x

    L(\prod s_i\cdot t,x)=
    \begin{cases}
    p+s+1,&x\in\prod s_i\\
    \max(p,s),&\text{otherwise}
    \end{cases}
    1. {\rm first}(t)\not={\rm last}(t)
      与上相似。

Code

const int XN=1e5+11;
typedef std::array<long long,26> Record;

int main() {
    freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n;std::cin>>n;
    std::string s;std::cin>>s;
    auto Do=[&](std::string s)->std::tuple<long long,long long,Record> {
        s+=' ';
        long long pref=-1,suf=-1;
        Record mxl;
        for(int i=0;i<26;++i)
            mxl[i]=0;
        for(size_t i=1,len=1;i<s.length();++i)
            if(s[i]==s[i-1])
                len++;
            else {
                if(pref==-1)
                    pref=len;
                if(i==s.length()-1)
                    suf=len;
                Enlarge(mxl[s[i-1]-'a'],(long long)len);
                len=1;
            }
        if(pref==s.length()-1)
            suf=0;
        return {pref,suf,mxl};
    };
    Record smxl;long long pre,suf;
    static bool has[26];
    for(size_t i=0;i<s.length();++i)
        has[s[i]-'a']=1;
    std::tie(pre,suf,smxl)=Do(s);
    for(int i=2;i<=n;++i) {
        std::string t;std::cin>>t;
        Record tmxl;
        std::tie(pre,suf,tmxl)=Do(t);
        if(!suf) {
            long long temp=(smxl[t[0]-'a']+1)*(t.length()+1)-1;
            for(int c=0;c<26;++c)
                smxl[c]=(bool)smxl[c];
            Enlarge(smxl[t[0]-'a'],temp);
        } else {
            for(int c=0;c<26;++c)
                smxl[c]=(bool)smxl[c];
            if(t[0]==t[t.length()-1]) {
                long long temp=std::max(pre,suf);
                if(has[t[0]-'a']) {
                    temp=pre+suf+1;
                }
                smxl[t[0]-'a']=temp;
            } else {
                if(has[t[0]-'a']) {
                    smxl[t[0]-'a']=pre+1;
                }
                if(has[t[t.length()-1]-'a']) {
                    smxl[t[t.length()-1]-'a']=suf+1;
                }
            }
        }
        for(size_t i=0;i<t.length();++i)
            has[t[i]-'a']=1;
        for(int c=0;c<26;++c)
            Reduce(smxl[c],(long long)1e9);
        for(int c=0;c<26;++c)
            Enlarge(smxl[c],tmxl[c]);
    }
    std::cout<<*std::max_element(smxl.begin(),smxl.end())<<'\n';
    return 0;
}

Tips

题意理解反了浪费了半个小时。。
题目给了答案\le 10^9,就直接暴力取min就好了。