2019华工校赛 - B, F, H, K题题解

本场比赛四道中等题,其中三道题数据范围故意放水降低难度。 然后。。没放水那题。。好像。。没人过啊。。? B - 修仙时在做什么?有没有空?可以来炼丹吗? 题目链接 M姓出题人:这么老的idea怎么还没人做XD 考虑到本题的idea非常古老,所以在预估难度时设为中等题,然而现场没人过。题意本质上就是给出一个含$2^{18}$个结点的无向连通图,再指定其中$n$个点,求这$n$个指定点的两两之间的最短路的最小值。 接下来的讨论假定$n$个指定点的编号两两不同(如果出现相同编号的话答案就是$0$)。我们不妨考虑二进制分组。

  • fshp971
    fshp971
11 min read
ACM

2019华工校赛 - D, G, J题解

D - 神经网络 题目链接 这是一道经典题目改编,原题是dreamoon出的NTU-WF选拔赛D题(题目链接)。 不难发现,修复时所产生的花费,可以分解为一系列有向简单路径上结点权值之和。因此由期望的线性性可知,要求总花费的期望值,我们只需分别计算$n^2$条有向简单路径对总花费产生贡献的期望值。 对于树上一条有向简单路径$u \rightarrow v$,设该路径长度为$d \ (0 \leq d \leq n-1)$(也就是说有$d$条边,$d+1$个结点)

  • fshp971
    fshp971
15 min read
hihoCoder 1579 : 统计后缀数组相同的字符串个数
ACM

hihoCoder 1579 : 统计后缀数组相同的字符串个数

今年北京网赛出了一道字符串计数论文题hihoCoder 1579,简单来说就是给定一个后缀数组,统计有多少个仅含小写字母的字符串的后缀数组和它一样。 既然有论文,那就来学习一下咯。论文叫Counting suffix arrays and strings,里面有大段大段看不懂的数学证明,我这里就大概说下结论吧。 令$P[]$为一长度为$n$的后缀数组(此时$P[]$是$n$的一个排列)。 令$R[]$表示$P[]$对应的rank数组。$R[i]=j$当且仅当$P[

  • fshp971
    fshp971
2 min read
Blog搭建流程(一):在服务器上搭建Ghost
网络

Blog搭建流程(一):在服务器上搭建Ghost

Upd 2018-12-26: 这篇流程仅针对ghost v0.x,新版ghost可以直接用官方推荐的工具ghost-cli来完成安装,我这几天也将博客升级成了ghost v2.x。 需要注意的是,ghost官方的安装教程是基于ubuntu的。如果你像我一样在centos7上安装ghost,数据库最好不要用yum中默认的mysql开源版本mariaDB,否则可能会出现各种神乎其神的bug。推荐使用官方源安装mysql,或者改用sqlite3。 连续搞了几个晚上 (肝要废了),今天终于弄好了Ghost Blog+域名+全局SSL (好菜啊)。那第一篇blog就来说说搭建流程咯。 准备服务器 首先你需要买个服务器,国外的话可以考虑Vultr或者DigitalOcean,这两个有5刀/月的服务器卖;国内的不是很了解,但要注意若服务器在国内,建网站是需要去备案的。我用的是Vultr的5美元服务器(

  • fshp971
    fshp971
5 min read