[NOI2014]动物园

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

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的根是否一样即可。

[JLOI2014]松鼠的新家

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

[SHOI2007]Vote 善意的投票

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

[JLOI2010]冠军调查

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

[SCOI2015]国旗计划

[SCOI2015]国旗计划
这题简单来说就是给出n个区间,还有给去区间总长为m,问要多少个区间才能完全覆盖全部m长度的区间。
这题主要就是贪心做法,对于给一个区间,假如选择了它,就要选择在其区间内有另一个端点的区间,然后递增做一下贪心,看看最多有多少就行了。 ......  查看更多

Bubble Cup 11 – Finals [Div. 2] Palindrome Pairs

Bubble Cup 11 – Finals [Div. 2] Palindrome Pairs
找了好久把前几天打的比赛的代码找了出来
题目大意就是给出 n 串字符串,问在里面有多少对字符串可以形成回文串。字符可以改变位置排列。
这题其实思路很简单,但是代码坑点很多。假如我们拼接起来的串串的长度是奇数的,那么它只有一个字母是可能是出现奇数个的,假如凭借起来是偶数的话,那么不可能有一个字母是出现奇数次的。利用这个,我们用二进制26个位分别记录字母出现的奇偶数。然后对于每一个串查询时枚举那一个字母是奇数的或者全部都是偶数的情况,这样加上就可以解决了。
又因为该题卡空间卡的厉害,所以消耗多一点时间用map节约空间使用。
AcceptCode ......  查看更多