Eternity

Until The End

夏记，但是被吊打

发表于 更新于 分类于
本文字数： 41k 阅读时长 ≈ 37 分钟

记录一次又一次的被单调队列。

8.19

以四季为题材的四道题，第二个字读音相同，主角是 $\text{yluiQ,EDGNB}$ 。

$\text{_Eternal_:}18pt+22pt=40pts$

春荔

题意

给定一个长度为 $n$ 的区间，每次可以选取一个长度在 $[l,r]$ 大小内的区间将权值减 $1$ ，权值不能为负，求最少次数。

$1\leq n\leq 10^6,r-l+1\geq\lceil\frac n 2\rceil,a_i\leq 10^9$

部分分

考场没想出来，做了一个 $\text{Subtask1:}l=1,r=n$ 的搞法。

直接用线段树维护当前最小权值的编号，并以该点将当前区间划分成 $[l,mid-1]$ 和 $[mid+1,r]$ 两个区间，递归统计答案，并计算当前答案。

实测能过，应该有 $30pts$ ，但测出来只有 $18pt$ 。

正解

因为有一个很阴间（我没看见）的提示：$r-l+1\geq\lceil\frac n 2\rceil$ 。

所以满足至多 $2$ 步即可覆盖整个区间，然后从网络流的思路来考虑，每一次的费用要么是 $1$ 要么是 $2$ ，满足当前结点满流，否则无解。

这是正解，但是复杂度不可过。

然后从这个思路延申，我们可以先固定左端点，然后从当前端点 $l$ 向右延申一条射线。因为题目所求的是最少操作次数，所以我们肯定每一次选择的区间越大越好。

把 $a_i$ 想象成一根宽度为 $a_i$ 的管道，那么有两种情况：

  • $a_i>a_{i-1}$ ，则无法将 $a_i$ 流满，我们只能重新开一条，即以 $i$ 开始的一条射线；
  • $a_i<a_{i-1}$ ，则会滞留，需要将前面的射线在此截断。

然后考虑范围限制，如果当前结点怎么都无法满流的话，直接判无解，然后按照上面两种情况讨论，开一个队列来记录当前射线，以满足先入先出的性质。

时间复杂度 $\mathcal O(n)$ 。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
const int MAXN=1e6+10;
const int INF=0x3f3f3f3f;
int N,L,R;
namespace Sub1
{
    #define ls p<<1
    #define rs p<<1|1
    struct ST
    {
        int l,r,val,id;
    }Tree[MAXN<<2];
    int Val[MAXN];
    inline void pushUp(int p)
    {
        Tree[p].val=std::min(Tree[ls].val,Tree[rs].val);
        if(Tree[p].val==Tree[ls].val) Tree[p].id=Tree[ls].id;
        else Tree[p].id=Tree[rs].id;
    }
    inline int minId(int a,int b)
    {
        if(Val[a]==Val[b]) return a>b?b:a;
        return Val[a]>Val[b]?b:a;
    }
    void build(int p,int l,int r)
    {
        Tree[p].l=l,Tree[p].r=r;
        if(l==r)
        {
            Tree[p].val=Val[l];
            Tree[p].id=l;
            return ;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid),build(rs,mid+1,r);
        pushUp(p);
    }
    int queryId(int p,int l,int r)
    {
        if(l<=Tree[p].l&&Tree[p].r<=r) return Tree[p].id;
        int mid=(Tree[p].l+Tree[p].r)>>1;
        int res1=0,res2=0;
        if(l<=mid) res1=queryId(ls,l,r);
        if(mid<r) res2=queryId(rs,l,r);
        if(!res1) return res2;
        if(!res2) return res1;
        return minId(res1,res2);
    }
    inline ll Conq(int l,int r,ll x)
    {
        if(l>r) return 0;
        if(l==r) return Val[l]-x;
        int mid=queryId(1,l,r);
        return Val[mid]-x+Conq(l,mid-1,Val[mid])+Conq(mid+1,r,Val[mid]);
    }
    inline bool solve()
    {
        Val[0]=INF;
        for(re int i=1;i<=N;++i) read(Val[i]);
        build(1,1,N);
        write(Conq(1,N,0));
        return 0;
    }
    #undef ls
    #undef rs
};
std::pair<int,ll>Que[MAXN];
int Dif[MAXN],Val[MAXN];
int head=1,tail;
ll Ans,Tot;
int main()
{
    // freopen("cut.in","r",stdin);
    // freopen("cut.out","w",stdout);
    read(N,L,R);
    if(L==1&&R==N) return Sub1::solve();
    for(int i=1;i<=N;++i) read(Val[i]);
    bool End=1;
    for(int i=1;i<=N;++i)
    {
        ll delta=abs(Val[i]-Val[i-1]);
        if(!delta) continue;
        if(Val[i]>Val[i-1])
        {
            if(i+L-1>N)
            {
                End=0;
                break;
            }
            Ans+=delta,Que[++tail]={i,delta};
        }
        else
        {
            while(head<=tail&&Que[head].first+R-1<i-1)
                Ans+=Que[head].second,Tot+=Que[head].second,++head;
            while(head<=tail&&delta>0)
            {
                if(Que[head].first+L-1>=i) break;
                ll flow=std::min(delta,Que[head].second);
                delta-=flow,Que[head].second-=flow;
                if(!Que[head].second) ++head;
            }
            if(Tot<delta)
            {
                End=0;
                break;
            }
            Tot-=delta;
        }
    }
    while(head<=tail&&Que[head].first+R-1<N)
        Ans+=Que[head].second,++head;
    if(!End) write(-1);
    write(Ans);
    return 0;
}
/*
5 2 4
1 2 3 4 1
*/

夏鲤

考场唯一可做的题，但是还是挂掉了。

题意

给定一个长度为 $n$ 的序列，和 $m$ 次操作，共有三种操作：

  • $0,l,r,x$ ，把区间 $[l,r]$ 中的数 $a_i$ 变成 $|{a_i-x}|$ ；
  • $1,l,r,x$ ，把区间 $[l,r]$ 中的数 $a_i$ 变成 $a_i+x$ ；
  • $2,l,r$ ，询问 $\displaystyle\sum_{i=l}^{r}a_i,\min_{l\leq i\leq r}a_i$ 。

$n,m\leq 5\times 10^5,0\leq a_i,x\leq 20$ 。

题解

因为前不久做过一道题叫做教主的魔法，虽然那道题根本不能用线段树做，不过 $\text{l18q}$ 还是过掉了，然后我就尝试势能分析一波，可以把第一个操作拆成两个操作：

  • 如果 $\min_i\geq x$ ，则转换为区间减操作；
  • 如果 $\max_i\leq x$ ，则把区间乘上 $-1$ 并区间加。

正确性显然，所以维护三个参数：区间和，区间最大值，区间最小值，第一个操作的时候，只有满足上述两种情况才停止递归，否则直到叶结点暴力修改。

通过势能分析可以知道这个复杂度实际上是正确的，因为每进行一次操作之后，权值区间都会相应缩小，以至于最后变成几个相差不大的数，所以到后来递归次数也就会越来越少。

