Posted in: 比赛公告

Goodbye 2019

时间过得真快啊,2019年已经接近尾声了。

在2019年里,小E碰到了许多事情,其中最重要的就是认识了小L。他们两个人一起干过了许多愉快的事情(这里请各位看官自己脑补)。

有一天,小E突然意识到一件事情,他们还没有一起出过一场比赛!

于是就有了这场象征着告别2019的历史的比赛了。

本次比赛时长4小时,共有5题,将在2019年12月28日(星期六)13:30开始,难度横跨入门到csp-s中的中等偏难,出题人是 limstashEncodeTalker 。本次比赛不分设Div1和Div2.

赛制采取类OI赛制,每一题的测试数据被分成了若干subtask,只有通过了某一subtask的全部测试数据才能获得这个subtask的所有分数,同时对每个subtask良心的出题人都造了一组样例数据,在提交代码时会作为pretest进行测试。

祝大家玩得开心!GL&HF!

UPD:由于各种原因,本次比赛不提供赛时答疑,出题人将会尽可能保证不出锅qwq。

UPD2:Solution

Posted in: 解题报告

HNOI 2018 省队集训 Day 1 – 解题报告

A - Tree

这道题粗看需要 Link Cut Tree,其实不然:如果我们仍然在把节点 $1$ 作为根节点来处理子树信息、放入线段树,之后的询问我们只需要灵活的分类讨论即可。在实根为 $root$ 时,$u, v$ 之间的 $LCA$ 显然是 $lca(u, v), lca(root, u), lca(root, v)$ 之间深度最大的那一个。而修改权值和查询权值,只需要讨论两种祖先关系和平行关系即可。

Read More "HNOI 2018 省队集训 Day 1 – 解题报告"

Posted in: QuestOJ 比赛题解

「FZOI」OI 周赛 #1 Div.1 – 题解

致歉

由于准备的比较仓促,所以这次周赛组题上出现了一些问题,并对受影响的选手表示道歉。

题解

A - 回旋旅行

显然是一个 Hamilton 路径,设置状态$dp[stat][j]$来进行转移即可。

B - 模拟赛水题

这道题的原题是 CF1257E。考虑对于当前三个序列的每一个序列都在值域上做一个前缀和,记为$prefix_1[i], prefix_2[i], prefix_3[i]$。考虑枚举值域上的两个断点$i, j$,那么操作次数则为:$prefix_1[n] - prefix_1[i] + prefix_3[j] + prefix_2[i] + prefix_2[n] - prefix_2[j]$。这样做$\Theta(n^2)$次,取最小值即可拿到答案,可以得到 60 分。

那么正解是啥?我们发现式子中有两项可以放在一起来算:$prefix_3[j] - prefix_2[j], i < j$。我们只要考虑让这个部分最小即可让当前选中$i$的决策下值最小。做个后缀最小值即可。

C - 彩灯

这道题的出题人为长沙市雅礼中学的 Wearry。以下是他的原题解:

<hr >

子区间之间只有相互包含和不交的关系,因此它们的包含关系会构成一棵树。

首先考虑一个暴力的解法,
记 $f[i][j]$ 表示在 $i$ 为根的子树中点被覆盖的最多次数为 $j$ 的最优答案,
转移的时候首先将所有子树的答案直接合并,然后考虑点 $i$ 的贡献:

$$
f[i][j] = \max{f[i][j], f[i][j-1] + a[i]}
$$

不难发现可以维护 $f[i]$ 的差分表,
则 $f[i]$ 的差分表一定单调,
则合并子树相当于将差分表对应相加,
点 $i$ 的贡献则相当于将 $a[i]$ 按照大小顺序插入差分表。

Posted in: QuestOJ 比赛题解

kal0rona 的 CSP-S2 模拟赛 #1 出题分析

Day 1

篮球 - Basketball

前 30% 的数据

直接枚举上场状态和中间断开的点,由于上场状态只有上场和不上场,所以总的复杂度是$\Theta(2^n n)$。

正解

我们发现球员的数位非常小,且上场球员也非常少。那么,我们可以考虑设计一个前缀异或和还有后缀与和,那么在相同的数字上相乘即可得到结果。$prefix[i][j]$表示前$i$个中,能凑成$j$的方案数,$suffix[i][j]$表示$[i, n]$中,能凑成$j$的方案数。相乘的时候要固定后缀部分一定要选当前球员,这样可以避免算重。

Read More "kal0rona 的 CSP-S2 模拟赛 #1 出题分析"