7.26模拟考试总结

为了今年的NOIP而奋斗

题目网址：

清华大学云盘

Process（比赛过程）

首先花了10分钟看了一下四道题，然后我开始做第一道题，第一眼看到这个题目的时候其实没有什么思路，后来我渐渐联想到了约瑟夫问题，我意识到得想办法让数组头尾连接起来，但是这样很麻烦。于是我换了一个思路，小W是逆时针走的，也就是向后走，如果用x-y就有可能出现负数的情况。题目上说是个圆，也就是个周期。我只需要让x-y的值一直加上n直到大于0为止。然后我就开始写暴力代码：

#include
using namespace std;
int main(){
	int n,x,y;
	cin>>n>>x>>y;
	int num=x-y;
	if(num<=0){
		num+=n;
	}
	cout< 
但是暴力有一个致命的问题——超时。
 
如果细心的话会发现他的数据限制很大，是肯定会超时的。
 
当时我也没想到更好的、巧妙地方法求解决，就只能拿部份分。
 
 
刚看到第二题时就被吓了一跳，那一大段专业语言的叙述看得上人头皮发麻。但如果耐心的看完的话，其实那一段话跟下面的题目半毛钱关系都没有。但是却涉及到了进制转换，其实看到进制转换我都有一种想要跳楼的冲动，别说是代码，光纸上硬算我都还没完全整明白呢。只能先往后看了。
 
 
第三题，我的第一反应是这很简单，直接暴力就好了。
 
#include
using namespace std;
int main(){
	int n,k;
	cin>>n>>k;
	int a[n];
	for(int i=0;i>a[i];
	}
	int cnt=0;
	for(int i=0;i 
但是我之前说过暴力会超时，果然，超时了。
 
 
第四题二叉树，我看到二叉树心中就暗暗叫苦，二叉树可不是C++中的数据结构所能存储的，也就是说要通过模拟的方法去储存，当初老师教我时，我压根是毛都没听懂。那又有什么办法呢？摆烂呗。
 
Problem（赛后）
 
赛后，老师发布了题解我才逐渐明白了
 
T1 其实用模运算就可以轻松解决了
 
#include
using namespace std;
int main(){
	long long n,x,y;
	cin>>n>>x>>y;
	long long num=(x-y)%n;
	if(num<=0){
		num+=n;
	}
	cout< 
T2 其实将小写字符串视作 26 进制数，求一个 26 进制数在模 p 意义下的值。按照题意模拟即可。
 
T3 可以将所有 a i 均模掉 k，他们的取值范围便变成了 [0,k − 1]。两者加起来是 k 的倍数，当且仅当他们模 k 之后的数的和是 k 或者是 0。那么，对于 a[i]，找到 k − a[i] 有多少个即可。这个可以用桶来轻易解决。
 
T4 题目中 −1 出现的次数较少，首先我们可以使用 O(k!) 的做法枚举所有 −1的位置填哪些数字。
 接下来，只需要判断给定一个中序遍历和一个后序遍历，是否能构造出一棵合法的二叉树。
 这个问题与“求先序排列 (NOIP2001PJT3)”类似，我们采用递归的方法，先利用后序遍历的最后一个值找出整棵树的根，再在中序遍历中把左右子树划分开来，最后回到后序遍历，划分左右子树。
 只是这个过程中有可能左右子树并不匹配。不过没关系，我们依旧递归下去，直到发现在中序遍历的区间中无法找到对应的根，或是递归到只剩一个数，却发现两种遍历方式对应的数字不同。这就说明方案不合法。只要递归过程中不存在矛盾，则方案合法。
 
Debug
 
在这些题中，有一些坑，提醒一下大家。
 
第一题：注意可能会得到负数或 0，这种情况下要记得加上一个 n，才能得到正确答案。
 
第二题：1. 几乎所有要模一个数的题目都需要边乘边模，不可能用高精度算出来再模。
 2. 边乘边模的过程中，需要注意一个小于 p 的数乘上 26 可能超出 int 范围，故需要使用 long long。
 
第三题：需要注意的细节是，如果 a i 模 k 后的结果为 0，则应当找 0 有多少个，而非k − a[i] = k 有多少个。
 
第四题：没啥坑注意细节就好。如：i、j不要敲错了。
 
谢谢大家