再加上这道题权值的范围本来就很小，所以就这样可以糊过去了。（虽然考场上 pushdown 写假了）

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
namespace Suball
{
    const int MAXN=5e5+10;
    const int INF=0x3f3f3f3f;
    int Val[MAXN];
    #define ls p<<1
    #define rs p<<1|1
    struct ST
    {
        int l,r,maxn,minn,siz,sum,tag,rev;
    }Tree[MAXN<<2];
    inline void pushUp(int p)
    {
        Tree[p].sum=Tree[ls].sum+Tree[rs].sum;
        Tree[p].maxn=std::max(Tree[ls].maxn,Tree[rs].maxn);
        Tree[p].minn=std::min(Tree[ls].minn,Tree[rs].minn);
    }
    inline void pushAdd(int p,int x)
    {
        Tree[p].sum+=Tree[p].siz*x;
        Tree[p].maxn+=x,Tree[p].minn+=x;
        Tree[p].tag+=x;
    }
    inline void pushReverse(int p)
    {
        Tree[p].rev^=1;
        std::swap(Tree[p].maxn,Tree[p].minn);
        Tree[p].sum*=-1,Tree[p].tag*=-1;
        Tree[p].maxn*=-1,Tree[p].minn*=-1;
    }
    inline void pushDown(int p)
    {
        if(Tree[p].rev)
        {
            pushReverse(ls),pushReverse(rs);
            Tree[p].rev=0;
        }
        if(Tree[p].tag)
        {
            pushAdd(ls,Tree[p].tag),pushAdd(rs,Tree[p].tag);
            Tree[p].tag=0;
        }
    }
    void build(int p,int l,int r)
    {
        Tree[p].l=l,Tree[p].r=r,Tree[p].siz=r-l+1;
        if(l==r)
        {
            Tree[p].sum=Tree[p].maxn=Tree[p].minn=Val[l];
            return ;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid),build(rs,mid+1,r);
        pushUp(p);
    }
    void modifyRev(int p,int l,int r,int x)
    {
        if(l<=Tree[p].l&&Tree[p].r<=r)
        {
            if(Tree[p].maxn<=x)
            {
                pushReverse(p);
                pushAdd(p,x);
                return ;
            }
            if(Tree[p].minn>=x)
            {
                pushAdd(p,-x);
                return ;
            }
        }
        pushDown(p);
        int mid=(Tree[p].l+Tree[p].r)>>1;
        if(l<=mid) modifyRev(ls,l,r,x);
        if(mid<r) modifyRev(rs,l,r,x);
        pushUp(p);
    }
    void modifyAdd(int p,int l,int r,int x)
    {
        if(l<=Tree[p].l&&Tree[p].r<=r)
        {
            pushAdd(p,x);
            return ;
        }
        pushDown(p);
        int mid=(Tree[p].l+Tree[p].r)>>1;
        if(l<=mid) modifyAdd(ls,l,r,x);
        if(mid<r) modifyAdd(rs,l,r,x);
        pushUp(p);
    }
    int querySum(int p,int l,int r)
    {
        if(l<=Tree[p].l&&Tree[p].r<=r) return Tree[p].sum;
        pushDown(p);
        int mid=(Tree[p].l+Tree[p].r)>>1,res=0;
        if(l<=mid) res+=querySum(ls,l,r);
        if(mid<r) res+=querySum(rs,l,r);
        return res;
    }
    int queryMin(int p,int l,int r)
    {
        
        if(l<=Tree[p].l&&Tree[p].r<=r) return Tree[p].minn;
        pushDown(p);
        int mid=(Tree[p].l+Tree[p].r)>>1,res=INF;
        if(l<=mid) res=std::min(res,queryMin(ls,l,r));
        if(mid<r) res=std::min(res,queryMin(rs,l,r));
        return res;
    }
    inline void solve()
    {
        for(int i=1;i<=N;++i) read(Val[i]);
        build(1,1,N);
        for(int opt,l,r,x;Q--;)
        {
            read(opt,l,r);
            if(opt==2) write(querySum(1,l,r),' ',queryMin(1,l,r),'\n');
            else
            {
                read(x);
                if(opt==0) modifyRev(1,l,r,x);
                else modifyAdd(1,l,r,x);
            }
        }
        return ;
    }
    #undef ls
    #undef rs
};

秋丽

题意

判断一张无向图是否存在唯一最大完全匹配，并输出方案。多组数据。

$T\leq 5,n\leq 500$ 。

题解

一般图最大匹配的神仙题，根本不会。

似乎可以用 $\mathcal O(n^3)$ 的带花树拿到 $\text{Subtask4:}$ 保证唯一完美匹配的 $26pt$ ，但我还是不会。

正解的话，似乎是从桥来考虑的，连通性问题一窍不通，直接开摆。

冬礼

题意

给定一个有向图，有 $q$ 个询问，走边 $(i,j)$ 的概率为 $\frac{val_{i,j}}{\sum_{k}val_{i,k}}$ ，求从 $s$ 到 $t$ 的期望边数，模数 $998244353$ 。

$n\leq 500,q\leq n^2$ 。

题解

什么一般图随机游走，什么矩阵，什么高斯消元。

开摆，不可能会做。

8.21

被高年级和低年级和同年级联合吊打。

一套以《弹丸论破》为主题的神仙题。

$\text{_Eternal_:}100pt+5pt=105pts$

相遇

题意

给定一个数列 $n$ ， 两个数 $a,b$ ，每一次可以将 $a$ 变成：

  • $a-1$ ；
  • $i\in[1,n],a-a\bmod x_i$

求把 $a$ 变成 $b$ 的最少次数。

$n\leq 10^5,a,b\leq 10^9,a-b\leq 10^6$ 。

题解

首先看到有 $a-b\leq 10^6$ 来考虑。

定义 $Max_i$ 表示能够一步转移到 $i$ 的最大的数，并用 $f[i]$ 表示从 $a$ 变成 $a-i$ 最少需要的步数。然后转移：

$\displaystyle f[i]=\min(f[i-1],\min_{k-Max_i+1}^{i-1}f[k])+1$

前半段的预处理时间复杂度为 $\mathcal O(m\log n)$ ，然后后半段用线段树维护即可。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=getchar(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<>
inline void write(char c)
{
    putchar(c);
}
template<>
inline void write(char *s)
{
    while(*s) putchar(*s++);
}
template<class T,class ...T1>
inline void write(T x,T1 ...x1)
{
    write(x),write(x1...);
}
template<class T>
inline bool checkMax(T &x,T y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T y)
{
    return x>y?x=y,1:0;
}
using Pir=std::pair<int,int>;
const int MAXN=1e6+10;
const int INF=0x3f3f3f3f;
int N,M,B,A,X[MAXN];
namespace Segment
{
    #define ls p<<1
    #define rs p<<1|1
    struct Seg
    {
        int l,r,val;
    }Tr[MAXN<<2];
    int Max[MAXN],Dp[MAXN];
    inline void pushUp(int p)
    {
        Tr[p].val=std::min(Tr[ls].val,Tr[rs].val);
    }
    void build(int p,int l,int r)
    {
        Tr[p].l=l,Tr[p].r=r;
        if(l==r) return ;
        int mid=(l+r)>>1;
        build(ls,l,mid),build(rs,mid+1,r);
    }
    void modifyX(int p,int x,int k)
    {
        if(Tr[p].l==Tr[p].r)
        {
            Tr[p].val=k;
            return ;
        }
        int mid=(Tr[p].l+Tr[p].r)>>1;
        if(x<=mid) modifyX(ls,x,k);
        else modifyX(rs,x,k);
        pushUp(p);
    }
    int queryMin(int p,int l,int r)
    {
        if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].val;
        int mid=(Tr[p].l+Tr[p].r)>>1,res=INF;
        if(l<=mid) checkMin(res,queryMin(ls,l,r));
        if(mid<r) checkMin(res,queryMin(rs,l,r));
        return res;
    }
    inline void init()
    {
        for(int i=1;i<=N;++i)
        {
            int L=((B-1)/X[i]+1)*X[i];
            for(int j=L;j<=A;j+=X[i])
                checkMax(Max[A-j],X[i]);
        }
    }
    inline int main()
    {
        init();
        build(1,0,A-B);
        for(int i=A-1;i>=B;--i)
        {
            int id=A-i;
            if(Max[id]>1) Dp[id]=std::min(Dp[id-1],queryMin(1,std::max(id-Max[id]+1,0),id-1))+1;
            else Dp[id]=Dp[id-1]+1;
            modifyX(1,id,Dp[id]);
        }
        write(Dp[A-B]);
        return 0;
    }
}
int main()
{
    // freopen("meet.in","r",stdin);
    // freopen("meet.out","w",stdout);
    read(N);
    for(re int i=1;i<=N;++i) read(X[i]);
    read(A,B);
    std::sort(X+1,X+1+N);
    M=std::unique(X+1,X+N+1)-X-1;
    return Segment::main();
}
/*
3
3 4 5
30 17
3
5 6 7
1000 200
*/

