2018.03.07 HAOI 模拟赛

套题

puts("gg");

目录

• 2018.03.07 HAOI 模拟赛
  • diyiti
    • 思路
    • 代码
  • dierti
    • 思路
    • 代码：
  • disanti
    • 思路

diyiti

思路

• 首先考虑当$\frac{a}{b}=\frac{1}{2}$时的情况，这时等价于询问$n$个点的强连通竞赛图的个数，套路就是枚举第一个强连通分量的大小；
• 考虑到太久不做这种题，考场上居然忘了怎么写，这里再详细说一下；
• 将竞赛图缩点后肯定是一个（因为任意两点间有连边）DAG，我们可以用补集转化的思想，只要让DAG上有至少两个强连通分量，就是不合法的情况了；
• 设$f(i)$表示$i$个点的强连通竞赛图个数。而不合法的情况可以这样做：枚举第一个强连通分量大小和由哪些点组成，剩下的部分就是一个任意的竞赛图，所以有：
  $$f(i)=2^{\frac{i(i-1)}{2}}-\sum_{j=1}^{i-1}\text{C}_{i}^j \times f(j)\times 2^{\frac{(i-j)(i-j-1)}{2}}$$
• 现在考虑一般情况，由于这样，边指向两个方向的概率不再相同，我们不妨预处理出来这个概率；
• 注意到现在的问题其实可以分为三部分：第一个强连通分量内部连边的概率$f(i)$，第一个强连通分量向剩余部分连边的概率，剩余部分内部连边的概率$g(i)$；
• 其中第二部分其实就是要求两个部分之间的连边只能由第一个强连通分量指向剩余部分；
• 设$p(i,j)$是前$i$个点，第一个强连通分量大小为$j$的第二部的分概率之和，那么转移也很简单，考虑新加入的一个点放在哪部分，因为新加入的点标号最大，所以很好考虑：
  $$p(i,j)=p(i-1,j)\times(1-\frac{a}{b})^j+p(i-1,j-1)\times\left(\frac{a}{b}\right)^{i-j}$$
• 而第三部分其实恒为$1$，如果把这一部分忽略向外的连边，看做一个整体，就很好理解了；
• 第一部分依然像上面的特殊情况那样递推：
  $$f(i)=1-\sum_{j=1}^{i-1}f(j) \times p(i,j)$$

代码

#include <cstdio>
const int MAXN=2005,P=998244353;
int n,psb;
int p[MAXN][MAXN];
inline int pow(int x,int y){
    int ret=1;
    for(;y;x=(long long)x*x%P,y>>=1){
        if(y&1) ret=(long long)ret*x%P;
    }
    return ret;
}
inline int inv(int x){return pow(x,P-2);}
inline void cal_p(){
    p[0][0]=1;
    for(int i=1;i<=n;++i){
        for(int j=0;j<i;++j){
            p[i][j]=(p[i][j]+(long long)p[i-1][j]*pow((1-psb+P)%P,j)%P)%P;
            p[i][j+1]=(p[i][j+1]+(long long)p[i-1][j]*pow(psb,i-(j+1))%P)%P;
        }
    }
}
inline int cal_f(){
    static int f[MAXN];
    f[1]=1;
    for(int i=2,tmp;i<=n;++i){
        tmp=0;
        for(int j=1;j<i;++j)
            tmp=(tmp+(long long)f[j]*p[i][j]%P)%P;
        f[i]=(1-tmp+P)%P;
    }
    return f[n];
}
int main(){
    freopen("diyiti.in","r",stdin);
    freopen("diyiti.out","w",stdout);
    int a,b;
    scanf("%d%d%d",&n,&a,&b);
    psb=(long long)a*inv(b)%P;
    cal_p();
    printf("%d",cal_f());
    return 0;
}

dierti

思路

