【题解】「2019 山东一轮集训 Day3」小孩召开法 —— Alpha1022
支持一下 Qiuly /tyt 令 $a_k(n)$ 为答案。 为了导出递推式，我们考虑一下原问题。 注意到必然至少存在一个最长交替子序列经过最大值 $n$，于是考虑枚举 $n$ 的位置为 $i$。 然后首先要从 $n-1$ 个数中选择 $i-1$ 个放到左边。 接下来考虑两边分配的交替子序列长度。 阅读更多…
【题解】一道不知道哪里来的趣题——永无岛
懒得修格式了。 之前咕的文章…… 看心情更了，高考完当然是要先玩啦！ 感谢 icy 的指正，之前有个地方 i，j 搞反了，已更正。 顺便安利：hopeless cactus V 开发现场直播间 题目 一个区间 (元素是一个 pair，priority 和 value) 分成可 阅读更多…
【题解】P5094 MooFest 分治
Description 给定两个长度为 $n$ 的序列 $v_i,x_i$，定义一个点对 $(i,j)$（$i \ne j$）的价值 $f(i,j)$ 为 $\max(v_i,v_j) \times |x_i-x_j|$，求： $$\sum\limits_{i=1}^n \sum\limits_{j 阅读更多…
【题解】AGC 017 — Qiuly
AGC 017 A DP 即可。 const int N = 55; int n, p, a[N]; ll dp[N][2]; int main () { IN (n), IN (p); lep (i, 1, n) IN (a[i]), a[i] &= 1; dp[0][0] = 1; le 阅读更多…
【游记】HNOI2021 没翻车记 — Qiuly
Day -2 考了一套神仙题，dandandan 又虐场了，我又垫底了。后面被 ysu 吐槽了一句” 分太低了”（改了前两题，第三题是个巨大恶心多项式，就咕了。 Day -1 去桃花岭散心。 路上青山一直在讨论博弈论，被要求唱歌了（然后芙卡米也被要求唱歌了 后面发现了一条小 阅读更多…
【题解】CF1349D SLIME AND BISCUITS 概率与期望 — dabuliuzp
有 $n$ 个人，第 $i$ 个人有 $a_i$ 个饼干，每次随机选择一个饼干，将其随机分配给除了它现在所有者的其他 $n-1$ 个人，求使得一个人拥有所有饼干的期望步数，对 $998244353$ 取模。 $n\le 10^5 , \sum a_i\le 3\times 10^5$ 。 毒瘤题， 阅读更多…
【题解】UR #19 通用测评号 容斥，求导 – UOJ#514
题面 UOJ# #514.【UR #19】通用测评号 给定 $n$ 个燃料舱，容量为 $a$ 升 。每次会往没有满的燃料舱里面加 $1$ 升油，直到所有的燃料舱都至少包含 $b$ 升油。求最后满了的燃料舱个数期望。 数据范围：$n, a, b \le 250$。 题解 感觉这题的思想十分巧妙 qwq 阅读更多…
【算法】伯努利数相关 — Qiuly
公式挂了，所以请移步：这里
【算法】杨氏矩阵入门 — Qiuly
杨氏矩阵 简要定义： 一个 $N$ 的整数划分 $x_1+x_2+\cdots x_m = N$ ，满足 $x_1\geq x_2\geq\cdots\geq x_m>0$ 。考虑有 $m$ 行，第 $i$ 行有 $x_i$ 列的表格，称为杨图。将 $1$ 到 $N$ 这 $N$ 个正整数填进去并满 阅读更多…
【题解】雅礼集训 2017 Day7 题解 — Qiuly
「雅礼集训 2017 Day7」事情的相似度 注意到 最长公共后缀 其实是 SAM 上的 LCA ，因此原题变成了询问深度最深的 LCA 。 定义一个前缀在 parent 树上对应的点为其” 结束点”。考虑一个树上的点什么时候可能成为答案，注意到如果这个点的子树内有两个以上的 阅读更多…