然后捏，初三巨佬 $\text{Nich}$ 有一个更加神奇的思路，效率快了线段树接近三倍，写法类似于单调队列。我也不太会，直接就也被单调队列了。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=getchar(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<>
inline void write(char c)
{
    putchar(c);
}
template<>
inline void write(char *s)
{
    while(*s) putchar(*s++);
}
template<class T,class ...T1>
inline void write(T x,T1 ...x1)
{
    write(x),write(x1...);
}
template<class T>
inline bool checkMax(T &x,T y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T y)
{
    return x>y?x=y,1:0;
}
using Pir=std::pair<int,int>;
const int MAXN=1e6+10;
const int INF=0x3f3f3f3f;
int N,M,B,A,X[MAXN],NewSt=INF,head=1,tail,Dp[MAXN];
std::vector<int>Nums[MAXN];
struct Que
{
    int x,y;
    inline bool operator<(const Que &d)const
    {
        return (x>=d.x&&y<d.y)||(x>d.x&&y<=d.y);
    }
}Q[MAXN];
namespace Subtask2
{
    inline bool solve()
    {
        std::queue<Pir>Q;
        Q.push({0,A});
        while(!Q.empty())
        {
            Pir u=Q.front();Q.pop();
            if(u.second<B) continue;
            if(u.second==B)
            {
                write(u.first);
                return 0;
            }
            for(int i=1;i<=N;++i)
                if(u.second%X[i]!=0)
                    Q.push({u.first+1,u.second-(u.second%X[i])});
            Q.push({u.first+1,u.second-1});
        }
        return 0;
    }
};
inline void init()
{
    for(int i=1;i<=M;++i)
        for(int j=(B-1)/X[i]+1;X[i]*j<=A;++j)
            Nums[X[i]*j-B].push_back(X[i]);
}
int main()
{
    // freopen("meet.in","r",stdin);
    // freopen("meet.out","w",stdout);
    read(N);
    for(re int i=1;i<=N;++i) read(X[i]);
    read(A,B);
    if(abs(B-A)<=20) return Subtask2::solve();
    std::sort(X+1,X+1+N);
    M=std::unique(X+1,X+N+1)-X-1;
    init();
    for(int i=0;i<Nums[0].size();++i)
    {
        Que u=(Que){0,Nums[0][i]};
        while(head<=tail&&Q[tail]<u) --tail;
        Q[++tail]=u;
    }
    for(int i=1;i<=A-B;++i)
    {
        Dp[i]=Dp[i-1]+1;
        while(Q[head].y<=i&&head<=tail) ++head;
        for(int j=0;j<Nums[i].size();++j)
        {
            Que u=(Que){i,i+Nums[i][j]};
            while(head<=tail&&Q[tail]<u) --tail;
            Q[++tail]=u;
        }
        if(head<=tail) checkMin(Dp[i],Dp[Q[head].x]+1);
    }
    write(Dp[A-B]);
    return 0;
}
/*
3
3 4 5
30 17
3
5 6 7
1000 200
*/

绝命终结室

神仙数位 $\text{Dp}$ 。

题意

给定一个数 $n$ ，每一次可以选择 $n$ 中的某一位 $x_i$ ，并把 $n$ 变成 $n-x_i$ ，求变成 $n=0$ 的最小次数。模数 $998244353$ 。

$n\leq 10^{500}$ 。

部分分

有一个超级弱智的部分分 $\text{Subtask1:}n\leq 9$ ，显然地，答案是 $1$ 。

然后跑 $\mathcal O(n\log n)$ 的暴力能够拿到 $30pt$ ，用 $f[i]$ 表示从 $i$ 变成 $0$ 的最小次数，然后用 $\mathcal O(\log n)$ 的时间枚举位数并暴力转移即可。

贴一个代码。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
const int MAXN=5e2+10;
char Nums[MAXN];
int Len,N[MAXN];
bool Zero;
namespace LowNum
{
    const int MAXNUM=1e6+10;
    int Dp[MAXNUM];
    inline bool solve()
    {
        int Sum=0;
        for(int i=1;i<=Len;++i) Sum=(Sum<<3)+(Sum<<1)+N[i];
        memset(Dp,0x3f,sizeof(Dp));Dp[0]=0;
        for(int i=0;i<=Sum;++i)
        {
            int T=i;
            while(T)
            {
                checkMin(Dp[i],Dp[i-T%10]+1);
                T/=10;
            }
        }
        write(Dp[Sum]);
        return 0;
    }
};
int main()
{
    // freopen("number.in","r",stdin);
    // freopen("number.out","w",stdout);
    scanf("%s",Nums+1);
    Len=strlen(Nums+1);
    if(Len==1) return printf("1")&0;
    for(int i=1;i<=Len;++i) N[i]=Nums[i]-'0';
    if(Len<=7) return LowNum::solve();
    return 0;
}
/*
114514
*/

正解

然后考虑正解，每一次都减最大的数的话，肯定能使当前局部最优，就需要证明当 $x\geq y$ 时， $f[x]\geq f[y]$ 。可以分情况讨论，然后证明。

然后设计状态 $Dp[max][i][j][k][0/1]$ ，其中表示第 $i$ 位为 $j$ ，个位为 $k$ ，第 $1\sim i$ 位最大数字为 $max$ ，其余位为 $0$ 的数，保持第 $i$ 位之前不变，第 $i$ 位以下除了各位之外都减到 $0$ 的次数以及个位的值。

时间复杂度是 $\mathcal O(10^3n^2)$ 。

贴一个出题人的代码：

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<ctime>
#include<vector>
#define ll long long
using namespace std;
const int mod=998244353;
inline int MOD(int x) {return x+((x>>31)&mod);}
int read()
{
	int kkk=0,x=1;
	char c=getchar();
	while((c<'0' || c>'9') && c!='-') c=getchar();
	if(c=='-') c=getchar(),x=-1;
	while(c>='0' && c<='9') kkk=(kkk<<3)+(kkk<<1)+(c-'0'),c=getchar();
	return kkk*x;
}
char s[510];
int n,dp[10][510][10][10][2],A[510],maxn[510];
int main()
{
	freopen("number.in","r",stdin);
	freopen("number.out","w",stdout);
	scanf("%s",s);
	n=strlen(s);
	if(n==1)
	{
		puts("1");
		return 0;
	}
	for(int p=1;p<n;++p)
		for(int minv=0;minv<10;++minv)
			for(int val=0;val<10;++val)
				for(int lasv=0;lasv<10;++lasv)
				{
					if(val==0)
					{
						dp[minv][p][val][lasv][0]=lasv;
						continue;
					}
					int dv=max(minv,max(val,lasv));
					if(dv==lasv)
					{
						dp[minv][p][val][lasv][1]=MOD(dp[minv][p][val][0][1]+1-mod);
						dp[minv][p][val][lasv][0]=dp[minv][p][val][0][0];
						continue;
					}
					int ans=1,las=lasv+10-dv;
					for(int i=1;i<=p;++i)
					{
						int MAX=minv,nv=9;
						if(i==p) nv=val-1;
						if(i<p) MAX=max(MAX,val-1);
						if(i<p-1) MAX=9;
						ans=MOD(ans+dp[MAX][i][nv][las][1]-mod);
						las=dp[MAX][i][nv][las][0];
					}
					dp[minv][p][val][lasv][1]=ans;
					dp[minv][p][val][lasv][0]=las;
				}
	for(int i=0;i<n;++i) A[n-1-i]=s[i]-'0';
	maxn[n]=0;
	for(int i=n-1;i>=1;--i) maxn[i]=max(maxn[i+1],A[i]);
	int tmp=A[0],ans=1;
	for(int i=1;i<n;++i)
	{
		ans=MOD(ans+dp[maxn[i+1]][i][A[i]][tmp][1]-mod);
		tmp=dp[maxn[i+1]][i][A[i]][tmp][0];
	}
	printf("%d\n",ans);
	cerr<<(double)clock()/CLOCKS_PER_SEC<<endl;
	return 0;
}
//ore no turn,draw!

木又寸

神仙树剖，隔壁 $\text{l18q}$ 说是树剖裸题，反正我没想到怎么做。

题目没有读太懂，反正是一个有向树，操作反向。然后，就读不懂了。改不出来。

题意

一棵有 $n$ 个结点的树，初始时每一条边都是顺的，这里的顺定义为从父结点连接到子结点，反之为逆。

有 $q$ 个操作：

  • $opt,u,v$ ，把 $(u,v)$ 边反向；
  • $opt,u,v$ ，查询路径 $(u,v)$ 的权值，这里的权值为下述定义。

一条路径的权值可以定义为很多条简单路径之和，一条简单路径 $(x,y)$ 满足，从 $x$ 到 $y$ 或者从 $y$ 到 $x$ 全部都经过的是顺边，则这条简单路径的权值为 $\displaystyle\sum_{k\in(u,v)}val_k\times|(u,v)|$ ，即路径大小乘以路径点权和。

举一个简单的例子：路径 $(5,6)$ 会经过 $(5,3)(3,1)(1,6)$ 其中 $(3,1)(1,6)$ 相对于路径 $(5,6)$ 为逆边，即从 $5$ 开始经过这条边时是逆边，则简单路径就有三条：$(5,3)(1)(6)$ 。

$n,q\leq 10^5$ 。

思路

今天早上困得要死，就没认真读题。以为是一个不可做的 $\operatorname{LCT}$ 。

树上路径操作，所以考虑树剖。

对于一个整的区间，我们可以直接在线段树上进行操作和查询（虽然我好像还是不会），所以现在考虑跳链的情况。

首先要考虑当前结点是否已经越过了 $lca$ ，即下一次跳是往上跳还是往下跳（因为路径有顺序，所以不可以两端同时跳），但是，区间和并还是很难搞，所以每一次跳链的时候，我们就单独把这条边剔出来，然后判断是顺序合并还是逆序合并。然后对于每一根链，我们维护两个线段树，一个维护顺序权值一个维护逆序权值，对于修改操作，如果修改的边位于某一根链的中间，就直接更新区间；如果一条边连接了两根链，就可以忽略这次操作，因为毕竟我们每一次查询的时候都会单独判定跳链的边。

这样看起来大概思路就有了，不过码量惊人，树剖本来就长，这种神仙树剖也就只有口胡就好了，代码真的不太想写。

至于暴力的话，$\mathcal O(n^2)$ 可以得到 $20pt$ 。

想象挖掘

神仙构造题，$\text{Dyd}$ 爆切。（真的爆切，他一讲我就懂了）

题意

有一个长度为 $n$ 的环，一共有三种颜色，有初始串 $s$ 和目标串 $t$ ，结点 $i$ 的颜色可以任意改变的条件是 $col_{i-1}\neq col_{i+1}$ ，即一个结点的左右邻结点颜色不同时，该结点可以任意改变颜色。

构造出一种方案，使得 $s=t$ 。

$5\leq n\leq 10^6$ 。

思路

有一个需要了解的性质，是：

如果该串中存在一个结点能够改变，则该串的任意一个结点都可以改变位置。

证明也很简单：设当前我们已经找到了一个结点 $i$ 可以改变颜色，那么，我们一定可以将 $col_x$ 改变成使得 $col_x\neq col_{x-2},col_x\neq col_{x+2}$ ，因为一共有三种颜色，这样修改的话， $col_{x-1},col_{x+1}$ 就都可以变了，然后以此类推即可。

那么，构造思路在于：首先将 $s,t$ 转换成一个任意位置都可以变颜色的串 $s’,t’$ ，这样的话题目会简单很多。（因为没有限定次数，所以可以稍微乱搞）

然后考虑如何把 $s’$ 变成 $t’$ ，需要分为两种情况讨论：

  • $n\equiv 0\pmod 2$ ，即 $n$ 为偶数。那么我们交叉修改，当前位置为 $x$ ，我们先使 $s_x=t_x$ ，然后令 $s_{x+2}=t_{x+2}$ ，因为已经有 $t_x\neq t_{x+2}$ ，所以现在的 $s_{x+1}$ 是可变的。然后依次循环，每一次修改的循环节为 $2$ ，最后会剩下第 $n$ 个，但是，当前的 $1$ 和 $n-1$ 都已经被修改了，所以 $n$ 也是可修改的。结束。
  • $n\equiv 1\pmod 2$ ，即 $n$ 为奇数。我们可以转换为偶数的讨论形式。因为有三种颜色，所以我们首先将 $s_1$ 变为不同于原来 $s_3$ 和 $t_{n-1}$ 的第三种颜色。然后从 $2$ 开始用偶数的方式开始循环直到 $n-1$ ，此时还有 $s_n\neq t_n$ ，但是我们已经有了 $s_1$ 是与 $t_{n-1}$ 不同的颜色，所以满足了 $s_n$ 是可变的。就只剩下了 $s_1$ ，因为 $s_n$ 和 $s_2$ 都已经变了，所以肯定也是不同的，所以 $s_1$ 可变，结束。

之后的操作就是把 $t’$ 还原成 $t$ 了。

时间复杂度是常数略微有一点大的 $\mathcal O(n)$ 。

8.22

以小可可为主角的一系列故事，同样是一套神仙题。代表是题目都是五个无法理解的汉字。

（因为不想做就滚回来写博客了）果然还是被 $\text{LuckyLeaves}$ 大帝暴捶惹。

$\text{_Eternal_:}100pt+100pt+0+60pt=260pts$

厜蓧篈壻鑨

题意

给定一张 $n\times m$ 的二维字符图，由 . 和 # 组成，其中每存在一个 # 就会把四周方向位置也变成 # ，初始是可以放置任意个数的 # ，求变成给定目标图（一个都不能差）的最长时间。

$n,m\leq 1000$ 。

题解

因为是求时间，所以考虑二分，时间复杂度的话，$\mathcal O(n^2\log n)$ 应该可以过。

每次暴力匹配扩展 $x$ 次之后的图是否对等，然后就更新二分区间即可。

对于初始化的点，我们记一个数组 $cnt[i][j]$ ，表示离最近 . 的距离，然后对于 $cnt[i][j]>x$ 的点，就记为初始点。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=getchar(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<>
inline void write(char c)
{
    putchar(c);
}
template<>
inline void write(char *s)
{
    while(*s) putchar(*s++);
}
template<class T,class ...T1>
inline void write(T x,T1 ...x1)
{
    write(x),write(x1...);
}
template<class T>
inline bool checkMax(T &x,T y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T y)
{
    return x>y?x=y,1:0;
}
const int MAXN=1e3+10;
const int dx[]={0,1,-1,0,0};
const int dy[]={0,0,0,1,-1};
using Pir=std::pair<int,int>;
int N,M,Map[MAXN][MAXN],Edg[MAXN][MAXN],Cnt[MAXN][MAXN];
char Str[MAXN][MAXN];
struct Que
{
    int x,y,d;
};
bool Vis[MAXN][MAXN];
inline bool check(int x)
{
    std::queue<Que>Q;
    memset(Vis,0,sizeof(Vis));
    for(re int i=1;i<=N;++i)
        for(re int j=1;j<=M;++j)
            if(Cnt[i][j]>x) Q.push({i,j,x}),Vis[i][j]=1;
    while(!Q.empty())
    {
        Que u=Q.front();Q.pop();
        for(int k=1;k<=4;++k)
        {
            int nx=u.x+dx[k],ny=u.y+dy[k];
            if(nx<1||nx>N||ny<1||ny>M) continue;
            if(Map[nx][ny]&&(!Vis[nx][ny]))
            {
                Vis[nx][ny]=1;
                if(u.d-1) Q.push({nx,ny,u.d-1});
            }
        }
    }
    for(re int i=1;i<=N;++i)
        for(re int j=1;j<=M;++j)
            if(Map[i][j]&&(!Vis[i][j])) return 0;
    return 1;
}
int main()
{
    // freopen("1ysa93e.in","r",stdin);
    // freopen("1ysa93e.out","w",stdout);
    read(N,M);
    std::queue<Pir>Q;
    for(re int i=1;i<=N;++i) scanf("%s",Str[i]+1);
    for(re int i=1;i<=N;++i)
        for(re int j=1;j<=M;++j)
            Map[i][j]=(Str[i][j]=='#');
    for(re int i=1;i<=N;++i)
        for(re int j=1;j<=M;++j)
            if(Map[i][j]&&(!(Map[i-1][j]&&Map[i+1][j]&&Map[i][j-1]&&Map[i][j+1])))
                Q.push({i,j}),Edg[i][j]=1,Cnt[i][j]=1;
    while(!Q.empty())
    {
        Pir u=Q.front();Q.pop();
        for(int k=1;k<=4;++k)
        {
            int nx=u.first+dx[k],ny=u.second+dy[k];
            if(nx<1||nx>N||ny<1||ny>M) continue;
            if(Map[nx][ny]&&!Edg[nx][ny]&&!Cnt[nx][ny])
            {
                Q.push({nx,ny});
                Cnt[nx][ny]=Cnt[u.first][u.second]+1;
            }
        }
    }
    int l=0,r=N+M,res;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) res=mid,l=mid+1;
        else r=mid-1;
    }
    write(res);
    return 0;
}
/*
10 9
.........
...#.....
..###....
.#####...
..####...
...####..
...#####.
....###..
.....#...
.........
*/