• 这真是个神仙题。。。
• 先将传送序列按照正常的标号大小排序（即就考虑在$1,2,3,\cdots$这个序列上跳动的情况，而不是将问题变为一个排列，$p_i$和$p_{i+1}$之间满足大小关系的限制），那么考虑一下每一个路径是怎么走的；
• 设终点为$i$，那么一定是从$i$两边某一侧开始，经过若干次跨越$i$，最后又回到$i$；
• 我们将每一个连续在$i$一侧的部分叫做一条链，那么按照上面的分析，在$i$左侧的链的结尾必定是'>'，不然没法从小的传送到大的，同理，右侧的链的结尾必定是'<'；
• 设$l/r(i,j)$表示标号前或后$i$个点组成$j$条链的方案数；
• 以$l$为例，对于新加入的一个点$i$，有以下情况：
  
  1. 它可以加到一个链中：如果是'>'就加到尾部，否则加到头部，考虑到$i$是目前标号最大的点，这样肯定合法。+=$l(i-1,j)$；
  2. 如果是'<'，还可以合并两条链：一个链的尾部指向它，它指向一个链的头部，并且两个链的先后顺序显然有区别。+=$\text{A}_{j+1}^2 \times l(i-1,j+1)$；
  3. 如果是'>'，那么可以自己单独成一条新链。+=$l(i-1,j-1)$；
• 现在考虑怎么统计答案，按照最开始的分析，我们只需要枚举在$i$左右两侧的链数并乘上对应的排列数就可以了，但是这样是$O(n^3)$的；
• 仔细考虑就可以发现，既然是从一侧开始，交替跳到两侧，最后再跳到$i$，两侧的链数最多差$1$：
  
  1. $[(j+1)! \times l(i-1,j+1)]\times[j! \times r(i+1,j)]$。从左侧开始，最后跳回左侧，再跳到$i$；
  2. $[j! \times l(i-1,j)]\times[(j+1)! \times r(i+1,j+1)]$。同理；
  3. $2 \times [j! \times l(i-1,j)]\times[j! \times r(i+1,j)]$。从两侧开始都可以，最后跳到另一侧并跳到$i$；
• 所以，最后的复杂度就是$O(n^2)$了。

代码：

#include <cstdio>
#include <cstring>
const int MAXN=5005,P=1e9+7;
int n;
int fac[MAXN],l[MAXN][MAXN],r[MAXN][MAXN];
int ans[MAXN];
char s[MAXN];
inline void cal_l(){
    l[0][0]=1;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=i;++j)
            l[i][j]=(long long)l[i-1][j]*j%P;
        if(s[i]=='<'){
            for(int j=1;j<=i;++j)
                l[i][j]=(l[i][j]+(long long)l[i-1][j+1]*(j+1)%P*j%P)%P;
        }
        else{
            for(int j=1;j<=i;++j)
                l[i][j]=(l[i][j]+l[i-1][j-1])%P;
        }
    }
}
inline void cal_r(){
    r[n+1][0]=1;
    for(int i=n,lim;i;--i){
        lim=n-i+1;
        for(int j=1;j<=lim;++j)
            r[i][j]=(long long)r[i+1][j]*j%P;
        if(s[i]=='>'){
            for(int j=1;j<=lim;++j)
                r[i][j]=(r[i][j]+(long long)r[i+1][j+1]*(j+1)%P*j%P)%P;
        }
        else{
            for(int j=1;j<=lim;++j)
                r[i][j]=(r[i][j]+r[i+1][j-1])%P;
        }
    }
}
inline void pre_fac(){
    fac[0]=1;
    for(int i=1;i<=n;++i)
        fac[i]=(long long)fac[i-1]*i%P;
}
inline void DP(){
    for(int i=1;i<=n;++i){
        for(int j=0;j<=n;++j){
            ans[i]=(ans[i]+(long long)l[i-1][j+1]*fac[j+1]%P*r[i+1][j]%P*fac[j]%P)%P;
            ans[i]=(ans[i]+(long long)l[i-1][j]*fac[j]%P*r[i+1][j+1]%P*fac[j+1]%P)%P;
            ans[i]=(ans[i]+((long long)l[i-1][j]*fac[j]%P*r[i+1][j]%P*fac[j]%P<<1)%P)%P;
        }
    }
}
int main(){
    freopen("dierti.in","r",stdin);
    freopen("dierti.out","w",stdout);
    scanf("%s",s+1);
    n=strlen(s+1);
    if(n==1){
        putchar('1');
        return 0;
    }
    cal_l();
    cal_r();
    pre_fac();
    DP();
    for(int i=1;i<=n;++i)
        printf("%d ",ans[i]);
    return 0;
}

disanti

思路

