[ICPC Northern Eurasia Finals 2018 K]King Kog’s Reception

Link

多年不碰数据结构的老年选手,估计是做麻烦了。

Solution

对所有来的时刻开线段树,记录每个区间来的骑士的开始时间和结束时间,再记录一下这段时间内有多少时间是空白的,那么这些空白时间可以在开始时间延后时起到“缓冲作用”。
合并也好合并,就是一开始写错了没看出来。

Code

#include <bits/stdc++.h>

const int XN=3e5+11;

struct SegTree {
    struct Info {
        long long l,r,blank;
        Info():l(0),r(-1) {}

        operator bool() const {
            return l<=r;
        }

        friend Info Merge(Info const &a,Info const &b) {
            if(!a) return b;
            else if(!b) return a;
            else {
                Info res=a;
                long long rblank=b.blank+std::max(b.l-a.r-1,0ll);
                res.r=b.r+std::max(a.r-b.l+1-rblank,0ll);
                res.blank+=std::max(rblank-std::max(a.r-b.l+1,0ll),0ll);//
                return res;
            }
        }
    };
    struct Node {
        Node *son[2];
        Info v;
        Node() {
            son[0]=son[1]=0;
        }
    }*root;
    int L,R;

    SegTree(int L,int R):root(0),L(L),R(R) {}

    void Modify(int t,int d) {
        std::function<void(Node*&,int,int)> Modify=[&](Node *&pos,int L,int R) {
            if(!pos)
                pos=new Node;
            if(L==R) {
                pos->v.r=(pos->v.l=t)+d-1;
                pos->v.blank=0;
            } else {
                int M=(L+R)/2;
                t<=M?Modify(pos->son[0],L,M)
                    :Modify(pos->son[1],M+1,R);
                pos->v=Merge(pos->son[0]?pos->son[0]->v:Info()
                            ,pos->son[1]?pos->son[1]->v:Info());
            }
        };
        Modify(root,L,R);
    }

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

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    SegTree seg(1,1e6);
    int q;std::cin>>q;
    static int vt[XN];
    for(int ks=1;ks<=q;++ks) {
        char op[10];
        std::cin>>op;
        if(op[0]=='+') {
            int t,d;std::cin>>t>>d;
            vt[ks]=t;
            seg.Modify(t,d);
        } else if(op[0]=='-') {
            int id;std::cin>>id;
            seg.Modify(vt[id],0);
        } else {
            int t;std::cin>>t;
            std::cout<<std::max(0ll,seg.Query(t).r+1-t)<<'\n';
        }
    }
    return 0;
}

[Codeforces 908D]New Year and Arbitrary Arrangement

Link

Solution

首先,前导b对于ab子序列的个数不会产生影响,为了简化,强制第一个位置是a。
一个比较好用的想法是,任意一个合法解都以b为结尾,可以在最后一个b前面添加任意个a。
从第二个位置开始填,f[i][j]表示填了i个a,有j个ab子序列的概率。
i + j < n时,转移显然。
否则,就直接将在f[i][j]后面加任意个a和一个b产生的贡献累加到答案里,不再进行转移。因为如果将这部分f[i][j]加上一个a继续转移到f[i+1][j]中,就会与f[i][j]后面加任意个a和一个b重复。
f[i][j]后面加任意个a和一个b产生的贡献如下:

\begin{aligned}
&f[i][j]p_b\sum_{k=0}^{\infty}(i+j+k)p_a^k\\
=&f[i][j]p_b[\frac {i+j}{1-p_a}+\frac {p_a}{(1-p_a)^2}]
\end{aligned}

求出最后的答案还要乘上\sum_{i=0}^{\infty}p_b^i=\frac 1{1-p_b},因为在序列前方加上任意个b对概率是有影响的,因而对期望也有影响。

Code

#include <bits/stdc++.h>

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

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

void AddBy(int &x,int const &y) {
    x=Add(x,y);
}

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) {
    static long long res;
    for(res=1;v;v>>=1,(base*=base)%=P)
        if(v&1)
            (res*=base)%=P;
    return res;
}

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

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n,a,b;std::cin>>n>>a>>b;
    int pa=Mul(a,Inverse(a+b)),pb=Mul(b,Inverse(a+b));
    static int f[XN][XN];
    f[1][0]=pa;
    int c1=Inverse(Minus(1,pa)),c2=Mul(pa,Mul(c1,c1));
    int Ans=0;
    for(int i=1;i<=n;++i)
        for(int j=0;j<=n;++j) {
            if(i+j<n) {
                AddBy(f[i+1][j],Mul(pa,f[i][j]));
                AddBy(f[i][i+j],Mul(pb,f[i][j]));
            } else
                AddBy(Ans,Mul(Mul(pb,f[i][j]),((long long)(i+j)*c1+c2)%P));
        }
    Ans=Mul(Ans,Inverse(Minus(1,pb)));
    std::cout<<Ans<<'\n';
    return 0;
}

ICPC EC-Final 2018 I Misunderstood … Missing

Link

Solution

小数据爆搜,大数据三个贪心取max
DP的话,需要让2、3操作的贡献能够提前计算。
而2的贡献与后面攻击的下标和有关,3的贡献和后面攻击的次数有关,这样就有了状态。

Code

const int XN=1e2+11;

void Work() {
    static int a[XN],b[XN],c[XN];
    static long long f[2][XN][XN*XN];
    int n;fin>>n;
    for(int i=1;i<=n;++i)
        fin>>a[i]>>b[i]>>c[i];
    memset(f,0,sizeof(f));
    int cur=0;
    for(int i=1,sum=n*(n+1)/2-1;i<=n;sum-=++i,cur^=1)
        for(int j=0;j<=n-i;++j)
            for(int k=0;k<=sum;++k)
                f[cur][j][k]=Max(f[cur^1][j][k]+Max((long long)b[i]*(k-i*j),(long long)c[i]*j),f[cur^1][j+1][k+i]+a[i]);
    fout<<f[cur^1][0][0]<<'\n';
}

int main() {
    int T;fin>>T;
    while(T--)
        Work();
    return 0;
}