HGOI 20190822 OCWA提高组模拟赛二

矫情吗；* 2023-06-05 11:26 12阅读 0赞

**Problem A 快递**

> 根节点为$1$ ， 含有$n$个节点的树，每一条边都有一段开放的时间$\[s\_i,e\_i\]$，和经过需要的时间。
> 
> 有$q$组询问，每一次在时刻$t\_i$出发从根节点出发走到第$u$个节点，沿着最短路走，询问是否可行。
> 
> 注意到，当在边开放的时间走到这条边上均被认为合法，走出边的时间不会因此而限制。
> 
> 对于$100\\%$的数据，满足$1 \\leq n,q \\leq 5\\times 10^5$

Solution :

考虑能否到达$u$的条件，就是能否在$u$上方的那条边$(fa,u)$的规定时间内到达该点的父亲$fa$。

我们注意到从根节点出发的时间为$time$，那么到达一个节点$u$的总时间就是这个点父亲前缀边的长度之和$pre$。

转化一下，能否到达这个点上方的那一条边的条件就是$time\_u + pre \\in \[s\_\{Edge\} , t\_\{Edge\}\]$

解出来就是$time\_u \\in \[s\_\{Edge\}-pre,t\_\{Edge\}-pre\]$

所以到达一个点既有当前点的限制，又有该点到根之间点的限制，所以我们只需要将这个点到根的所有点限制的区间交起来就可以了。

这样子，我们直接做一遍$dfs$即可，复杂度就是$O(n+q)$

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

# pragma GCC optimize(3)
    # include <bits/stdc++.h>
    # define inf (1e12)
    # define int long long
    # define Rint register int
    # define YES putchar('Y'),putchar('E'),putchar('S')
    # define NO putchar('N'),putchar('O')
    using namespace std;
    const int N = 5e5+10;
    struct A { int pre,to,w,s,t; }a[N<<1];
    struct B { int l,r; }tim[N];
    int tot,n,m;
    int head[N],d[N],f[N];
    inline int read()
    {
        int X=0,w=0; char c=0;
        while(c<'0'||c>'9') {w|=c=='-';c=getchar();}
        while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();
        return w?-X:X;
    }
    void adde(Rint u,Rint v,int w,int s,int t)
    {
        a[++tot].pre=head[u];
        a[tot].to=v; a[tot].w=w;
        a[tot].s=s; a[tot].t=t;
        head[u]=tot;
    }
    void dfs(Rint u,Rint fa)
    {
        for (Rint i=head[u];i;i=a[i].pre) {
            int v=a[i].to; if (v==fa) continue;
            tim[v].l=max(tim[u].l,a[i].s-d[u]);
            tim[v].r=min(tim[u].r,a[i].t-d[u]);
            d[v]=d[u]+a[i].w;
            dfs(v,u);
        }
    }
    signed main()
    {
        n=read();m=read();
        for (Rint i=2;i<=n;i++) {
            int u=read()+1,v=read()+1,w=read(),s=read(),t=read();
            adde(u,v,w,s,t); adde(v,u,w,s,t);
        }
        tim[1].l=-inf; tim[1].r=inf;
        dfs(1,0);
        while (m--) {
            int u=read()+1,t=read();
            (t>=tim[u].l && t<=tim[u].r)?(YES):(NO);
            putchar('\n');
        }
        return 0;
    }

A.cpp

**Problem B 工资**

> 给出一个$1$为根节点，含有$n$个节点的树,每个点初始有一个权值$v\_i$。
> 
> 维护两种操作，"u A x" 表示将编号为$A$的子树除了节点$A$的所有节点权值加$x$,"p A"表示求编号为$A$节点的权值。
> 
> 对于$100\\%$的数据满足$1 \\leq n,q \\leq 5\\times 10^5$

Solution :

由于子树的$dfs$序是连续的，所以本题直接按照dfs序建立树状数组即可。

维护区间加，单点求和。

复杂度是$O((q+n) log\_2 n)$

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

# pragma GCC optimize(3)
    # include <bits/stdc++.h>
    # define int long long
    # define Rint int
    using namespace std;
    const int N=5e5+10;
    struct rec{
        int pre,to;
    }a[N<<1];
    int c[N],head[N],dfn[N],R[N],val[N];
    int tot,n,m;
    # define lowbit(x) (x&(-x))
    void update(int x,int y){
         for (;x<=n;x+=lowbit(x)) c[x]+=y;}
    int query(int x) { int ret=0; for (;x;x-=lowbit(x)) ret+=c[x];return ret;}
    int modify(int l,int r,int d) {update(l,d); update(r+1,-d);}
    #undef lowbit
    inline int read()
    {
        int X=0,w=0; char c=0;
        while(c<'0'||c>'9') {w|=c=='-';c=getchar();}
        while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();
        return w?-X:X;
    }
    void write(int x)
    {
        if (x<0) x=-x,putchar('-');
        if (x>9) write(x/10);
        putchar('0'+x%10);
    }
    inline void writeln(int x) {
        write(x); putchar('\n');
    }
    inline void adde(Rint u,Rint v)
    {
        a[++tot].pre=head[u];
        a[tot].to=v;
        head[u]=tot;
    }
    void dfs(Rint u,Rint fa)
    {
        dfn[u]=++dfn[0]; R[u]=dfn[u];
        for (Rint i=head[u];i;i=a[i].pre) {
            int v=a[i].to; if (v==fa) continue;
            dfs(v,u);
        }
        R[u]=dfn[0];
    }
    signed main()
    {
        n=read(); m=read(); val[1]=read();
        for (Rint i=2;i<=n;i++) {
            int f; val[i]=read(); f=read();
            adde(i,f); adde(f,i);
        }
        for (int i=1;i<=n;i++) if (!dfn[i]) dfs(i,0);
        for (Rint i=1;i<=n;i++) modify(dfn[i],dfn[i],val[i]);
        while (m--) {
            char c=0; while (c!='p' && c!='u') c=getchar();
            if (c=='u') {
                int x=read(); 
                writeln(query(dfn[x]));
            }else {
                int x=read(),y=read();
                if (dfn[x]+1<=R[x]) modify(dfn[x]+1,R[x],y);
            }
        }
        return 0;
    }

