百度云 免费 网站主机,网站开发对cpu要求高吗,重庆保安公司,网站名词解释记suma[1]a[2]a[3]...a[n]。
该序列以a[1]#xff0c;a[2]#xff0c;a[3]....a[n]为循环节#xff0c;明显的#xff0c;问题可转化为:s%sum是否为该序列的某个连续子序列和。
断环为链。将a复制一份。
枚举a[i]为左端点的所有区间的和。再查找s是否存在。二分O#x… 记suma[1]a[2]a[3]...a[n]。
该序列以a[1]a[2]a[3]....a[n]为循环节明显的问题可转化为:s%sum是否为该序列的某个连续子序列和。
断环为链。将a复制一份。
枚举a[i]为左端点的所有区间的和。再查找s是否存在。二分Ologn,哈希O1)均可以实现查找。
以a[i1]为左端点的所有区间再从头求一遍
不行的。
在处理a[i]时每个区间减去a[i]即是a[i1]的情况。
这里在查找s的时候加上要减去的值就可以巧妙地实现了。
#includebits/stdc.h
using namespace std;
#define int long long
#define endl \n
unordered_mapint,boolmp;signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,s; cinns;vectorinta(2*n10),suma;for(int i1;in;i)cina[i],a[in]a[i];for(int i1;i2*n;i)sum[i]sum[i-1]a[i],mp[sum[i]]1;s%sum[n];if(!s){coutYes; return 0;}for(int i0;in;i){if(mp[ssum[i-1]]){coutYes; return 0;}}coutNo;
} 对比总结
map优点有序缺点增、删、改、查时间O(logn)。
unordered_map,优点增、删、改、查O(1)缺点无序。
25/2/21