鞩铃夐鑏繦

题意

给定一棵树 $n$ ，每一个点的权值为 $a_i$ ，每一次可以选取一条路径 $(u,v)$ 使得该路径上的点权值减 $1$ ，权值不能为负数，求最少操作次数。

$n\leq 2\times 10^5,a_i\leq 10^9$ 。

部分分

比较神仙的树型 $\text{Dp}$ 题，我考虑的是使用树链剖分维护，理论可以拿到 $65pt$ 的好成绩，更暴力一点的话也有 $30pt$ 。

对于 $30pt$ 的话，直接乱搞，时间复杂度在 $\mathcal O(2^{2n}\log^2n)$ 都可以过，每次用 $\mathcal O(n^2)$ 的时间来枚举当前路径是否可以被修改，如果可以，就修改，然后回溯操作。

对于 $65pt$ 的话，有一个不知道正确性的贪心思路：每次找到当前树中权值最小的点，然后找到该结点所在的直径，并修改这条路径。

用暴力树型 $\text{Dp}$ 的 $\mathcal O(n)$ 求出最小结点，再用 $\mathcal O(n)$ 的时间换根扫描求得直径，修改即可。

其实的话，这道题 $\mathcal O(n\log^4n)$ 是可过的。但我们需要在 $\mathcal O(\log n)$ 的时间查询最小结点，并在 $\mathcal O(\log n)$ 的时间内得到其最小直径。至少最后这两步我不会，所以这个题也就 $65pt$ 即可。

