JSOI第一轮滚粗记

Orz第一轮省选结束了,滚粗严重、同学里面ZYH(160),ZSA(170+T3格式错误丢了100),LRY150、全都虐我、我只有100分,第一题40,第二题60,第三题0分、再配合上我的NOIP似乎大滚粗了。
不过想想也是,去年一整个高一我大概小半年在搞FTC、剩余的时间里面花了一部分在软件开发社团经营上面又花了一部分在我的Android程序开发上面,然后平时文化课还要死撑着认真一字一划写作业,平时在学校还把把妹子之类的无聊浪费时间的行为、基本上花在OI上的时间少之又少、BZOJ还是今年暑假结束之后才开始刷的、CF是几周之前才鼓起勇气开始刷的、这样能考好嘛、我自己说着努力要跪着走自己的路,但是却又不肯放下身来踏踏实实,也是醉了、希望一切还来得及罢、最近找回了自己的信仰,希望这样能长久。
好的废话不说,我们来讲一下题目:
第一题题目大意大概是,我们有n个节点,n-1条边的无向联通图,每个节点有价值/花费(之能在第一次访问的时候奏效),然后每个点有限制访问次数,我们从1点出发,通过联通图走一遍能获得最大价值是多少,且此方案是否唯一?【数据范围:100%数据:N<=100000 50%数据N<=500】
额、我考场上的思路大约就是对于每个点,我们处理出它子节点的最优价值,然后排序去前(限制次数-1)个节点的答案更新本节点答案(只更新正数的答案)。关于方案是否唯一,对于一个节点存在总花费为0的子节点且剩余访问次数,那么这个节点时多解的;对于一个节点我们取到的最小花费,存在多个且未取完那么这个节点是多解的;如果用于更新本节点答案的子节点存在多解,那么这个节点是多解的。然后直接树DP就可以了,连多叉转二叉都不用、、我考场上只拿了40分,大约是手滑那里写错了吧、手滑毁一生、
第二题,我们有一个N*N的01矩阵,要求计算 1.存在一个对称轴的子正方形矩阵最大边长 2.存在一组相互垂直对称轴的子正方形矩阵最大边长 3.存在4条对称轴的子正方形矩阵最大边长 4.旋转180度能重合的子正方形矩阵最大边长 5.旋转90度能重合的子正方形矩阵最大边长
【数据范围:100%数据:N<=500 50%数据N<=100】
我考场上写了一个N^4的暴力,枚举中心点,然后扩展边长,判断扩展的部分是否符合要求。这样大概不用N^4因为边长不会阔出去很多,然后大概常数过大或者程序写搓了?60分、听大神们讲什么manacher算法、、我竟然不知道能这么用QAQ、还听大神讲、扩展边长用二分,这样就是O(N^3logN)似乎很有道理!
第三题,我们把一颗树度为2的节点成为假节点,其他节点为真节点,然后去掉所有的假节点,得到一颗实质树?【记不得叫什么了。】我们有N普通树,请把他们转化为实质树,然后判断实质树之间是否同构。统计输出不同构的实质树数量,然后再升序输出不同构的实质树的实质节点数量。
【数据范围:100%数据N<=10000,M<=20 其他记不得了】
卧槽,这题、、我最后半个小时看题,8分钟看懂题目,15分钟写出程序,3分钟调试,一遍过了样例,然后我就交了、但是最后、我0分、、我明明写出来了写出来了,我觉得算法没问题、、QAQ我是通过标记来看节点是否有意义,然后统计有意义的节点中,一棵树上对于入读为x的节点连着一个入读为y的节点的二元组的数量,然后两棵树判断所有二元组是否相同,全相同则为同构树,否则不然、、我觉得没问题、、肯定是那里写Wa了、有一个A掉的大神告诉我,这题和化学的同分异构体很像,我们可以每次去掉有机物上的H,然后循环往复来判断、、【Orz】
那么,大神球在下面评论里指导本蒟蒻、