《noip2015批批替by姬树流》由会员分享，可在线阅读，更多相关《noip2015批批替by姬树流（31页珍藏版）》请在金锄头文库上搜索。
1、NOIP2015,姬树流,Day1,T1,神奇幻方,可以，这很模拟 听说有人现场手玩出所有数据然后打表交了orz,T2,信息传递,当年这题我在递归里开了二十万的数组然后过了八组最后两组还是T掉的linux的栈容量真是恐怖 这题的本质是判环 核心思路是每个点只有一条出边(因为一个人只能把他知道的告诉另一个人) 所以每个连通块儿只有一个环,就像酱紫,因为每个点只有一条出边，所以路径是固定的，不会有分支,但如果要有两个环就必须要有分支，即两条出边，因为某个点已经在一个环中，想要通过这个点到另个一环中，就必须要跳出这个环，就必须要有分支,钠就好办辣,我目前的方法是开一个next数组来存图，同时用邻接表
2、用双向边再存个图，用visited数组记录访问情况，找到一个环后更新答案，用bfs覆盖连通块儿 开一个数组记录第一次遇到这个点的时间，第二次遇到这个点时(也就是内个数组里边内个点的值不为零时)说明找到环了，更新答案也很方便 从点1到点n，如果没访问，就进去操作，否则无视,过程大概就是酱紫,从1开始,找到环,覆盖连通块儿,2,3,4都被覆盖了，从5开始，后面的就不画了,需要注意，图不一定连通，也就是说可能有多个连通块儿，就有可能有多个环 如果这题出在2016我就被坑了QwQ 听说还能用并查集，tarjian什么的，但我觉得我的方法挺简单的，这题也没呢么复杂 具体如何实现留给读者思考,T3,斗地主
3、,以前看很吓人饿，A掉后就是一大水体 我是看了网上的题解才做出来这道题(同样如果这题出在2016我就GG了QwQ) 实际上没什么难度，数据量看上去很大实际上很小，不论是DFS还是DP状态量都少得出奇，只是需要注意些节，搞暴力的胆量，和逆天的脑洞,怎么搞呐,花色没有卵用，所以核心思路是用数组记录每种牌有几个(比如5共有三张表示为a5=3)，在来一个数组记录有几张牌的有几种(比如有5种牌有三张表示为b3=5) 然后就是随意深搜play了加个最优化剪枝就能A，连hash判重都不用 有一些很容易被坑的牌：三张，四带两对，三顺两组就能上，二不能顺但可以带，单顺是5张，尼玛龟居然可以带,有个中魔性的技巧能
4、降低时间和代码复杂度比如三个顺可以合体什么的 做这题不能怂，看上去复杂自己瞎胡搞一些魔性的技巧一点一点搞还是比较容易的 然而最重要的还是核心思路，就是记录每种牌有几个和有几张牌的有几种的内两个数组，用这两个数组可以让时间复杂度和代码复杂度都大大降低 真正到NOIP的时候想不粗来怎么办麻QAQ,Day2,T1,跳石头,毕竟T1麻比较水，然而当年太nave，明知道自己不会二分却听到过几遍都不去学，然后痛拿二等 二分答案验证，记录一个last表示上一个没有被拿掉的石头，如果当前和last的差小于验证的答案，个数+，否则last=i，正确性还要想想，好像有数据能卡这种方法？ 需要注意，给出的都是中间的
5、石头，起点终点还各有一个,T2,子串,裸DP，看了题解后还是比较简单的 状态很明显（题解都是这么说的），匹配系列的题应该都是酱紫，a进行到i，b进行到j，共用了k段,过程大概是酱紫的,如果ai=bj，就加上f1-i-1j-1k-1，j-1因为所有的b都要匹配，但a不一定都要匹配所以1-i-1，k-1表示新开一段 在ai=bj里面，如果ai-1=bj-1，就加上fi-1j-1k，和上一段并上,但是酱紫会T,因为加的是1-i-1，就可以搞个大新闻前缀和 但是空间上面1000*200*200=40000000好像会炸，就可以用两个数组交替滚，写成酱紫2比较方便，f也要用两个，用来加ai-1=bj-1
6、时的内个fi-1j-1k 注意，跟上一段不连时加的是前缀和，连到上一段时加的是上一段的最优值 sro_dydxh_orz小优化： 取余可以写成酱紫：if(anum)a-=num，避免了大量的模运算（模运算相当慢）,T3,运输计划,A掉之后还是比较水的吧一点一点写就能A然而这题如果出在2016我依旧会GG QAQ 白纸黑字的所以我们搞二分 先说一点，删除的边一定在最长的内条路径上，否则对答案没贡献(这个对正解帮助不大，但如果写暴力还是非正常有用的),二分,二分一个最大值，然后把所有超过这个值的路径找出来 这里可以用个结构体，记录路径的两端点，长度和lca，然后sort一下，找路径用二分找，因为之
7、前sort过已经单调了 然后给这些路径求个交，在这个交集中如果删除最大的一条边仍旧不能满足答案就return false,否则return true 判断的时候可以直接用最长的内条路径的长度减去内条边的长度,为什么呐,因为这条在所有大于答案的路径上(因为它是交集中的边) 如果最长的内条路径减去这个边都能满足答案，下面的大于答案的路径减去内条边后不会比最长的内条路径减去内条边还要长，也就不会大于答案 如果最长的内条路径减去内个边不能满足答案，呢么已经有一条路径不能满足答案了，就说明这个答案不对 (上面说的答案指的都是二分的内个答案),怎么求交呐,可以考虑区间求交的方法：新建一个flag数组，区间
8、开头+1，结尾-1,然后从1开始遍历，把flag往后累加，如果当前点的flag等于区间的个数，它就是所有区间交集中的一个点,延伸到树上,就是在路径两个端点上+1，lca上-2，每个点的flag值代表它和它的父节点连的内条边的flag,从叶子节点开始遍历，用dfs比较好写，把子节点的flag往上累加，如果某个点的flag等于所有大于二分出来的内个答案的路径的个数，这个点与它父节点连得内条边就是所有大于二分出来的内个答案的路径的交集中的一条边,代码基本上就是花式求个中值，求粗一个就输并检查，一点一点搞还是比较容易的 如果用树剖求lca要两个dfs，我的内个求交的方法也要一个dfs，在部分oj上提交要用汇编开栈 如果是NOIP，省选，NOI就不用考虑这个问题辣，Linux栈容量赛高 具体如何实现留给读者思考,总结,2015的NOIP还是比较简单的（至少A过后是酱紫的） 两个第三题都不难，主要考验代码能力和脑洞的大小 不能怂，逐步求出个中条件，分治问题会简单得多 建存档是个好习惯 祝各位同学rp+,GG,
