玩客云 做网站服务器,网站运营策略,建企业网站,seo网站编辑专业正题
题目链接:https://www.luogu.com.cn/problem/CF618F 题目大意
给出大小为nnn#xff0c;值域为[1,n][1,n][1,n]的两个可重集合A,BA,BA,B
需要你对它们各求出可重子集使得两个子集中的数字和相等
输出方案。 1≤n≤1061\leq n\le 10^61≤n≤106 解题思路
这个值域范围…正题
题目链接:https://www.luogu.com.cn/problem/CF618F 题目大意
给出大小为nnn值域为[1,n][1,n][1,n]的两个可重集合A,BA,BA,B
需要你对它们各求出可重子集使得两个子集中的数字和相等
输出方案。
1≤n≤1061\leq n\le 10^61≤n≤106 解题思路
这个值域范围就很提示性的往鸽笼原理方面考虑。
此题的结论就是一定有连续子序列的解。
先搞一个前缀和A,BA,BA,B假设An≤BnA_n\leq B_nAn≤Bn。 现在我们要求两个l,rl,rl,r满足 Ar1−Al1Br2−Bl2A_{r_1}-A_{l_1}B_{r_2}-B_{l_2}Ar1−Al1Br2−Bl2 ⇒Ar1−Br2Al1−Bl2\Rightarrow A_{r_1}-B_{r_2}A_{l_1}-B_{l_2}⇒Ar1−Br2Al1−Bl2
现在问题就变为了求两个相同的Ax−ByA_x-B_yAx−By.
对于每个AxA_xAxx∈[0,n]x\in[0,n]x∈[0,n]求出一个最大的yyy使得By≤AxB_y\leq A_xBy≤Ax 那么显然有Ax−By∈[0,n−1]A_x-B_y\in[0,n-1]Ax−By∈[0,n−1]也就是Ax−ByA_x-B_yAx−By一共只有nnn种取值而我们有n1n1n1个所以至少有两个相同的。
开两个桶记录一下出现位置就好了。
时间复杂度O(n)O(n)O(n) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e610;
ll n,a[N],b[N],la[N],lb[N];
signed main()
{scanf(%lld,n);for(ll i1;in;i)scanf(%lld,a[i]),a[i]a[i-1];for(ll i1;in;i)scanf(%lld,b[i]),b[i]b[i-1];bool f0;if(a[n]b[n]){for(ll i1;in;i)swap(a[i],b[i]);f1;}ll ala,alb,ara,arb;for(ll i0,j0;in;i){while(b[j]a[i])j;j--;if(la[a[i]-b[j]]){alala[a[i]-b[j]];alblb[a[i]-b[j]];arai;arbj;}la[a[i]-b[j]]i1;lb[a[i]-b[j]]j1;}if(f)swap(ala,alb),swap(ara,arb);printf(%lld\n,ara-ala1);for(ll iala;iara;i)printf(%lld ,i);printf(\n%lld\n,arb-alb1);for(ll ialb;iarb;i)printf(%lld ,i);return 0;
}
