首页 > 其他分享 >联测 1

联测 1

时间:2024-09-25 20:50:22浏览次数:7  
标签:选出 子树内 奇点 附加 联测 操作 转移

我是考场策略大师

A

\(O(|s||x||y|)\) DP 是朴素的,上个 bitset 除个 \(w\) 即可。

B

称花费 \(A\) 的操作为一操作,花费 \(B\) 的操作为二操作。

注意到可以先做一操作(选出若干条边,加它们的重边)再做二操作,

而做完一操作之后,设有 \(k\) 个度数为奇数的点(下称“奇点”),则需要做 \(k/2-1\) 次二操作。

设 \(f_{u,0/1/2}\) 表示做完一操作后,(\(u\) 子树内没有奇点 / \(u\) 是奇点 / \(u\) 不是奇点但 \(u\) 子树内有奇点)时所需的最小代价。

转移比较平凡,分讨时注意细节。

C

根据期望线性性,\(f_u\) 等于 \(\sum\limits_{i_1=1}^n\cdots\sum\limits_{i_k=1}^nP(i_1\dots i_k\text{ 都在 }u\text{ 子树内})\),

也就等于任选出 \(k\) 个点,都在 \(u\) 子树内的概率乘上 \(n^k\)。

虚空加 \(k\) 个附加点 \(n+1\dots n+k\),它们的父亲取 \([1,n]\),

把 \(k\) 个附加点的父亲看成上面任选出的 \(k\) 个点,则需要求附加点的父亲都在 \(u\) 子树内的概率,即附加点都在 \(u\) 子树内的概率。

从后往前构造这棵树,设 \(f_{i,j}\) 表示只留 \(\ge i\) 的点,附加点被分到 \(j\) 棵树中的概率,则需要求出 \(f_{u,1}\)。

考虑转移,\(f_i\) 的状态只比 \(f_{i+1}\) 的状态多加了 \(i\),也就是只选出了若干棵树的根连到了 \(i\),

若在 \(f_{i+1,j}\) 的状态中选出 \(l\) 棵树的根连到 \(i\),则转移到 \(f_{i,j-l+1}\),有转移:

\[f_{i,j-l+1}\gets f_{i,j-l+1}+f_{i+1,j}\times{j\choose l}(i-1)^{j-l}/i^j \]

枚举 \(l\) 转移即可。

D

懒得喷,自己看 APIO 课件吧

标签:选出,子树内,奇点,附加,联测,操作,转移
From: https://www.cnblogs.com/5k-sync-closer/p/18432184

相关文章

  • B. 【20省选十联测day2】bitrev
    B.【20省选十联测day2】bitrev求\(\sum_{i-1}^Rpopcount(i+g(i))\),其中\(g(i)\)表示把\(i\)的二进制(不含前导\(0\))reverse得到的数。\(R\le10^{14}\)。显然这种东西我们会想到数位DP。于是正解是一个很恶心的数位DP。首先我们要按枚举有效位数\(x\),显然\(x=1\)......
  • 突破距离限制 远程级联测径仪 让您使用更安心!
    关键词:在线测径仪,测径仪,远程级联在现代工业领域,测量的准确性和高效性至关重要。在线测径仪不仅具备了这两项特质,更能进行远程级联,能更快速的为您解决软件系统在使用中遇到的问题。在线测径仪能做到以下几点精准测量,毫厘不差:先进的测量技术确保了直径测量的高精度,让您......
  • AC475B 2024省选联测26 排列
    题意对于所有满足\(1\lea<b\len\)的\((a,b)\)的排列,需要满足:对于\(1\lea<b<c\len\),\((a,c)\)处在\((a,b)\)和\((b,c)\)之间。另外再给出\(m\)个限制,形如\((a,b,c,d)\)要求\((a,b)\)在\((c,d)\)的前面。Sol其实这道题没有那么hard......
  • AC475A 2024省选联测26 博弈
    题意两个人在一张DAG上移动棋子,每个格子的颜色为黑/白。每次操作可以移动一个格子颜色和自己相同的棋子。不能走的人输掉游戏。先手为白色,问所有放棋子的\(2^n\)种方案,先手必胜有多少。Sol不难发现,自己颜色内的棋子不会被对方偷走,也就是说,想控制所有棋子使得对方判负,......
  • 2024省选模拟26联测23
    T1首先,存在一个显然的事情:若集合\(S\)满足要求,那么\(S\)的任何子集也满足要求。还有一个比较显然的事实:对于一个合法的集合,其每个元素的位置一定在范围的交内。难道要用奇怪的容斥???但是好像根本容斥不了。。。。哈哈。能不能考虑减去不合法的状态?也许可以连边找完全图???好......
  • AC470A 2024省选联测22 送信
    题意有\(n\)个位置,\(m\)次操作,每次操作选择一个位置向左/右走到第一个没有选择过的位置,一个方案合法,当且仅当每次操作都有一个对应点。求有多少个不同的操作序列。Sol考虑集中注意力。不难打出对于\(n,m\)的表。241263212886040020001096864691241472......
  • AC466A 2024省选联测19 寄(post)
    题意一棵有边权的树,给定\(m\)个关键点,让你选择若干个点,使得每个关键点到你选择的点的距离的最小值之和加上选择的点的个数乘\(C\)最小。求这个最小值。\(n\le3000\)Sol考虑将选择点的个数扔掉,直接考虑对于每个点加上\(C\)的贡献。设\(f_{i,j}\)表示\(i\)的贡献......
  • 2024 省选联测部分题解
    目录目录R15T1树V图R15T2矩阵缺失题目:R15T3.R15T1树V图原题:SNOI2024D1T1.注意到答案肯定是形如每个连通块选一个点组成,把连通块缩起来后令\(dp_{u,x}\)表示连通块\(u\)选\(x\)的方案数,每次合并子树转移即可.因为只有\(n^2\)个合法点对所以时间复杂度......
  • 2023NOIP A层联测9 风信子+P2048 【NOI2010】 超级钢琴 2023
    P2048【NOI2010】超级钢琴2023NOIPA层联测9风信子一年OI一场空,一道原题见祖宗……Ps:超级钢琴是风信子的前置题。超级钢琴题意在一段序列上,选择长度为\(x\)的区间且\(x\in[L,R]\),求选择\(k\)个区间求和的最大值。思路来自洛谷第一篇Nekroz的题解。将区间和......
  • 2024省选联测12
    A.硬币给定\(n\),在满足\(x\timesy=n^2+1\)且\(x,y\ge2\)的前提下,最大化\(x+y\)。从后向前扫描序列,第\(i\)个数被扫到时为\(p\),\(p\)为质数或者为\(1\)。第\(i+kp,k\in\mathbb{Z}\)个数仍然是\(p\)的倍数。因为\[i^2+1\equiv0\modp\]所以\[(i+kp)^2+......