Contest0117 (SHOI2017)

还好没生在上海。。。

T1 摧毁树状图

题面太长不放了，大意是一颗树，删除其中最多有一个交点的两条链，得到的最多联通块

非常暴躁的树形DP

BZOJ2738 矩阵乘法 传送门

Description

　　给你一个N*N的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第K小数。

Input

　　第一行两个数N,Q，表示矩阵大小和询问组数；
　　接下来N行N列一共N*N个数，表示这个矩阵；
　　再接下来Q行每行5个数描述一个询问：x1,y1,x2,y2,k表示找到以(x1,y1)为左上角、以(x2,y2)为右下角的子矩形中的第K小数。

BZOJ2001 HNOI2010城市建设 传送门

Description

PS国是一个拥有诸多城市的大国，国王Louis为城市的交通建设可谓绞尽脑汁。Louis可以在某些城市之间修建道路，在不同的城市之间修建道路需要不同的花费。Louis希望建造最少的道路使得国内所有的城市连通。但是由于某些因素，城市之间修建道路需要的花费会随着时间而改变，Louis会不断得到某道路的修建代价改变的消息，他希望每得到一条消息后能立即知道使城市连通的最小花费总和， Louis决定求助于你来完成这个任务。

BZOJ4025二分图 传送门

Description

神犇有一个n个节点的图。因为神犇是神犇，所以在T时间内一些边会出现后消失。神犇要求出每一时间段内这个图是否是二分图。这么简单的问题神犇当然会做了，于是他想考考你。

NKOJ2670 动态区间第K小数

%%%a58124751…

整体二分

二分一个mid,以时间顺序讨论，对于值小于等于mid的数和修改，用树状数组统计起来

由于是以时间顺序讨论，所以当前讨论的询问中，若满足k个，说明它的答案是小于mid的（因为树状数组里只统计了小于mid的值），将它划到左边继续讨论

CDQ分治

慢慢更吧。。。

Problem List:戳这里

I’m Darth Vader.Hahaha