Welcome To YuGao's House

被浏览
置顶

欢迎来到我的个人主页,Have a good time! ヾ(≧▽≦*)o

于 2018/4/21,终于借助 Hexo 和 Coding 的页面托管服务将个人主页搭建完毕。

于 2019/1/28,更新主题并换用 Netlify 托管。

于 2019/7/21,更换Valine评论后端储存,评论丢失,从零开始。

P.S. 如果有谁想一起建个人主页的,可以通过”关于”联系我一起探讨,顺便交换一下友链蛤

CF498B Name That Tune

被浏览

作为一道英文题先解释一下题意。

用 $T$ 秒时间按顺序听 $N$ 首歌,第 $i$ 首歌播放时间为 $t_i$ 秒,且每播放一秒都会有 $p_i$ 的概率被识别出来,跳到下一首。某首歌播放时间过完默认被识别,也跳到下一首。若时间有剩余而歌已全部听完则直接结束。求识别出歌数量的期望。

看见题目就想到期望DP。

第一眼想到的方程是设 $f_{i,j}$ 表示第 $i$ 秒识别到第 $j$ 首歌的期望,不难想出一个 $O(n^3)$ 的算法。

枚举一个 $k$ 表示第 $j$ 首歌已经放了几秒,注意一下边界即可。

什么是P问题、NP问题和NPC问题

被浏览

为了准备初赛,发现自己对P问题、NP问题和NPC问题一点都不熟悉,在网上找到了 Matrix67 大佬的博文,感觉很棒,所以转载一下。

其实是太久没写博文了来充数的

原文链接

遵循署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

以下为原文,对公式略加修改,删改了逻辑电路部分内容,并且重绘了逻辑电路图(原文排版实在难以看清)。

CF643D - Bearish Fanpages

被浏览

作为一道英文题,我们先解释一下题意。

题面有点长就不解释了,大家自己翻译吧。

首先有一个 Simple 的想法,直接维护啊,变的节点又不多,修改不是 $O(1)$ 的吗?

然后发现错了。

网络流24题

被浏览

前言

最近发现网络流只会板子不会模型转换,于是来做网络流 24 题。

本文代码以 LibreOJ 上的数据为准,Luogu 的题面可能稍有不同。

本文不定时更新。 (有可能永久咕咕咕)

美化你的PowerShell

被浏览

前言

作为 Windows 用户,常羡慕 Linux 用户高端大气的终端。

其实,Windows 自带的 PowerShell 也十分的强大。

但是过于简陋的界面不知道劝退了多少用户,于是让我们来美化一下 PowerShell 吧。

以下教程环境均为 PowerShell 5.x。

洛谷P4884 - 多少个1?

被浏览

我们通过观察可以发现 $11\cdots1$ 可以变化为 $\frac{10^{n}-1}{9}$,于是根据取模的性质,我们可以把原式两边同乘九再加一、原式变为 $10^{n} \equiv k \cdot 9 + 1 \pmod m$,发现这是个 BSGS 的标准式子,由于$m$保证为质数,所以也不必用拓展 BSGS。

CF1037D - Valid BFS?

被浏览

作为一道英文题,我们先解释一下题意:

给你一棵树和它的一个 BFS 序,让你判断这个 BFS 序是否是一个从节点 1 开始的合法 BFS 序。

接下来我们进入正题。

第一眼看到这题时,大部分人都会想到,既然是树,那么它一定是一层一层地向下 BFS。

也就是说,BFS 序中越后出现的节点,它树上的深度肯定是大于它前面的节点的。

于是照这个思想打完后,发现 Wrong Answer 了。