东莞做一个企业网站,wordpress搬家出现404,建站快车是什么,大型公司办公室设计题目大意
有 n n n个数#xff0c;你希望能删除其中不超过 k k k个数#xff0c;然后将剩下的数划分为两个子集#xff08;可以有重复的数字#xff09;#xff0c;满足这两个子集的数的和是相等的。
为了降低出题和做题的难度#xff0c;可以认为这 n n n个数在 1 1 1…题目大意
有 n n n个数你希望能删除其中不超过 k k k个数然后将剩下的数划分为两个子集可以有重复的数字满足这两个子集的数的和是相等的。
为了降低出题和做题的难度可以认为这 n n n个数在 1 1 1到 W W W内随机的。 2 ≤ n ≤ 2 × 1 0 5 , min ( 25 , n − 2 ) ≤ k ≤ n − 2 , W 2 × 1 0 5 2\leq n\leq 2\times 10^5,\min(25,n-2)\leq k\leq n-2,W2\times 10^5 2≤n≤2×105,min(25,n−2)≤k≤n−2,W2×105 题解
当 n ≤ 25 n\leq 25 n≤25时枚举所有子集找到元素和相同的集合 A A A和 B B B。如果 A A A和 B B B有交集则两个集合都去掉交集的这部分最终得到的两个集合即为题意所求。时间复杂度为 O ( n ) O(n) O(n)。
当 n 25 n25 n25时我们可以将这些数从小到大排序取后 n − 25 n-25 n−25个数从后往前扫即要按数值从大到小扫。维护两个集合的元素和之差 n o w now now
如果 n o w ≤ 0 now\leq 0 now≤0则当前的 a i a_i ai给集合 A A A n o w a i nowa_i nowai如果 n o w 0 now0 now0则当前的 a i a_i ai给集合 B B B n o w − a i now-a_i now−ai
最后的 n o w now now一定满足 ∣ n o w ∣ ≤ W |now|\leq W ∣now∣≤W。
在剩下的 25 25 25个元素中我们要找到两个集合满足这两个集合的元素和之差为 n o w now now。
对于所有这 25 25 25个元素的子集元素和都不超过 25 W 25W 25W并且子集个数为 2 25 2^{25} 225是比 26 W 26W 26W大很多的。又因为是选择两个子集使得两个子集的元素和之差等于 n o w now now而且数据随机所以几乎一定会出现两个集合的元素和之差为 n o w now now。求这两个集合的方法和 n ≤ 25 n\leq 25 n≤25时求答案方法类似。
时间复杂度为 O ( n 2 25 ) O(n2^{25}) O(n225)。
code
#includebits/stdc.h
using namespace std;
const int N200000;
int n,k,now0,a[N5],id[N5],cnt[125],sum[125];
int z[N*305],ans1[N5],ans2[N5];
bool cmp(int x,int y){return a[x]a[y];
}
int lb(int i){return i(-i);
}
void solve(int s,int t){for(int i1;imin(n,25);i){if((s(i-1)1)(t(i-1)1)) continue;if(s(i-1)1) ans1[ans1[0]]i;else ans2[ans2[0]]i;}
}
void print(){printf(%d ,ans1[0]);for(int i1;ians1[0];i) printf(%d ,id[ans1[i]]);printf(\n%d ,ans2[0]);for(int i1;ians2[0];i) printf(%d ,id[ans2[i]]);
}
int main()
{scanf(%d%d,n,k);for(int i1;in;i){scanf(%d,a[i]);id[i]i;}for(int i0;i24;i) cnt[1i]i1;if(n25){for(int s1;s1n;s){sum[s]sum[s^lb(s)]a[id[cnt[lb(s)]]];if(z[sum[s]]){solve(z[sum[s]],s);print();return 0;}z[sum[s]]s;}printf(-1);return 0;}sort(id1,idn1,cmp);for(int in;i26;i--){if(now0){ans1[ans1[0]]i;nowa[id[i]];}else{ans2[ans2[0]]i;now-a[id[i]];}}for(int s1;s125;s){sum[s]sum[s^lb(s)]a[id[cnt[lb(s)]]];z[sum[s]]s;}for(int s1;s125;s){int tmpsum[s]now;if(z[tmp]){solve(s,z[tmp]);print();return 0;}}printf(-1);return 0;
}
