{"id":36,"date":"2009-11-19T17:25:00","date_gmt":"2009-11-19T09:25:00","guid":{"rendered":"http:\/\/localhost\/?p=36"},"modified":"2009-11-19T17:25:00","modified_gmt":"2009-11-19T09:25:00","slug":"spoj_2150_subseq","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=36","title":{"rendered":"SPOJ 2150 SUBSEQ"},"content":{"rendered":"\n<p>Sum[i..j]=S[j]-S[i-1]&#8230;<\/p>\n<p>\u6240\u4ee5\u4e00\u4e2a\u4e2a\u63d2\u5165\u3002\u3002\u76f4\u63a5\u7528MAP\u3002\u3002<\/p>\n<p>\u6162\u7684\u5413\u4eba\u3002\u3002\u3002<\/p>\n<p>\u5e94\u8be5\u7528Hash\u7684\u3002\u3002\u3002\u4e0d\u8fc7\u61d2\u7684\u5199\u4e86\u3002\u3002<\/p>\n<p>#include&lt;iostream&gt;#include&lt;cstdio&gt;#include&lt;map&gt;#define REP(i,n) for(int i=0;i&lt;n;i++)using namespace std;typedef long long LL;typedef map&lt;LL,int&gt;::iterator It;int t;void solve(){     scanf(&quot;[^\/n]&quot;);     int n;scanf(&quot;%d&quot;,&amp;n);     LL s=0,ans=0,t;     map&lt;LL,int&gt; M;     M[0]=1;     REP(i,n)     {       scanf(&quot;%lld&quot;,&amp;t);s+=t;       It a=M.find(s-47);       if(a!=M.end()) ans+=(*a).second;       a=M.find(s);       if(a!=M.end()) (*a).second++;       else M[s]=1;     }     cout&lt;&lt;ans&lt;&lt;endl;}int main(){    cin&gt;&gt;t;    while(t&#8211;)    {       solve();    }}5.8s\u3002\u3002\u3002 <\/p>\n","protected":false},"excerpt":{"rendered":"<p>Sum[i..j]=S[j]-S[i-1]&#8230; \u6240\u4ee5\u4e00\u4e2a\u4e2a\u63d2\u5165\u3002\u3002\u76f4\u63a5\u7528MAP\u3002\u3002 \u6162\u7684\u5413\u4eba\u3002\u3002\u3002 \u5e94\u8be5\u7528Hash\u7684\u3002\u3002\u3002\u4e0d\u8fc7\u61d2\u7684\u5199\u4e86\u3002\u3002 #include&lt;iostream&gt;#include&lt;cstdio&gt;#include&lt;map&gt;#define REP(i,n) for(int i=0;i&lt;n;i++)using namespace std;typedef long long LL;typedef map&lt;LL,int&gt;::iterator It;int t;void solve(){ scanf(&quot;[^\/n]&quot;); int n;scanf(&quot;%d&quot;,&amp;n); LL s=0,ans=0,t; map&lt;LL,int&gt; M; M[0]=1; REP(i,n) { scanf(&quot;%lld&quot;,&amp;t);s+=t; It a=M.find(s-47); if(a!=M.end()) ans+=(*a).second; a=M.find(s); if(a!=M.end()) (*a).second++; else M[s]=1; } cout&lt;&lt;ans&lt;&lt;endl;}int main(){ cin&gt;&gt;t; while(t&#8211;) { solve(); }}5.8s\u3002\u3002\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/36"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=36"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/36\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=36"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=36"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=36"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}