一些没搞懂但是暂时通过了的题目记录

2021-07-27

【全程NOIP计划】线性优化策略

【全程NOIP计划】线性优化策略前缀和，差分序列前缀和 si=∑1iais_i=\sum_1^i a_isi=1∑iai差分 bi=ai−ai−1b_i=a_i-a_{i-1}bi=ai−ai−1 前缀和和差分序列是存在递推关系的前缀和 12for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]; 差分 12for(int i=1;i<=n;i++) b[i]=a[i]-a[i-1] 由此观之，我们可以发现前缀和和差分存在递推关系所以前缀和的差分序列等于原序列 s[i]−s[i−1]=s[i−1]+a[i]−s[i−1]=a[i]s[i]-s[i-1] \\=s[i-1]+a[i]-s[i-1] \\=a[i]s[i]−s[i−1]=s[i−1]+a[i]−s[i−1]=a[i] 注意局部变量赋初值的问题，要让s[0]=0s[0]=0s[0]=0 前缀和和差分的用法前缀和用法有这两个 1.快速区间求和，包括区间异或和区间乘 2.快速做区间加减法比如，给你一个区间[l,r][l,r][l,r]，让你给这个区间上面...

2021-08-22

【全程NOIP计划】模拟赛#5

【全程NOIP计划】模拟赛#5 A 么么题题目描述 nnn 个人坐成一圈打牌，第 iii 个人开始时手中有 aia_iai 张牌。从第一个人开始，每个人轮流选择出牌。轮到某个人选择出牌时，他可以选择出一张牌，也可以选择不出牌。不过，如果上一个出牌的人是他自己，或者从来没有人出过牌，那么他就必须选择出牌。然后轮到他的下一个人选择出牌，nnn 的下一个人是 111。如果有一个人出完了他所有的牌，游戏结束。你需要求出，游戏最多能进行多少回合。一个人一次选择叫做一回合。输入格式第一行包括一个整数 nnn。第二行 nnn 个整数，第 iii 个表示 aia_iai。输出格式输出一个整数表示答案输入输出样例输入 #1 1222 2 输出 #1 14 输入 #2 121111 4 5 1 4 1 9 1 9 8 10 输出 #2 1563 输入 #3 122100 1 输出 #3 1199 说明/提示样例一解释：第一回合 111 必须出牌。第二回合 222 选择出牌。第三回合 111 选择不出牌。第四回合 222 必须出牌，他的牌出完了，游戏结束。共进行...

2021-03-30

NOI Online2021第一场游记

NOI Online2021第一场游记 0 准备 2021年3月27日，一个美妙的早上，我从我温暖的被子里滚了出来，走向了襄阳五中的大门，内心踌躇：这可能是我最后一次参加NOI Online了，但是不慌，因为此时学校俨然已经被封锁起来，变成了公务员考试的考场。我从旁边的宁静湖穿过，走了比平时多了大约一倍的路程直达我的竞赛场地——大成楼，有诗云：大成楼里集大成，大成楼旁小成生，小小大大大小成，小小大大状元名好不费力，我从一层的电梯起步坐到五层，然后从五层的楼梯爬到六层，这里就是我所在的机房了——只有我一个人的机房。拿出钥匙，我将钥匙插进门锁中，前后倒腾了几下，门开了，里面散发出一股灰尘的味道，我知道，是我上周月考，没有进去，已经布满灰尘了。进门之后向右转，打开电闸，快到墙的时候，又及时来了一个急转弯，走到倒数第二排的电脑面前，放下书包，踱到窗旁，打开窗户，迎接这一天的新鲜空气。电脑缓缓地开了，滴滴的声音和窗外公务员考试的广播声加大了比赛的真实感觉，让我身临其境，时间一分一秒地过去，终于到了8：30这个时间，题目发下来了 1 提高组 T1 愤怒的小N 鸽 T2 积木小赛...

2021-03-30

NOI Online2021游记

NOI Online2021第一场游记 0 准备 2021年3月27日，一个美妙的早上，我从我温暖的被子里滚了出来，走向了襄阳五中的大门，内心踌躇：这可能是我最后一次参加NOI Online了，但是不慌，因为此时学校俨然已经被封锁起来，变成了公务员考试的考场。我从旁边的宁静湖穿过，走了比平时多了大约一倍的路程直达我的竞赛场地——大成楼，有诗云：大成楼里集大成，大成楼旁小成生，小小大大大小成，小小大大状元名好不费力，我从一层的电梯起步坐到五层，然后从五层的楼梯爬到六层，这里就是我所在的机房了——只有我一个人的机房。拿出钥匙，我将钥匙插进门锁中，前后倒腾了几下，门开了，里面散发出一股灰尘的味道，我知道，是我上周月考，没有进去，已经布满灰尘了。进门之后向右转，打开电闸，快到墙的时候，又及时来了一个急转弯，走到倒数第二排的电脑面前，放下书包，踱到窗旁，打开窗户，迎接这一天的新鲜空气。电脑缓缓地开了，滴滴的声音和窗外公务员考试的广播声加大了比赛的真实感觉，让我身临其境，时间一分一秒地过去，终于到了8：30这个时间，题目发下来了 1 提高组 T1 愤怒的小N 鸽 T2 积木小赛...

2021-09-18

【全程NOIP计划】初赛

【全程NOIP计划】初赛计算机基础 IT发展历史第一台计算机：埃尼阿克，1946 应用：计算，数据储存处理，通信，辅助工作等第一个程序员：Ada（女），为了纪念她，命名了一个编程语言是她的名字计算机：图灵奖数学：菲尔兹奖物理化学生物经济文学和平：诺贝尔奖 ACM（美国计算机协会），IEEE（美国工程院学会），臭名远扬CCF 【NOIP2018】下列关于图灵奖的说法中，正确的有（）。 A. 图灵奖是由电气和电子工程师协会（IEEE）设立的。 B. 目前获得该奖项的华人学者只有姚期智教授一人。 C. 其名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵。 D. 它是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称。【解析】答案选择BCD，图灵奖是又ACM设立的，其它的没得一点问题计算机组成冯诺依曼结构（储存程序原理）——计算机的基础模型字长：32位和64位；意思指的是每次指令可以处理32位的数据或者64位的数据主频：2.4GHz，指的是计算机处理的速度内存：8GB，临时存放东西，也叫RAM，随机存储设备，断电丢失位Bit：一个...

2021-11-19

【全程NOIP计划】分治与倍增

【全程NOIP计划】分治与倍增分治分治就是分而治之，化整为零的思想分治的原理是把困难的大问题化解为简单的小问题然后先解决小问题，然后根据小问题的答案解决大问题它本质上不是一个算法，而是一个思想比如快速幂，倍增求lca，归并排序，线段是cdq分治，甚至后缀数组FFT都利用了分治思想分治虽然不经常出题，但是也非常有用快速幂快速幂可以在O(logb)O(logb)O(logb)的时间复杂度内计算aba^bab 方法很简单注意到如果b是偶数，那么就可以先计算ab2a^{\frac{b}{2}}a2b,这样问题的规模就减少了一半如果b是奇数，那么我们就可以计算ab2a^{\frac{b}{2}}a2b平方之后再乘a，问题规模同样以不大的代价减少了一般这里的aba^bab就是大问题，而ab2a^{\frac b 2}a2b就是小问题了 12345678910111213141516171819long long f(long long a,long long b,long long c){ long long temp=f(a,b/2) ...