首页 > 其他分享 >2023.11.12 近期杂题

2023.11.12 近期杂题

时间:2023-11-12 22:24:47浏览次数:30  
标签:连边 cnt 12 2023.11 个数 最小值 杂题 dp dis

CF1657E

发现充要条件即为对于每个点 \(i\),其与 \(1\) 的连边为其所有连边中最小的。
这 \(dp_{i,j}\) 表示处理了 \(i\) 个点,当前与 \(1\) 连的最大的边长度是 \(j\)。
\(dp_{i,j}=\sum_{t=1}^{i-1}(\sum_{x=0}^{j-1}dp_{t,x})\times C_{n-t}^{i-t}\times (k-j+1)^{(i+t-3)(i-t)/2}\).
表示枚举与 \(1\) 连边小于 \(j\) 距离的有 \(t\) 个,且新加的点与 \(1\) 的连边的值是 \(j\)。
在新加的 \(i-t\) 个点中,两两之间的边和与之前点的边权都不小于 \(j\)。
这里 \(\sum_{x=0}^{j-1}dp_{t,x}\) 应该用前缀和优化。

CF1109D

考虑枚举 \(a,b\) 之间距离为 \(i\)。那么先选 \(i-1\) 个点出来排列,贡献为 \(A_{n-2}^{i-1}\)。
根据插板法,确定这些边的距离,贡献为 \(C_{m-1}^{i-1}\)。
对于其他边的距离,贡献为 \(m^{n-i-1}\)。
最后,确定树的形态,根据广义 Cayley 定理,我们需要将原图构建为 \(i+1\) 个树。
贡献为 \((i+1)\times n^{n-1-(i+1)}\)。注意特判 \(i+1=n\)。

CF1753C

首先由于值域只有 \(0,1\),那么如果有 \(cnt\) 个 \(0\),排序的充要条件就是前 \(cnt\) 个数都是 \(0\)。
设 \(f_i\) 表示就是前 \(cnt\) 个数有 \(i\) 个数 都是 \(0\) 的期望。
从 \(f_{i}\) 到 \(f_{i+1}\),概率是 \(\dfrac{(cnt-i)^2}{C_n^2}\)
那么 \(f_{i+1}=f_{i}+\dfrac{C_n^2}{(cnt-i)^2}\)。

CF1253F

考虑计算走 \(u\to v\) 这条边最少的容量。
考虑贪心,我们肯定在走之前先去充满电,设最近的充电距离是 \(dis_u\),充满电走回要花 \(dis_u\)。
然后走过这条边,花费 \(w_{u\to v}\)。
然后,我们要支持剩下的点去最近的站,还需要 \(dis_v\)。
那么,走过 \(u\to v\) 的最少容量是 \(dis_u+w_{u\to v}+dis_v\)。
建出最小生成树即可。
考虑计算 \(dis\),考虑建立超级源点,向所有站点连边,跑一遍最短路即可。

CF526F

发现二维问题可以转化为一维问题,对于一个点 \((x,y)\),令 \(a_x=y\)。
现在我们要处理所有子区间,计算 \(\max-\min-len=-1\) 的个数。
扫描线,考虑往右推右端点,同时线段树维护每个左端点的 \(\max-\min-len\)。
发现 \(\max-\min-len\) 中 \(-1\) 一定是最小值,因为题目满足每行每列只有一个棋子。
那么线段树只需要维护最小值的个数,这是容易维护的。
单调栈辅助。

CF802O

恰好 \(k\) 道题,考虑 wqs 二分,现在求代价最小值。
考虑贪心,从小到大枚举 \(i\),并 \(b_i\) 与之前的最小的 \(a_i\) 匹配。
或者,替换之前最大的 \(b\)。用反悔贪心实现。
只需要维护一个堆,维护 \(a_i,-b_i\) 的最小值。

标签:连边,cnt,12,2023.11,个数,最小值,杂题,dp,dis
From: https://www.cnblogs.com/Simon-Gao/p/17827998.html

