Siyuan 的博客

「Codeforces Gym 102268K」Knowledge

题目链接：Codeforces Gym 102268K

你有一个长度为 $n$ 的字符串，只包含小写字母 a 和 b。

你可以进行任意次（包括 $0$ 次）如下操作：

• 从字符串任意位置删除子串 aa。
• 从字符串任意位置删除子串 bbb。
• 从字符串任意位置删除子串 ababab。
• 在字符串任意位置插入子串 aa。
• 在字符串任意位置插入子串 bb。
• 在字符串任意位置插入子串 ababab。

请求出最终能得到多少本质不同的长度为 $x$ 的字符串。答案对 $998244353$ 取模。

数据范围：$1 \le n \le 3 \times 10 ^ {5}$，$0 \le x \le 10 ^ {9}$。

「Codeforces Gym 102538F」Farm of Monsters

题目链接：Codeforces Gym 102538F

有 $n$ 个怪物，第 $i$ 个怪物有 $h_{i}$ 的血量。

你和对手要合力击杀这些怪物，你的攻击力为 $a$，对手的攻击力为 $b$。你们要轮流对活着的怪物进行攻击，你是先手。每次攻击，怪物都会损失攻击者的攻击力的血量。如果某一回合后被攻击怪物的血量非正，则它将会死亡，击杀它的人会得到 $1$ 分。当所有怪物都死亡后，游戏结束。

在你的回合，你可以选择任意攻击一只活着的怪物，也可以选择不进行攻击。

在对手的回合，对手会选择当前活着的、编号最小的怪物进行攻击。

如果你合理安排攻击策略，请求出你能获得的最大得分。

数据范围：$1 \le n \le 3 \times 10 ^ {5}$，$1 \le a, b, h_{i} \le 10 ^ {9}$。

「AtCoder Japan Alumni Group Summer Camp 2018 Day 2 K」Short LIS

题目链接：AtCoder Japan Alumni Group Summer Camp 2018 Day 2 K

给定 $n, a, b$，求满足如下条件的 $0 \sim n - 1$ 的排列 $P$ 的个数：

• $P$ 的最长上升子序列的长度至多为 $2$。
• $P_{a} = b$。

数据范围：$1 \le n \le 10 ^ {6}, 0 \le a, b < n$。

「UOJ 424」【集训队作业 2018】count

题目链接：UOJ 424

如果一个序列满足序列长度为 $n$，序列中的每个数都是 $1$ 到 $m$ 内的整数，且所有 $1$ 到 $m$ 内的整数都在序列中出现过，则称这是一个「挺好序列」。

对于一个序列 $A$，记 $f_{A}(l, r)$ 为 $A$ 的第 $l$ 个到第 $r$ 个数中最大值的下标（如果有多个最大值，取下标最小的）。

两个序列 $A$ 和 $B$ 同构，当且仅当 $A$ 和 $B$ 长度相等，且对于任意 $i \le j$，均有 $f_{A}(i, j) = f_{B}(i, j)$。

给出 $n, m$，求有多少种不同构的「挺好序列」。答案对 $998244353$ 取模。

数据范围：$1 \le n, m \le 10 ^ {5}$。

「TopCoder SRM 686B」CyclesNumber

题目链接：TopCoder SRM 686B

求所有长度为 $n$ 的置换的循环数量之和的 $m$ 次方。

本题有 $T$ 组数据。

数据范围：$1 \le T \le 300$，$1 \le n \le 10 ^ {5}$，$0 \le m \le 300$。

$$ \newcommand{\stra}[2]{\begin{bmatrix} #1 \\ #2 \end{bmatrix}} \newcommand{\strb}[2]{\begin{Bmatrix} #1 \\ #2 \end{Bmatrix}} $$

「AtCoder Regular Contest 106F」Figures

题目链接：AtCoder Regular Contest 106F

Takahashi 有 $n$ 个不同的零件和 $n - 1$ 个连接件，第 $i$ 个零件上有 $d_{i}$ 个不同孔。每个连接件可以插入属于不同零件的两个孔，每个孔不能插入多个连接件。现在，Takahashi 需要把用连接件把所有零件连接成一棵树，求出不同的连接方案数，答案对 $998244353$ 取模。

数据范围：$2 \le n \le 2 \times 10 ^{5}$，$1 \le d_{i} < 998244353$。

ZPCPC 2020 题解

比赛题目在 Gym 的地址：The 17th Zhejiang Provincial Collegiate Programming Contest

和两个高一小神仙组队（听说他们是第一次打 ACM？），没想到合作默契融洽，最后打了个 rank 18，可以说是非常快乐啦！

「HDU 6810」Imperative Meeting

题目链接：HDU 6810

给定一棵 $n$ 个节点的树，两点之间的距离定义为最短路径的边数。定义点集 $S$ 的权值为：

$$ f(S) = \min_{u \in \mathbb{V}} \left(\sum_{v \in S} \text{dist}(u, v)\right) $$

对于所有大小为 $m$ 的点集 $S$，求出 $f(S)$ 的总和，即求 $\sum_{\lvert S\rvert = m} f(S)$。

本题有 $T$ 组数据。

数据范围：$1 \le T \le 1000$，$1 \le m \le n \le 10 ^ {6}$。

算法树

暂时无可提供的摘要

「算法笔记」组合数学

老鸽子 Siyuan 时隔半年终于更新博客了！