题目题解(4)讨论(2)排行较难 通过率13.63% 时间限制1秒 空间限制1024M知识点动态规划校招时部分企业笔试将禁止编程题跳出页面为提前适应练习时请使用在线自测而非本地IDE。描述小红定义一个字符串的权值为该字符串包含的 0101子序列[1][1]的数量。现在小红拿到了一个由字符 ‘0’‘0’ 和 ‘1’‘1’ 组成的字符串环即最后一个字符下一个是第一个字符。现在小红想知道这个环的所有长度不小于 22 的连续子串[2][2]权值之和是多少由于答案可能很大请将答案对 (1097)(1097) 取模后输出。0101子序列[1][1]为从原字符串中删除任意个可以为零、可以为全部字符得到的新字符串字符串恰好为 0101。子串[2][2]为从原字符串中连续的选择一段字符可以全选、可以不选得到的新字符串。在本题中环上的子串为任取两个下标 ll 和 rr从 ll 不断向右取直到 rr 形成的连续子串特殊的若 rlrl则会从 ll 向右取到最后一个字符之后从第一个字符取到 rr。输入描述第一行输入一个正整数 n(1≦n≦105)n(1≦n≦105) 代表字符串的长度。第二行输入一个长度为 nn、由字符 ‘0’‘0’ 和 ‘1’‘1’ 构成的字符串 ss。输出描述输出一个整数代表所有长度不小于 22 的连续子串的权值之和。由于答案可能很大请将答案对 (1097)(1097) 取模后输出。示例1输入3 001复制输出4复制说明在这个样例中长度为 22 的连续子串有 33 个 ∙ ∙0000权值为 00 ∙ ∙0101权值为 11 ∙ ∙1010权值为 00。 长度为 33 的连续子串有 33 个 ∙ ∙001001权值为 22 ∙ ∙010010权值为 11 ∙ ∙100100权值为 00。 所有长度不小于 22 的连续子串的权值之和为 01021040102104 。#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; }