首页 > 其他分享 >[一直更新中]一句话题解

[一直更新中]一句话题解

时间:2024-10-30 09:12:11浏览次数:1  
标签:2024.10 limits 一句 sum 话题 更新 节点 2n binom

目录

一句话题解

不能什么题都随便写写就过了,留点印象好一点。一直更新。

2024.10.29

AT_abc290_f

组合数数。满足树的形态要有 \(\sum deg_i=2n-2\)。考虑目前有 \(k\) 个儿子节点,直径最大肯定是 \(n-k\) 个非儿子点串一条长度为 \(n-k+1\) 的链,然后再挂儿子节点。总度数 \(2n-2\),给 \(n-k\) 个非儿子节点支配的还剩 \(2n-2-k\),易得插板:\(\binom{(2n-2-k)-2(n-k)+(n-k)-1}{(2n-2-k)-2(n-k)}=\binom{n-3}{k-2}\)。答案即为:\(\sum\limits_{k=1}^n \binom{n}{k}\binom{n-3}{k-2}(n-k+1)\)。

根据吸收恒等式(\(k\binom{n}{k}=n\binom{n-1}{k-1}\))和范德蒙德卷积(\(\sum\limits_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}\))可以化简成 \(O(1)\):\(Ans=(n-1)\binom{2n-3}{n-1}-(n-3)\binom{2n-4}{n-1}\)。

AT_arc156_c

构造。观察可得价值最小无论如何都是 \(1\)。方向转为构造排列。观察树是链的情况,排列直接为序号翻转过来。考虑树普通情况,每次取两个叶子节点交换序号即可。类似拓扑地,可以处理至原树变成一条链。

正确性证明:一条 \(u\to v\) 的简单路径,路上的编号大概形如 \(v\to u\) 的路径的编号。刚好是完全相反的,满足了 LCS 为 \(1\)。

2024.10.30

P5749 [IOI2019] 排列鞋子

贪心。对于每种大小用 vector 存鞋的位置,从后往前遍历,每次可配对鞋一定在 vector 最后一个最优。贪心显然成立。可以用树状数组优化求区间 \(1\)(交换次数)操作。

AT_abc285_e

DP。可设 \(S_i\) 表示一周 \(i+1\) 天只有一天休息日的贡献。易得 \(S_i=2\sum\limits_{j=1}^{\lfloor\frac{i}{2}\rfloor}a_j+[i\bmod 2=1]a_{\lceil\frac{i}{2}\rceil}\)。设 \(F_i\) 表示一周有 \(i\) 天的贡献,初始状态有 \(F_i=S_{i-1}\)。可以枚举休息日的个数:\(F_i=\max\limits_{j=2}^{i-2} F_j+F_{i-j}\)。答案为 \(F_n\)。

标签:2024.10,limits,一句,sum,话题,更新,节点,2n,binom
From: https://www.cnblogs.com/WerChange/p/18514973

相关文章

  • 深入浅出:SpringBoot启动流程源码分析(持续更新中......)最新日期:2024年10月29日
    Hello,大家好,我是此林。今天来深入底层讲一讲SpringBoot是如何启动的,也就是我们单击运行SpringBoot启动类,它底层发生了什么?SpringBoot启动类很简单,只有一行代码。我们点进run()方法。我们发现,它底层其实进行了两步操作。第一步是new出一个SpringApplication对象,第二个是......
  • 袋鼠云产品功能更新报告12期|让数据资产管理更高效
    本期,我们更新和优化了数据资产平台相关功能,为您提供更高效的产品能力。以下为第12期袋鼠云产品功能更新报告,请继续阅读。一、【元数据】重点更新|01元数据管理优化,支持配置表生命周期之前系统中缺少一个可以基于数据源和数据库维度,批量配置数据表生命周期的入口,导致用户在处理......
  • JAVA对于图片的花式操作(不定期更新)
    JAVA对于图片的花式操作(不定期更新)MultipartFile转Base64字符串图片url转Base64字符串图片url转MultipartFile图片url转File流base64图片压缩引入依赖代码编写抠图MultipartFile转Base64字符串/***MultipartFile文件转bash64字符串**@parammult......
  • 【DzzOffice官方动态】DzzOffice更新至V2.3.0版本!
    ......
  • 安卓13 连接usb设备后不更新ui
    总纲android13rom开发总纲说明文章目录1.前言2.问题分析3.代码更改4.彩蛋1.前言  有些界面在链接usb设备后,ui会被刷新,导致闪烁问题。2.问题分析像这种问题一般是usb事件,导致的ui事件更新了,处理方法是禁止该事件3.代码更改这块我们就需要在输入事件管......
  • 题目记录(一直更新
    OI记录(持续更新P2568GCD题意:给定正整数\(n\),求\(1\lex,y\len\)且\(\gcd(x,y)\)为素数的数对\((x,y)\)有多少对(\(n\leq10^7\))题解:注意,可以不用莫比乌斯反演,单纯的欧拉函数便可以解决,首先列出式子:\[\sum_{p\inprime}\sum_{i=1}^{n}\sum_{j=1}^{n}(gcd(i,j)=p)\]......
  • Android13 通过OTA升级更新系统默认设置
    系统进行OTA升级时更改默认设置的详细步骤在进行系统的OTA(Over-The-Air)升级过程中,如果需要对系统默认设置进行更改,以确保升级后的系统能够应用新的默认配置,那么需要执行一系列关键步骤。以下是详细的操作指南:修改设备Overlay资源首先,需要定位到设备特定的Overlay资源文件......
  • 帝国cms一句MySQL语句实现多表数据之和
    SQL语句:SELECTCOUNT(AA.id)AStotalFROM(SELECTidFROMwww_moban5_cn_ecms_newsUNIONALLSELECTidFROMwww_moban5_cn_ecms_xiazaiUNIONALLSELECTidFROMwww_moban5_cn_ecms_photoUNIONALLSELECTidFROMwww_moban5_cn_ecms_download)......
  • 苹果和安卓在系统更新政策上有哪些不同_1
    苹果(iOS)和安卓(Android)在系统更新政策上存在显著差异,这些差异对用户体验、安全性和设备寿命产生重要影响。苹果提供定期且统一的更新,覆盖所有支持的设备,确保安全性和功能的一致性。苹果和安卓在以下方面的差异:1.更新发布的一致性;2.更新的控制和自定义;3.安全更新和漏洞修复;4.操作系......
  • Xshell6 要继续使用此程序,您必须应用最新的更新或使用新版本
    在xshell的使用过程中,经常会遇到“要继续使用此程序,您必须应用最新的更新或使用新版本”的提示对话框,其实简单点的就是把自己电脑的日期往前更改一年,然后再打开Xshell就行了(亲测可以)。解决办法使用二进制编辑器修改nslicense.dll文件文件位置:xshell安装根目录 具体步骤1、......