3 条题解
-
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记录
信息
- ID
- 115
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- (无)
- 递交数
- 82
- 已通过
- 19
- 上传者