SkyWT

Fighting 2019!

2019.11.07 Upd:其实不是真的完结了,有些题目实在搞不动 QwQ
还有太多薄弱的地方要补了,这个项目就先到此为止吧。
今年联赛比完可能就要退役了,那些 To be continued 的格子可能不会 be continued 了
更多伤感的话还是在退役总结里写吧……

Read more...

发布 0 条评论

Codeforces Round #578 (Div. 2)

D - White Lines

Description

*1900

给出一个 n\ast m 的黑白矩阵,你可以将一块 k\ast k 的矩形全部变成白色。
问你执行一次上述染色之后,全空白的行和全空白的列数量总和的最大值。

数据范围:n,m\leq 2000

Read more...

发布 0 条评论

Codeforces Round #581 (Div. 2) 比赛链接:LInk

C - Anna, Svyatoslav and Maps

Description

给出一张有向图,每条边的边权都是 1。给出一个 m 个点的路径序列 {p_i },表示依次经过这 m 个点的路径。路径序列中相邻元素之间有边相连。
现在需要你找出这个序列的一个最短的子序列 {v_i },长度为 k,使得经过这 k 个点的路径也经过 {p_i } 中所有点。

Read more...

发布 0 条评论

Description

给出一个长度为 n 的数列,2\leq n\leq 4\ast 10^5,每个数字 a_i 都在 [1,20] 内。
可以对这个数列中相邻的两个数字交换位置,最终要使得相同的数字都在一起。
求最小交换次数。

LInk

Read more...

发布 0 条评论

树链剖分,可以把一棵树划分成多条链,对于每条链可以用线段树等数据结构进行维护,将树形结构的问题转化。

常见的方法是轻重链剖分,即 Heavy-Light Decomposition。

Read more...

发布 0 条评论

引言

Bitset 是一种利用对布尔数组压位存储的方法,达到优化时间常数、空间常数的目的的黑科技。利用 Bitset,可以方便地对布尔数组进行按位逻辑运算,优化 32 或 64 的常数。在某些素质极差的卡常题中运用会有奇效。

Read more...

发布 0 条评论

转自知乎:八大排序算法稳定性分析,原来稳定性是这个意思……
这是 €€F 非常喜欢的排序稳定性分析……

稳定性定义: 排序前后两个相等的数相对位置不变,则算法稳定。
稳定性的好处: 从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。

各排序算法的稳定性:

  1. 堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法;
  2. 基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

Read more...

发布 0 条评论

快看看 CCF 是怎么把初赛完成脑筋急转弯竞赛的……

孙某和张某是考古学家老李的学生。有一天,老李拿了一件古物来考验两人,两人都无法验证出来这件古物试谁的。老李告诉了孙某拥有者的姓,告诉张某拥有者的名,并且在纸条上写下以下几个人的人名,问他们知道谁才是拥有者?
纸条上的名字有:沈万三、岳飞、岳云、张飞、张良、张鹏、赵括、赵云、赵鹏、沈括。

  • 孙某说:如果我不知道的话,张某肯定也不知道。
  • 张某说:刚才我不知道,听孙某一说,我现在知道了。
  • 孙某说:哦,那我也知道了。

请问:那件古物是谁的?

Read more...

发布 0 条评论

\begin{bmatrix} x_{11} & x_{12} & x_{13} \\ x_{21} & x_{22} & x_{23} \\ x_{31} & x_{32} & x_{33} \end{bmatrix}

每增加一个维度,世界便会增加无限的美感。

Read more...

发布 0 条评论