Dy's Home

Seize the day. Gather ye rosebuds while ye may.

--Dead Poets Society

  • 2018-11-08

    集训队互测2018 矩形
    Snuke 使用动态规划解决了一道题目。具体来说,她设计了如下递推式:其中 $i,j$ 是非负整数,$a,b,c$是给定的常数,$f_i$是给定的数列。
    分类: TUOJ  标签: 离散数学 

  • 2018-11-08

    集训队互测2018 三角形
    Snuke 有一棵 $n$ 个点的有根树,每个点有权值 $w_i$,初始每个结点上都没有石子。Snuke 准备了一些石子,并把它们拿在手中。她可以进行以下两种操作任意多次:1.从手中取 $w_i$ 个石子放在结点 $i$ 上,进行该操作要求结点 $i$ 的所有孩子 $j$ 上都有 $w_j$ 个石子。2.将结点 $i$ 上的所有石子收回手中。
    分类: TUOJ  标签: 树链剖分  贪心 

  • 2018-04-24

    HAOI2018 Round1 解题报告
    考完HNOI,忽然听说要给HA出题,于是临时东拼西凑出了几个idea.有个idea也是在别的地方看到的(T2的一个核心结论),T1的模型似乎比较经典,而T3的算法其实并不优美,主要是缺一道工业题所以yy出一个奇怪的字符串匹配.
    分类: 省选  OI历程  标签: 其它 

  • 2018-04-16

    HNOI2018 游记与总结
    考前一直说就当作平常的考试来考,但那终究是一种理想的状态,到了考场上还是会紧张...题目出乎意料地难,三道题看起来都很可做,几次以为找到了正解没过一会儿就发现是假的。。旁边的同学似乎思如泉涌,然而我在开考近两个小时后才开始敲键盘,打的还是T1$O(nmq)$的暴力,如果严格按照数据给出的范围只有30分,T1部分分似乎没有考虑到很多复杂度劣于标算的算法。不过复杂度不太满,在数据较为随机的情况下效果不错,后来发现不开氧气vector比较慢又换成了数组。
    分类: OI历程  标签: 其它 

  • 2018-04-09

    HAOI2017 新型城市化
    有一个$n$个点的无向图,其中只有$m$对点之间没有连边,保证这张图可以被分为至多两个团.对于$m$对未连边的点对,判断有哪些点对满足将他们连边后最大团的大小增加.
    分类: 省选  标签: 二分图  网络流  图的连通性