Merlin's Blog

**T1** **模拟+计数** 计数数组为了最后统计，魔杖服从过多少个不同的巫师。 模拟的时候，可以用一个变量记录当前魔杖在谁手上，如果输的人刚好拥有这根魔杖，则魔杖进行转移。 注意，统计不同，所以不要用++，有可能一个巫师多次获得魔杖。 **T2** **模拟题** 为了方便处理，把读入的字符串翻转一下。 ``` reverse(s.begin(),s.end()); ``` 然后s[0]就

**T1** **数学模拟** 原型来自蜗牛爬井的奥数题，但是错误率极高，情况考虑不仔细。 首先，数据范围是重中之重，不要以为了解了一下最大值，就以为数据范围掌握了，这题，你考虑最小值了吗？ 总共有3种情况： 1.特殊情况，n=0，应输出0，因为不需要记单词。 2.永远都背不出单词，有些人以为a<=b就是永远背不出单词，你考虑a>=n的情况了吗？背不出单词的情况需要满足n>a且a<=b。 3.普通情况，前两种通过后，就是普通情况，这时候直接模拟好了，但是有人就偏偏用数学直接计算，例如n/(a-b)，如果有余数再加1。这逻辑……翻车翻到西伯利亚了，想数据吧，例如n=10，a=4，b=2。如果用n/(a-b)计算，答案是5，那么答案真的是5吗？模拟即知，应是4。n最大$10^6$，放心大胆的直接模拟吧。真要数学计算，也不是n/(a-b)，你奥数白学了。 **T2** **前后缀和+枚举** 先要把常规思路练出来，能拿到保底分数（即比较明显可以得分的方式）。 题意，通过对一只猫染色，把前后两个品种的区间合并成一个。 那直接枚举i，从i-1位置开始向左统计出跟a[i-1]品种相同的区间长度，再从i+1位置开始向右统计出跟a[i+1]品种相同的区间长度。如果a[i-1]==a[i+1]，那么两个区间长度+1根擂主Pk，反之，不相同，那么左边区间长度+1和右边区间长度+1分别跟擂主Pk，也就是你要想到染色猫的位置有可能是区间的端点位置。 看数据范围就应该知道，这样直接暴力只能拿一部分分数。位置的枚举必不可少，所以要把目光转移到统计区间长度上，如果枚举i位置时候，能立刻知道以i-1为结尾的区间长度和以i+1开头的区间长度，那么时间复杂度为$O(n)$。 要计算区间长度，前缀和就很方便。 ``` for(int i = 1; i <= n; i++){ if(a[i]==a[i-1]) f1[i]=f1[i-1]+1; else f1[i]=1; } ``` 同理，要知道后面区间的长度，后缀和倒推一下即可。 最后，枚举每一个位置，把所有情况都计算一遍。 ``` for(int i = 1; i <= n; i++){ if(a[i-1]==a[i+1]) ans=max(ans,f1[i-1]+f2[i+1]+1); else{ //前后两段区间品种不同 ans = max(ans,f1[i-1]+1); ans = max(ans,f2[i+1]+1); } } ``` **T3** **坐标型DP** 宁波市**瓶子涂色**变形题，这里八卦几句。学知识，重在积累，你明明做过几次类似的题了，还看不出来，这不是学习应有的习惯和态度。看题解订正也一样，不是看到提交正确了，知识就跑进你脑袋了，应该反思自己，应该如何思考，自己哪里没想好。 价值的定义是：绿色数字总和-红色数字总和。蓝色的不统计进去。 而且，题目给出的是瓶子上的数字，那么每个瓶子就会有3种状态，这样状态自然是$dp[i][j]$，前i个瓶子，颜色为j时候的最大值。 还要留意瓶子上数字的范围，出现负数了，所以$dp$数组应初始化为无穷小，不会用memset，也可以用循环赋值。 三要素中，两个已经确定了 (1)阶段：瓶子的位置 (2)状态：dp[i][j]，前i个瓶子，第i个颜色涂为j的最大价值 **状态转移方程的思考**，假设j=0为绿色，j=1为红色，j=2为蓝色 那么对第i个瓶子来说，这3种状态都要计算(假设第i个瓶子上的数字为x)。 如果涂成绿色，那么dp[i][0]=max(dp[i-1][1],dp[i-1][2])-x; 如果涂成红色，那么dp[i][1]=max(dp[i-1][0],dp[i-1][2])+x; 如果涂成蓝色，那么dp[i][2]=max(dp[i-1][0],dp[i-1][1]); 最后在dp[n][0],dp[n][1],dp[n][2]中取最大值。 还有，看转移方程就要知道，应对dp[0][0],dp[0][1],dp[0][2]初始化为0，否则i=1的时候，转移要错误。 **T4** **二分答案** 如果你从排列情况考虑，那就掉到坑里出不来了，因为看数据范围就知道，排列情况极其恐怖。 那该如何思考呢？因为黑白奶牛，可以随意改变位置，高度还是不会变的，那可以把问题变成，一开始想成都是黑色的奶牛，然后给它们涂白色（涂色次数不能超过题目中给定的白奶牛数量）。当然也不能随便涂来找答案，还是掉进坑里的。 题目要寻找一个最小值，我们可以试着从二分角度思考问题，假设二分一个高度x，相邻的两头奶牛的高度差如果大于x了，那么我们可以把右边那只涂成白色，肯定不是左边那只，不然浪费涂色次数。这样我们只对相邻两只黑色，高度差超过x的，施展一次涂色，最后涂色的次数如果小于或等于一开始给我们的白色奶牛数量，则验证通过，调低x的值继续验证，反之，涂色次数大于白色奶牛只数，说明x过小，往右寻找。这样这题就符合了二分特性，可以用二分答案计算。 ``` bool check(int x) { bool v[200005]; memset(v,1,sizeof(v)); //1表示黑色 int cnt = 0; for(int i = 1; i < n; i++){ int h = max(a[i],a[i+1]); int l = min(a[i],a[i+1]); if(h-l>x && v[i] && v[i+1]) cnt++,v[i+1]=0; } return cnt<=sum; //sum为白色奶牛只数 } ```

