11.5noip模拟赛总结

11.5日NOIP模拟赛总结

先来看看每一道题

T1

第一遍读题，看到数据范围和题意，肯定是一道结论题。复杂度肯定是$O(mlogn)$或者是$O(m)$的。

我先想了想$O(m)$的写法，发现每次求编号并不能通过$O(1)$求出，于是去想$O(mlogn)$的写法。首先发现二叉树的深度就是 l o g2nlog_2 nlog2​n的，那么每一次求编号肯定都是和二叉树的深度有关。

通过观察规律，我先发现在先序遍历下，二叉树点的编号与遍历顺序有如下规律：

然后，我们就可以将所有的点分为左儿子和右儿子，还有最左侧的链。

首先，最左侧的链的编号 l o g2 log_2log2​就是这个点的先序遍历编号，那么我们只用通过转移，直到转移到了最左侧的链上就可以得出答案。

接下来，当前转移到的是左儿子，那么我们只需要转移到它的父节点，因为父节点的先序遍历顺序一定是当前点的上一个（如上图）。如果是右儿子，那么当前节点的先序遍历编号一定是它的兄弟（父节点的左儿子）的编号加上左节点的子树大小。

unsigned long long getcnt(unsigned long long num){//num为点的编号 if(int(log2(num))==log2(num)){return log2(num)+1;}if(num%2==0){return getcnt(num/2)+1;}else{return getcnt(num-1)+getsize(num-1);}}

我们递推求解的复杂度是 l o g2nlog_2 nlog2​n的，那我们如何在 l o g2nlog_2 nlog2​n的时间内求出子树大小呢？（考场上我开始没有想到，做了第二题才想到）

首先，我们可以 l o g2nlog_2 nlog2​n求出子树的深度（因为左儿子是父节点编号的两倍），然后再判断这个子树的叶子结点有多少个（可以$O(1)$求出），如果$n$（点的数量）大于这个子树的最大编号，那么叶子结点就是满的，否则用$n$就可以算出。最后，再将所有的数量加起来就是该子树的大小，总的复杂度应该是 O ( 2 l o g2n )O(2log_2 n)O(2log2​n)。

unsigned long long getsize(unsigned long long num){//num为点的编号 long long cnt=0;unsigned long long pos,cntline,sum=0;while(qpow(2,cnt+1)*num<=n) cnt++;cntline=qpow(2,cnt);pos=qpow(2,cnt)*num;if(n-pos+1>=cntline){for(unsigned long long i=0;i<=cnt;i++){//sum+=qpow(2,i);sum+=(1ll<<i);}return sum;}else{for(unsigned long long i=0;i<=cnt-1;i++){//sum+=qpow(2,i);sum+=(1ll<<i);}sum+=n-pos+1;return sum;}}

其实还可以优化，这里只稍微的卡了下常（不卡常过不了）（考试只拿了90分）。

考试的时候这道题花了巨多的时间（），因为感觉就只有这道题可以做。

还有其他思路的。

T2

这次考试感觉在T2上面失误了，因为做完第一题时还没有想到怎么 O ( l o g2n )O(log_2 n)O(log2​n)地求出子树大小，所以做第二题的时候心里面一直在想第一题，导致想到了能拿40分的代码却没有写，最后只拿了10分。

首先，这个乘积式只和$x,y$这两个数的最大公约数的质因子有关系。这个结论考场上我很快就想到了，但是在我看完数据范围后，我陷入了沉思。两个数的范围是$1e9$，按理来说这没什么问题，可是我考场上面我脑袋有一点抽。我当时想到那么大的数，那他的质因子一定会很大，那么线性筛需要开数据范围那么大的$vis$数组，那不肯定炸吗（当时我线性筛都写出来了，看到不对劲就把它删了，后悔呀）？？然而，我却忘了，一个数只可能有一个大于 n \sqrt nn ​的质因子，因为两个 n \sqrt nn ​相乘已经是原来的数字了，不可能再大了。脑壳一抽，然后我就想，完了完了，这道题完全没有思路，然后就只打了个暴力跳过了，其实说不定把最开始的想法写出来就可以拿40分（可能更多）。（这个就不放代码了）

T3

emm，这道题看起很动态规划。然而，我的动态规划烂的一批。然后我非常不情愿做这道题，但毕竟是考试，我耐心看完题以后，发现这并不是一道动态规划，我想到了之前DJC讲的二维前缀和。心里面狂喜！！！然后花了40分钟打出了二维前缀和，然后枚举选出子矩阵的左上端点和右下端点（ O ( ( m × n )2)O((m\times n)^2)O((m×n)2)），就把这道题跳了。

最后拿到了44分，部分分是拿齐了。后来才知道，在二维前缀和可以枚举较小维度上的上界和下界，然后另一个维度通过尺取法来枚举，这样，枚举的效率就变成了 O ( m i n ( n , m )2× m a x ( n , m ) )O(min(n,m)^2\times max(n,m))O(min(n,m)2×max(n,m))这样就可以把这道题过了。

有一点小细节是但有一段的数字全部都是0的情况，这种情况下尺取法的效率会变得很低。

T4

写T4的时候还有30多分钟我先把m转化成了10进制，然后写了一个大暴力，模拟整个过程。成功的拿到了30分（还好没有RE）。

然后想了一下正解，首先，这两个操作是将所有的数在二进制条件下，将最后一位取反以后，放在第n位上，所以说最坏的情况下，需要$2\times n$次就一定可以跳回到原来的状态，所以所有的情况应该都是成立的（不理解为什么题面写有不成立的情况），然后呢，如果二进制下有循环节（或者是对称？？？），那么这个答案就不是$2\times n$。然后就不会写了。

总结

第一题其实可以拿满的（既然已经花了那么多时间），以后可以记得求解2的$n$次方可以用位运算实现（但是记得变量开$unsignedlonglong$，$1ll<<n$），这样就不会超时了，以后不要只会写快速幂。

第二题超级亏：

第一，如果我还记得那个结论，那么肯定不会这么惨。

第二，如果我坚持把我已经有了的思路写完，那么也不会这么惨。

第三题和第四题我认为在考试的时候做的很好，第一，能拿的部分分都拿到了，第二，也都尝试了想一想正解。