• 周日. 7月 3rd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[杂题笔记]20210807-20210817

admin

11月 28, 2021

就先定个小目标每天写他个三题(x),但最近还是有点累,大概就还是写点简单的题(Div2里ABCD差不多,EF这种过段时间如果状态好点补上)


https://www.luogu.com.cn/problem/P2260求(egin{aligned}sum_{i=1}^n sum_{j=1}^m (nmod i)(mmod j),(i
eq j),n,mleq 10^9end{aligned})
取模的值。

取模的定义展开,拆成四项分别用除法分块处理,再扣掉(i=j)的部分,注意模数不是质数。

https://www.luogu.com.cn/problem/P3935

(egin{aligned}x=p_1^{k_1}p_2^{k_2}dots p_n^{k_n},f(x)=(k_1+1)(k_2+1)dots(k_n+1),end{aligned})(sum_{i=l} ^r f(i)).

我好铸币,(f(x))对应的就是(x)的因数个数,然后前缀和变成(sum_{i=1}^n sum_{d=1}^n [d|i]=sum_{d=1}^n lfloorfrac{n}{d}floor),除法分块。

https://codeforces.com/problemset/problem/1557/A, 把数组排好序,最后一个单独一个集合,剩下的n-1个一个集合。考虑一个轻微的扰动,用反证法证明。

https://codeforces.com/problemset/problem/1557/B, 因为每个数都是unique的,二分求出每个数排好序之后的位置,要分割的每个子段一定是连续递增的整数。

https://codeforces.com/problemset/problem/1557/C, 数学题,(a_1,dots,a_n)​要让他们(&)​的结果不小于(oplus)​的结果,因为懒得考虑取等的情况,那就考虑(a_1&dots& a_n<a_1oplusdots oplus a_n)​的情况,假设在第(p)​位的地方出现左边<右边,那也就是左边的第p位是0,右边的是1,进一步(a_{1p}&dots& a_{np}=0)​,也就是第(p)​位至少有一个0,以及(a_{1p}oplus dots oplus a_{np}=1)​,也就是有奇数个1,两个条件结合起来意味着:(n)​是奇数时,((a_{1p},a_{2p},dots,a_{np}))(C_n^2+C_n^4+dots+C_n^{n-1}=2^{n-1}-1)​种,如果是偶数则是(2^{n-1})​种,接着对于比第(p)​位更高的位,与运算结果要和异或一样,同样的方法分类讨论,(n)​为奇数时每一位有(2^{n-1}+1)​种,偶数时有(2^{n-1}-1)​种,而对后面的位置则无所谓,最后答案就是:(n)​为奇数时,(2^{nk}-(2^{n-1}-1)sum_{i=0}^{k-1}(2^{n-1}+1)^i 2^{n(k-i-1)})​,(n)为偶数则是(2^{nk}-2^{n-1}sum_{i=0}^{k-1}(2^{n-1}-1)^i 2^{n(k-i-1)})种。

https://codeforces.com/problemset/problem/1555/A, 暴力

https://codeforces.com/problemset/problem/1555/B, 贪心地,新桌子一定在某个角落里,同时必要条件是新加的桌子要在水平/竖直的一个方向上能放得下,仔细想想这也是充分的条件,于是如果能移,那一定只在水平/竖直的一个方向上移动。

https://codeforces.com/problemset/problem/1555/C, 先手会拿到一个(a[1][1,dots,x])(a[2][x,dots,n])​,后手只会拿到(a[1][x,dots,n])或者(a[2][1,dots,x])其中最大的那个,于是答案就是让这两者的最大值尽可能小。

https://codeforces.com/problemset/problem/1555/D, 这题性质很特殊,只有3种字母,动手画一画会发现,一个字符串要是beautiful的(任何一个长度不小于2的子串,都不能是回文的),假设是ab开头,下一个只能是c,接着abc的再下一个只能是a,以此往复只能是abcabcabc重复的结构,((a,b,c))一共6种轮换,(O(6n))地暴力处理。

