题目链接:http://codeforces.com/contest/519/problem/D
对于此题,刚开始我想到的是先把每个位置的和求出来,用sum[i]保存,然后把每种字母所在的位置求出来,用vector[i]来保存。这样一来我们就可以枚举每种字母,在枚举这种字母的位置,求出满足和为零的区间就可以了。可没想到的是这样的时间达到了O(n^2),行不通!
看了别人的代码,恍然大悟:因为区间是没有方向性的,我们可以按一定方向找区间,可以从左到右,也可以从右到左。由于习惯性,就按从左到右吧!
这一样来,类似于Dp的以某点为起始点或以某点为终点的思想(这里选择以某点为终点),只需一次扫描即可。由于需要用map的查找操作为O(log n)所以总时间复杂度为O(nlog n)。
代码及详解:
//freopen("C:\\Documents and Settings\\All Users\\桌面\\in.txt","w",stdout); #include<iostream> #include<iostream> #include<string> #include<cstdio> #include<vector> #include<map> #include<string> #define LL __int64 using namespace std; string s; map<LL,LL> mp[30];//mp[i][j]表示字母i的和为j的个数 int val[30]; LL sum[100010]; vector<int> v[30]; int main(){ //freopen("C:\\Documents and Settings\\All Users\\桌面\\kk.txt","r",stdin); while(cin>>val[0]){ for(int i=0;i<30;i++){ v[i].clear(); mp[i].clear(); } for(int i=1;i<26;i++) cin>>val[i]; cin>>s; LL ans=0; for(int i=0;i<s.size();i++){ int tmp=s[i]-'a'; if(i==0){sum[i]=val[tmp];mp[tmp][sum[i]]++;continue;} if(mp[tmp].count(sum[i-1])) ans+=mp[tmp][sum[i-1]]; sum[i]=sum[i-1]+val[tmp]; mp[tmp][sum[i]]++;//记录在i的前面,tmp有多少个和为:sum[i] } printf("%I64d\n",ans); } return 0; }