本文共 1939 字，大约阅读时间需要 6 分钟。
题目链接：
分两种情况，奇数位正偶数位负或者相反。
从1到n枚举，在Hash表中查询 Sum[i] - k ，然后将 Sum[i] 加入 Hash 表中。
BestCoder比赛的时候我写了 STL map， 然后TLE...
注意： Hash负数的时候 % 了一个质数，得到的是负数还要 + Mod ！！
#include #include #include #include #include #include #include #include #include #include using namespace std;#define Debug(x) cout << #x << " = " << x << endltypedef long long LL;typedef double DB;inline int gmax(int a, int b) {return a > b ? a : b;}inline int gmin(int a, int b) {return a < b ? a : b;}inline void Read(int &Num) { char c = getchar(); bool Neg = false; while (c < '0' || c > '9') { if (c == '-') Neg = true; c = getchar(); } Num = c - '0'; c = getchar(); while (c >= '0' && c <= '9') { Num = Num * 10 + c - '0'; c = getchar(); } if (Neg) Num = -Num;}const int MaxN = 1000000 + 5, Mod = 1000007;int T, n, k;int A[MaxN];struct HashNode{ int x; HashNode *Next;} HA[MaxN], *P = HA, *Hash[2][Mod + 5];bool Find(int f, LL Num) { int HN = ((Num % Mod) + Mod) % Mod; for (HashNode *j = Hash[f][HN]; j; j = j -> Next) if (j -> x == Num) return true; return false;}void Insert(int f, LL Num) { int HN = ((Num % Mod) + Mod) % Mod; ++P; P -> x = Num; P -> Next = Hash[f][HN]; Hash[f][HN] = P;}int main() { scanf("%d", &T); for (int Case = 1; Case <= T; ++Case) { memset(Hash, 0, sizeof(Hash)); P = HA; scanf("%d%d", &n, &k); for (int i = 1; i <= n; ++i) Read(A[i]); int Temp; LL Sum0, Sum1; Sum0 = Sum1 = 0; Insert(1, 0); bool Flag = false; for (int i = 1; i <= n; ++i) { if (i & 1) Temp = -A[i]; else Temp = A[i]; Sum0 = Sum0 + (LL)Temp; Sum1 = Sum1 - (LL)Temp; if (Find(0, Sum0 - (LL)k) || Find(1, Sum1 - (LL)k)) { Flag = true; break; } if (i & 1) Insert(0, Sum0); if ((i & 1) == 0) Insert(1, Sum1); } if (Flag) printf("Case #%d: Yes.\n", Case); else printf("Case #%d: No.\n", Case); } return 0;}
转载于:https://www.cnblogs.com/JoeFan/p/4321345.html