NOI2021 加油！

RainAir's Blog

2018 EC Final B Mysterious … Host

题目链接注意到两个排列本质不同，当且仅当它们的析合树不同。所以我们就是要对所有有 $n$ 个叶子的析合树计数。考虑析合树的性质：首先析合树是区分儿子顺序的，所以我们会思考能否用生成函数去表示一棵树。设 $F(x)$ 表示析合树的生成函数，其中 $[x^m]F(x)$ 表示有 $m$ 个叶子的析合树的个数，我们先不考虑 $[x^0]F(x)$ 是啥，之后要用的时候再特殊定义。那么下一步我们要考...

  • RainAir
  • June 19, 2021
  • No comments

    • CF243E Matrix PQTree

    题目链接题解对于维护「某些元素之间必须贴贴相邻」这样的问题，可以考虑使用一种叫做 PQTree 的结构来维护。PQTree 上的点有三种类型：叶子结点，表示一个元素P 类节点，表示这个节点的儿子的顺序是可以任意排布的Q 类节点，表示这个节点的儿子的顺序必须是当前给出的顺序或者逆序现在我们考虑如何加入一个限制。设这一次限制是要求 $S$ 内的元素贴贴，那么我们把 $S$ 内对应的叶子都标记成黑...

  • RainAir
  • June 19, 2021
  • No comments

    • Topcoder UniqueMST

    题意问有多少个 $n$ 个点的完全图，满足所有边权在 $[1,K]$ 内，并且最小生成树只有一个。答案对质数 $p$ 取模。$n \leq 50,K \leq 10^9,\max(n,K)+1 \leq p \leq 10^9$。题解先考虑如何求最小生成树：将所有边从小到大排序，按照顺序选择两个端点不在一个联通块的边，并合并这两个联通块。所以我们可以考虑按照权值去考虑这些边：设 $f_{n,...

  • RainAir
  • June 5, 2021
  • 1 comments

    • SRM566 FencingPenguins

    题意平面上有 $m$ 个特殊点，每个点有一个颜色。还有 $n$ 个点均匀分布在半径为 $r$ 的圆上，认为有一个点在 $(r,0)$。现在问有多少种方式，可以在这些点之间连线，满足：每个点度数是 $0$ 或 $2$这些线段与点构成了若干个封闭的简单多边形，并且互不相交，互不包含所有相同颜色的特殊点必须在同一个多边形内每一个多边形内部至少要有一个特殊点每一个特殊点至少要在一个多边形内部问这样分...

  • RainAir
  • June 5, 2021
  • No comments

    • SRM579 RockPaperScissors

    题意你要和一堆骰子玩剪刀石头布。有 $n$ 个骰子，每个骰子有三种结果：R，S，P。概率分别是 $pR_i,pS_i,pP_i$。每次你会随机选择一个没有用过的骰子，然后你决定好出什么，然后扔这个骰子。如果获胜得 $3$ 分，平局得 $1$ 分，失败得 $0$ 分。你无法分辨出每一次拿出的骰子是什么，但你可以通过每一局的结果来决策之后的操作。求期望最多可以获得多少得分。$1 \leq n \...

  • RainAir
  • June 5, 2021
  • No comments