正解

直接树型 $\text{Dp}$ 考虑。

首先可以知道，最大代价就是 $\displaystyle\sum_{i\leq n}a_i$ ，那么，我们就知道了整个答案区间。

考虑二分。

考虑把一些能够合并的修改合并掉，考虑拆点，把权值为 $a_i$ 的点拆成 $a_i$ 个权值为 $1$ 的点，然后看当前结点 $u$ 的子结点 $v$ 能够给 $u$ 贡献出多少的匹配（也就是说 $u$ 的权值有多少点能够在它的子树处理时同时被处理）。用 $f[i]$ 表示 $i$ 一共最大有的匹配个数，$g[i]$ 表示 $i$ 能够给 $fa_i$ 贡献的匹配个数。

设 $\displaystyle res=\sum_{fa_v=u}g(v)$ 为 $u$ 的子树能够贡献的匹配，很明显必须满足 $res\leq a_u$ ，所以计算 $res$ 时要取 $\min$ 。

然后先考虑计算 $f[u]$ ，肯定有 $\displaystyle f[u]=\sum_{fa_v=u}f[v]$ 这里是统计了子树贡献，没有统计当前点与子树之间的贡献，还要考虑 $g[v]$ 的贡献，我们所说的匹配，就是，从 $u$ 的子树中延伸出来的修改链是否会通过 $u$ ,从而把 $u$ 给改掉，那么 $res$ 就是子树贡献出的匹配，不可能超过当前结点的总匹配数 $2a_i$ 。

为什么上限是 $2a_i$ ？（感谢 $\text{_Live_}$ 和 $\text{LuckyLeaves}$ 陪我死磕了那么久）

因为统计的是以 $u$ 为根的子树的贡献，所以当前修改的这一条路径肯定会经过 $u$ 结点，（$u$ 结点是其子树中的最大 $lca$）所以，拆点之后，$u$ 中每一个权值为 $1$ 的结点，都能够与其子树匹配至多 $2$ 次（修改路径是树上的一条必定经过 $u$ 的链），所以贡献上限为 $2a_i$ 。

所以，$f[i]$ 的计算为：

$\displaystyle f[u]=\sum_{fa_v=u}f[v]+\min\left(\sum_{fa_v=u}\min\left(g(v),a_u\right),2a_u\right)$

实际代码两行解决。

然后说计算 $g[u]$ 。

  • 如果 $u$ 点的权值全部都在其子树被计算完了，那它就只能给自己的父结点贡献个屁了。
  • 否则，$u$ 点最多给父结点的贡献不会超过 $a_u$ ，因为此时计算的 $g[u]$ 是从 $u$ 出发向父结点即其父结点的其他子结点的一条链的贡献，所以 $u$ 一定是链头，能匹配的次数也就至多只有 $a_u$ 次。那么，我们希望贡献地越少越好。（不对未知态抱有足够幻想，以现实解决问题）
    • 考虑 $res,a_i,2a_i$ 三者的大小关系。
    • 如果 $res>2a_i$ ，贡献为 $0$ ；
    • 如果 $res<a_i$ ，则贡献为 $a_i$ ；
    • 否则，贡献为 $2a_i-res$ 。

对于第一种情况，保证 $u$ 结点在其子树内已经被解决完了，所以无需贡献；然后对于第二三种情况，那就是 $u$ 无法被处理完的情况，剩下了 $2a_i-res$ 的贡献，然后取小值即可，可以一行代码带走。

$\displaystyle g[u]=\min(\max(0,2a_i-res),a_i)$

然后就解决了，实际代码十分简洁，但是要理解的话，可能还比较费劲。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
const int MAXN=2e5+10;
const int INF=0x3f3f3f3f;
int N,Val[MAXN];
struct TC
{
    int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
    Edge[++Total]=(TC){Head[u],v};Head[u]=Total;
    Edge[++Total]=(TC){Head[v],u};Head[v]=Total;
}
namespace Subtask1
{
    const int MAXN=10;
    int Dep[MAXN],Fa[MAXN],Siz[MAXN],Son[MAXN];
    int Top[MAXN],Dfn[MAXN],Bck[MAXN],Cnt;
    void dfsTree(int x,int last)
    {
        Dep[x]=Dep[last]+1,Siz[x]=1,Fa[x]=last;
        for(int e=Head[x],v;e;e=Edge[e].next)
        {
            if((v=Edge[e].to)==last) continue;
            dfsTree(v,x);
            Siz[x]+=Siz[v];
            if(!Son[x]||Siz[v]>Siz[Son[x]]) Son[x]=v;
        }
    }
    void dfsChain(int x,int topf)
    {
        Top[x]=topf,Dfn[x]=++Cnt;
        Bck[Cnt]=x;
        if(!Son[x]) return ;
        dfsChain(Son[x],topf);
        for(int e=Head[x],v;e;e=Edge[e].next)
        {
            if((v=Edge[e].to)==Fa[x]||v==Son[x]) continue;
            dfsChain(v,v);
        }
    }
    #define ls p<<1
    #define rs p<<1|1
    struct ST
    {
        int l,r,val,tag,minn,siz;
    }Tr[MAXN<<2];
    inline void pushUp(int p)
    {
        Tr[p].val=Tr[ls].val+Tr[rs].val;
        Tr[p].minn=std::min(Tr[ls].minn,Tr[rs].minn);
    }
    inline void pushDown(int p)
    {
        if(Tr[p].tag)
        {
            Tr[ls].val+=Tr[ls].siz*Tr[p].tag,Tr[rs].val+=Tr[rs].siz*Tr[p].tag;
            Tr[ls].minn+=Tr[p].tag,Tr[rs].minn+=Tr[p].tag;
            Tr[ls].tag+=Tr[p].tag,Tr[rs].tag+=Tr[p].tag;
            Tr[p].tag=0;
        }
    }
    void build(int p,int l,int r)
    {
        Tr[p].l=l,Tr[p].r=r,Tr[p].siz=r-l+1;
        if(l==r)
        {
            Tr[p].val=Tr[p].minn=Val[Bck[l]];
            return ;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid),build(rs,mid+1,r);
        pushUp(p);
    }
    void modifyAdd(int p,int l,int r,int k)
    {
        if(l<=Tr[p].l&&Tr[p].r<=r)
        {
            Tr[p].val+=Tr[p].siz*k;
            Tr[p].minn+=k,Tr[p].tag+=k;
            return ;
        }
        pushDown(p);
        int mid=(Tr[p].l+Tr[p].r)>>1;
        if(l<=mid) modifyAdd(ls,l,r,k);
        if(mid<r) modifyAdd(rs,l,r,k);
        pushUp(p);
    }
    int queryMin(int p,int l,int r)
    {
        if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].minn;
        pushDown(p);
        int mid=(Tr[p].l+Tr[p].r)>>1,res=INF;
        if(l<=mid) checkMin(res,queryMin(ls,l,r));
        if(mid<r) checkMin(res,queryMin(rs,l,r));
        return res;
    }
    int querySum(int p,int l,int r)
    {
        if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].val;
        pushDown(p);
        int mid=(Tr[p].l+Tr[p].r)>>1,res=INF;
        if(l<=mid) res+=querySum(ls,l,r);
        if(mid<r) res+=querySum(rs,l,r);
        return res;
    }
    inline void modifyPath(int x,int y,int k)
    {
        while(Top[x]!=Top[y])
        {
            if(Dep[Top[x]]<Dep[Top[y]]) std::swap(x,y);
            modifyAdd(1,Dfn[Top[x]],Dfn[x],k);
            x=Fa[Top[x]];
        }
        if(Dep[x]>Dep[y]) std::swap(x,y);
        modifyAdd(1,Dfn[x],Dfn[y],k);
    }
    inline int queryPathMin(int x,int y)
    {
        int res=INF;
        while(Top[x]!=Top[y])
        {
            if(Dep[Top[x]]<Dep[Top[y]]) std::swap(x,y);
            checkMin(res,queryMin(1,Dfn[Top[x]],Dfn[x]));
            x=Fa[Top[x]];
        }
        if(Dep[x]>Dep[y]) std::swap(x,y);
        checkMin(res,queryMin(1,Dfn[x],Dfn[y]));
        return res;
    }
    int Idx=INF;
    void Search(int pos)
    {
        if(pos>Idx) return ;
        bool flag=0;
        for(int x=1;x<=N;++x)
            for(int y=1;y<=N;++y)
            {
                int add=queryPathMin(x,y);
                if(!add) continue;
                flag=1;
                modifyPath(x,y,-add);
                Search(pos+add);
                modifyPath(x,y,add);
            }
        if(!flag) checkMin(Idx,pos);
    }
    inline bool main()
    {
        dfsTree(1,0),dfsChain(1,1);
        build(1,1,N);
        Search(0);
        write(Idx);
        return 0;
    }
};
namespace Subtask3
{
    ll Dp[MAXN],Cnt[MAXN];
    void dpTree(int x,int last)
    {
        ll res=0;
        for(int e=Head[x],v;e;e=Edge[e].next)
        {
            if((v=Edge[e].to)==last) continue;
            dpTree(v,x);
            Dp[x]+=Dp[v];
            res+=std::min(Cnt[v],1ll*Val[x]);
        }
        Dp[x]+=std::min(res,Val[x]*2ll);
        Cnt[x]=std::min(std::max(0ll,2ll*Val[x]-res),1ll*Val[x]);
    }
    inline bool main()
    {
        ll sum=0;
        for(int i=1;i<=N;++i) sum+=Val[i];
        dpTree(1,-1);
        write(sum-Dp[1]);
        return 0;
    }
};
int main()
{
    // freopen("snow.in","r",stdin);
    // freopen("snow.out","w",stdout);
    read(N);
    for(re int i=1;i<=N;++i) read(Val[i]);
    for(int i=2,u,v;i<=N;++i)
    {
        read(u,v);
        addEdge(u,v);
    }
    if(N<=6) return Subtask1::main();
    Subtask3::main();
    return 0;
}
/*
5
5 4 5 3 2
1 2
2 3
3 4
3 5
*/