### 学会观察数据范围，数据范围决定做题的方向。 订正题目，不是做对就好，要反思自己做题时的不足，否则做练习毫无意义。 ##**T1** **模拟** 送分题 1.把6改成5，求出最小值 2.把5改成6，求出最大值 其实读入用字符串，写起来更容易些，整数还要分解，麻烦。 ##**T2** **字符串+排序** 题意，取出字符串中的整数，然后按从小到大排序。 可惜，做对的没几个，多数人很粗心。

##**前方预警** **只有有实力和编程非常熟练的学生才可以考虑用这个方法，熟练度一般的，不建议使用，因为你没有多余的时间写这个。** ###**原理** 利用windows的输出输入重定向功能(即改变输入输出的设备)，结合windows的fc(文件比较命令)，结合数据生成器，对程序进行对拍，一脸懵逼的看下图。 ![](/api/file/getImage?fileId=61615b83d17

###**一.队列** 队列就是生活中的排队，例如：  队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。 我们可以用数组来模

###**信息技术模拟卷一** **选择题8** 可以逐步模拟，即手动模拟程序执行。 也可以找关键语句进行分析 (1)$i$每次递增1 (2)$s=1+2+...$。 (3)循环终止条件为$i\leq 10$ (4)循环内的判断条件为$s$是$10$的倍数 根据(2)和(4)，可以得出$s=10$的时候跳出程序，输出$s$的值，并未输出$i$的值，只有从$i\leq 10$结束才会输出$i$的值

**priority_queue**优先队列，默认是大根堆，写法如下： ``` priority_queue, less > q; //队列保存整型数据 //less右边有一个空格，如果不加，则变成>>运算，会报错 ``` 但平时默认大根堆，可以省略$less$，可以这样写 ``` priority_queue q; ``` **小根堆写法** ``` priority_queue

**一、单项选择题** **1**:答案:cn **2**:答案:01 0010 1000 0011 **3**:答案:4个字节 **4**:答案:s = a - c **5**:答案:7次 $log_{2}100≈7$ **6**:答案:可随机访问任一元素。链表是插入和删除方便，定位困难。 **7**:答案:18。算式不好摆，列举吧。 |有球袋子数量|方案数|摆法| |:--:|:--:|:-

##**目标** 1.实现道具使用功能：绿色提高移动速度、红色提高爆炸范围、橙色减少放置炸弹的间隔时间 2.能根据碰到不同的造型广播相应的效果 3.效果倒计时15秒，时间过了之后恢复原状 ###**一、修改道具爆率及停留时间**  修改是

##**目标** 1.玩家可以被炸死 2.箱子可以被炸掉 3.玩家被炸死时，显示对方赢的信息 4.箱子被炸掉时，随机掉落物品，物品功能将在下一课时讲解。 ###**一、玩家被炸死脚本** 1.首先选中炸弹角色，在**外观**大类中双击**显示**，然后**造型切换到爆炸**，获取角色的颜色。 **玩家A的脚本设计**： ![](http://magicoj.imwork.net/api/fil