VPS如何做网站服务器,网站怎么发布到iis上,seo如何优化排名,wordpress验证码国内XSY3318 CSA35G 对于一个询问区间的集合SSS#xff0c;求出每一个数被哪些区间覆盖了#xff0c;记为SiS_iSi。 要能保证猜出选中数#xff0c;当且仅当每个数的SiS_iSi互不相同。 考虑求出不满足要求的集合SSS的个数。
首先可以观察得到SiS_iSi的一个性质#xff1…XSY3318 CSA35G 对于一个询问区间的集合SSS求出每一个数被哪些区间覆盖了记为SiS_iSi。 要能保证猜出选中数当且仅当每个数的SiS_iSi互不相同。 考虑求出不满足要求的集合SSS的个数。
首先可以观察得到SiS_iSi的一个性质若abcdabcdabcd且SaSc,SbSdS_aS_c,S_bS_dSaSc,SbSd则必有SaSbScSdS_aS_bS_cS_dSaSbScSd。
证明因为SaScS_aS_cSaSc所以如果一个区间覆盖了aaa一定也覆盖了ccc那么这个区间一定也覆盖了bbb又因为SbSdS_bS_dSbSd所以该区间一定也覆盖了ddd。同理可证覆盖了bbb或ccc或ddd的区间一定也覆盖了其它三个数。
我们给每个数一个编号aia_iai满足当且仅当SiS_iSi相同的数aia_iai相同。
由刚才的性质我们知道不同的aaa值的排布 只可能是以下情况 –x--xx–xy—y–yy–x,yx,yx,y出现范围呈并列关系 –x--y-yy-y-x-xx-----x,yx,yx,y出现范围呈包含与被包含关系 不可能是这种情况 –xx-y-x-x-yyy-------x,yx,yx,y出现范围呈相交关系
所以可以把 构造形如 x–xy–yz–z 的序列aaa 分解成 构造形如 x—x 的序列aaa构造形如 y–y 的序列aaa构造形如 z–z 的序列aaa 三个子问题。
并且在构造形如 x—x 的序列aaa时 — 不管怎么填最后得到的方案都一定猜不出选中数。 y–y z–z 同理。
形式化地每次把aaa中的第一个数xxx放入bbb的末尾然后在aaa中删掉最后一个xxx前的所有数包括最后一个xxx。 例如a[1,2,3,2,4,2,5,5,10,6,7,8,7,6,9]a[1,2,3,2,4,2,5,5,10,6,7,8,7,6,9]a[1,2,3,2,4,2,5,5,10,6,7,8,7,6,9] 此时b[1,2,5,10,6,9]b[1,2,5,10,6,9]b[1,2,5,10,6,9] 可以发现只包含被删掉数的区间可有可无但包含未被删掉数的区间一定要使未被删掉数的aaa值互不相同即这些包含未被删掉数的区间对应着一个长度为∣b∣|b|∣b∣的序列的答案。 例如序列bbb中一个包含1,2的区间对应着序列aaa中一个包含1,2,3,2,4,2的区间。
那么就可以DP了 记fif_ifi为iii个数的答案gi,jg_{i,j}gi,j为iii个数处理之后之剩jjj个数的答案。则有
fi2Ci12−∑j1i−1fjgi,jf_i2^{C_{i1}^{2}}-\sum_{j1}^{i-1}f_jg_{i,j}fi2Ci12−j1∑i−1fjgi,j
gi,jgi−1,j−1∑k0gi−k−2,j−12Ck12g_{i,j}g_{i-1,j-1}\sum_{k0}g_{i-k-2,j-1}2^{C_{k1}^{2}}gi,jgi−1,j−1k0∑gi−k−2,j−12Ck12
时间复杂度O(n3)O(n^3)O(n3)或O(n2logn)O(n^2logn)O(n2logn)
还可以用多项式优化但我不会。