B.cpp

**Problem C** **坤坤数**

> 坤坤数的定义是：对于一个数，不含前导零，给定$k$,存在$wk ,w \\geq 1$作为后缀的数。
> 
> 现在，我们给出$n$,$k$和$m$，求出$n$位坤坤数的数的个数$mod \\ m$的值。
> 
> 对于$100\\%$的数据满足$n \\leq 1000 ,1 \\leq k \\leq 100 , 1 \\leq m \\leq 10^9$

Solution :

考虑$f\[i\]\[j\]\[0/1\]\[0/1\]$表示当前考虑到第$i$位，当前数$mod \\ k$为$j$，是否含有前导零，是否之前的后缀已经是$wk$了(即是否已经构成)

设从第$0$位开始添加数，那么最后的答案就是$\\sum\\limits\_\{i = 0\}^\{k-1\} f\[n-1\]\[i\]\[0\]\[1\]$ 。

考虑刷表法转移，

*  $f\[i\]\[j\]\[0\]\[0\] -> f\[i+1\]\[j\]\[1\]\[0\] , f\[i+1\]\[(w\\times 10^\{i+1\}+j)\\% k\]\[0\]\[0\]((w\\times 10^\{i+1\}+j)\\% k \\neq 0) , f\[i+1\]\[0\]\[0\]\[1\]$　　
 *  $f\[i\]\[j\]\[0\]\[1\] -> f\[i+1\]\[j\]\[1\]\[1\] , f\[i+1\]\[(w\\times 10^\{i+1\}+j)\\% k\]\[0\]\[1\]$
 *  $f\[i\]\[j\]\[1\]\[0\] -> f\[i+1\]\[j\]\[1\]\[0\] , f\[i+1\]\[(w\\times 10^\{i+1\}+j)\\% k\]\[0\]\[0\]((w\\times 10^\{i+1\}+j)\\% k \\neq 0) , f\[i+1\]\[0\]\[0\]\[1\]$
 *  $f\[i\]\[j\]\[1\]\[1\] -> f\[i+1\]\[j\]\[1\]\[1\] , f\[i+1\]\[(w\\times 10^\{i+1\}+j)\\% k\]\[0\]\[1\]$

我们可以预处理出幂次取模，那么最后的复杂度就是$O(10 \\times n \\times k)$

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#pragma GCC optimize(3)
    # include <bits/stdc++.h>
    # define int long long
    using namespace std;
    int n,k,m;
    int f[1005][105][2][2];
    int Pow(int x,int n,int mo)
    {
        int ans=1;
        while (n) {
            if (n&1) ans=ans*x%mo;
            x=x*x%mo;
            n>>=1;
        }
        return ans%mo;
    }
    signed main()
    {
        scanf("%lld%lld%lld",&n,&k,&m);
        (f[0][0][1][0]+=1)%=m; 
        for (int i=1;i<=9;i++) {
            bool ok = 0;
            for (int w=1;w<=10;w++) {
                 if (w*k>9) break;
                 if (w*k==i) { (f[0][i%k][0][1]+=1)%=m; ok = 1; break;}
             }
            if (!ok) (f[0][i%k][0][0]+=1)%=m;
        }
        for (int i=0;i<=n-2;i++)
         for (int j=0;j<=k-1;j++) {
             (f[i+1][j][1][0]+=f[i][j][0][0])%=m;
             for (int w=1;w<=9;w++)
              if ((w*Pow(10,i+1,k)%k+j)%k==0) (f[i+1][0][0][1]+=f[i][j][0][0])%=m;
              else (f[i+1][(w*Pow(10,i+1,k)%k+j)%k][0][0]+=f[i][j][0][0])%=m;
              
             (f[i+1][j][1][1]+=f[i][j][0][1])%=m;
            for (int w=1;w<=9;w++) 
             (f[i+1][(w*Pow(10,i+1,k)%k+j)%k][0][1]+=f[i][j][0][1])%=m;
             
            (f[i+1][j][1][0]+=f[i][j][1][0])%=m;
            for (int w=1;w<=9;w++)
             if ((w*Pow(10,i+1,k)%k+j)%k==0) (f[i+1][0][0][1]+=f[i][j][1][0])%=m;
             else (f[i+1][(w*Pow(10,i+1,k)%k+j)%k][0][0]+=f[i][j][1][0])%=m;
             
            (f[i+1][j][1][1]+=f[i][j][1][1])%=m;
            for (int w=1;w<=9;w++)
             (f[i+1][(w*Pow(10,i+1,k)%k+j)%k][0][1]+=f[i][j][1][1])%=m;
         }
        int ret = 0;
        for (int i=0;i<=k-1;i++) (ret+=f[n-1][i][0][1])%=m;
        printf("%lld\n",ret);  
        return 0;
    }

C.cpp

转载于:https://www.cnblogs.com/ljc20020730/p/11393898.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/a236b2c6ab0a45ed86dcb071a74283e9.png