Codeforces Wunder Fund Round 2016 F.Double Knapsack[鸽巢原理]

题意:给定两个长为n \(1\leq n\leq 10^6\)的序列a,b，值域 \([1..n]\) ，从这两个序列中个找出任意一对和相同的子序列（长度可以不同）

首先进行一个处理：若a的元素和大于b的元素和，则交换序列 a 和 b

令 A 表示序列a的前缀和数组 Ｂ表示序列b的前缀和数组 对于A中的每个元素 \(A_i\) ，B中一定存在 \(B_j\) 满足 \(B_j \geq A_i\)，我们找到最小的满足条件的 \(B_j\), 又因为值域在 \([1..n]\) 内，所以 \(0\leq A_i-B_{j-1}< n\)

\([0,n)\) 有 \(n\) 个数，但前缀和有 \(n+1\) 个（算上第０个），所以一定存在 \(v, i_1, j_1, i_2, j_2\) 满足 \(A[i_1]-B[j_1]=A[i_2]-B[j_2]=v\) 那么 a 中的 \([i_1,i_2]\) 和 b 中的 \([j_1,j_2]\) 两段的和一定相等

ll prea[MAXN], preb[MAXN];
pii g[MAXN];
void solve() {int n = in;fill(g, g+n+1, mp(-1,-1));lop1(i, n) prea[i] = prea[i - 1] + ll(in);lop1(i, n) preb[i] = preb[i - 1] + ll(in);bool flag = 0;if (prea[n] > preb[n]) swap(prea, preb), flag = 1;lop0(i, n + 1) {int v = upper_bound(preb, preb + 1 + n, prea[i]) - 1 - preb;if (g[prea[i] - preb[v]] != mp(-1,-1)) {int l = g[prea[i] - preb[v]].fi, L = g[prea[i] - preb[v]].se, r = i, R = v;if (flag) swap(l, L), swap(r, R);out, r - l, '\n';lop(i, l + 1, r) out, i, ' ';puts("");out, R - L, '\n';lop(i, L + 1, R) out, i, ' ';return ;}g[prea[i] - preb[v]] = {i, v};}
}

转载于:https://www.cnblogs.com/storz/p/10423305.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！