2022-05-14 12:21:41    43    0    0
**T1** **模拟+计数** 计数数组为了最后统计,魔杖服从过多少个不同的巫师。 模拟的时候,可以用一个变量记录当前魔杖在谁手上,如果输的人刚好拥有这根魔杖,则魔杖进行转移。 注意,统计不同,所以不要用++,有可能一个巫师多次获得魔杖。 **T2** **模拟题** 为了方便处理,把读入的字符串翻转一下。 ``` reverse(s.begin(),s.end()); ``` 然后s[0]就
2022-05-14 08:59:21    56    0    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为白色奶牛只数 } ```
2022-04-18 09:53:25    62    0    0
### 学会观察数据范围,数据范围决定做题的方向。 订正题目,不是做对就好,要反思自己做题时的不足,否则做练习毫无意义。 ##**T1** **模拟** 送分题 1.把6改成5,求出最小值 2.把5改成6,求出最大值 其实读入用字符串,写起来更容易些,整数还要分解,麻烦。 ##**T2** **字符串+排序** 题意,取出字符串中的整数,然后按从小到大排序。 可惜,做对的没几个,多数人很粗心。
2021-10-09 17:06:07    133    0    0
##**前方预警** **只有有实力和编程非常熟练的学生才可以考虑用这个方法,熟练度一般的,不建议使用,因为你没有多余的时间写这个。** ###**原理** 利用windows的输出输入重定向功能(即改变输入输出的设备),结合windows的fc(文件比较命令),结合数据生成器,对程序进行对拍,一脸懵逼的看下图。 ![](/api/file/getImage?fileId=61615b83d17
2021-07-11 10:15:51    211    0    0
###**一.队列** 队列就是生活中的排队,例如: ![](/api/file/getImage?fileId=60e9aa87d170a10012004844) 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。 我们可以用数组来模
2021-04-05 09:54:13    76    0    0
###**信息技术模拟卷一** **选择题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$的值
优先队列    2020-05-18 11:05:23    86    0    0
**priority_queue**优先队列,默认是大根堆,写法如下: ``` priority_queue, less > q; //队列保存整型数据 //less右边有一个空格,如果不加,则变成>>运算,会报错 ``` 但平时默认大根堆,可以省略$less$,可以这样写 ``` priority_queue q; ``` **小根堆写法** ``` priority_queue
CSP    2019-10-24 10:18:51    44    0    0
**一、单项选择题** **1**:答案:cn **2**:答案:01 0010 1000 0011 **3**:答案:4个字节 **4**:答案:s = a - c **5**:答案:7次 $log_{2}100≈7$ **6**:答案:可随机访问任一元素。链表是插入和删除方便,定位困难。 **7**:答案:18。算式不好摆,列举吧。 |有球袋子数量|方案数|摆法| |:--:|:--:|:-
Scratch    2019-04-07 21:38:05    402    0    0
##**目标** 1.实现道具使用功能:绿色提高移动速度、红色提高爆炸范围、橙色减少放置炸弹的间隔时间 2.能根据碰到不同的造型广播相应的效果 3.效果倒计时15秒,时间过了之后恢复原状 ###**一、修改道具爆率及停留时间** ![](http://magicoj.imwork.net/api/file/getImage?fileId=5cb3e4521d41c807270057fc) 修改是
Scratch    2019-04-01 09:00:35    645    0    0
##**目标** 1.玩家可以被炸死 2.箱子可以被炸掉 3.玩家被炸死时,显示对方赢的信息 4.箱子被炸掉时,随机掉落物品,物品功能将在下一课时讲解。 ###**一、玩家被炸死脚本** 1.首先选中炸弹角色,在**外观**大类中双击**显示**,然后**造型切换到爆炸**,获取角色的颜色。 **玩家A的脚本设计**: ![](http://magicoj.imwork.net/api/fil
1/4