蘄壺螸壚黜

题意

给定一个有 $n$ 个点，$m$ 条边的有向图，不保证无环不保证连通，每个点有 $a_i$ 种权值，相邻两个点权值不能相等，求方案数。模数 $998244353$ 。

$n,m\leq 2\times 10^5,a_i\leq 2\times 10^5$ ，保证度数小于 $2$ 。

题解

因为保证了度数的大小，所以对于每一个连通图，只会存在简单环和链两种情况。

首先考虑链，相当于是一个区间。就可以考虑使用动态规划，设 $Dp[i][j]$ 表示第 $i$ 个结点选择第 $j$ 种颜色的方案数，这样的话，其实转移是很简单的。

$\displaystyle Dp[i][j]=\sum_{k=1}^{a_i} Dp[i-1][k],k\neq j$

但是，因为有 $n,a_i\leq 2\times 10^5$ 的限制，不要说转移了，连状态的构造都成问题，所以考虑滚动数组。然后对于状态的转移的话，必须要控制到 $\mathcal O(n\log n)$ 的复杂度内，所以考虑使用线段树优化。

具体怎么用线段树优化我也不太清楚，但反正 $\text{LuckyLeaves}$ 和 $\text{Dyd}$ 都写出来了，所以可以证明是可做的。（我不太可做就是了）

然后考虑用链的思路来做环。

考虑断环成链，从环上一点开始扩展，然后直到其上一个结点。然后就会出现当前起点 $u$ 和当前终点 $v$ 选择相同颜色的部分方案并没有被计算，所以要减去这一部分的贡献。

这部分的计算会考虑到容斥，具体来讲，真正的环的答案应该是：

总方案数减去开头与结尾选择一样的方案数加上开头与结尾两个结点选择一样的方案数减去开头与结尾三个结点选择一样的方案数等等。

然后捏，为了方便容斥，我们的起点可以设在环上 $a_i$ 最小的结点，而保证容斥的时候一定有颜色相等的方案。

链上计算时间复杂度 $\mathcal O(n\log n)$ ，环上计算时间复杂度 $\mathcal O(n\log n)$ ，总时间复杂度 $\mathcal O(n\log n)$ 。

没写这道题，贴一个 $\text{LuckyLeaves}$ 的部分代码。

CE Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
const int N = 2e5 + 5, mod = 998244353;
struct Node{
    int l, r;
    LL flag, add, val;
    #define l(x) (x << 1)
    #define r(x) (x << 1 | 1)
}tr[N << 2];
int n, m;
int idx;
int e[N << 1], ne[N << 1], h[N], a[N];
inline void add(int x, int y)
{
    idx ++;
    e[idx] = y, ne[idx] = h[x], h[x] = idx;
}
inline void pushup(int x)
{
    tr[x].val = (tr[l(x)].val + tr[r(x)].val) % mod;
}
inline void change(int x, int val)
{
    if(val == 1) return;
    tr[x].val = 1ll * tr[x].val * val % mod;
    tr[x].add = 1ll * tr[x].add * val % mod;
    tr[x].flag = 1ll * tr[x].flag * val % mod;
}
inline void modify(int x, int val)
{
    if(val == 0) return ;
    tr[x].val = (tr[x].val + 1ll * val * (tr[x].r - tr[x].l + 1) % mod) % mod;
    tr[x].add = (tr[x].add + val) % mod;
}
inline void pushdown(int x)
{
    if(!tr[x].add && tr[x].flag == 1) return;
    change(l(x), tr[x].flag), change(r(x), tr[x].flag);
    tr[x].flag = 1;
    modify(l(x), tr[x].add), modify(r(x), tr[x].add);
    tr[x].add = 0;
}
inline void build(int x, int l, int r)
{
    tr[x].l = l, tr[x].r = r;
    if(l == r) return tr[x].val = 0, tr[x].flag = 1, void();
    int mid = l + r >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    pushup(x);
}
inline void modify(int x, int l, int r, int val)
{
    if(l <= tr[x].l && tr[x].r <= r) return modify(x, val);
    pushdown(x);
    int mid = tr[x].l + tr[x].r >> 1;
    if(l <= mid) modify(x << 1, l, r, val);
    if(r > mid) modify(x << 1 | 1, l, r, val);
    pushup(x);
}
inline void change(int x, int l, int r, int val)
{
    if(l <= tr[x].l && tr[x].r <= r) return change(x, val);
    pushdown(x);
    int mid = tr[x].l + tr[x].r >> 1;
    if(l <= mid) change(x << 1, l, r, val);
    if(r > mid) change(x << 1 | 1, l, r, val);
    pushup(x);
}
vector<int>s;
int vis[N], ans = 1;
inline void check()
{
    change(1, 1, N - 1, 0);
    modify(1, 1, a[s[0]], 1);
    for(int i = 1, val;i < s.size();i ++)
    {
        val = tr[1].val;
        change(1, 1, a[s[i]], mod - 1);
        modify(1, 1, a[s[i]], val);
        change(1, a[s[i]] + 1, N - 1, 0);
    }
    ans = 1ll * ans * tr[1].val % mod;
}
inline void hack()
{
    vector<int> q;
    pair<int, int> o = {1e9, 1e9};
    for(int i = 0;i < s.size();i ++)
        o = min(o, {a[s[i]], i});
    for(int i = o.second;i < s.size();i ++)
        q.push_back(s[i]);
    for(int i = 0;i < o.second;i ++)
        q.push_back(s[i]);
    swap(q, s);
}
inline void check1()
{
    change(1, 1, N - 1, 0);
    hack();
    int flag = s.size() & 1;
    modify(1, 1, a[s[0]], 1);
    int res = 0;
    for(int i = 1, val;i < s.size();i ++)
    {
        val = tr[1].val;
        change(1, 1, a[s[i]], mod - 1);
        modify(1, 1, a[s[i]], val);
        change(1, a[s[i]] + 1, N - 1, 0);
        if(flag) res = (res - tr[1].val) % mod;
        else res = (res + tr[1].val) % mod;
        flag ^= 1;
    }
    res = (res + mod) % mod;
    ans = 1ll * ans * res % mod;
}
/*
缺失的部分有两个函数：
一个是判断是链还是环的dfs
一个是初始化以及找环和链的主函数
*/

Extra

题意

一个 $n\times n$ 的棋盘，放置主教（行动方式为走斜边）。定义一个主教只能攻击 $m$ 个方向，求放置的最大个数和方案。

$10^3\leq n\leq 10^5,m\in\{0,1,2,3,4\}$ ，$m$ 的五种取值各 $20pt$ 。

题解

五个部分分，挨个拿。