https://codeforces.com/problemset/problem/1554/A, 考虑某个已经包含(max_i a_i)​的区间([l,r])​​,一旦去扩展区间,只可能让区间的(min)​变小,所以我们要尽可能控制区间长度,也就是只要检测长度为2的区间。

https://codeforces.com/problemset/problem/1554/B, 很有意思的题,给一个长度(nleq 10^5)的非负整数序列,找到最大的$ij-k(a_i|a_j),kleq min(100,n),i
eq j,forall i:a_ileq n (。和位运算其实没什么关系,重要的性质还是)(a_i|a_j)leq 2n(和)kleq 100$这个。

接着这么分析,先考虑(f(i,n))​​​​​要成为答案的必要条件,取(f(i,j)>f(n-1,n))​​​​​得到(ingeq ijgeq ij-k(a_i|a_j)>n^2-n-2kn,)​​​​​联系两边得到(i>n-1-2k)​​​​​,即(igeq n-2k)​​​​​​。同样对称地有(jleq n-2k),复杂度(O(k^2))

https://codeforces.com/problemset/problem/1554/C, 又是一个和位运算相关的问题,给(n,m)(noplus 0,dots,noplus m)的mex。

假设答案(k)是由(n)和另一个(x>m)异或出来的结果,即(noplus x=k),则一定有(x=noplus k>m),于是变成找最小的(k)使得(noplus k >m)​,构造地考虑二进制位,从高往低考虑二进制位:①如果某个位置出现了(n_i>m_i),也就是(n_i=1,m_i=0)的情况,那只要让后面更低的位置(k_p)​全部取0就行,这时候的(k)就是答案。②否则就取(k_i=n_ioplus m_i),这样往下取至少能保证最后的(noplus k=m),(当然一旦遇到①的话就直接大于了),如果到最后都没遇到①的情况,那就微调(k)的低位,也就是找到(m)最低位的0,让(noplus k)这一位变成1。

https://codeforces.com/problemset/problem/1554/D, 构造题,要构造(s)使得每个非空子串在(s)中出现奇数次,考察形如s=aa...aaa这样子的串,其长度为(|s|-1)的子串在里面出现奇数次,(|s|-2)的子串出现了偶数次,以此类推,于是就拿两个形式一样的,长度相差为1的串拼起来。

这次是有嘉然小姐的一场题!(看了眼果然是中国人出的)

https://codeforces.com/problemset/problem/1559/A, 对每个二进制数位考虑所有数,如果都是1那怎么操作都是1,否则就是0.

https://codeforces.com/problemset/problem/1559/B, 对于B?…?B和B?…?R这样的结构,只要和开头那个不一样,交错着填下去就行,特别判一下左/右一端。

https://codeforces.com/problemset/problem/1559/C, 画一下图,如果有01这种结构的出现,那就走(1 o dots o i o (n+1) o i+1 o dots n)这条路线,否则一定是形如(11dots100dots 00)的结构,如果有1就从((n+1))出发走一遍,否则全是0就从1开始走,最后走(n+1)。综上,符合条件的路径一定存在。

剩下的两题之后补上(x)

https://codeforces.com/problemset/problem/1540/A, Div1的A,题读了好久(可恶),说现在有一张有向图但是忘了长什么样,只知道1到别的点的最短距离(d_igeq 0),以及不会出现负环和重边,求所有边权之和最小值。

注意到(1 o 2 odots o n)的这条链是一定要有的,他们边权求和是固定的(d_n-d_1=d_n),那就想着怎么加负权边,只要(i<j,d_i<d_j),就意味着(d_j-d_i)有一条正的路径,这样就可以连一条(j o i)(d_i-d_j)的负权边,这就启示我们把(d[])升序排序之后统计(sum_{i=1}^{n-1}sum_{j=i+1}^n(d_i-d_j)=sum_{i=1}^{n-1}(n-i)d_i-sum_{j=2}^n (j-1)d_j),复杂度(O(nlog n))。(可恶,Div1的A怎么这么难,2分钟过的真的是碳基生物吗(x))

发表评论

您的电子邮箱地址不会被公开。