【题解】相互再归的鹅妈妈 容斥 YZOJ50120 — Iris
同步发表于 博客园 题目大意 给出一个二进制数 $R$,在 $[0, R-1]$ 中选 $n$ 个互不相同数,问异或和为 $0$ 的方案数。 $|R|\le 10^6,n\le 7$. 解题思路 因为限制 $n$ 个数互不相同难以实现,所以考虑允许相同怎么求方案数,然后容斥做。 记可以相同的 $n$ 阅读更多…
同步发表于 博客园 题目大意 给出一个二进制数 $R$,在 $[0, R-1]$ 中选 $n$ 个互不相同数,问异或和为 $0$ 的方案数。 $|R|\le 10^6,n\le 7$. 解题思路 因为限制 $n$ 个数互不相同难以实现,所以考虑允许相同怎么求方案数,然后容斥做。 记可以相同的 $n$ 阅读更多…
同步发表于 博客园 基础知识 卡特兰数的式子 $$ \begin{aligned} &h(n)=\sum_{i=0}^{n-1}h(i)\cdot h(n-i-1)\\ &h(n)=\frac{h(n-1)\cdot(4n-2)}{n+1}\\ &am 阅读更多…
前置: 1. 目前没有进行代码实现,所有内容均是口胡,如有错误或者不严谨的地方烦请指出,谢谢! 2. 由于这篇文章中会同时出现 “线段树上的节点”,“树上的结点” 等多种点,为便于理解,维护连续段的线段树的点统称 “节点”,树的点统称 “结点”。 3. 线段树上的节点对应/表示的区间指线段树函数参数 阅读更多…
在以前的文件里翻了翻,找到了许久之前写的两篇游记。那时的文笔还是太稚嫩了,思想也有点偏激。但是不得不说,那段时间在外地比赛的经历使我的世界观受到了巨大的冲击,开始意识到自己身处的世界存在的不合理。也许这就是所谓的成长。从那时起我开始发觉自己学习的不止是一个个没有色彩的算法和数据结构,眼中的世界渐渐鲜 阅读更多…
题意 给定一棵 n 个节点的树,每个点有点权,让你找一个最大的联通块满足块内权值和不大于 m。 n,m, 点权不大于 1e5,点权互不相同。 解 点权互不相同,且点权和不大于 m,所以显然联通块的大小不会超过 $\sqrt{m}$。 令 $dp_{i,j}$表示以 i 节点为根的大小为 j 的联通块 阅读更多…
传送门 结论:当 $\binom{n}{a_1,a_2,…,a_k}$是奇数并且 $n$是偶数的时候 Alice 必败 首先我们来证明这个结论 首先当你有 $n$个字母的时候(假设上一轮还有 $n+1$个字母),那么你有两种方案,如果删掉一个字母可以让对手进入必败态,就直接删;否则如果 阅读更多…
同步发表于 博客园 题目大意 对于满足以下要求的长度为 $n$ 的序列进行计数: 序列的值域为 $[1,k]$; 对于序列的任意位置 $p\in[1,n]$,可以找到至少一个 $i$ 满足 $p\in[i,i+k-1]$,且区间 $[i,i+k-1]$ 为一个 $1\sim k$ 的排列。 $n\l 阅读更多…
题目大意 有一个长度为 $n$ 的非负整数序列 $a_i$,每次可以选择一段区间减去 $1$,要求选择的区间长度 $\in[l,r]$,问最少多少次把每个位置减成 $0$。 不保证有解,$1 \leq l \leq r \leq n \leq 10^6,\ r – l + 1 \geq 阅读更多…
wrp 划水记录 (cnblogs.com) 题意 给定一张连通无向简单图 $G$,每条边有一个边权。 给定正整数 $k$,你需要找到 $G$ 的一条从 $1$ 到 $n$ 的路径,设该路径的长度为 $l$,你需要使得这条路径中边权前 $\min\left{ k, l \right 阅读更多…
记录一下出题的过程。 关于 t1: 这是最早就定好的,在萱有次模拟赛看错题的时候就觉得可以作为一个简单题放上去。 开始觉得还行,在某一个周末突然意识到是个笛卡尔树板子,但是似乎更好地对标 noip t1 了,所以没关系。 造数据的时候重造了好几次,不小心全造成大数据了,不小心 srand() 有问题 阅读更多…