首先考虑 $m=0$ ，你都不能攻击，那直接摆满就完事了。

答案为 $n^2$ 。

然后考虑 $m=4$ 时，会发现答案为 $2n-2$ ，第一行摆满，最后一行摆 $2\sim n-1$ 个。

然后考虑 $m=2$ 时，发现可以摆满一圈，答案 $4(n-1)$ ，两个能攻击的方向对着棋盘外即可。

对于 $m=1,3$ 的情况，那就麻烦了不止一点点了。

读者可以自行进行思考，就我个人而言，$60pt$ 已经是一个不错的成绩了。

8.23

考的是洛谷上的 $\text{SCP-001}$ 的 $S$ 组初赛模拟。

被吊打，$55pt$ ，悬。

8.24

一套以小可可为主角，题目名称为颜文字的题目，除了 $\text{T4}$ 以外都是线性规划的数学题或者线性动态规划，与期望概率有关。

有幸做出了一道，可贺可贺。

$\text{_Eternal_:}100pt+0+100pt+52pt=252pts$

qwq

题意

有一个长度为 $n$ 的数列 $a_i$ ，按照 $1\sim n$ 的顺序，每一次会以相等的概率将当前持有的数值分给其余 $n-1$ 个，求最后每一个的期望数值，模数 $998244353$ 。

$n\leq 10^6$ 。

题解

期望时间复杂度是 $\mathcal O(n)$ ，但是可以选择用 $\mathcal O(n\log n)$ 的线段树卡过去。

首先考虑模拟整个运算。如果当前数值为 $a_i$ ，其余位置上的数为 $a_k,1\leq k\leq n,i\neq k$ ，在进行完成第 $i$ 次转移后，$a_i$ 会变成 $0$ ，然后其余数会变成 $a_k+\frac{a_i}{n-1}$ ，这样暴力转移，时间复杂度是 $\mathcal O(n^2)$ ，能够过 $70\%$ 的数据，也算是良心了。

然后考虑优化，每一次转移，相当于是对三个区间进行了相同的操作：

  • $[1,i-1]$ 加上了 $\frac{a_i}{n-1}$ ；
  • $[i,i]$ 减去了 $a_i$ ；
  • $[i+1,n]$ 加上了 $\frac{a_i}{n-1}$ 。

这样的话，考虑线段树，可以优化到 $\mathcal O(n\log n)$ ，$10^6$ 的极限数据可过。

维护一个支持区间加和单点查询的线段树即可。

AC Code Segment Tree ver. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
const int MAXN=1e6+10;
const ll Mod=998244353;
int N;
ll Val[MAXN];
inline ll qPow(ll a,ll b,ll p)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=1ll*a*res%p;
        a=1ll*a*a%p;b>>=1;
    }
    return res;
}
#define ls p<<1
#define rs p<<1|1
struct ST
{
    int l,r;
    ll val,tag,siz;
}Tr[MAXN<<2];
inline void pushUp(int p)
{
    Tr[p].val=Tr[ls].val+Tr[rs].val;
}
inline void pushDown(int p)
{
    if(Tr[p].tag)
    {
        Tr[ls].val=(Tr[ls].val+Tr[ls].siz*Tr[p].tag)%Mod,Tr[ls].tag=(Tr[ls].tag+Tr[p].tag)%Mod;
        Tr[rs].val=(Tr[rs].val+Tr[rs].siz*Tr[p].tag)%Mod,Tr[rs].tag=(Tr[rs].tag+Tr[p].tag)%Mod;
        Tr[p].tag=0;
    }
}
void build(int p,int l,int r)
{
    Tr[p].l=l,Tr[p].r=r,Tr[p].siz=r-l+1;
    if(l==r)
    {
        Tr[p].val=Val[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushUp(p);
}
void modifyAdd(int p,int l,int r,ll k)
{
    if(l>r) return ;
    if(l<=Tr[p].l&&Tr[p].r<=r)
    {
        Tr[p].val=(Tr[p].val+Tr[p].siz*k)%Mod;
        Tr[p].tag=(Tr[p].tag+k)%Mod;
        return ;
    }
    pushDown(p);
    int mid=(Tr[p].l+Tr[p].r)>>1;
    if(l<=mid) modifyAdd(ls,l,r,k);
    if(mid<r) modifyAdd(rs,l,r,k);
    pushUp(p);
}
int querySum(int p,int x)
{
    if(Tr[p].l==Tr[p].r) return Tr[p].val%Mod;
    pushDown(p);
    int mid=(Tr[p].l+Tr[p].r)>>1;
    if(x<=mid) return querySum(ls,x);
    else return querySum(rs,x);
}
int main()
{
    // freopen("qwq.in","r",stdin);
    // freopen("qwq.out","w",stdout);
    read(N);
    for(int i=1;i<=N;++i) read(Val[i]);
    ll Inv=qPow(N-1,Mod-2,Mod);
    build(1,1,N);
    for(int i=1;i<=N;++i)
    {
        ll cut=querySum(1,i);
        modifyAdd(1,i,i,-cut);
        cut=cut*Inv%Mod;
        modifyAdd(1,1,i-1,cut);
        modifyAdd(1,i+1,N,cut);
    }
    for(int i=1;i<=N;++i) write(querySum(1,i),' ');
    return 0;
}
/*
3
1 1 1
*/

然后说一下题解给出的线性复杂度正解。

记录 $f_i$ 表示操作到第 $i$ 个数时（第 $i$ 个尚未操作），第 $i$ 个数的期望值。

然后有 $\displaystyle ans_i=\sum_{j=i+1}^{n}\frac{f_j}{n-1}$ ，$f_i$ 的转移类似。

所以，我们可以首先线性处理 $f_i$ ，再线性处理 $ans_i$ 即可。

从刚刚的线段树思路来考虑的话，三个区间的划分取决于 $i$ ，那么，当我们清空 $a_i$ 时，可以给 $i-1,i+1$ 都打上一个标记，然后捏，当你往后递推的时候，右边的懒标记也会跟着你的枚举往右边走，越滚越大。

那么，我们顺序递推一次，来处理右边的懒标记，随后逆序递推一次，清空左端的懒标记，这样，就可以代替线段树所有的操作。

时间复杂度 $\mathcal O(n)$ 。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
const int MAXN=1e6+10;
const ll Mod=998244353;
int N;
ll Val[MAXN],ans[MAXN];
inline ll qPow(ll a,ll b,ll p)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=1ll*a*res%p;
        a=1ll*a*a%p;b>>=1;
    }
    return res;
}
int main()
{
    // freopen("qwq.in","r",stdin);
    // freopen("qwq.out","w",stdout);
    read(N);
    for(int i=1;i<=N;++i) read(Val[i]);
    ll Inv=qPow(N-1,Mod-2,Mod);
    ll s=0;
    for(int i=1;i<=N;++i)
    {
        Val[i]=(Val[i]+s*Inv%Mod)%Mod;
        s=(s+Val[i])%Mod;
    }
    s=0;
    for(int i=N;i>=1;--i)
    {
        ans[i]=s*Inv%Mod;
        s=(s+Val[i])%Mod;
    }
    for(int i=1;i<=N;++i) write(ans[i],' ');
    return 0;
}
/*
3
1 1 1
*/

qaq

题意

求长度为 $n$ ，字符集大小为 $m$ 的字符串数组的个数，使第 $i$ 个字符串长是 $a_i$ 且是第 $i-1$ 个字符串的子序列。

$2\leq n\leq 10^6,2\leq m<10^9+7,0<a_n\leq a_{n-1}\cdots\leq a_2\leq a_1\leq 10^7$ 。

题解

神仙组合数题，$\text{Dyd}$ 爆切。

对于删除一些字符不太好做的话，考虑逆序整个数列，并把删除操作改为添加操作，把题目转换为在一个字符串中添加一些字符。

一般的方法的话，很有可能会导致计算重复，所以要考虑一种不会重复计算的方法。

首先明晰，第 $i-1$ 个字符串中的所有字符都必须在第 $i$ 个字符串中出现，但这些字符可能是原来就有的，也有可能会存在我们添加的，这样很难搞。

那么，我们强制要求新插入的字符与原字符串不同，以避免重复。

首先考虑插入原有字符，即 $1\sim a_{i-1}$ 种字符，有 $m-1$ 种方式，然后是 $a_{i-1}+1\sim a_i$ 种，每一种有 $m$ 种方案。

上述是字符集的方案，而对于每一种字符集，插入在字符串的顺序和位置不同，方案依然不同，所以现在考虑字符串。

