Dy's Home

Seize the day. Gather ye rosebuds while ye may.

--Dead Poets Society

  • 2018-04-16

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

  • 2018-04-09

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

  • 2018-03-08

    SDOI2017 切树游戏
    一棵树$T$,节点带权,两种操作. Change x y , 将编号为$x$ 的结点的权值修改为$y$ 。Query k, 询问有多少棵 $T$ 的非空连通子树,满足其中所有点权值的异或和恰好为$k$ 。
    分类: 省选  标签: DP  矩阵  树链剖分 

  • 2017-12-19

    Codeforces 382 Div1D Permutations
    你要生成一个长度为$n$的排列,有$m$个可行数对,每个可行数对形如'$b_i$这个数可以放在第$a_i$个位置上'。现在你知道通过这$m$个可行数对能够生成出来的排列的数量是奇数,对于每个可行数对,你想知道:如果把这个可行数对删掉,那么能够生成的排列的数量是否还是奇数.
    分类: TUOJ  Codeforces  标签: 矩阵  二分图 

  • 2017-12-18

    Monkey and Tree
    有一天, Monkey得到了一棵有个$N$节点的树。树上的边用一个三元组$(u_i,v_i,l_i)$来表示,意思是$u_i$和$v_i$之间有一条边长为$l_i$的边。于是可爱的Monkey和她的妹妹Little Monkey在树上开心地玩耍。她们要一起玩游戏。因为Monkey特别喜欢跑步,而且跑得特别快,所以她们两人决定在树上跑步。可起点和终点怎么决定呢?Monkey决定从$M$个点对$(a_i,b_i)$,中选出两个点对$(a_i,b_i)$ 和 $(a_j,b_j)$。然
    分类: TUOJ  标签: 点分治