Dy's Home

Seize the day. Gather ye rosebuds while ye may.

--Dead Poets Society

  • 2017-04-12

    HNOI2015 接水果
    风见幽香非常喜欢玩一个叫做 osu!的游戏,其中她最喜欢玩的模式就是接水果。由于她已经DT FC 了The big black, 她觉得这个游戏太简单了,于是发明了一个更加难的版本。首先有一个地图,是一棵由 $n$ 个顶点、$n-1$ 条边组成的树。这颗树上有 $P$ 个盘子,每个盘子实际上是一条路径),并且每个盘子还有一个权值。第 $i$ 个盘子就是顶点$a_i$到顶点$b_i$的路径(由于是树,所以从$a_i$到$b_i$的路径是唯一的),权值为$c_i$。
    分类: 省选  标签: 莫队 

  • 2017-04-10

    NOI 2015 寿司晚宴
    为了庆祝 NOI 的成功开幕,主办方为大家准备了一场寿司晚宴。小 G 和小 W 作为参加 NOI 的选手,也被邀请参加了寿司晚宴。在晚宴上,主办方为大家提供了 $n−1$ 种不同的寿司,编号 $1,2,3,…,n−1$,其中第 $i$ 种寿司的美味度为 $i+1$ (即寿司的美味度为从 $2$ 到 $n$)。现在小 G 和小 W 希望每人选一些寿司种类来品尝,他们规定一种品尝方案为不和谐的当且仅当:小 G 品尝的寿司种类中存在一种美味度为 $x$ 的寿司,小 W 品尝的寿司中存在一种美味度为 $y$ 的寿司,而 $x$ 与 $y$ 不互质。现在小 G 和小 W 希望统计一共有多少种和谐的品尝寿司的方案(对给定的正整数 $p$ 取模)。注意一个人可以不吃任何寿司。
    分类: NOI  标签: DP 

  • 2017-04-10

    HNOI2015 开店
    风见幽香有一个好朋友叫八云紫,她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。最近她们灵机一动,打算在幻想乡开一家小店来做生意赚点钱。这样的想法当然非常好啦,但是她们也发现她们面临着一个问题,那就是店开在哪里,面向什么样的人群。很神奇的是,幻想乡的地图是一个树形结构,幻想乡一共有 $n$个地方,编号为 $1$ 到 $n$,被 $n-1$ 条带权的边连接起来。每个地方都住着一个妖怪,其中第 $i$ 个地方的妖怪年龄是 $x_i$。
    分类: 省选  标签: 树链剖分  主席树 

  • 2017-04-09

    ZJOI 2009 对称的正方形
    Orez很喜欢搜集一些神秘的数据,并经常把它们排成一个矩阵进行研究。最近,Orez又得到了一些数据,并已经把它们排成了一个n行m列的矩阵。通过观察,Orez发现这些数据蕴涵了一个奇特的数,就是矩阵中上下对称且左右对称的正方形子矩阵的个数.Orez自然很想知道这个数是多少,可是矩阵太大,无法去数。只能请你编个程序来计算出这个数。
    分类: 省选  标签: Manacher 

  • 2017-04-08

    ZJOI 2010 贪吃的老鼠
    奶酪店里最近出现了$m$只老鼠!它们的目标就是把生产出来的所有奶酪都吃掉。奶酪店中一天会生产$n$块奶酪,其中第$i$块的大小为$p_i$,会在第$r_i$秒被生产出来,并且必须在第$d_j$秒之前将它吃掉。第$j$只老鼠吃奶酪的速度为$s_j$,因此如果它单独吃完第i快奶酪所需的时间为$p_i * s_j ^ {-1}$。老鼠们吃奶酪的习惯很独特,具体来说:
    分类: 省选  标签: 网络流