2018.03.08 HAOI 模拟赛

套题

目录

• 2018.03.08 HAOI 模拟赛
  • 福斯特
    • 思路
    • 代码
  • 赛肯德
    • 思路
    • 代码
  • 鏼尔德
    • 思路
    • 代码

福斯特

思路

• 看到第$k$小莫名就想到主席树了，可是因为没想到怎么用差分优化式子，就没推出来。。。
• 考虑到直接算价值的话，三种覆盖情况需要三段考虑，我们部分差分，即令$b_i'=b_i-a_i,c_i'=c_i-b_i$，下面的$b_i,c_i$均是这里的$b'_i,c'_i$；
• 这样任何情况，价值均有$\sum_{i=1}^n a_i$的贡献，对于覆盖的我们再加上相应的增量即可；
• 考虑第$k$小这种如果不好直接构造的话可以用二分答案，我们不妨这样；
• 现在考虑对于一个给定的价值怎么计算排名；
• 显然有两种情况要考虑，两段表演不重叠和重叠，显然至少要枚举一段的位置，不妨枚举第二段的左端点。设二分的答案为$mid$，第一段左端点为$j$，第二段左端点为$i$，形如$suf_x(i)$的为$x_i$的后缀和（由于上面说总有$\sum_{i=1}^n a_i$的贡献，所以式子里的$suf_a(1)$就指代这个）：
  
  1. 不重叠，那么只需考虑$b$的贡献，所以此时价值和小于$mid$的$j$有：
     $$\begin{eqnarray*} && suf_b(j)-suf_b(j+r)+suf_b(i)-suf_b(i+r)\leq mid-suf_a(1) \\ && 含i的至于当前枚举的i有关，移到右边，我们只统计满足式子的j的个数： \\ && suf_b(j)-suf_b(j+r)\leq mid-suf_a(1)-suf_b(i)+suf_b(i+r) \end{eqnarray*}$$
  2. 重叠的同理：$suf_b(j)-suf_c(j+r)\leq mid-suf_a(1)+suf_b(i+r)-suf_c(i)$
• 上面的部分很容易用权值线段树来解决，但是上面两个情况还有$i,j$间的限制，比如不重叠就需要$i \in (r,n-r+1],j \in [1,i)$，改成主席树就可以实现了；
• 总复杂度就是$O(n \log^2{maxval})$，注意插入的权值可能为负，要加$offset$。

代码

#include <cstdio>
#include <algorithm>
using std::max;
const int MAXN=30005;
const long long OFFSET=1e12;
int n,k,r;
long long sufa[MAXN],sufb[MAXN],sufc[MAXN];
class CMT{
    private:
        int cnt;
        int rt[MAXN];
        struct node{int ls,rs,cnt;}d[MAXN*45];
        int copy_nd(int u){
            d[++cnt]=d[u];
            return cnt;
        }
        void ist(int pre,int &now,long long l,long long r,long long val){
            now=copy_nd(pre);
            ++d[now].cnt;
            if(l==r) return;
            long long mid=(l+r)/2;
            if(val<=mid) ist(d[pre].ls,d[now].ls,l,mid,val);
            else ist(d[pre].rs,d[now].rs,mid+1,r,val);
        }
        int lt_cnt(int pre,int now,long long l,long long r,long long val){
            if(r<val) return d[now].cnt-d[pre].cnt;
            long long mid=(l+r)/2;
            int ret=lt_cnt(d[pre].ls,d[now].ls,l,mid,val);
            if(val>mid+1) ret+=lt_cnt(d[pre].rs,d[now].rs,mid+1,r,val);
            return ret;
        }
    public:
        void ist(int pre,int now,long long val){ist(rt[pre],rt[now],0,OFFSET<<1,val+OFFSET);}
        int lt_cnt(int pre,int now,long long val){return lt_cnt(rt[pre],rt[now],0,OFFSET<<1,val+OFFSET);}
}T1,T2;
inline void prepare(){
    for(int i=1;i<=n;++i){
        sufc[i]-=sufb[i];
        sufb[i]-=sufa[i];
    }
    for(int i=n-1;i;--i){
        sufa[i]+=sufa[i+1];
        sufb[i]+=sufb[i+1];
        sufc[i]+=sufc[i+1];
    }
    for(int i=1,lim=n-r+1;i<=lim;++i){
        T1.ist(i-1,i,sufb[i]-sufb[i+r]);
        T2.ist(i-1,i,sufb[i]-sufc[i+r]);
    }
}
//不重叠
inline int cal1(long long mid){
    int ret=0;
    mid-=sufa[1];
    for(int i=r+1,lim=n-r+1;i<=lim;++i)
        ret+=T1.lt_cnt(0,i-r,mid-sufb[i]+sufb[i+r]);
    return ret;
}
//重叠
inline int cal2(long long mid){
    int ret=0;
    mid-=sufa[1];
    for(int i=2,lim=n-r+1;i<=lim;++i)
        ret+=T2.lt_cnt(max(0,i-r),i-1,mid+sufb[i+r]-sufc[i]);
    return ret;
}
inline int rank(long long mid){
    return cal1(mid)+cal2(mid);
}
inline long long bin_chop(long long l,long long r){
    long long mid;
    while(l<=r){
        mid=l+r>>1;
        if(rank(mid)<k) l=mid+1;
        else r=mid-1;
    }
    return r;
}
int main(){
    freopen("fst.in","r",stdin);
    freopen("fst.out","w",stdout);
    scanf("%d%d%d",&n,&r,&k);
    long long minans=0;
    for(int i=1;i<=n;++i){
        scanf("%d",&sufa[i]);
        minans+=sufa[i];
    }
    for(int i=1;i<=n;++i)
        scanf("%d",&sufb[i]);
    long long maxans=0;
    for(int i=1;i<=n;++i){
        scanf("%d",&sufc[i]);
        maxans+=sufc[i];
    }
    prepare();
    printf("%lld",bin_chop(minans,maxans));
    return 0;
}