• 考场上居然一直在考虑怎么优化建图，明明式子都化出来了。。。
• 看到平方，拆一下式子，并且发现可以DP那样转移，就该想到斜率优化了；
• 设航班$i$的起点终点、出发到达的时间为$u_i,v_i,s_i,t_i$，坐完前$i$个航班（按$s$升序排序）后的最小代价为$dp(i)$，那么：
  $$\begin{eqnarray*} dp(i) &=& \min_{\substack{j=1 \\ v_j=u_i \\ t_j<s_i}}^{i-1}\{(s_i-t_j)^2+dp(j)\} \\ &=& \min_{\substack{j=1 \\ v_j=u_i \\ t_j<s_i}}^{i-1}\{-t_j \times s_i+t_j^2+dp(j)\}+s_i^2 \end{eqnarray*}$$
• 所以，按时间序，对每个城市维护一个已经到达的航班的决策的下凸壳，每次查询即可；
• 由于按时间序，所以不妨将起飞和降落拆成两个事件，由于坐飞机没有代价，我们每次起飞时计算DP值，降落时将这个决策加入相应的下凸壳，保证了时间顺序的合法性，如果降落到$n$号城市就更新答案；
• 这样比某些做法少了在凸壳上二分，然而还是要先排序，复杂度仍是$O(m \log{m})$。。。
• 注意，应先将$1$号城市的凸壳上加入$0$的决策，其它都没有决策，这样保证只能从$1$号城市坐飞机到别的城市进而再到$n$。

代码：

#include <cstdio>
#include <algorithm>
#include <vector>
#include <climits>
#include <cstring>
using std::sort;
using std::vector;
using std::min;
const int MAXN=200005,MAXM=200005;
const long long INF=1LL<<60;
int n,m,ocnt;
long long dp[MAXM];
struct data{int u,v,s,t;}flight[MAXM];
struct option{
    int now,tm,id;
    bool type;
    static bool cmp_tm(const option &a,const option &b){
        return a.tm<b.tm || (a.tm==b.tm && a.type<b.type);
    }
}opt[MAXM<<1];
inline long long sqr(long long x){return x*x;}
inline int slope(int i){return -(flight[i].t<<1);}
inline long long y_itsct(int i){return sqr(flight[i].t)+dp[i];}
inline long long cal(int i,int j){
    return (long long)slope(j)*flight[i].s+y_itsct(j);
}
inline double itcpt(int i,int j){
    return (double)(y_itsct(j)-y_itsct(i))/(slope(i)-slope(j));
}
inline long long DP(){
    static int head[MAXN],tail[MAXN];
    static vector<int> dq[MAXN];
    sort(opt+1,opt+ocnt+1,option::cmp_tm);
    memset(tail,-1,sizeof(tail));
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    ++tail[1],dq[1].push_back(0);
    long long ret=LLONG_MAX;
    for(int i=1;i<=ocnt;++i){
        if(opt[i].type==0){
            if(head[opt[i].now]>tail[opt[i].now]) continue;
            while(head[opt[i].now]<tail[opt[i].now] && cal(opt[i].id,dq[opt[i].now][head[opt[i].now]])>=cal(opt[i].id,dq[opt[i].now][head[opt[i].now]+1]))
                ++head[opt[i].now];
            dp[opt[i].id]=cal(opt[i].id,dq[opt[i].now][head[opt[i].now]])+sqr(flight[opt[i].id].s);
        }
        else{
            while(head[opt[i].now]<tail[opt[i].now] && itcpt(opt[i].id,dq[opt[i].now][tail[opt[i].now]-1])<=itcpt(dq[opt[i].now][tail[opt[i].now]],dq[opt[i].now][tail[opt[i].now]-1]))
                --tail[opt[i].now],dq[opt[i].now].pop_back();
            ++tail[opt[i].now],dq[opt[i].now].push_back(opt[i].id);
            if(opt[i].now==n) ret=min(ret,dp[opt[i].id]);
        }
    }
    return ret;
}
int main(){
    freopen("disanti.in","r",stdin);
    freopen("disanti.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1,u,v,s,t;i<=m;++i){
        scanf("%d%d%d%d",&u,&v,&s,&t);
        flight[i]=(data){u,v,s,t};
        opt[++ocnt]=(option){u,s,i,0};
        opt[++ocnt]=(option){v,t,i,1};
    }
    printf("%lld",DP());
    return 0;
}