不写了

Read more

本帖所有内容均来自 Open Cup News 频道(https://t.me/opencup_ru), 若信息有冲突请以频道内容为准.

本帖所提及的发帖时间均指莫斯科时间 (UTC +3)

05/27/2020 18:48: The rules for the next season will be adjusted soon, so stay tuned
09/24/2020 13:03: The next season starts with GP of Eurasia at the Sep 27, followed by some GP based on one of Petrozavodsk problemsets in a week and the GP of Korea in two weeks.
09/25/2020 14:24: New changes in the OpenCup rules are coming. First, there will be no Div 1 Yandex Sponsor Championship for NERC ICPC teams this year. Second: the team with participant who is author or tester of the some Grand Prix, earns the team's season average score for this Grand Prix (note that this value changes through whole season and will be finalized only at the season ends). Third: there may be some changes in team formation rule, those changes are under consideration
10/26/2020 14:24: GP of Siberia will be held at the Nov 1, GP of Weihai at the Nov 8. As for Nov 15, there still no decision if there will be any Grand Prix.
11/26/2020 04:08: GP of NorthBeach (aka GP of Bei Sha Tan) will be held at the Nov 29.
12/14/2020 11:09: GP of Xiaomi will be held at the Dec 20. For the teams participated in the MW results from MW will be integrated.. Usual time. The early participation hopefully will be opened very soon.
12/24/2020 02:04: GP of Samara will be held at the Jan 3. 2021. For the teams participated in the MW results from MW will be integrated. Usual time. The early participation will be opened
12/24/2020 02:11: No GP is planned for Dec 27 due to intersection with AtCoder event
01/09/2021 18:24: GP of Nanjing will be held on Jan 10 (tomorrow)
01/28/2021 23:48: GP of Krakow will be held on Jan 31, usual time. For the Petrozavodsk camp teams the camp participation will count
01/28/2021 23:49: Feb 7 and Feb 14 here will be GP too, based on Petrozavodsk contests. Names of the GP will be announced later
01/29/2021 10:30: GP of Nizhny Novgorod will be held on Feb 7, usual time. For the Petrozavodsk camp teams and ICPC/Shanghai Training camp teams the camp participation will count.
02/06/2021 17:03: GP of Belarus will be held on Feb 14, usual time. For the Petrozavodsk camp teams the camp participation will count
02/06/2021 17:04: GP of Suwon will be held on Feb 21, usual time. For the Petrozavodsk camp teams the camp participation will count
02/25/2021 04:12: GP of Tokyo will be held on Feb 28, usual time.
04/23/2021 23:18: GP of China will be held on May 2, usual time. For the MW teams the camp participation will count
05/03/2021 21:43: GP of Urals will be held on May 9, usual time. Ural championship onsite teams results will be counted
05/03/2021 21:44: With good chances there will be two GP at May 16 and May 23, names and other details will be told at short time
05/06/2021 14:11: The GP at May 16 is cancelled. GP of Southern Europe will be held on May 23, usual time.
05/16/2021 21:15: Due to SEERC is moved from Sat to Sun, the GP of Southern Europe will start at 16:00 Moscow time (5 hours later than the standard time). The ext teams link appears approximatelly at the standard time or hour later.
05/16/2021 21:16: Today the final contest for the XX Open Cup was held online. The winner is USA1, the runner-up is Past Glory, third place goes to Polish Mafia. Congratultations to the winners!
05/23/2021 11:06: The ext teams may start the GP of Southeastern Europe from now. The link for the GP of Southeastern Europe is http://official.contest.yandex.com/opencupXXI/contest/27619/enter
06/02/2021 17:21: GP of Beijing will be held on June 6, usual time, on the CCPC Finals tasks

本帖最后更新于 06/03/2021 09:58 (UTC +3)

Read more

A

把所有形如$(a,ka)$的路径提出来，共有$O(n\log n)$条路径，后面将这种路径称为限制。

考虑答案路径如果要不合法，那么必然覆盖了至少一条完整的限制。

考虑覆盖限制$(u,v)$的路径$(a,b)$，设$dfn_x$表示$x$的$dfs$序，$end_x$表示$x$的子树中最大的$dfs$序，不妨设$dfn_u < dfn_v,dfn_a < dfn_b$。

当$u$是$v$的祖先的时候，考虑$g$是离$u$最近的路径$(u,v)$上的点，要么$dfn_a < dfn_g,dfn_v\leq dfn_b\leq end_v$，要么$dfn_v\leq dfn_a\leq end_v,dfn_b>end_g$。
当$u$不是$v$的祖先的时候，显然$dfn_u\leq dfn_a\leq end_u, dfn_v\leq dfn_b\leq end_v$。

第一种情况构成了$2$个矩形，第二种情况构成了$1$个矩形。

最终我们只要求出所有矩形的并然后取个反即可，扫描线$+$线段树，总复杂度$O(n\log^2 n)$。

B

观察一下可以发现，如果将同一行与同一列的$1$用边连起来，一种方案可以拆成很多个环，从这个方面入手。

设$f_n$表示$n\times n$矩阵的答案，我们枚举第一行所在环的大小，那么有递推式： $$f_n = \sum_{i = 2}^{n}A_i\cdot \binom{n}{i}\cdot \binom{n - 1}{i - 1}\cdot f_{n - i}$$

其中$A_i$表示$i\times i$的矩阵只有一个环的方案数，$\binom{n}{i}$表示选出$i$列，$\binom{n-1}{i-1}$表示选出除了第$1$行的剩下的$i-1$行。

先给出结论：$A_n = \frac{n!(n-1)!}{2}$，那么式子化成： $$f_n = \sum_{i = 2}^{n}\frac{i!(i-1)!}{2}\cdot \binom{n}{i}\cdot \binom{n - 1}{i - 1}\cdot f_{n - i}$$

将组合数拆开化简，得到： $$f_n = \frac{n!(n-1)!}{2}\sum_{i = 2}^{n}\frac{f_{n-i}}{((n-i)!)^2}$$

设$g_n = \frac{f_n}{(n!)^2}$，那么有： $$g_n = \frac{1}{2n}\sum_{i = 2}^{n}g_{n - i}$$

维护前缀和即可，复杂度$O(n)$。

现在考虑怎么证明$A_n = \frac{n!(n-1)!}{2}$。

先$n!$每行每列放一个$1$，设$p_i$表示第$i$行$1$的列编号。在$p_1$列放第二个$1$ 有$n-1$种方案，假设第二个$1$行号为$q_i$，那么接下来考虑$p_{q_i}$列，这列第二个$1$有$n-2$ 种放法，因为不能在此时返回第一行，再加上已有$2$个$1$的行不能再放$1$。接下来就是$n-3...$。除以二是因为这个过程的逆过程也被计算过了。

C

一眼费用流裸题，但是数据范围有点大，考虑动态维护流量。

设当前加入的点编号为$x$，因为深度是$O(\log n)$的，因此我们可以枚举$x$和$x$要到的点的LCA，对于当前LCA设为$g$，我们需要求出$g$往子树中走最小的代价使得可以流到一个还有剩余容量的点，设为$down_g$。注意子树中行走的代价可以根据每条边的流量正负来确定，因此要维护每条边的流量，其实就是手动维护网路流。我们需要求出$down_g+cost(x\rightarrow g)$中代价最小的那个，然后暴力维护每条边的流量即可。

复杂度$O(n\log n)$。

Read more

似乎 BZOJ 挂了以后就没有地方有 JSOI 2017 的题目了，于是上传了一下。

JSOI 2017 Round 1 Day 1: https://qoj.ac/contest/121
- [JSOI 2017] 王国
- [JSOI 2017] 预言
- [JSOI 2017] 代码
JSOI 2017 Round 1 Day 2: https://qoj.ac/contest/122
- [JSOI 2017] 骑士
- [JSOI 2017] 街道
- [JSOI 2017] 奥术
JSOI 2017 Round 2 Day 1: https://qoj.ac/contest/123
- [JSOI 2017] 原力
- [JSOI 2017] 隧道
- [JSOI 2017] 税收
JSOI 2017 Round 2 Day 2: https://qoj.ac/contest/124
- [JSOI 2017] 码农
- [JSOI 2017] 博弈
- [JSOI 2017] 魔法

Enjoy!

Read more

这篇博客可以公开，就公开了。

A

算法1

$O(2^n)$ 枚举一下每个点染成什么颜色，然后从底向上确定每一个点的权值，如果所有点的权值都 $\geq 0$，则这是一组合法解，输出 POSSIBLE 否则继续做。

若没有合法解，则输出 IMPOSSIBLE。

时间复杂度 $O(n \cdot 2^n)$，期望得分 20 分。

算法2

可以考虑用树形 DP 来做。用 $f_{i,j}$ 表示 $i$ 的子树里和 $i$ 颜色不同的点的权值和为 $j$ 可不可行。从底向上树形 DP 即可。

时间复杂度 $O(nv^3)$，期望得分 40 分。

算法3

因为这部分数据是一条链，从底向上 dp 用 $f_{i,j}$ 表示是否存在一个合法方案满足上一个与 $i$ 颜色不同的节点是 $j$ 转移的时候，对于 $i$ 号点，枚举上一个和它颜色相同的点 $k$ ，如果 $f_{i+1,k}=\mathsf{true}$ 且 $v_i\geq v_k$，那么这就是一种合法方案。

时间复杂度 $O(n^2)$，期望得分 20 分。

算法4

因为一个点的点权 $a$ 可以是 $\geq 0$ 的任意数，所以 $i$ 的子树里 (不包括 $i$)，和 $i$ 颜色相同的点的权值和要 $\leq v_i$ ，那么显然权值和要越小越好。那么可以参考算法 2 ，此时不需要两维 dp 了，只需要用 $f_i$ 表示 $i$ 的子树里和 $i$ 颜色不同的点的权值和的最小值。因为这部分数据里一个点的儿子最多只有 $16$ 个，可以用 $2^{16}$ 枚举每个儿子 $j$ 和 $i$ 的颜色是否相同，若相同，则它的贡献是 $v_j$，否则贡献是 $f_j$，然后更新一下 $f_i$，从底向上 DP 。时间复杂度 $O(n \cdot 2^{16})$，期望得分 20 分。

算法5

算法 4 已经很接近标算了。只需要把算法 4 中 $2^16$ 的 0,1 枚举改成背包即可。时间复杂度 $O(nv)$，期望得分 100 分。

B

基础知识

https://en.wikipedia.org/wiki/Laplacian_matrix

Laplacian matrix for ''simple graphs''

Given a simple graph $G$ with $n$ vertices, its Laplacian matrix $L_{n \times n}$ is defined as

$$L = D - A$$

where $D$ is the degree matrix and $A$ is the adjacency matrix of the graph. Since $G$ is a simple graph, $A$ only contains 1s or 0s and its diagonal elements are all 0s.

In the case of directed graphs, either the indegree or outdegree might be used, depending on the application.

The elements of $L$ are given by

$$L_{i,j} := \begin{cases} \deg(v_i) & \mbox{if}\ i = j \\ -1 & \mbox{if}\ i \neq j\ \mbox{and}\ v_i \mbox{ is adjacent to } v_j \\ 0 & \mbox{otherwise} \end{cases} $$

where $\operatorname{deg}(v_i)$ is the degree of the vertex $i$.

Symmetric normalized Laplacian

The symmetric normalized Laplacian matrix is defined as:

$$L^\text{sym} := D^{-\frac{1}{2}} L D^{-\frac{1}{2}} = I - D^{-\frac{1}{2}} A D^{-\frac{1}{2}}$$

The elements of $L^\text{sym}$ are given by

$$L^\text{sym}_{i,j} := \begin{cases} 1 & \mbox{if } i = j \mbox{ and } \deg(v_i) \neq 0\\ -\frac{1}{\sqrt{\deg(v_i)\deg(v_j)}} & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j \\ 0 & \mbox{otherwise}. \end{cases}$$

Random walk normalized Laplacian

The random-walk normalized Laplacian matrix is defined as:

$$L^\text{rw} := D^{-1}L = I - D^{-1}A$$

The elements of $L^\text{rw}$ are given by $$L^\text{rw}_{i,j} := \begin{cases} 1 & \mbox{if } i = j \mbox{ and } \deg(v_i) \neq 0\\ -\frac{1}{\deg(v_i)} & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j \\ 0 & \mbox{otherwise}. \end{cases}$$

Generalized Laplacian

The generalized Laplacian $Q$ is defined as:

$$\begin{cases} Q_{i,j} < 0 & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j\\ Q_{i,j} = 0 & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is not adjacent to } v_j \\ \mbox{any number} & \mbox{otherwise}. \end{cases}$$

