3 条题解
-
4
赛时只想到了这种方法,就是统计以每一个位置为结尾的“孤独串”的个数,没想到换别的角度能够减少不少讨论分支。
直接维护四个变量 A、B、C、D,分别代表上一个、上一个的上一个 1 和 0 的位置。
然后直接分情况讨论,每种分支考虑得仔细一点就不会有问题了。
复杂度 O(n)。
#include <bits/stdc++.h> using namespace std; const int N = 1e7 + 5; typedef long long ll; char s[N]; ll X, n, A, B, C, D; int main() { cin >> n; for(int i=1; i<=n; ++i) cin >> s[i]; if(s[1] == '0') A = 1; else C = 1; for(int i=2; i<=n; ++i) { if(s[i] == '0') { if(!A) X += i; else { X += i - A; if(C && !D) { if(A > C) X += C; else X += A; } else if(C && D) { if(A > C) X += C - D; else if(A < C && A > D) X += A - D; } } B = A, A = i; } else { if(!C) X += i; else { X += i - C; if(A && !B) { if(C > A) X += A; else X += C; } else if(A && B) { if(C > A) X += A - B; else if(C < A && C > B) X += C - B; } } D = C, C = i; } } cout << X + 1; return 0; }大分讨.
信息
- ID
- 115
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- (无)
- 递交数
- 82
- 已通过
- 19
- 上传者