相关文章

  • Win10完美克隆迁移120g ssd升级500g
    120gssd升级500g、win10完美克隆迁移只是后面多了三个螺丝、问题不大、反正能用!新的500gssd硬盘装硬盘盒,进入winPE,使用DiskGenius克隆旧硬盘的系统和资料到新硬盘;拆机打开笔记本内部,准备更新SSD新旧SSD的合照;进入系统,通过磁盘管理工具调整一下硬盘的分区,然后......
  • 11.12
    退役倒计时6天不知道有没有人听过\(golden\)\(hour\)和$void$两首钢琴曲每日负能量庆幸于自己在潺潺的世界中遇到小狗,偶尔也怀疑它是不是专门来找我的,否则又会有多大的概率能让我们在这个世界中相遇,又慢慢的相伴16年,我依旧坚信小狗的身体里住着一个饱满的灵......
  • P1129 [ZJOI2007] 矩阵游戏
    挺喜欢的一题。首先我们很容易观察到一个性质:每一行和每一列上的黑色方格的数量是不变的,只能改变它在那一行和那一列的排列顺序。由此若是有某一行或某一列上没有黑色方格,直接输出No即可。此时我们考虑的情况就是每一行和每一列上至少都会有一个黑色方格。这时有一个结论:若有......
  • 解决vue-element-admin安装报错npm ERR! code 128
    在安装vue-element-admin的npminstall的时候报错npmERR!code128npmERR!AnunknowngiterroroccurrednpmERR!commandgit--no-replace-objectsls-remotessh://[email protected]/nhn/[email protected]:Permissiondenied(publickey).npmERR!fatal:......
  • 2023-2024-1 20231312 《计算机基础与程序设计》第7周学习总结
    作业信息这个作业属于哪个课程<班级的链接>2023-2024-1-计算机基础与程序设计|-这个作业要求在哪里<作业要求链接>2023-2024-1计算机基础与程序设计第6周作业|这个作业的目标《计算机基础概论》第8章《C语言程序设计》第6章|作业正文作业链接教材学习......
  • 231112洛谷模拟赛
    T1种树P9836种树只需要运用一些小学奥数即可解决首先需要知道的一点是将\(p_i\)质因数分解后得到\(p_i=\prod\limits_{j=1}^ma_j^{k_j}\),则有\(\prod\limits_{i=1}^{m}(k_i+1)\)个因数则最终就是把所有的都再乘起来考虑\(w\)分解后能造成什么影响,依据乘法......
  • 2023.11.2测试
    \[\text{NOIP模拟赛-2023.11.12}\]T1马有\(n\)匹马,\(m\)个人来骑马。有三个项目,分别是骑小圈、骑大圈、过河,三个项目对马的疲劳值的影响分别是\(+20,+50,\times2\)。初始时每匹马的疲劳值是\(1\),且每匹马的疲劳值不能超过\(100\)。给定每个项目的人数\(c_1,c_2,c_3(c_1......
  • 11月12日js的基础引入和注释
    目录1.js的引入1.在内部写入js代码2.外部引入js代码2.js的注释1.js的引入1.在内部写入js代码在html文档中用script标签进行编写<script>//在这里写你的JS代码</script>2.外部引入js代码html文档使用script来引入外部的js代码<scriptsrc="myscript.js"></script>在sc......
  • C++U2-第12课-单元测评(二)
    上节课作业部分(点击跳转)单元测评2题目和答案解析1、 2、  3、不定长数组,不允许不初始化列,可以不初始化行;  4、比较常见的字符的ASCII码,空格为32,字符0为48,大写字母A为65,小写字母a为97  5、abs为绝对值函数,正数的绝对值是本身,负数的绝对值为相反数,ceil表示向......
  • 2023.11.10测试
    \[\text{NOIP模拟赛-2023.11.10}\]T1进步科学一棵以\(1\)为根的\(n\)个点的树,初始时所有点的点权都是\(0\),每个点有期望的点权(\(0\)或\(1\))。每次操作可以选择一个点\(i\)变化它的点权,这个操作效果会在一秒后传给它的父亲,在\(j\)秒后传给它的\(j\)级祖先。特别的,......