Notice the ordinary Laplacian is a generalized Laplacian.

Adjugate matrix

The adjugate matrix $\operatorname{adj}(A)$ is the transpose of the matrix of the cofactors, that is, : $(\operatorname{adj}(A))_{ij} = (-1)^{i+j} M_{ji}.$

For every matrix, one has

$$(\det A) I = A\operatorname{adj}A = (\operatorname{adj}A)\,A. $$

Thus the adjugate matrix can be used for expressing the inverse of a [[nonsingular matrix]]:

$$A^{-1} = \frac 1{\det A}\operatorname{adj}A. $$

暴力：

60 分做法：我们只需要枚举每条边，看看这条边出现在多少个树形图中，将这个值乘上边权，累加就是答案了。

如何求这条边在多少个树形图中呢？可以用补集转换，先求出树形图的总数；然后将这条边从图上删去，即在矩阵上加加减减，求出树形图个数，两者相减就是我们所要的值。

每次求一遍行列式，效率为 $O(mn^3)$

标算

容易发现，求解的 $m$ 次行列式，每次只会修改矩阵某一行的两个值。运用简单的线性代数知识，可以求出基尔霍夫矩阵的伴随矩阵，就可以 $O(1)$ 计算行列式了！

至于伴随矩阵，可以求出逆矩阵，乘上行列式即可；至于逆矩阵，和原矩阵一起消元就可以啦！$O(m+n^3)$

