首页 > 其他分享 >冲刺 CSP 联训模拟 2

冲刺 CSP 联训模拟 2

时间:2024-10-05 08:53:40浏览次数:8  
标签:超过 sum 30 个数 冲刺 联训 连续 binom CSP

T1 挤压

概率期望,二进制拆位

看到异或想到拆位算贡献

\[\begin{aligned} ans&=\sum_xx^2P(x)\\ &=\sum_x(b_1+b_2+...+b_{30})^2P(x)\ \ \ (b_i表示\ x\ 二进制下\ i\ 位的值)\\ &=\sum_x(b_1b_1+b_1b_2+. . .b_{30}b_{29}+b_{30}b_{30})P(x)\\ &=\sum_i^{30}\sum_j^{30}b_ib_j\sum_{b_i\in x\ and\ b_j\in x}P(x) \end{aligned}\]

后面一部分直接简单 \(DP\) 计算即可

时间复杂度瓶颈在 \(DP\) ,为 \(O(nlog^2n)\)

T2 工地难题

计数题,排列组合,容斥

发现最大恰好这一限制不好满足,考虑对答案做个前缀和,即计算最大不超过这一限制。

问题转移到计算最大不超过的方案

考虑到 \(0\) 的个数是固定的为 \(n-m\) 个,它把 \(1\) 分成了 \(n-m+1\) 个连续段(可能长度为 \(0\) )。
记限制最大不超过的值为 \(k\) ,\(1\) 的个数为 \(n\),连续段的个数为 \(m\)。
当抛弃限制 \(k\) 的时候答案显然为 \(\dbinom{n+m-1}{m-1}\)

思考怎么处理限制 \(k\),发现抛弃限制 \(k\) 时算出的答案就是连续段的长度超过 \(k\) 至少有 \(0\) 个的个数,即等于 \(\sum_{i=0} cnt_{连续段长度超过\ k\ 恰好为 i 的个数}\) 如果能算出连续段的长度超过 \(k\) 至少有 \(1\) 个的个数,直接作差就算完了,但发现这个东西同样不好求。

我们可以钦定出多少个大于 \(k\) 的个数 \(i\),即从总数 \(n\) 中取出 \(i(k+1)\) 个来,再从剩下的 \(n-i(k+1)\) 个中做抛弃限制 \(k\) 的计算,再在其基础上塞入这 \(i\) 个长为 \((k+1)\) 的连续段即乘上 \(\dbinom{m}{i}\),但是这样计算会算重,举个例子在计算长度超过 \(k\) 至少有 \(1\) 个的个数时它会将 \(cnt_{连续段长度超过\ k\ 恰好为 2 的个数}\) 多算一遍,即会在这两个连续段中都插入一次。

考虑容斥去重,下表中至少的个数是以上述方案计算的,其中第 \(i\) 行 \(j\) 列是以至少有 \(0\) 个中恰有 \(i\) 个超过的个数为单位 \(1\) 所算的系数。

恰有 \(i\) 个超过\ 至少有 \(i\) 个超过 \(0\) \(1\) \(2\) \(3\) \(4\) ...
\(1\) \(\binom{1}{0}\) \(\binom{1}{1}\) \(0\) \(0\) \(0\)
\(2\) \(\binom{2}{0}\) \(\binom{2}{1}\) \(\binom{2}{2}\) \(0\) \(0\)
\(3\) \(\binom{3}{0}\) \(\binom{3}{1}\) \(\binom{3}{2}\) \(\binom{3}{3}\) \(0\)
\(4\) \(\binom{4}{0}\) \(\binom{4}{1}\) \(\binom{4}{2}\) \(\binom{4}{3}\) \(\binom{4}{4}\)
...

目的是为了清除上表中所有的个数,由 \(\sum_{i=0}^{n}(-1)^i\dbinom{n}{i}=0\) 注意到上表每行满足这样一个式子,直接做即可。

时间复杂度分析,对于给定 \(k\) ,最多能有 \(\dfrac{n}{k}\) 个连续段的长度超过 \(k\),所以时间复杂度是调和级数为 \(O(nlogn)\)。

T3 星空遗迹

特殊性质,栈,线段树

性质1:对于连续一段操作其实本质有用的只有一个

性质2:若一段操作两边的操作都能赢它,则可将这一段变为两边的操作

证明可以考虑操作 \(f\) 本质上是获胜者蔓延的过程

考虑询问,可以用一个单调栈去维护这样的性质,即从栈顶的第 \(i+1\) 个操作赢第 \(i\) 个操作,每次对于一个新的操作入栈时,如果相同则 \(pop\) 栈顶将自己放入,如果赢了栈顶则 \(pop\) 两次栈顶将自己放入,如果输给了栈顶则直接放入。这样是满足以上的性质,则最后的答案就是栈底元素,这样就得到了查询 \(O(n)\) 的做法。

发现不用真的去维护这样一个栈,只需要记录栈的 \(size\) 即可,记 \(f\) 为栈的 \(size\) 则得到式子

