“蔚来杯“2022牛客暑期多校训练营9 A B G (持续更新中)

"蔚来杯"2022牛客暑期多校训练营9 A B E G (持续更新中)

---

A-Car Show

题意： 有 $n$ 个数字，并且数字的种类不超过 $m$ ，问一共有多少个区间满足区间内 $m$ 种数字至少出现 $1$ 次。

思路： 我们可以使用双指针来 $solve$ 此题，$l$ 表示左端点，$r$ 表示右端点，我们通过不断将 $r$ 右移，一旦出现区间 $[l-r]$ 内满足 $m$ 个不同种类数出现至少 $1$ 次，那我们就不断将 $l$ 右移，直至区间内不满足 $m$ 个不同种类的数出现至少 $1$ 次。那么每有区间 $[l,r]$ 满足 $m$ 个不同种类数出现至少 $1$ 次，那么贡献就可以加上 $n-r+1$ 。因为 $[r-n]$ 区间 无论放几个数都一定满足条件 。

代码：

#include
using namespace std;
#define int long long 
const int N = 1e5+10;
int n,m;
int a[N];
signed main(){
   ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   cin>>n>>m;
   for(int i=1;i<=n;i++){
       cin>>a[i];
   }
   set<int>s;
   map<int,int>mp;
   int l=0;
   int ans=0;
   for(int r=1;r<=n;r++){
       s.insert(a[r]);
       mp[a[r]]++;
       if(s.size()==m){
           ans+=n-r+1;
           l++;
           mp[a[l]]--;
           if(mp[a[l]]==0)s.erase(a[l]);
           while(l<r&&s.size()==m){
               l++;
               ans+=n-r+1;
               mp[a[l]]--;
               if(mp[a[l]]==0)s.erase(a[l]);
           }
       }
   }
   cout<<ans<<endl;
   return 0;
}
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

---

B Two Frogs

题意： 有两只青蛙，起始位置在 $1$ 号点，每个点都有一个跳跃区间，跳跃区间内的点落地概率相同，假设 $a[1]=5$ ，那么 $1$ 号点到 $2-6$ 号点的概率相同，求两只青蛙从 $1$ 跳到 $n$ 号点，所有步数的概率之和。

思路: 首先由于青蛙不会呆在原地，所以跳跃次数最多不超过 $n-1$ ，设 $dp[i][j]$ 表示到达 $j$ 点需要 $i$ 步，那么初始状态为 $dp[0][1]=1$ 即消耗 $0$ 步到达 $1$ 的概率为 $1$ 。那么很容易就推出 $dp$ 转移方程 $：$

dp[0][1]=1;
for(int i=1;i<n;i++){//枚举点往后贡献
    for(int j=1;j<=i;j++){//步数肯定不会超过i
        for(int k=1;k<=a[i];k++){//从i能跳跃到的点
            dp[j][i+k]=(dp[j][i+k]+dp[j-1][i]*na[i]%mod)%mod;
        }
    }
}
1
2
3
4
5
6
7
8

但是我们会发现这样做时间复杂度为 $O(n^3)$ ，复杂度是不能 $solve$ 此题的，因此我们需要优化 。容易发现青蛙每次跳跃对一段区间内的点贡献是相同的，那么意味着我们可以用区间加操作，即枚举每一步时用差分来维护贡献，最后跑一遍前缀即每个点在 $dp[i][j]$ 第 $i$ 步中跳跃到 $j$ 点的概率，复杂度为 $O(n^2)$ ，需要注意本题用到逆元 需要预先处理 ，否则会再带一个 $log$ 容易 $tle$。 最终所求的概率之和即平方一下即可。

代码：

#include
using namespace std;
#define int long long 
#pragma GCC optimize(3)
const int N = 8010;
int dp[N][N];
int na[N];
int a[N];
int v[N];
const int mod = 998244353;
int qmi(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<n;i++)cin>>a[i];
    for(int i=1;i<n;i++)na[i]=qmi(a[i],mod-2);
    dp[0][1]=1;
    for(int i=1;i<n;i++){//前缀和优化改成枚举步数
        for(int j=i;j<n;j++){//统计这一回合贡献(差分)
            v[j+1]=(v[j+1]+dp[i-1][j]*na[j])%mod;
            v[j+a[j]+1]=((v[j+a[j]+1]-dp[i-1][j]*na[j])%mod+mod)%mod;
        }
        int sum=0;
        for(int j=i+1;j<=n;j++){
            sum+=v[j];
            sum%=mod;
            v[j]=0;
            dp[i][j]=sum;
        }
    }
    int ans=0;
    for(int i=1;i<n;i++){
        ans+=(dp[i][n]*dp[i][n])%mod;
        ans%=mod;
    }
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int _=1;
    // cin>>_;
    while(_--){
        solve();
    }
    return 0;
}
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

---

