Problem
题目地址
Solution
集合最小不能表示数
定义 ：对于一个多重数集 (S)，对于一非负整数 (x)，若存在 (S'⊆ S) 且 (S') 中所有数字之和恰好等于 (x)，则说 (S) 可以表示 (x) 。显然对于任意的多重数集都可以表示 (0)，因为空集是所有集合的子集。定义集合 (S) 的最小不能表示数为，一个最小的非负整数 (x)，(S) 不能表示 (x)。举个例子来说，例如 (S={1,2,3,8,9}) ，那么集合 (S) 的最小不能表示数就为 (7) 。
如何求一个集合的最小不能表示数？
将数字按升序排列，假设前 (i) 个数可以表示的数是 ([0,k])，那么如果 (a_{i+1} le k+1)，则前 (i+1) 个数可以表示的数有 ([0,k+a_{i+1}])，否则前 (i+1) 个数可以表示的数是 ([0,k])，进一步可以推断出整个集合的的最小不能表示数就是 (k+1)。
相当于我们要将数字排序，然后用 (sum) 记录前 (i) 个数的和。如果 (a_{i} le sum+1)，就把 (a_i) 加入 (sum)，否则如果 (a_{i} > sum)，那么 (sum+1) 就是这个集合最小不能表示数。求单个集合时间复杂度 (O(n log n)) （排序）。
迭代算法求解
排序求解法是我们直接推导得到的，我们可以考虑用一种迭代法：
不将数字排序，把 (n) 个数扫一遍，将 (le sum+1) 的数加入 (sum)，上一轮已经加入过 (sum) 的数不能再加入。记新的 (sum) 为 (sum')。用 (sum') 代替 (sum)，重复迭代上述操作。若第 (k) 轮操作后 (sum = sum')（没有数被加入进去）则算法结束 break。
接近 (log n) 层迭代，每层迭代 (O(n)) 的复杂度，时间复杂度 (O(n log n))
进一步优化
一共 (m) 个查询区间，将查询区间离线，同时进行 (m) 个查询区间的迭代求解。用树状数组处理每个查询区间，统计该区间 (le) 当前区间的 (sum+1) 的数之和。树状数组从左到右把数加入处理一遍可以把 (m) 的查询区间全部处理完，时间复杂度 (O(n log n))
总复杂度 (O(n log^2 n))
Code
Talk is cheap.Show me the code.
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
return x * f;
}
const int N = 1e5+7;
int n,m,ntmp;
int a[N],ida[N],L[N],R[N],sum[N],pre[N],c[N],btmp[N];
vector<pair<int,int> > query[N];
void Add(int x,int y) {
while(x <= ntmp) {
c[x] += y; x += x & -x;
}
}
int Ask(int x) {
int res = 0;
while(x > 0) {
res += c[x]; x -= x & -x;
}
return res;
}
int Getpos(int x) {
int l = 1, r = ntmp, mid, ans;
while(l <= r) {
mid = (l + r) >> 1;
if(btmp[mid] <= x) {
ans = mid;
l = mid + 1;
} else r = mid - 1;
}
return ans;
}
signed main()
{
n = read(), m = read();
for(int i=1;i<=n;++i) btmp[i] = a[i] = read();
sort(btmp+1, btmp+1+n);
ntmp = unique(btmp+1, btmp+1+n) - btmp - 1;
for(int i=1;i<=n;++i) ida[i] = lower_bound(btmp+1, btmp+1+ntmp, a[i]) - btmp;
for(int i=1;i<=m;++i) {
L[i] = read(), R[i] = read();
query[L[i]-1].push_back(make_pair(i, -1));
query[R[i]].push_back(make_pair(i, 1));
}
for(int i=1;i<=m;++i) pre[i] = -1;
while(true) {
bool flag = 1;
cout << endl << endl;
for(int i=1;i<=m;++i) {
if(sum[i] != pre[i]) {
flag = 0; break;
}
}
if(flag == 1) break;
for(int i=1;i<=m;++i) pre[i] = sum[i];
memset(c ,0, sizeof(c));
for(int i=1;i<=n;++i) {
Add(ida[i],a[i]);
for(int j=0;j<query[i].size();++j) {
int qid = query[i][j].first, f = query[i][j].second;
int sid = Getpos(pre[qid] + 1);
sum[qid] += Ask(sid) * f;
}
}
for(int i=1;i<=m;++i) sum[i] -= pre[i];
}
for(int i=1;i<=m;++i) printf("%lld
",sum[i]+1);
return 0;
}
/*
10 10
10 6 2 7 1 4 1 6 3 4
2 3
1 9
6 6
2 8
1 4
2 7
4 5
7 7
6 8
7 10
1
41
1
28
1
22
2
2
2
2
*/
Summary
-
集合最小不能表示数
-
迭代算法思想