HJ139 小红的01子序列计数（hard）
- 题目
- 题解(4)
- 讨论(2)
- 排行
较难 通过率：13.63% 时间限制：1秒 空间限制：1024M
知识点动态规划
校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
小红定义一个字符串的权值为，该字符串包含的 "01""01"子序列[1][1]的数量。
现在小红拿到了一个由字符 ‘0’‘0’ 和 ‘1’‘1’ 组成的字符串环（即最后一个字符下一个是第一个字符）。现在小红想知道，这个环的所有长度不小于 22 的连续子串[2][2]权值之和是多少？
由于答案可能很大，请将答案对 (109+7)(109+7) 取模后输出。
"01""01"子序列[1][1]为从原字符串中删除任意个（可以为零、可以为全部）字符得到的新字符串，字符串恰好为 "01""01"。
子串[2][2]为从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。在本题中，环上的子串为，任取两个下标 ll 和 rr，从 ll 不断向右取直到 rr 形成的连续子串；特殊的，若 r<lr<l，则会从 ll 向右取到最后一个字符，之后从第一个字符取到 rr。
输入描述：
第一行输入一个正整数 n(1≦n≦105)n(1≦n≦105) 代表字符串的长度。
第二行输入一个长度为 nn、由字符 ‘0’‘0’ 和 ‘1’‘1’ 构成的字符串 ss。
输出描述：
输出一个整数，代表所有长度不小于 22 的连续子串的权值之和。由于答案可能很大，请将答案对 (109+7)(109+7) 取模后输出。
示例1
输入：
3 001
复制输出：
4
复制说明：
在这个样例中，长度为 22 的连续子串有 33 个： ∙ ∙"00""00"，权值为 00； ∙ ∙"01""01"，权值为 11； ∙ ∙"10""10"，权值为 00。 长度为 33 的连续子串有 33 个： ∙ ∙"001""001"，权值为 22； ∙ ∙"010""010"，权值为 11； ∙ ∙"100""100"，权值为 00。 所有长度不小于 22 的连续子串的权值之和为 0+1+0+2+1+0=40+1+0+2+1+0=4 。
#include <iostream> #include <string> using namespace std; #define rep(i, a, b) for (int i = (a), _##i = (b); i <= _##i; ++i) using ll = long long; const int N = 1e5 + 5; const int mod = 1e9 + 7; // 全局变量 ll ans = 0; // 最终答案 ll sum = 0; // 当前窗口内0的数量，用于辅助更新 ll num0 = 0; // 当前窗口内0的数量 ll sum0 = 0; // 当前窗口内所有0的下标之和 ll num1 = 0; // 当前窗口内1的数量 ll sum1 = 0; // 当前窗口内"01"子序列数量 void solve() { int n; cin >> n; string s; cin >> s; // 为了模拟环形，把s复制一份自己接到自己后面，并在前面加空格使下标从1开始 s = " " + s + s; // 初始化滑动窗口，处理前n个字符 rep(i, 1, n) { if (s[i] == '0') { num0++; sum0 += i; } else { // s[i] == '1' num1++; sum1 += sum0; // 新加入的1，与之前所有0形成"01"子序列 sum += num0; // 统计出现过的0的数量 } } // 滑动窗口，处理后续n个字符 rep(i, n + 1, 2 * n) { // 移除窗口左端点元素 i - n 的影响 sum1 -= sum; // 去掉以移除元素为起点产生的贡献 sum0 -= num0; // 更新所有0下标和 if (s[i - n] == '0') { num0--; // 0数量减少 sum -= num1; // 0被移除，减少对后续1的贡献 } else { num1--; // 1数量减少 // 移除1不会影响sum } // 加入新的元素 s[i] if (s[i] == '0') { num0++; sum0 += n; // 加入0，位置视为n（窗口固定大小） } else { // s[i] == '1' num1++; sum1 += sum0; // 新加入的1，与已有0形成新子序列 sum += num0; // 0的数量影响sum } // 累加当前窗口的贡献 ans = (ans + sum1) % mod; } cout << ans << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; // cin >> t; // 如果有多组测试数据可以打开 while (t--) { solve(); } return 0; }