[CF 618F]Double Knapsack
转载请注明出处：http://danihao123.is-programmer.com/
我zzs就算掉光rating，R2爆炸，也不会做你们半道构造题！
啊构造题真好玩（一转）。
不妨钦定A中所有元素的和不大于B的。然后把两个集合按照任意顺序搞成一个序列，然后求出两者的前缀和SA和SB。
考虑对于0...n的SAi，找出SB中不大于他的数中最大的一个（不妨设为SBj），可以发现有0≤SAi−SBj≤n−1（不然j还能再大）。然后发现：我们处理的i和j的数对有n+1组，但是SAi−SBj的取值却只有N种！也就是说一定存在i≠i′且j≠j′满足SAi−SBj=SAi′−SBj′。
我们找出两对这样的数对，移一下项就可以构造一组解了。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | #include <cstdio>#include <cstring>#include <cstdlib>#include <cctype>#include <algorithm>#include <utility>#include <vector>using ll = long long;using pii = std::pair<int, int>;int n;void gen_S(int *arr, ll *S) { S[0] = 0LL; for(int i = 1; i <= n; i ++) { S[i] = (S[i - 1] + (ll(arr[i]))); }}const int maxn = 1000005;std::vector<pii> cs[maxn];int main() { scanf("%d", &n); int *A = (int*)calloc(n + 1, sizeof(int)); int *B = (int*)calloc(n + 1, sizeof(int)); ll sum_A = 0LL, sum_B = 0LL; for(int i = 1; i <= n; i ++) { scanf("%d", &A[i]); sum_A += A[i]; } for(int i = 1; i <= n; i ++) { scanf("%d", &B[i]); sum_B += B[i]; } bool flip = false; if(sum_A > sum_B) { flip = true; std::swap(A, B); std::swap(sum_A, sum_B); } ll *SA = (ll*)calloc(n + 1, sizeof(ll));; ll *SB = (ll*)calloc(n + 1, sizeof(ll));; gen_S(A, SA); gen_S(B, SB); for(int i = 0; i <= n; i ++) { int j = std::upper_bound(SB, SB + n + 1, SA[i]) - SB - 1; ll val = SA[i] - SB[j]; cs[val].push_back(std::make_pair(i, j)); } int l1, r1, l2, r2; for(int i = 0; i < n; i ++) { if(cs[i].size() > 1) { int i1 = cs[i][0].first; int j1 = cs[i][0].second; int i2 = cs[i][1].first; int j2 = cs[i][1].second; if(i1 > i2) { std::swap(i1, i2); std::swap(j1, j2); } l1 = i1; r1 = i2; l2 = j1; r2 = j2; break; } } if(flip) { std::swap(l1, l2); std::swap(r1, r2); } printf("%d\n", r1 - l1); for(int i = l1 + 1; i <= r1; i ++) { if(i > l1 + 1) putchar(' '); printf("%d", i); } putchar('\n'); printf("%d\n", r2 - l2); for(int i = l2 + 1; i <= r2; i ++) { if(i > l2 + 1) putchar(' '); printf("%d", i); } putchar('\n'); free(A); free(B); free(SA); free(SB); return 0;} |
评论 (0)
