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;
}
投递字节跳动等公司10个岗位 >