G Magic Spells

题意： 给定不超过 $5$ 个字符串，统计这些字符串中公有的不同回文串数量，下标不同若回文串相同认为是同一个回文串。

思路： $manacher$ + $hash$ ， $manacher$ 用来统计每个字符串中的回文子串的左右端点，$hash$ 用于 $O(1)$ 查询该回文子串是否出现，并放入 $set$ 进行记录。最终如果一个回文子串出现个数和字符串个数相同那么说明该回文子串在所有字符串中皆出现过，总贡献 $+1$ 。前面部分都不是难点，该题毒瘤 难点在于会卡掉 $ull$ 自然溢出的情况。因此要开两个 $hash$ 一个自然取模，另一个设定一个模数例如 $1e9+7$ ，减少冲突，方可 $ac$ 。

代码：

#include
using namespace std;
#define int long long
#define PII pair<ll,ll>
typedef unsigned long long ull;
const int N = 6e5+10,P=131;
const ull mod = 1e9+7;
ull h1[N],h2[N],p1[N],p2[N];
map<pair<ull,ull>,int>v;
set<pair<ull,ull>>s;
set<pair<int,int>>v2;
char a[N];
char b[N];
int p[N];
int res;
int t;
int n;
pair<ull,ull> find(int l,int r){//降低冲突
    return {(h1[r]-h1[l-1]*p1[r-l+1]%mod+mod)%mod,(h2[r]-h2[l-1]*p2[r-l+1])};
}
void manacher(){
    int mr=0,mid;
    memset(p,0,sizeof p);
    for(int i=1;i<n;i++){//首尾是$^
        if(i<mr)p[i]=min(p[mid*2-i],mr-i);//p[mid*2-i]就是j
        else p[i]=1;
        int l=i-p[i]+1,r=i+p[i]-1;
        while(b[i-p[i]]==b[i+p[i]]){
            p[i]++;
            if(p[i]<2)continue;
            int l=i-p[i]+1,r=i+p[i]-1;
            if(b[l]!='#') continue;
            v2.insert({l,r});//当前字符串的回文子串左右端点
        }
        if(i+p[i]>mr){
            mr=i+p[i];
            mid=i;
        }
    }
}
void init(){
    int k=0;
    b[k++]='$';b[k++]='#';
    for(int i=0;i<n;i++)b[k++]=a[i],b[k++]='#';
    b[k++]='^';
    n=k;
    s.clear();v2.clear();
}
signed main(){
    scanf("%d",&t);
    for(int tt=1;tt<=t;tt++){
        scanf("%s",a);
        n=strlen(a);
        init();
        manacher();
        p1[0]=1;p2[0]=1;
        for(int i=1;i<n-1;i++){
            h1[i]=(h1[i-1]*P+b[i]-'#')%mod;//mod 1e9+7
            p1[i]=(p1[i-1]*P)%mod;
        }
        for(int i=1;i<n-1;i++){
            h2[i]=(h2[i-1]*P+b[i]-'#');
            p2[i]=(p2[i-1]*P);
        }
        for(auto x:v2){
            int l=x.first,r=x.second;
            auto get=find(l,r);
            s.insert(get);
        }
        for(auto x:s){
            v[x]++;
            if(tt==t&&v[x]==t)res++; 
        }
        for(int i=0;i<=n;i++)a[i]='\0',b[i]='\0';
    }
    cout<<res<<endl;
    return 0;
}

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

---

E Longest Increasing Subsequence

题意： 构造一个 $1,2,...,n$ 的排列，使其 恰好有 $m$ 个不同的最长上升子序列。

思路： 参考至 严格鸽 ，图文搭配更易理解。

代码：

#include
using namespace std;
#define int long long 
#pragma GCC optimize(3)
#define re register int
typedef pair<int,int>PII;
#define pb push_back
#define mb pop_back
#define debug(a) cout<<a<<' ';
#define fer(i,a,b) for(re i=a;i<=b;i++)
#define der(i,a,b) for(re i=a;i>=b;i--)
const int N = 110;
int a[N];
void cf(){
    int n;
    cin>>n;
    int bit = 0;
    int nn=n;
    while(nn){
        bit++;
        nn>>=1;
    }
    int need=bit-1;
    int st=need*2+1;
    nn=n;
    int sum=0;
    for(int i=need-1;i>=0;i--){
        if((nn>>i)&1){
            a[i]=need-i-sum;
            sum+=a[i];
        }
        else a[i]=0;
    }
    cout<<sum+st<<endl;
    for(int i=0;i<need;i++){
        for(int j=1;j<=a[i];j++)cout<<st<<' ',st++;
        cout<<(i+1)*2<<' '<<(i+1)*2-1<<' ';
    }
    cout<<st<<endl;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int _=1;
    cin>>_;
    while(_--){
        cf();
    }
    return 0;
}
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