1 条题解
-
0Takagi-san (njnu19200437) LV 10 MOD @ 2021-11-06 18:39:18
90pts:
取所有子串,然后判断是否含有'5'。
Code:#include<bits/stdc++.h> using namespace std; int main() { string s;cin>>s; int n = s.length(); int ans = 0; for(int i=0;i<n;i++)for(int j=0;i+j<=n;j++) if(s.substr(i,j).find('5') != string::npos) ans++; cout<<ans<<'\n'; return 0; }
中间两个测试点:
这两个测试点是提示正解的。如果所有字符均为'5',则总数量是\(n*(n+1)/2\)。
200pts:
让我们反向考虑,不符合条件的子串有多少?
其起止点应当都位于两个'5'的中间,所以,只需要减去这些子串即可。
例如,54445应当有\(5*6/2 - 3*4/2 = 9\)个符合条件的子串。Code:
#include<bits/stdc++.h> using namespace std; using ll = long long; int main() { string s;cin>>s; ll n = s.length(); vector<ll> v = {-1}; for(int i=0;i<s.length();i++) if(s[i]=='5') v.push_back(i); ll ans = n*(n+1)/2; //记录总个数 v.push_back(n); for(int i=1;i<v.size();i++) ans-=(v[i]-v[i-1])*(v[i]-v[i-1]-1)/2; // 减去两个'5'之间的子串个数。 cout<<ans<<'\n'; }
- 1
信息
- ID
- 1290
- 难度
- 7
- 分类
- (无)
- 标签
- 递交数
- 188
- 已通过
- 32
- 通过率
- 17%
- 被复制
- 2
- 上传者