首页 > 其他分享 >CSP-S 2024 第九次

CSP-S 2024 第九次

时间:2024-10-06 21:22:06浏览次数:9  
标签:dfrac limits 第九次 sum 2024 Delta 矩形 CSP 鸽笼

A

设 \(f_{i,S}\) 表示考虑前 \(i\) 行,选出的矩形在第 \(i\) 行上形成 \(S\) 中的区间的方案数,

每行的 \(S\) 只有 \(O(2^m)\) 种,总复杂度 \(O(n2^{2m})\)。

B

考虑先修改再查询怎么做。

考虑左下角为 \((x_1,y_1)\),右上角为 \((x_2,y_2)\) 的矩形,发现斜率在 \(\left[\dfrac{y_1}{x_2},\dfrac{y_2}{x_1}\right]\) 内的向量会穿过它,

考虑扫描斜率,扫到 \(\dfrac{y_1}{x_2}\) 时加入这个矩形,扫到 \(\dfrac{y_2}{x_1}\) 时删除它,则扫到一个向量的斜率时已经加入了所有其能穿过的矩形。

考虑一个向量 \((\Delta x,\Delta y)\) 能穿过的、左下角在 \((x,y)\) 的矩形,则这个向量需要延伸 \(\max\left(\dfrac x{\Delta x},\dfrac y{\Delta y}\right)\) 倍才能碰到它,

要求向量碰到的第一个矩形,即要求向量能穿过的、\(\max\left(\dfrac x{\Delta x},\dfrac y{\Delta y}\right)\) 最小的矩形。

考虑分讨掉这个 \(\max\)。对于 \(\dfrac x{\Delta x}>\dfrac y{\Delta y}\iff\dfrac yx<\dfrac{\Delta y}{\Delta x}\) 的矩形,只需求 \(\dfrac x{\Delta x}\) 的最小值,也就只需求 \(x\) 的最小值,

对于 \(\dfrac x{\Delta x}<\dfrac y{\Delta y}\iff\dfrac yx>\dfrac{\Delta y}{\Delta x}\) 的矩形,只需求 \(\dfrac y{\Delta y}\) 的最小值,也就只需求 \(y\) 的最小值。

以 \(\dfrac yx\) 为下标对加入的所有矩形建权值线段树,维护区间 \(x,y\) 最小值即可。

然后这个题不是先修改再查询,套个 CDQ 变成先修改再查询即可。

C

选到每个鸽笼的概率会随着鸽笼的填满而变化,这个不太好处理,所以先用拒绝采样转化下题意:

每次可以选任意一个鸽笼,这个鸽笼满了就再选一个。记下每次选择的鸽笼作为操作序列。

考虑对 \(i\) 算答案。考虑容斥,把答案看成恰好 \(0\) 个鸽笼比 \(i\) 更晚填满的概率,

设 \(g(S)\) 表示钦定 \(S\) 中鸽笼比 \(i\) 更晚填满的概率,则答案为 \(\sum\limits_{S\in U-\{i\}}(-1)^{|S|}g(S)\)。

钦定 \(S\) 中鸽笼比 \(i\) 更晚填满,实际上就是操作序列上 \(S\) 中每个数都在 \(i\) 的最后一次出现后出现过,

也就是 \(\forall j\in S\),\(j\) 在 \(i\) 的最后一次出现前出现小于 \(a_j\) 次。

考虑只留操作序列中,\(i\) 的最后一次出现前的 \(i\) 以及 \(S\) 中的数,求满足条件的方案数除以总方案数。

\(i\) 比较特殊,必须出现 \(a_i\) 次,所以我们先不填 \(i\)。

设 \(f_x\) 表示当前在操作序列中填入 \(x\) 个数的方案数,每次对于一个 \(j\in S\) 考虑填入 \(k\) 个 \(j\),则有转移 \(f_x\gets f_{x-k}{x\choose k}(k<a_j)\),

填完长度为 \(x\) 的操作序列后,有 \({x+a_i-1\choose a_i-1}\) 种填 \(i\) 的方案(因为 \(i\) 的最后一次出现一定在最后),

所以在操作序列中填入 \(x+a_i\) 个数的满足条件的方案数为 \(f_x{x+a_i-1\choose a_i-1}\)。

而如果不需要满足条件,每个数都可以随便填,所以在操作序列中填入 \(x+a_i\) 个数的总方案数为 \((|S|+1)^{x+a_i}\),

所以 \(g(S)=\sum\limits_{x}\dfrac{f_x{x+a_i-1\choose a_i-1}}{(|S|+1)^{x+a_i}}\)。(\(x\) 不会很大,最多只有 \(a_i+\sum\limits_{j\in S}(a_j-1)\))

考虑同时计算大小相同的 \(S\) 的 \(g\) 值。设 \(f_{o,x}\) 表示除 \(i\) 外填入了 \(o\) 种数(即 \(|S|=o\)),且填入了 \(x\) 个数的方案数,

则有转移 \(f_{o,x}\gets f_{o-1,x-k}{x\choose k}(k<a_j)\)。