\[f_{i+1}= \begin{cases} f_i+1&win(s_i,s_{i+1})=s_i\\ f_i&s_i=s_{i+1}\\ max(f_i-1,1)&win(s_i,s_{i+1})=s_{i+1} \end{cases} \]

答案即为最后一个 \(f=1\) 时的栈中的元素,但情况 \(3\) 中对 \(1\) 取 \(\max\) 并不好维护,发现不对 \(1\) 取 \(\max\) 直接减到负的答案是最后一个 \(f\) 最小时的操作,但其实任意一个最小都是相同的,证明考虑 \(f\) 本质上是一个前缀和的形式

简单转化,用线段树维护即可

时间复杂度 \(O(nlogn)\)

T4 纽带

析合树

不会

p

标签:超过,sum,30,个数,冲刺,联训,连续,binom,CSP
From: https://www.cnblogs.com/07Qyun/p/18446474

相关文章

  • 代码源CSP-S模拟赛Day7-9赛后总结
    代码源CSP-S模拟赛Day7-9赛后总结Day7赛时先扫一遍题,T1显然数位dp,感觉放在T1应该不难,而且题面有一种很亲切的感觉,感觉很可做。T2简单思考一下发现最终合成的数就是\(a_1\),\(a_2\),\(a_3\)……,\(a_n\)这n个数填正负号再加上一个k的倍数,估计会有一些比较智慧的手法,感觉很......
  • CSP-S 模拟赛34
    CSP-S模拟赛34T1考虑对原序列将\(k\)的左右分成两个序列。simple的想法是分别从\(1\)开始跑前缀和,每一次总跑到下一个小于它的点,然后依次类推。发现这样做碰到序列最小值之后难以继续。然而我们发现这样跑点的过程从前往后和从后往前是等价的。这样考虑的原因是发现这样......
  • CSP-S 模拟赛 32
    CSP-S模拟赛32rnk25,\(0+0+9+0=9\)。T1[CF1578K]KingdomofIslands还没改出来。T2[CF1578L]Labyrinth警钟嚼烂:改代码改干净。首先考虑如果从\(a\)走到\(b\),人最胖是多少。毫无疑问,这是一个最大生成树问题。在这个基础上考虑原问题,我们发现由于人会越来越胖,一定有边......
  • CSP-S模拟赛20241004
    A你考虑可以把这个数组当中的每个数表示成另一种形式:\(a_i=k_i\timesx+b\)(其中\(x\)是模数,\(b\)为余数)。对于求两个数是否对于某个余数同余,显然你要判断他们两个的差,即\(a_i-a_j\),那么我们用上面那种形式表示其实就是\(a_i-a_j=(k_i-k_j)\timesx\),所以你要判断整个数......
  • CSP-JS多省分数线分析!复赛如何准备?(附复赛流程视频)
    截止目前已经有多个省份CSP-JS的分数线已经出了,很多省份比去年提升了不少,像河南等地都提升了20多分,不过也有一些省份,天津比去年提升分数却不是很多。还有很多省份分数线没出,各位家长想要预估是否能够晋级的,以下是已出分数线省份表格统计:目前已出分数线省份省份入门组......
  • [CSP-J 2023] 小苹果(apple)-----------用数组
    1#include<iostream>2usingnamespacestd;3intmain(){4intn,m;5cin>>n>>m;6intg=n,t=0,li,s[n+1],b;7for(inti=1;i<=n;i++){8s[i]=i;9}10while(g){11t+=1,b=0,li=0,g-=(g+......
  • CSP小苹果详细解法
    #include<bits/stdc++.h>usingnamespacestd;intmain(){intn,ant=0,t,j;cin>>n;cout<<"小苞的桌上一共放了"<<n<<"个苹果。"<<endl;inta[n+5],b[n+5];for(inti=1;i<=n;i++){a[i......
  • 信息学奥赛复赛复习11-CSP-J2020-04方格取数-动态规划、斐波那契数列、最优子结构、重
    PDF文档公众号回复关键字:202410041P7074[CSP-J2020]方格取数[题目描述]设有n×m的方格图,每个方格中都有一个整数。现有一只小熊,想从图的左上角走到右下角,每一步只能向上、向下或向右走一格,并且不能重复经过已经走过的方格,也不能走出边界。小熊会取走所有经过的方格中......
  • 冲刺CSP联训模拟2
    冲刺CSP联训模拟2过T2了,赢了T3T4暴力没写满,输了A挤压我是唐诗老哥一个半小时才过T1发现要求的是\(E(s^2)\),因为有个异或,所以直接考虑拆贡献到每一位\[E(s^2)=E(\sums_i\sums_j)=\sumE(s_is_j)\]所以直接考虑后面那个咋做,就是\(i,j\)位同时是一的时候贡献\(2^......
  • 10.2 代码源 2024 CSP-S 模拟赛 Day 7
    省流:\(55+5+0+10=70\)简称:唐诗T1第一眼发现在二进制下加法不能进位,然后码了个DP就放那了……DP代码:intS=(1<<14)|1;fd(i,0,r[1])f[1][i]=1;fd(i,2,n){fd(j,0,S){f[i][j]=f[i-1][j];for(ints=j;s;s=(s-1)&j){(f......