【题目记录】——2021牛客暑期多校训练营5

快来打我* 2022-08-29 10:02 96阅读 0赞

### 文章目录 ###

*  B Boxes 数学 概率
 *  D double strings 思维，模拟
 *  H Holding Two 思维
 *  K King of Range 队列模拟，思维

题目集地址 [2021牛客暑期多校训练营5][2021_5]  
这次题目集做的有点差，只做出了H题

# B Boxes 数学 概率 #

题目地址【[B Boxes][]】  
题意：  
思路：两种情况第一种情况就是不问，即 Σ w \[ i \] \\Sigma w\[i\] Σw\[i\]。  
第二种情况需要询问，先加上C。之后枚举需要问几个才能确定，答案为 C + Σ p r e \[ i \] ∗ ( 1 2 ) n − i C+\\Sigma pre\[i\]\*(\\frac\{1\}\{2\})^\{n-i\} C\+Σpre\[i\]∗(21)n−i取最小值输出即可。  
AC代码：

#include <bits/stdc++.h>
    typedef long long ll;
    const int MAXN = 1e5 + 10;
    double w[MAXN], C, pre[MAXN];
    int n;
    int main()
    { 
        scanf("%d%lf", &n, &C);
        for (int i = 1; i <= n; ++i)
            scanf("%lf", &w[i]);
        std::sort(w + 1, w + 1 + n);
        for (int i = 1; i <= n; ++i)
            pre[i] = pre[i - 1] + w[i];
        double p = 0.5, ans = C;
        for (int i = n - 1; i >= 1; --i, p *= 0.5)
            ans += p * pre[i];
        printf("%.10lf\n", std::min(ans, pre[n]));
        return 0;
    }

# D double strings 思维，模拟 #

题目地址【[D double strings][]】  
题意：给定两个字符串，从各自中选择一个长度相同的子串，找好的方案的个数，好的方案的构成是“一段相同的前缀+一个不同字符（a比b小）+长度相同的任意后缀”。  
思路： d p 1 \[ i \] \[ j \] dp1\[i\]\[j\] dp1\[i\]\[j\]：A串前i个字母与B串前j个字母的等长公共子序列个数(包括空串)  
 d p 1 \[ i \] \[ j \] = d p 1 \[ i − 1 \] \[ j \] + d p 1 \[ i \] \[ j − 1 \] − d p 1 \[ i − 1 \] \[ j − 1 \] \[ A \[ i \] ≠ B \[ j \] \] dp1\[i\]\[j\]=dp1\[i-1\]\[j\]+dp1\[i\]\[j-1\]-dp1\[i-1\]\[j-1\]\[A\[i\]\\not =B\[j\]\] dp1\[i\]\[j\]=dp1\[i−1\]\[j\]\+dp1\[i\]\[j−1\]−dp1\[i−1\]\[j−1\]\[A\[i\]=B\[j\]\]  
 d p 2 \[ i \] \[ j \] dp2\[i\]\[j\] dp2\[i\]\[j\]：A串前i个字母与B串前j个字母中选择等长的公共子序列并满足A串的子序列字典序小于B串子序列字典序的子序列个数  
 d p 2 \[ i \] \[ j \] = d p 2 \[ i − 1 \] \[ j \] + d p 2 \[ i \] \[ j − 1 \] + d p 1 \[ i − 1 \] \[ j − 1 \] \[ A \[ i \] < B \[ j \] \] dp2\[i\]\[j\]=dp2\[i-1\]\[j\]+dp2\[i\]\[j-1\]+dp1\[i-1\]\[j-1\]\[A\[i\]<B\[j\]\] dp2\[i\]\[j\]=dp2\[i−1\]\[j\]\+dp2\[i\]\[j−1\]\+dp1\[i−1\]\[j−1\]\[A\[i\]<B\[j\]\]  
转移即可。注意dp1的初始化。  
AC代码：

#include <bits/stdc++.h>
    typedef long long ll;
    const int MAXN = 5e3 + 10, MOD = 1e9 + 7;
    int dp1[MAXN][MAXN], dp2[MAXN][MAXN];
    char a[MAXN], b[MAXN];
    int main()
    { 
        scanf("%s%s", a + 1, b + 1);
        int n = strlen(a + 1), m = strlen(b + 1);
        for (int i = 0; i <= m; ++i)
            dp1[0][i] = 1;
        for (int i = 0; i <= n; ++i)
            dp1[i][0] = 1;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
            { 
                dp1[i][j] = ((dp1[i - 1][j] + dp1[i][j - 1] - dp1[i - 1][j - 1]) % MOD + MOD) % MOD;
                if (a[i] == b[j]) dp1[i][j] = (dp1[i][j] + dp1[i - 1][j - 1]) % MOD;
            }
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
            { 
                dp2[i][j] = (dp2[i - 1][j] + dp2[i][j - 1]) % MOD;
                if (a[i] < b[j]) dp2[i][j] = (dp2[i][j] + dp1[i - 1][j - 1]) % MOD;
            }
        printf("%d\n", dp2[n][m]);
        return 0;
    }

