今天写到E题，来写个小小题解吧！

A

题意

给你一个字符串s，删除前面n个和后面n个字母，然后输出

思路

使用substr进行截取

代码

1
2
3
4
5
6
7
8
9
10
11
void solve()
{
    string s;
    cin>>s;
    int n;
    cin>>n;
    s=s.substr(n);
    int len=s.size();
    s=s.substr(0,len-n);
    cout<<s<<"\n";
}

B

题意

给你一个二维数组，问每一个单元格的相邻的单元格数

思路

超出范围的不算，我们可以假设都为4，然后如果有在边上的就剪掉

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve()
{
   int n,m;
   cin>>n>>m;
   for(int i=1;i<=n;++i)
   {
        for(int j=1;j<=m;++j)
        {
            int f=4;
            if(i==1) f--;
            if(i==n) f--;
            if(j==1) f--;
            if(j==m) f--;
            cout<<f<<" ";
        }
        cout<<'\n';
   }
}

C

题意

给你一个字符串s，寻找奇数并且"C"在中间的子串个数（不同位置的子串不同）

思路

只要找到每一个位置的”C“，并且计算在每个位置的最长的子串长度的一半，全部加起来

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve()
{
    string s;
    cin>>s;
    int len=s.size();
    ll cnt=0;
    for(int i=0;i<len;++i)
    {
        if(s[i]=='C')
        {
            cnt++;//单独的"C"也是一个子串
            cnt+=min(i,len-i-1);//最长的长度取决于比较短的一边
        }
    }
    cout<<cnt<<"\n";
}

D

题意

给你一个x，然后进行q次加入ai和bi构成序列，并且查询序列的中位数

思路

刚开始以为是中间数，然后觉得怎么这么简单好奇怪，然后看了看样例
噢!中位数啊，要排序的！！！
然后想着排序？？于是想到优先队列（堆），但是呢这个是取中间的，不是求最大和最小啊
那我用两个！一大一小。
l是大根堆 用来存储所有数字中较小的那一半。 l.top()较小那一半之中的最大值。
r是小根堆（通过使用存入负值）用来存储所有数字中较大的那一半。r.top() 取负数后代表较大那一半之中的最小值。
因为每次循环都会同时插入两个数。加上初始的 1 个数，总数字个数序列永远是奇数。所以中位数是l.top()

代码

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
priority_queue<int> l,r;
void insert(int x)
{
    if(l.empty()||x<=l.top())
    {
	    // 比左边最大值还小，说明属于较小的一半
        l.push(x);
    }
    else{
	    // 比左边最大值大，说明属于较大的一半（存负数变小根堆）
        r.push(-x);
    }
    //调整两个堆的大小，左堆大小=右堆大小+1(保证l.top()是答案)
    if(l.size()>r.size()+1)
    {
        r.push(-l.top());
        l.pop();
    }
    else if(r.size()>l.size())
    {
        l.push(-r.top());
        r.pop();
    }
}
void solve()
{
    int x;
    cin>>x;
    insert(x);
    int q;
    cin>>q;
    while(q--)
    {
        int a,b;
        cin>>a>>b;
        insert(a);
        insert(b);
        cout<<l.top()<<"\n";
    }
}

E

题意

序列A满足有x1个1，x2个2，x3个3，并且 ∣ai+1​−ai​∣≤1 
问这样的A的个数，答案模998244353

思路

