2023 暑假集训模拟赛题解集

发表于 更新于 本文字数： 1.2k 阅读时长 ≈ 4 分钟

Day 1

T1 划

题意：给一个长度为 nn 的序列 aa 和一个 dd，求最长的子区间 [l,r][l,r]，使得区间内的数排序之后相邻元素相差不超过 dd，要求输出找到的区间长度。n≤3×105,0≤ai≤109n\leq 3\times 10^5,0\leq a_i\leq 10^9

即找到最大的区间使得每个除了区间最大值以外的元素 xx 都有 ≤x+d\leq x+d 的元素存在。

那么我们只需要跑出所有元素的左边和右边第一个 ≤x+d\leq x+d 的元素，这个可以用 setset 维护；还需要知道所有元素的左边和右边最大的区间使得该元素为此区间的最大值，可以用单调栈维护

然后枚举 rr ，用线段树维护其最小的左端点即可，时间复杂度为 O(nlog⁡n)O(n\log n)。

代码里有一点点注释。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+5;
const int inf=1e9+5;
int n,d,ans;
struct node
{
    int val,id;
}a[maxn];
int ld[maxn],rd[maxn],l1[maxn],r1[maxn];
//ld[i] 表示 i 左边第一个 <= a[i].val+d 的位置
//rd[i] 同理
//l1[i] 表示 i 左边使 [l1[i],i] 中最大值为 a[i].val 的最大区间的左端点
//r1[i] 同理
inline bool cmp1(node x,node y) {return x.val<y.val;}
inline bool cmp2(node x,node y) {return x.id<y.id;}
set<int> now;
int st[maxn],top;
struct operation
{
    int l,r,v;
};
vector<operation> opt[maxn];

struct segment_tree //线段树维护左端点
{
    int mn[maxn<<2],tag[maxn<<2];

    inline void push_up(int p)
    {
        mn[p]=min(mn[p*2],mn[p*2+1]);
    }
    inline void push_tag(int p,int v)
    {
        mn[p]+=v;
        tag[p]+=v;
    }
    inline void push_down(int p)
    {
        if(tag[p])
        {
            push_tag(p*2,tag[p]);
            push_tag(p*2+1,tag[p]);
            tag[p]=0;
        }
    }
    void add(int p,int l,int r,int nl,int nr,int v)
    {
        if(l>=nl&&r<=nr)
        {
            push_tag(p,v);
            return ;
        }
        if(r<nl||l>nr) return;
        push_down(p);
        int mid=(l+r)/2;
        if(mid>=nl) add(p*2,l,mid,nl,nr,v);
        if(mid<nr) add(p*2+1,mid+1,r,nl,nr,v);
        push_up(p);
    }
    int query(int p,int l,int r)
    {
        if(mn[p]!=0) return r+1;
        if(l==r) return l;
        push_down(p);
        int mid=(l+r)/2;
        if(mn[p*2]==0) return query(p*2,l,mid);
        else return query(p*2+1,mid+1,r);
    }
}tree;

int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>d;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].val;
        a[i].id=i;
    }    
    sort(a+1,a+1+n,cmp1);
    for(int i=n,l=n+1,r=n;i>=1;i--)
    {
        while(l>1&&a[l-1].val!=a[i].val) now.insert(a[--l].id);
        while(a[r].val-a[i].val>d) now.erase(a[r--].id);
        auto it=now.lower_bound(a[i].id);
        if(it!=now.end()) rd[a[i].id]=*it;
        else rd[a[i].id]=inf;
        if(it!=now.begin()) ld[a[i].id]=*--it;
        else ld[a[i].id]=-inf;
    }
    sort(a+1,a+1+n,cmp2);
    for(int i=n;i>=1;i--) //单调栈
    {
        while(top&&a[st[top]].val<=a[i].val) --top;
        if(top) r1[i]=st[top];
        else r1[i]=inf;
        st[++top]=i;
    }
    top=0;
    for(int i=1;i<=n;i++)
    {
        while(top&&a[st[top]].val<=a[i].val) --top;
        if(top) l1[i]=st[top];
        else l1[i]=-inf;
        st[++top]=i;
    }
    for(int i=1;i<=n;i++)
    {
        if(r1[i]<=n)
        {
            opt[r1[i]].push_back({ld[i]+1,i,1});
            if(rd[i]<=n) opt[rd[i]].push_back({ld[i]+1,i,-1});
        }
        opt[i].push_back({ld[i]+1,l1[i],1});
        if(rd[i]<=n) opt[rd[i]].push_back({ld[i]+1,l1[i],-1}); 
    }
    for(int r=1;r<=n;r++)
    {
        for(auto tmp:opt[r]) tree.add(1,1,n,tmp.l,tmp.r,tmp.v);
        ans=max(ans,r-tree.query(1,1,n)+1);
    }
    cout<<ans<<endl;
    return 0;
}

T2 Heinrich

std 10 kb 的带毒瘤题，果断放弃（

T3 朝花夕拾

题目大意：求解 xq≡a (mod p)x^q\equiv a\ (mod \ p)

Day 2

天−1∈R属实逆天天^{-1}\in \R\\ 属实逆天

有时间慢慢补

Day 3

T1 禁止复读

题意：给定 n,m,kn,m,k，mm 为字符集大小，问有多少长为 nn 的字符串满足不存在长度为 2k2k 的连续字串使得前一半和后一半相同，答案对 998244353998244353 取模，1≤2k≤n≤5×107,2≤m<9982443531\leq 2k\leq n\leq 5\times 10^7,2\leq m<998244353。

出题人的题解很复杂的样子，这里给出的是我在 QQ 群里看到的更简单的思路。

设 fi,jf_{i,j} 前 ii 位，已经和 i−k−ji-k-j 开始的子串匹配了 jj 位的方案数，其中 0≤j<k0\leq j<k，则：

fi,0=(m−1)×∑jfi−1,jfi,j=fi−1,j−1(i>k,j>0)fi,j=0(i≤k,j>0)\begin{aligned} f_{i,0}&=(m-1)\times\sum\limits_j f_{i-1,j}\\ f_{i,j}&=f_{i-1,j-1}(i>k,j>0)\\ f_{i,j}&=0 (i\leq k,j>0) \end{aligned}

然后可以发现第二种转移可以转化成 fi,j=fi−j,0f_{i,j}=f_{i-j,0}，因此只需要维护 fi−k,0f_{i-k,0} 至 fi−1,0f_{i-1,0} 的和即可，答案即为 ∑jfn,j\sum\limits_j f_{n,j}

代码非常简短，跑得也挺快

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e7+5;
const int mod=998244353;
ll n,m,k;
ll f[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    f[k]=1;
    for(int i=1;i<=k;i++) f[k]=f[k]*m%mod;
    ll sum=f[k];
    for(int i=k+1;i<=n;i++)
    {
        f[i]=(m-1)*sum%mod;
        sum=(sum-f[i-k]+f[i]+mod)%mod;
    }
    cout<<sum<<endl;
    return 0;
}