Bubble Cup 11 - Finals [Online Mirror, Div. 1] B. Space Isaac Hash
程序员文章站
2022-05-09 21:14:32
...
Description
有两个集合,两个集合里的数互不相同且都是0~m-1的数,现在给你第一个集合的数,每次你可以从第一个集合和第二个集合各选一个数出来,问有哪些数不能表示出来。
Sample Input
2 5
3 4
Sample Output
1
2
好强啊这题。。。
首先有一个比较显然的想法,一个数不能被表示出来,当且仅当对于每一个A集合中的数ai都能找到另一个A集合中的数匹配。
也就是说,最多只有n个,且n个可能的权值为:
a1+a1,a1+a2,a1+a3,…,a1+an,那么剩下你就要判对于一个权值是否满足条件。
那么我们可以假设当前枚举到第i个数,那么这个数的权值即为:
a1+ai,那么对于1~i的数我们肯定是a2和ai-1匹配得到a1+ai,a3和ai-2匹配得到a1+ai,为什么,很好证明。
假设a2没有跟ai-1匹配而是跟ai-2匹配,那么ai-1就无人可以匹配了,因为想跟ai-1匹配就一定需要一个更小的数,然而并没有,就不满足条件。
然后对于i~n的数,我们也是用类似的方法。
然后你将这个数列差分一下就相当于判回文了,你可以用Hash维护。。。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const ULL P = 131;
int _min(int x, int y) {return x < y ? x : y;}
int _max(int x, int y) {return x > y ? x : y;}
int read() {
int s = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
return s * f;
}
ULL s1[210000], s2[210000], o[210000];
int a[210000], b[210000], ans[210000];
int main() {
int n = read(), m = read();
for(int i = 1; i <= n; i++) a[i] = read(), b[i] = a[i];
sort(a + 1, a + n + 1);
for(int i = 1; i < n; i++) a[i] = a[i + 1] - a[i];
o[0] = 1; for(int i = 1; i < n; i++) s1[i] = s1[i - 1] * P + a[i], o[i] = o[i - 1] * P;
for(int i = n - 1; i >= 1; i--) s2[i] = s2[i + 1] * P + a[i];
int len = 0; bool bk = 0;
for(int i = 2; i <= n; i++) if((b[1] + b[1]) % m != (b[n - i + 2] + b[i]) % m) bk = 1;
if(!bk) ans[++len] = (b[1] + b[1]) % m;
for(int i = 2; i < n; i++) {
int hh = (b[1] + b[i]) % m;
if((b[i + 1] + b[n]) % m != hh) continue;
if(s1[i - 1] != s2[1] - s2[i] * o[i - 1]) continue;
if(s2[i + 1] != s1[n - 1] - s1[i] * o[n - i - 1]) continue;
ans[++len] = hh;
} if(s1[n - 1] == s2[1]) ans[++len] = (b[1] + b[n]) % m;
len = unique(ans + 1, ans + len + 1) - (ans + 1);
sort(ans + 1, ans + len + 1); printf("%d\n", len);
for(int i = 1; i <= len; i++) printf("%d ", ans[i]);
return 0;
}
推荐阅读
-
Bubble Cup 11 - Finals [Online Mirror, Div. 2] C. Space Formula
-
Bubble Cup 12 - Finals [Online Mirror, unrated, Div. 1] E. Product Tuples
-
Bubble Cup 11 - Finals [Online Mirror, Div. 1] I. Palindrome Pairs(字符串hash)
-
Bubble Cup 11 - Finals [Online Mirror, Div. 1] B. Space Isaac Hash
-
CodeForces Bubble Cup 11 - Finals [Online Mirror, Div. 2] F题
-
Bubble Cup 11 - Finals [Online Mirror, Div. 1] G.AI robots 主席树
-
Bubble Cup 11 - Finals [Online Mirror, Div. 2] B. Hyperspace Highways(tarjan - 点双连通分量 + LCA)
-
Bubble Cup 11 - Finals [Online Mirror, Div. 2], problem (H) Palindrome Pairs 字符处理优化