第一反应动态规划，正准备想转移状态，看了一下x1,x2,x3的范围，1~1e6,好吧，动态规划pass~~
重新开始看题目条件， ∣ai+1​−ai​∣≤1 ，那么我们推出 1和 3 绝对不能相邻，中间必须有2来隔开
那么！我们可以将2看成隔板，将1和3插入其中
将x2个 2 划分出的 x2+1 个空隙，每一个空隙要么全放 1（且至少放一个），要么全放 3（且至少放一个），要么都不放。
假设一共选了 i 个空隙来放 1，选了 j 个空隙来放 3。

  1. 选择空隙的位置：
    从 x2+1个空隙中选出 i 个放 $1$，再从剩下的空隙中选出j个放 $3$,方案数为：
    $\binom{x2+1}{i} \cdot \binom{x2+1-i}{j}$
  2. 分配元素的数量：
  • 将 $x1$ 个相同的 $1$ 放入 $i$ 个非空的空隙中，方案数为：$\binom{x1-1}{i-1}$
  • 将 $x3$ 个相同的 $3$ 放入 $j$ 个非空的空隙中，方案数为：$\binom{x3-1}{j-1}$
    所以，对于i和 j，合法的排列数为：

$$f(i, j) = \binom{x2+1}{i} \binom{x2+1-i}{j} \binom{x1-1}{i-1} \binom{x3-1}{j-1}$$

然后我们对每一个i和j进行计算，但是这样时间就是1e12，oh no!TLE!
我们要在进行优化
当 $i$ 固定时，我们需要对 $j$ 进行求和：

$$\sum_{j=1}^{x3} \binom{x2+1}{i} \binom{x2+1-i}{j} \binom{x1-1}{i-1} \binom{x3-1}{j-1}$$

将与 $j$ 无关的项提出来：

$$\binom{x2+1}{i} \binom{x1-1}{i-1} \sum_{j=1}^{x3} \binom{x2+1-i}{j} \binom{x3-1}{j-1}$$

利用恒等式 $\binom{x3-1}{j-1} = \binom{x3-1}{x3-j}$，后面的求和项变为：

$$\sum_{j=1}^{x3} \binom{x2+1-i}{j} \binom{x3-1}{x3-j}$$

根据范德蒙德恒等式，这个求和等于从两堆物品（一堆 x2+1-i 个，另一堆 x3-1个）中一共选出 j + (x3-j) = x3 个物品的方案数
即：

$$\sum_{j=1}^{x3} \binom{x2+1-i}{j} \binom{x3-1}{x3-j} = \binom{x2+x3-i}{x3}$$

然后我们惊奇的发现 j 没掉了！
注意：i的个数不能大于x1,也不能大于可用的空隙x2+1
那么我们可以推出总方案数可以表示为：
$$ans = \sum_{i=1}^{\min(x1, x2+1)} \binom{x2+1}{i} \binom{x1-1}{i-1} \binom{x2+x3-i}{x3} \pmod{998244353}$$
代码上面
我们需要求组合数C，我们对阶乘 fact[]和逆元阶乘 invfact[]进行预处理
运用费马小定理和快速幂来求出最后一个invfact[N-1],然后倒推剩下的invfact[]

代码

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
const int N=3e6+5,mod=998244353;
ll fact[N],invfact[N];
//快速幂
ll pw(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1)
            res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
void pre()
{
    fact[0]=1;
    invfact[0]=1;
    for(int i=1;i<N;++i)
    {
        fact[i]=(fact[i-1]*i)%mod;
    }
    //费马小定理
    invfact[N-1]=pw(fact[N-1],mod-2);
    for(int i=N-2;i>=1;--i)
    {
        invfact[i]=(invfact[i+1]*(i+1))%mod;
    }
}
ll C(int n,int k)
{
    if(k<0||k>n) return 0;
    return fact[n]*invfact[k]%mod*invfact[n-k]%mod;
}
void solve()
{
    pre();
    int x1,x2,x3;
    cin>>x1>>x2>>x3;
    ll ans=0;
    //i的个数不能大于x1,也不能大于可用的空隙x2+1
    int n=min(x1,x2+1);
    for(int i=1;i<=n;++i)
    {
        ll sum1=C(x2+1,i)%mod;
        ll sum2=C(x1-1,i-1)%mod;
        ll sum3=C(x3+x2-i,x3)%mod;
        ll now=((sum1*sum2)%mod*sum3)%mod;
        ans=(ans+now)%mod;
    }
    cout<<ans<<"\n";
}