C

The lower bound on the number of groups if $k$ is odd is $\sum_{i=\frac{k+1}{2}}^k \binom ni$: all subsets of size at least $\frac{k+1}{2}$ have to belong to different groups. Similarly, if $k$ is even, the lower bound is $\frac{1}{2} \binom{n}{k/2} + \sum_{i=k/2+1}^k \binom ni$.

Note that $\binom ni \geq \binom {n}{k-i}$ when $i \geq k/2$. Hence, if we can match all subsets of size $i$ with subsets of size $k-i$ into non-intersecting pairs without common elements, we can achieve the lower bound.

Such a matching always exists when $i \ne k-i$, since the graph is bipartite and “regular” (not exactly, but all vertices in each part have equal degrees). When $k$ is even, the graph is not bipartite, but it turns out that forming $\left\lfloor \frac{1}{2}\binom{n}{k/2} \right\rfloor$ pairs of subsets of size $\frac k2$ is always possible for $n \leq 17$. Even though the graphs are huge, we can build them and try to find maximum matchings: using Kuhn’s algorithm for bipartite graphs, and using Edmonds’ blossom algorithm (or maybe Kuhn’s algorithm with hacks...) for non-bipartite graphs. Even though time complexity looks big, a greedy initialization already builds a huge part of the matching, and augmenting chains are very short on average too. You can try all possible test cases to make sure your solution is fast enough.

If you know a constructive way to build the matchings, or if you have a proof that an optimal matching of subsets of size $\frac k2$ for even $k$ always exists, please share!

Qingyu的博客

博客

迁移

XXI Open Cup 新闻合集

Easy Contest Tutorial

A

B

C

JSOI 2017 题目合集

省选入门赛题解

A

算法1

算法2

算法3

算法4

算法5

B

基础知识

暴力：

标算

C

上半年附加题合集

Archive I

Archive II

Archive III

Archive IV

Archive V

Archive VI

Archive VII

Archive VIII

Archive IX

Archive X

你OJ278的详细题解

下发文件密码合集

题库功能已更新

题解