[NOI2014]动物园

[NOI2014]动物园
这题其实和前面有一题似乎在梦中见过的样子很像,只是这里要j*2>i时跳fail而已。

跳&最短路


最短路
先走长再走短,两条边。反正就是沿着边界走就行了,为什么想走长再走短?你打个表就知道了,其实C就是一个组合数,然后自己枚举一下先走长还是想走短就知道了。

最短路

最短路

这题看看就是叫你建边跑最短路的,但眨眼一看,哇赛,为什么这么多边!这样明显就是为了卡SPFA了。所以我们就要用到Dij算法去解答这题,Dij算法就是让当前路径最短的那个点去找边,减少枚举情况。具体如何去找当前路径最短的点,我们可以使用堆优化的Dij算法,但是呢规模还是太大呢,自己写的堆不够高效,所以我们要采用系统配对堆进行解答。 ......  查看更多

NOIP提高组模拟赛Day2

NOIP提高组模拟赛题解

比赛地址
Markdown&PDF&大样例
[数据以及全部压缩包]明天发

Agent2

对于40\%的数据 N,M \leq 10^3

对于N,M \leq 10^3的数据,我们可以O(n^2)判断一下前面有多少Agent的区间是包括当前要查询的天数的。

对于100\%的数据 1 \leq a,b \leq N \leq 10^7,M \leq 4*10^5

我们可以通过树状数组维护一个差分数列,在每次询问中只要O(logn)进行修改或者进行查询,总复杂度为O(mlog_{n})。 ......  查看更多

NOIP提高组模拟赛Day1

NOIP提高组模拟赛题解

比赛链接
Markdown&PDF&大样例
[数据以及全部压缩包]明天发

Agent1

对于20\%的数据 N \leq 10

这样的话我们可以使用DFS搜索进行枚举,枚举每一个Agent是进A队还是进B队还是不参加大战,复杂度为O(3^{10})

对于40\%的数据 N \leq 10^3

然而我们也可以加入一些剪枝,例如中间判断一下有没有元素是不符合的就剪掉,例如B里加入了个比A里最大元素小的人,那么就剪掉,估计可以再卡过几个点。 ......  查看更多

[SDOI2008]Cave 洞穴勘测

[SDOI2008]Cave 洞穴勘测
此题又三个操作,连接x,y一边,摧毁x,y一边,问x,y是否联通。着就是动态树LCT裸题了,连接就link,摧毁就cut,询问联通就问x,y的根是否一样即可。

DZY Loves Chinese

DZY Loves Chinese
做这题时发现这里原来有第二道题,于是点进去看了看
DZY Loves Chinese II
注意对比两题红字部分
这题的K同样被异或了,然而后面又输入K个数字,这样预处理一下,就知道异或的到底是个什么东西了。
于是这题就变成简单的字符串模拟,然后暴力求一下最后一次的并查集即可。 ......  查看更多

[JLOI2014]松鼠的新家

[JLOI2014]松鼠的新家
这题想让你求一条路径里面经过每个点次数多少次。
一看到树就要想到树链剖分,剖分时候就加上路径之间相邻的两个点的值,由于是在某一段区间加上一个相同的值,所以可以用树状数组解决,然而每两个路径之间首尾都会有一个点重复,最后一个点不用计算,所以除了路径开头的那个点,其他点都要将答案减1 ......  查看更多

[SHOI2007]Vote 善意的投票

[SHOI2007]Vote 善意的投票[JLOI2010]冠军调查
看到这种题目就知道要跑网络流啦。只要把赞成的连原点流量为1,反对连汇点流量为1,其他每个朋友互相连一条流量为一的边,然后跑一遍最短路就好。