赛肯德

思路

• 这是一道相当妙的题，不过要是不知道这个性质的话我觉得很难想出来；
• 注意到，对于路径上不足$k$条边的，我们其实可以认为每个点都有边权为$0$的自环，不足的边就是在自环上绕圈，这样就不需要考虑路径上边数不足的情况了；
• 我们考虑枚举$k$条边中最小的权值$\Delta$，并将其余边的权值赋为$\max(0,w-\Delta)$，那么这时的答案就是跑最短路后$dis(n)+k \times\Delta$；
• 但是这其中有不合法的情况，不过可以发现这时的答案一定不会更优：
  
  1. 当前枚举的$\Delta'$小于真正的$\Delta$，那么对于那$k$条应该计算代价的边（权值第$1$~$k$大），代价不会少计算，对于权值第$k+1$到第$\text{rank}(\Delta')$大的边被多计入代价了；
  2. 当前枚举的$\Delta'$大于真正的$\Delta$，那么对于权值第$1$到第$\text{rank}(\Delta')$大的边，代价不会少计算，对于权值第$\text{rank}(\Delta')+1$到第$k$大的边多计算了$\Delta'-w_i$的代价；
• 综上，这样求出来的就是答案，复杂度就是$O(mn \log{n})$，注意要枚举边权为$0$的情况，因为上面的做法是基于路径上至少有$k$条边的，而最开始说这个$0$可以看做绕边权为$0$的自环。

代码

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
#include <cstring>
#include <climits>
using std::sort;
using std::min;
using std::max;
using std::priority_queue;
using std::vector;
using std::greater;
const int MAXN=3005,MAXM=3005;
int n,m,k;
int he[MAXN],w[MAXM];
struct line{int to,nex,w;}ed[MAXM<<1];
struct node{
    int id;
    long long dis;
    node(int _id=0,long long _dis=0):id(_id),dis(_dis){}
    bool operator >(const node &that)const{
        return dis>that.dis;
    }
};
inline void addE(int u,int v,int w){
    static int cnt;
    ed[++cnt]=(line){v,he[u],w};
    he[u]=cnt;
}
inline long long Dijkstra(int dta){
    static long long dis[MAXN];
    static bool use[MAXN];
    static priority_queue<node,vector<node>,greater<node> > hp;
    memset(dis,0x7f,sizeof(dis));
    memset(use,false,sizeof(use));
    dis[1]=0;
    hp.push(node(1,0));
    int u;
    long long d;
    while(hp.size()){
        u=hp.top().id;
        hp.pop();
        if(use[u]) continue;
        use[u]=true;
        for(int i=he[u],v;i;i=ed[i].nex){
            v=ed[i].to,d=dis[u]+max(0,ed[i].w-dta);
            if(dis[v]>d){
                dis[v]=d;
                hp.push(node(v,d));
            }
        }
    }
    return dis[n];
}
inline long long solve(){
    long long ret=LLONG_MAX;
    for(int i=0;i<=m;++i)
        ret=min(ret,Dijkstra(w[i])+(long long)k*w[i]);
    return ret;
}
int main(){
    freopen("skd.in","r",stdin);
    freopen("skd.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1,u,v;i<=m;++i){
        scanf("%d%d%d",&u,&v,&w[i]);
        addE(u,v,w[i]),addE(v,u,w[i]);
    }
    printf("%lld",solve());
    return 0;
}

鏼尔德

思路

• 这题目前还没改出来，先记一下思路；
• 考试时写出了$n \leq 44$时的meet in the middle做法，不过捆绑测试把这部分和极限数据捆在一组，分一下就捆没了。。。
• 这部分就是考虑暴力枚举所有情况，但是将枚举的序列$c_0c_1 \cdots c_n$拆成两半：$c_1c_2 \cdots c_{\lfloor\frac{n}{2}\rfloor}$和$c_{\lceil\frac{n}{2}\rceil}c_{\lceil\frac{n}{2}\rceil+1}\cdots c_n$；
• 设两部分的$\sum c_ib_i \bmod{q}$为$l,r$，最终的密码为$x$，显然有：
  $$l+r \equiv x \pmod{q} \Rightarrow l \equiv x-r \pmod{q}$$
• 那么我们枚举$l$，在已经暴力枚举的所有情况的$r$中找对应的，找到了就说明这是答案；
• 这样复杂度是$O(2^{\frac{n}{2}}n)$。不过这题不保证解唯一，小火车也没写spj，他求的貌似是字典序最小解，我的不是，现在也没看我WA的那几个是不是合法解，有空再说吧；
• 对于$n>44$的时候，我们注意到$a_i$的限制，那么有$a_n \geq 2^{n-1}a_1$。又由于这是模意义下的，所以$a_1 \leq 2^{65-n}$；
• 那么我们可以暴力枚举$a_1$，这样就可以根据$a_1r \equiv b_1 \pmod{q}$来求出$r$，那么就可以求出$\sum_{i=1}^n c_ia_i \equiv r^{-1} \times\sum_{i=1}^n c_ib_i \pmod{q}$；
• 注意到，$a_i$的限制还可以让我们知道$\sum_{i=1}^n c_ia_i$后，可以贪心的判断出是选了哪些$a_i$。因为从大到小选，如果当前可以选这个$a_i$而不选，根据那个限制$a_i > \sum_{j=1}^{i-1}a_j$，后面怎么选也不可能出来合法解了；
• 但是这里直接枚举$a_1$再求会被卡，因为后面会说还要枚举$r$的一部分。我们可以用一个优化，就是由于$r$与$q$互质，$r$的二进制最低位必为$1$，那么我们可以根据$b_1$二进制下后导$0$的个数判断$a_1$二进制下后导$0$的个数（设其为$k$），这样只需要枚举高位就可以了，且第$k+1$位一定是$1$，不然$k$就不符合要求了；
• 而$r$不能直接求出来，因为$a_1$不一定与$q$互质，我们可以先通过$a_1$二进制下除去后导$0$的值求出$r$二进制下低位的值，因为这相当于是求模$2^{64-k}$意义下的$b_1 \times \left(\frac{a_1}{2^k}\right)^{-1}$；
• 那么高位的仍然枚举，只有$2^k$种；
• 这样就可以求出$r$了，最后按上面说的贪心验证就可以了，这部分复杂度是$O(2^{65-n}n)$，和第一部分的复杂度其实几乎是一样的；
• 不过求$r$的逆元时非常烦人，$q=2^{64}$，exgcd加一下就溢出了，std的做法是一个奇怪的迭代来求，我的做法是用欧拉定理：$a^{-1}\equiv a^{\varphi(m)-1}\pmod{m}$，快速幂中间不会溢出。

代码

先不放了，改完再说。