则答案为 \(\sum\limits_{S\in U-\{i\}}(-1)^{|S|}g(S)=\sum\limits_{o=1}^{n-1}(-1)^o\sum\limits_{|S|=o}g(S)=\sum\limits_{o=1}^{n-1}(-1)^o\sum\limits_{x}\dfrac{f_{o,x}{x+a_i-1\choose a_i-1}}{(|S|+1)^{x+a_i}}\)。

发现这个转移是背包的形式,所以一开始可以先把所有物品装进背包,求 \(i\) 的答案时把 \(i\) 拿出来。复杂度 \(O(n^5)\)。

D

最大值最小,考虑二分答案 \(k\)。

两个人至少有一个停在点上的那档部分分,直接设 \(f_{x,y}\) 表示可不可能一个人在 \(x\),一个人在 \(y\),BFS 转移即可。

但是他们可能停在边上。所以在每条边上加一个点,一个人在这个点上就代表他停在这条边上,然后就同上了。

转移时需要算点线距和线线距,合理利用点乘叉乘即可。

标签:dfrac,limits,第九次,sum,2024,Delta,矩形,CSP,鸽笼
From: https://www.cnblogs.com/5k-sync-closer/p/18449440

相关文章

  • 2024-2025 20241308《计算机基础与程序设计》第二周学习总结
    这个作业属于哪个课程https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP这个作业要求在哪里https://www.cnblogs.com/rocedu/p/9577842.html#WEEK02这个作业的目标阅读《计算机科学概论》和《C语言程序设计》的第一章内容并从中学习感悟,找到不懂的问题并想办法解决作......
  • 2024-10-6 模拟赛总结
    \(100+80+100+0=280\),暴力又写挂了。比赛链接:http://172.45.35.5/d/HEIGETWO/homework/67025b796735d3863dc7f60d或者http://yl503.yali.edu.cn/d/HEIGETWO/homework/67025b796735d3863dc7f60dA-fountain题意:给定一条线段和一个圆,求线段上任意一点到圆上任意一点的最大距......
  • 2024-2025 20241323第二周总结
    这个作业属于https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP这个作业要求这个作业的目标• 作业正文数字化• 信息安全• 自学教材o 计算机科学概论(第七版)第1章教材学习内容总结计算系统:计算系统不仅仅是计算机系统,它包括硬件、软件和数据,是一种动态实体,用于解......
  • 多校A层冲刺NOIP2024模拟赛02 & csp-s模拟9
    多校A层冲刺NOIP2024模拟赛02四道题因为暑假被拉去当模拟赛暑假集训CSP提高模拟22了,遂直接把赛后代码交了上去,然后就被通知换题了。原\(100+100+100+20\)被在accodersNOI上被卡成了\(100+100+90+10\),更改longlong和int后达到了\(100+100+100+30\)。\(T1\)P318......
  • [JOI 2024 Final] 建设工程 2
    [JOI2024Final]建设工程2题意给出一张图和\(S\),\(T\)。可在任意两点\(u,v(u<v)\)之间添加一条长度为\(L\)的边(只可添加一次)。求有多少种添加方案使得\(S\)到\(T\)的最短路长度\(\leK\)。思路首先,若\(S\)到\(T\)的最短路已经\(\leK\),答案为\(\frac{n\t......
  • 2024-2025-1 20241327 《计算机基础与程序设计》第2周学习总结
    作业信息|2024-2025-1-计算机基础与程序设计)||--|-|2024-2025-1计算机基础与程序设计第二周作业)||快速浏览一遍教材计算机科学概论(第七版),课本每章提出至少一个自己不懂的或最想解决的问题并在期末回答这些问题|作业正文|https://www.cnblogs.com/shr060414/p/18440575|教......
  • SMC 2024 游记
    (评分规则:25道五选一,满分125分,选对得5分,不选得1分,选错得0分)题目都没有什么难度啊,但是T3可以看一下:(回忆)两个标准骰子叠放在桌子上。已知:(1)两个骰子接触面上的点数相等,均为\(A\)。(2)\(9\)个可见的面(骰子之间接触面有两个,骰子与桌面的接触面有一个,这三个面不可见)的点数......
  • # 2024-2025-1 学号(2024130) 《计算机基础与程序设计》第二周学习总结
    作业信息|这个作业属于哪个课程|<[2024-2025-1-计算机基础与程序设计]>(https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP))||-- |-- ||这个作业要求在哪里|<[2024-2025-1计算机基础与程序设计第一周作业]>(https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP/home......
  • 20222412 2024-2025-1 《网络与系统攻防技术》实验一实验报告
    1.实验内容本周学习内容1.熟悉基本的汇编语言指令及其功能。2.掌握了栈与堆的概念及其在进程内存管理中的应用以及用户态与内核态的区别。3.熟练运用了Linux系统下的基本操作命令。实验任务1.手工修改可执行文件,改变程序执行流程,直接跳转到getShell函数。2.利用foo函数的Bo......
  • CCF-CSP认证资格考试题解系列——第4次第2题数字排序
    #include<iostream>#include<algorithm>usingnamespacestd;structre{ intvalue;//数值 intnum;//次数}re[1010];boolcmp(structrea,structreb){ if(a.num==b.num)returna.value<b.value;//次数相同是小的优先 returna.num>b.num;//次数不相同是次数优......