用隔板法得到，当前字符种数为 $j$ 时（$a_{i-1}\leq j\leq a_i$），每一种方案的插入方案为 $\mathbb C^{j-1}_{a_{i-1}-1}$ ，那么，我们就得到了一个答案式：

$\displaystyle ans=a_1^m\times\prod_{i=2}^{n}\sum_{j=a_{i-1}}^{a_i}\mathbb C^{j-1}_{a_{i-1}-1}\times(m-1)^{j-a_{i-1}}\times m^{a_i-j}$

然后递推求解，这样的时间复杂度应该是 $\mathcal O(a_1)$ 的，其中有 $a_1\leq 10^7$ ，所以相当于线性。

要注意的是，因为参与运算的数字都极其巨大，所以可能要爆 long long ，所以一定要及时取模，否则 $100pt\to 30pt$ 。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
const int MAXN=1e7+10;
const int Mod=1e9+7;
int N,M;
ll Len[MAXN],Dp[MAXN];
ll Inv[MAXN],Mul[MAXN],pow_M[MAXN],pow_m[MAXN];
inline ll qPow(ll a,ll b,ll p)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=a*res%p;
        a=a*a%p;b>>=1;
    }
    return res;
}
inline ll C(ll x,ll y)
{
    return Mul[x]*Inv[y]%Mod*Inv[x-y]%Mod;
}
int main()
{
    // freopen("qaq.in","r",stdin);
    // freopen("qaq.out","w",stdout);
    read(N,M);
    for(int i=1;i<=N;++i) read(Len[i]);
    std::reverse(Len+1,Len+N+1);
    int K=Len[N];
    Inv[0]=Mul[0]=pow_M[0]=pow_m[0]=1;
    for(int i=1;i<=K;++i)
        Mul[i]=Mul[i-1]*i%Mod,pow_M[i]=pow_M[i-1]*M%Mod,pow_m[i]=pow_m[i-1]*(M-1)%Mod;
    Inv[K]=qPow(Mul[K],Mod-2,Mod);
    for(int i=K-1;i>=1;--i) Inv[i]=Inv[i+1]*(i+1)%Mod;
    ll ans=qPow(M,Len[1],Mod);
    for(int i=2;i<=N;++i)
    {
        ll res=0;
        for(int j=Len[i-1];j<=Len[i];++j)
            res=(res+C(j-1,Len[i-1]-1)*pow_m[j-Len[i-1]]%Mod*pow_M[Len[i]-j]%Mod)%Mod;
        ans=ans*res%Mod;
    }
    write(ans);
    return 0;
}
/*
2 2
3 1
*/

题解好像不是这么做的，也没看太懂。

贴个代码在这里吧。

AC Code std ver. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 10000005, mod = 1e9 + 7;

int n, m, x, fac[N], ifac[N], ans = 1;

int power(int a, int n) {
  int tp = 1;
  while (n) {
    if (n & 1) tp = 1ll * tp * a % mod;
    a = 1ll * a * a % mod, n >>= 1;
  }
  return tp;
}

int c(int n, int m) { return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod; }

int main() {
  freopen("qaq.in", "r", stdin);
  freopen("qaq.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  cin >> n >> m, x = 1ll * m * power(m - 1, mod - 2) % mod;

  int len;
  cin >> len;
  fac[0] = 1;
  for (int i = 1; i <= len; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
  ifac[len] = power(fac[len], mod - 2);
  for (int i = len - 1; ~i; i--) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;

  while (--n) {
    int len2;
    cin >> len2;

    int tp = 0;
    for (int i = 0, y = 1; i <= len - len2; i++, y = 1ll * y * x % mod)
      tp = (tp + 1ll * c(len - 1 - i, len2 - 1) * y) % mod;
    for (int i = 1; i <= len - len2; i++) tp = 1ll * tp * (m - 1) % mod;

    ans = 1ll * ans * tp % mod, len = len2;
  }
  for (int i = 1; i <= len; i++) ans = 1ll * ans * m % mod;

  cout << ans << endl;
}

quq

题意

有 $n$ 个抽奖机，第 $i$ 个抽奖机可以等概率抽到 $1\sim a_i$ ，求抽到 $1\sim\max a_i$ 的最优策略的期望次数，模数 $19260817$ 。

$1\leq n\leq 10^6,1\leq a_i\leq 10^7$ 。

题解

首先可以考虑 $n=1$ 的情况，这里就有一个排列组合的公式。

在 $n$ 个小球内有放回拿出，使得每一个球至少被拿出一次的期望次数是 $n\log n$ 。

实际上，是 $n(1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n})$ ，然后用调和级数一波操作之后化简为 $n\log n$ ，虽然 $n\log n$ 的计算不支持取模，所以我们这道题还是使用的是第一个式子。

然后考虑最优策略，首先如果我们当前要抽 $x$ ，有两个抽奖机 $a,b$ ，且 $x<a<b$ ，那么，$a$ 中抽到 $x$ 的概率为 $\frac{1}{a}$ ，$b$ 中抽到 $x$ 的概率为 $\frac{1}{b}$ ，很明显，$a$ 的概率大。

那我们不妨大胆构造贪心策略：

首先按照 $a_i$ 的大小排序，对于当前 $a_i$ ，我们把 $a_{i-1}+1\sim a_i$ 的数在这个抽奖机里抽完即可，这样就是最优策略，期望为 $\frac{a_i-a_{i-1}}{a_i}$ ，然后一波递推，时间复杂度依然是线性 $\mathcal O(\max a_i)$ 。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
const int MAXN=1e6+10;
const int MAXC=1e7+10;
const ll Mod=19260817;
int N;
ll Val[MAXN];
inline ll qPow(ll a,ll b,ll p)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%p;
        a=a*a%p;b>>=1;
    }
    return res;
}
namespace Subtask1
{
    int Inv[MAXC];
    inline void init()
    {
        Inv[1]=1;
        for(int i=2;i<=Val[1];++i) Inv[i]=((Mod-Mod/i)*Inv[Mod%i])%Mod;    
    }
    inline bool main()
    {
        init();
        ll res=0;
        for(int i=1;i<=Val[1];++i) res=(res+Inv[i])%Mod;
        write(res*Val[1]%Mod);
        return 0;
    }   
};
ll Inv[MAXC],Sum_inv[MAXC];
ll ans;
int main()
{
    // freopen("quq.in","r",stdin);
    // freopen("quq.out","w",stdout);
    read(N);
    for(int i=1;i<=N;++i) read(Val[i]);
    if(N==1) return Subtask1::main();
    Inv[1]=1;
    std::sort(Val+1,Val+1+N);
    for(int i=2;i<=Val[N];++i) Inv[i]=((Mod-Mod/i)*Inv[Mod%i])%Mod;
    for(int i=N;i>=1;--i)
        for(int j=Val[i];j>Val[i-1];--j)
            ans=(ans+Val[i]*Inv[Val[N]-j+1])%Mod;
    write(ans);
    return 0;
}
/*
3
1 2 3
1
4730771
*/

awa

题意

给定一棵有 $n$ 个结点的树，每一个结点有一种颜色，有 $q$ 次询问，每次询问距离 $x$ 点距离小于等于 $d$ 的结点组成的连通块的颜色种类数。多组数据。

$1\leq T\leq 3,n,q\leq 10^5,1\leq col,x,d\leq n$ 。

$Subtask1:n,q\leq 5000$

$Subtask2:u_i=1$

$Subtask3:u_i=i,v_i=i+1$

$Subtask4:col_i=i$

$Subtask5:No\ more\ conditions$

部分分

这道题部分分极多，且每一个数据前会输出一个 $NUM$ 表示数据编号，非常良心。

对于第一个 $Subtask$ ，可以用一个 $\mathcal O(nq)$ 的暴力树型 $\text{Dp}$ 轻松解决；

对于第二个 $Subtask$ ，是一个以 $1$ 为中心的菊花图，那么，因为有 $d>1$ ，则当 $x=1$ 的询问，都是回答整棵树的颜色种数，而对于其他点，如果有 $d=1$ ，则只需要判断 $1$ 的颜色，否则，依然是整棵树的颜色；

对于第三个 $Subtask$ ，是一条链，则问题转换为求一个区间内的颜色个数，主席树模板题；

对于第四个 $Subtask$ ，可以用点分树来解决，我只想到了点分治，后来 $\text{LuckyLeaves}$ 告诉我只能用点分树，可惜不会，所以拿不到（而且很难写）。

题解

部分分甚至可以拿到 $80pt$ ，赚翻。

虚树神仙题，机房没人写，不可做，$80pt$ 的部分分够了。（然后发现 $\text{Sukwants}$ 正好发布了虚树的学习笔记，被卷死惹）

相关文章