A and B and Interesting Substrings CodeForces - 519D

xiaoxiao2021-03-01  26

http://codeforces.com/problemset/problem/519/D

把所有前缀都记录下来 包括前缀的值和结尾字符 然后每遍历到一个前缀s[i] 先把s[i]记录上 然后看有多少前缀与s[i+1]是相等的 即值和结尾字符相等 具体实现map搞一搞 类似思想的题还有个蓝桥题 k倍区间

#include <bits/stdc++.h> using namespace std; #define ll long long #define plc pair <ll,char> map <plc,int> mp; ll val[50],ary[100010]; int n; char ch[100010]; int main() { plc tmp; ll ans; int i; for(i=0;i<26;i++) scanf("%lld",&val[i]); scanf("%s",ch); n=strlen(ch); for(i=0;i<n;i++) ary[i+1]=ary[i]+val[ch[i]-'a']; ans=0; for(i=1;i+1<=n;i++) { tmp=make_pair(ary[i],ch[i-1]); mp[tmp]++; tmp=make_pair(ary[i],ch[i]); ans+=mp[tmp]; } printf("%lld\n",ans); return 0; }

 

转载请注明原文地址: https://www.6miu.com/read-4550096.html

最新回复(0)