# H Holding Two 思维 #

题目地址[H Holding Two][]  
题意：输出一个n*m大小的01矩阵，满足条件每行连续3个每列连续3个或者每一斜着的连续三个元素不完全相同，问满足条件的矩阵是否存在，存在则输出，否则输出-1；  
思路：经过思考发现不可能不存在这样的矩阵，因为构造一个很大的矩阵例如110011001100…第二行001100110011…第三行又重复第一行如此循环，这个矩阵中随意挑一个n*m的矩阵都满足条件。  
AC代码：

#include <bits/stdc++.h>
    
    using namespace std;
    
    int f[1001][1001];
    int main()
    { 
    	cin.sync_with_stdio(0);
    	cin.tie(0);
        for(int i = 1;i <= 1000;i++)
        { 
            for(int j = 1;j <= 500;j++)
            { 
                if(i&1)
                { 
                    if(j&1)
                    { 
                        f[i][2*j-1] = 1;
                        f[i][2*j] = 1;
                    }
                    else
                    { 
                        f[i][2*j-1] = 0;
                        f[i][2*j] = 0;
                    }
                }
                else
                { 
                    if(j&1)
                    { 
                        f[i][2*j-1] = 0;
                        f[i][2*j] = 0;
                    }
                    else
                    { 
                        f[i][2*j-1] = 1;
                        f[i][2*j] = 1;
                    }
                }
            }
        }
        int n,m;
        cin >> n >> m;
        for(int i = 1;i <= n;i++)
        { 
            for(int j = 1;j <= m;j++)
            { 
                cout << f[i][j];
            }
            cout << endl;
        }
        return 0;
    }

# K King of Range 队列模拟，思维 #

题意：给定一个长为n的序列和m次询问，每次询问给定一个k值，问有多少个区间的范围大于k，范围指的是区间最大值和最小值的差。  
思路：一个线性的做法：注意到因为区间端点都是单调的，所以可以维护两个单调队列，其中一个递增序列，队首维护最小值，一个递减序列，队首维护最大值，每次弹出两个队列中队首靠前的一个，直到极差 ≤ k。那么就可以在均摊 O(1) 的时间内求 Ri 了。  
AC代码：

/* ** Author:skj ** Time:2021-7-31 ** function:K */
    #include <bits/stdc++.h>
    #define maxn int(1e5+2)
    #define ll long long
    using namespace std;
    int a[maxn];
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    	cin.sync_with_stdio(0);
    	cin.tie(0);
        int n, m;
        cin >> n >> m;
        for(int i = 1;i <= n;i++)
        { 
            cin >> a[i];
        }
        ll ans = 0;
    
        while(m--)
        { 
            deque<int> maxi,mini;//maxi队首为最大值，单调递减序列。mini队首为最小值，单调递增序列。
            int k;
            cin >> k;
            int j = 1;
            for(int i = 1;i <= n;i++)
            { 
                while(!maxi.empty()&&a[maxi.back()]<a[i])//维护递减序列
                { 
                    maxi.pop_back();
                }
                maxi.push_back(i);
                while(!mini.empty()&&a[mini.back()]>a[i])//维护递增序列
                { 
                    mini.pop_back();
                }
                mini.push_back(i);
                while(a[maxi.front()]-a[mini.front()]>k)
                { 
                    while(j <= min(maxi.front(),mini.front()))//j相当于区间左端点，右移。
                    { 
                        ans += (ll)n + 1 - max(maxi.front(),mini.front());
                        j++;
                    }
                    if(maxi.front()==j-1)
                    { 
                        maxi.pop_front();
                    }
                    if(mini.front()==j-1)
                    { 
                        mini.pop_front();
                    }
                }
            }
            cout << ans << endl;
            ans = 0;
        }
        return 0;
    }

[2021_5]: https://ac.nowcoder.com/acm/contest/11256
[B Boxes]: https://ac.nowcoder.com/acm/contest/11256/B
[D double strings]: https://ac.nowcoder.com/acm/contest/11256/D
[H Holding Two]: https://ac.nowcoder.com/acm/contest/11256/H