正題

題目鏈接:https://www.luogu.com.cn/problem/CF618F

---

題目大意

給出大小為$n$，值域為$[1,n]$的兩個可重集合$A,B$

需要你對它們各求出可重子集使得兩個子集中的數字和相等

輸出方案。

$1\le n\le 10^6$

---

解題思路

這個值域范圍就很提示性的往鴿籠原理方面考慮。

此題的結論就是一定有連續子序列的解。

先搞一個前綴和$A,B$，假設$A_n\le B_n$。
現在我們要求兩個$l,r$滿足
$$A_{r_1}?A_{l_1}=B_{r_2}?B_{l_2}$$
$$?A_{r_1}?B_{r_2}=A_{l_1}?B_{l_2}$$

現在問題就變為了求兩個相同的$A_x?B_y$.

對于每個$A_x$（$x\in [0,n]$），求出一個最大的$y$使得$B_y\le A_x$
那么顯然有$A_x?B_y\in [0,n?1]$，也就是$A_x?B_y$一共只有$n$種取值，而我們有$n+1$個，所以至少有兩個相同的。

開兩個桶記錄一下出現位置就好了。

時間復雜度$O(n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e6+10; ll n,a[N],b[N],la[N],lb[N]; signed main() {scanf("%lld",&n);for(ll i=1;i<=n;i++)scanf("%lld",&a[i]),a[i]+=a[i-1];for(ll i=1;i<=n;i++)scanf("%lld",&b[i]),b[i]+=b[i-1];bool f=0;if(a[n]>b[n]){for(ll i=1;i<=n;i++)swap(a[i],b[i]);f=1;}ll ala,alb,ara,arb;for(ll i=0,j=0;i<=n;i++){while(b[j]<=a[i])j++;j--;if(la[a[i]-b[j]]){ala=la[a[i]-b[j]];alb=lb[a[i]-b[j]];ara=i;arb=j;}la[a[i]-b[j]]=i+1;lb[a[i]-b[j]]=j+1;}if(f)swap(ala,alb),swap(ara,arb);printf("%lld\n",ara-ala+1);for(ll i=ala;i<=ara;i++)printf("%lld ",i);printf("\n%lld\n",arb-alb+1);for(ll i=alb;i<=arb;i++)printf("%lld ",i);return 0; }

總結

以上是生活随笔為你收集整理的CF618F-Double Knapsack【结论】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。