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; }大分讨.
-
3
和lzm差不多,差别应该就是我用了数组存储(这个题不开long long的话会挂分,注意相乘的时候也要开)
code:
#include<bits/stdc++.h> using namespace std; string s; int n; int l[10000005],r[10000005],ansl[10000005],ansr[10000005]; int ll,l1,rr,r1; long long sum; int main(){ cin>>n>>s; rr=n,r1=n; ll=-1,l1=-1; for(int i=0;i<n;i++){ if(s[i]=='0'){ l[i]=ll; ll=i; } else{ l[i]=l1; l1=i; } } for(int i=n-1;i>=0;i--){ if(s[i]=='0'){ r[i]=rr; rr=i; } else{ r[i]=r1; r1=i; } } for(int i=0;i<n;i++){ int lhh=(i-l[i]-1),syn=(r[i]-i-1); sum=sum+lhh+syn; if(lhh>0&&syn>0)sum+=(long long)lhh*syn; } for(int i=0;i<n-1;i++){ if(s[i]=='0'&&s[i+1]=='1'||s[i+1]=='0'&&s[i]=='1')sum-=1; } cout<<sum+n; return 0; }ps:最快的一期
-
1
题意理解
比赛时没有想明白这个孤独的串是啥意思,后来才明白,不仅如 都是孤独的串,也是。
思路构想
我们可以发现,决定孤独的串的多少的数,只有两类。一类是紧跟着的那个数和它不一样,但是它前面的数和它一样的,如的第二个0。另一类则是它左边右边都和它不一样的数,如中的1。 对于第一类,我们可以往右推,直到右边第一个数和它一样,则从我们选的这个数那个一样的数左边一个数构成了一个孤独的串。如果一直到也没有一个数和我们选的这个数一样,则从这个数到这一长串都是孤独的串。由于左端点必须在这个串的字串内以保证这些串都是孤独的串,这个串的长度就是孤独的串的个数。然后从这个数左边的一个数开始找,向左找到第一个和它不一样的数,则这两个数之间的所有的数(不含端点)的个数又是孤独的串的个数。如果一直到1都没有找到和它不一样的数,则从1到这个数前一个数的个数就是孤独的串的个数。 对于第二类,我们需要找到它左边第一个和它一样的数,将这两个数之间数的个数(不含端点)计为。然后向右找第一个和它一样的数,把这两个数中间数的个数计为。然后由于必须要有这个数本身,子串数量就是。以这个数开头的孤独的串不会被其他的串记录,所以要再加一遍cnt1。
注意陷阱
1.子串是否相同只看左右端点,不看子串内容。 2.010等也是孤独的串,千万别漏掉 //这两个坑作者已经踩过多次,也是作者调了一下午都调不对这段代码的原因
代码实现
#include<bits/stdc++.h> #define int long long using namespace std; int n, ans = 0, cnt; string s; vector<int>v; vector<int>v2; signed main(){ ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin>>n>>s; s = 'A' + s; for(int i = 1; i < n; i ++){ if(s[i] != s[i+1]){ if(s[i] != s[i-1]) v2.push_back(i); else v.push_back(i); } } for(int i : v){ for(int j = i+1; j <= n; j ++){ if(s[i] == s[j]){ ans += j - i - 1; break; } else if(j == n){ ans += j - i; break; } } if(s[i-1] == s[i]){ for(int j = i-1; j >= 1; j --){ if(s[i] != s[j]){ ans += i - j - 1; break; } else if(j == 1){ ans += i - j; break; } } } } //ans += n - now + 1 - cnt; for(int i : v2){ int cnt1 = 0, cnt2 = 0; for(int j = i+1; j <= n; j ++){ if(s[i] == s[j]){ cnt1 += j - i - 1; break; } else if(j == n){ cnt1 += j - i; break; } } ans += cnt1 ; for(int j = i-1; j >= 1; j --){ if(s[i] == s[j]){ cnt2 += i - j - 1; break; } else if(j == 1){ cnt2 += i - j; break; } } ans += cnt2 * cnt1; } cout<<ans + n; return 0; }AC记录
- 1
信息
- ID
- 115
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- (无)
- 递交数
- 82
- 已通过
- 19
- 上传者