3.24字节笔试题解

分享题解攒人品

（写题能力严重退化~

第一题

题意：凸多边形有n条边，每条边上ai个标记，问选三个标记组成三角形的方案数，对1e9+7取模(n<=1e5, ai <=1e9)

思路：dp

dp[i][j]表示前i条边取了j个标记，有转移式

dp[i][j+k] += dp[i-1][j] + C(ai, k) 第i条边取了k个标记。

由于j不超过3，k不超过2，且C(ai, k)可以直接乘除得到，复杂度O(n)

看到有大佬容斥思路做的，很妙，没想到哈哈哈。

第二题

题意: 给定一个字符串，求包含"byte"或者"dance"的子串数量(字符串长度不超过1e5)

思路：数数

先求出所有byte,dance子串的位置，我们记为一个区间[l,r]，我们知道既然byte是个合法串，那么[l,r]区间往左往右延伸都是合法的。

然后就是怎么不重复计数了。我们对区间[l,r]按照l排序，从左往右扫，每个区间贡献是(l - last_l) * (n -1 - r + 1)，其中last_l表示上个区间的左端点，n表示字符串总长。只要保持当前区间的左端点，不超过上个区间左端点就不会重复计数。复杂度O(n)

第三题

题意: 给n个二元组，每个二元组<u,v>表示v个u，比如<1,3>表示1 1 1。然后q次询问，每次问区间[l, r]和。（n<=1e5,u,v<=1e9）

思路：前缀和，二分，数数

对u和v分别做前缀和，u的前缀和sum数组，v的前缀和cnt数组。

对于询问[l,r]我们先在cnt数组中用lower_bound或者二分找到对应的下标pl和pr

答案则为sum[pr-1] - sum[pl] + (cnt[pl] - l + 1) * 对应的u + (r - cnt[pr-1] ) * 对应的u，复杂度O(n + qlogn)

怎么理解呢，把[pl,pr]拆成[pl+1, pr - 1] 还有pl和pr单独两个点算贡献。[pl+1, pr - 1]区间肯定是吃满每个数和数量的贡献，这里用前缀和算下就可以。pl和pr单独两个点就要看多出或者缺少多少个数组，然后乘上对应的u，这里说的有点抽象。。。

贴个代码吧

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int mod = 1e9 + 7;
const int N = 1e5 + 10;;
int n, q;
int sum[N], cnt[N];
array<int, 2> E[N];
signed main() {
    cin >>n;
    for(int i = 1; i <=n; i++){
        int u, v;cin >> u >> v;
        E[i] = {u, v};
        cnt[i] = (cnt[i-1] + v);
        sum[i] = (sum[i-1] + u * v % mod) % mod;
    }
    cin >> q;
    while(q--){
        int l, r;
        cin >> l >> r;
        int pl = lower_bound(cnt+1, cnt+1+n, l) - cnt;
        int pr = lower_bound(cnt+1, cnt+1+n, r) - cnt;
        int ans = (pr - 1 >= pl + 1 ? (sum[pr-1] - sum[pl] + mod) % mod : 0);
        if(pl==pr){
            ans += (r - l  + 1) * E[pl][0] % mod;
            ans %= mod;
        }else {
            ans += (cnt[pl] - l  + 1 + mod) % mod * E[pl][0] % mod; 
            ans %= mod;
            ans += (r - cnt[pr-1] + mod) * E[pr][0] % mod;
            ans %= mod;
        }
        cout << ans << endl;
    }
}

第四题

题意: 给01矩阵，行不超过5，列不超过1000。其中有些位置是问号'?'。现在要把'?'变成01，不能出现相邻的1，问合法方案数，对1e9+7取模。

思路：dp,状压

由于就5行，2^5也就32。

dp很容易想dp[i][s]，表示第i列的字符串状态为s，s即二进制状压。

if(i列和i-1列没有相邻1) , 有转移dp[i][s] += dp[i-1][k]，复杂度O(4 ^n * m)

代码是难写点。凭回忆写了下大概。

这里状压有个特殊之处，就是01已知的地方就用已知的数表示即可，比如某列式01?（我把列横过来），的状态压缩是010或者011。所以下面我在check函数中首先会去check这个状态的合法性（代码11到14行）。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int mod = 1e9 + 7;
const int N = 1e5 + 10;;
int n, m;
int dp[1010][31];
string s[10];
bool check(int col, int col_state, int last_col_state){
    for(int i = 0; i < n; i++){
        if(s[i][col] != '?' && ((col_state>>i&1) != s[i][col] - '0')){
            return false;
        }
    }
    for(int i = 0; i < n; i++){
        int k = s[i][col] == '?' ? col_state>>i&1 : s[i][col] - '0';
        if(k){
            // 与上一行进行check
            int last_col_k = col_state>>(i-1)&1;
            if(last_col_k){
                return false;
            }
        }
    }
    // 与前一列check
    // 第一列无需与上一列check
    if(col){
        for(int i = 0; i < n; i++){
            int k = s[i][col] == '?' ? col_state>>i&1 : s[i][col] - '0';
            int last_col_k = last_col_state>>i&1;
            if(k == 1 && k == last_col_k){
                return false;
            }
        }
    }
    return true;
}
signed main() {
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> s[i];
    }
    for(int i = 0; i < m; i++){
        for(int j = 0; j < (1<<n); j++){
            if(i){
                for(int k = 0; k < (1<<n); k++){
                    if(dp[i - 1][k] && check(i, j, k)){
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;
                    }
                }
            }
            else {
                if(check(i, j, -1)){
                    dp[i][j]++;
                }
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < (1<<n) ; i++){
        ans = (ans + dp[m-1][i])%mod;
    }
    cout << ans;
}