文章作者: wweiyi
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 wweiyiのblog！
相关推荐
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 必须出牌，他的牌出完了，游戏结束。 共进行...
2020-11-06
CSP-S2020 游记
CSP-S2020 游记 Day0 今年的csp没有试机，这大概是历年来襄阳参加人数最多的一次吧，可能也是参加的最水的一次吧。然而，我被推到历史的风口浪尖，准备迎接这惊涛骇浪，向着省一勇往直前。有一个高三的学哥也参加了，他因为去年参加csp没有打return 0 而死了200分，所以他只有一百五十分，这也给了我一个前车之鉴，让我更加注意，去年也有一个四中的学哥连续两年没有写对文件输入输出，因此我依据这些学哥的事例，让我更加谨慎。 CSP作为2019年noip的替代品，我们当然参加。可是今年noip复活了，为什么我们还是要参加呢？这真的是不得而知的，我们也没有不要知道，我们应该知道的事情就是要好好比赛，拿出成绩来就是了。 在这阳光明媚的日子里，我们有什么理由不好好学习呢。 今天下午四点要去华科，老师要讲要求。 老师讲完要求了，我也听了。 现在是周五 2020年11月6日 22：09分 我现在在历史的交汇点 明天将会有我无法想象的比赛等着我参加。 在这里分享一下考试技巧 进考场水不要带太多，带个半杯就够了，可以带一点吃的。 进考场之后看电脑是不是好的，最好把每一个按键都试一遍，看看能...
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) ...
2021-09-04
【全程NOIP计划】初赛模拟
【全程NOIP计划】初赛模拟 单项选择 1.补码等于源码加上符号位然后除符号位按位取反加一，看出来选择A 2.32位指的是对于每一个分辨率的小格子的大小为32bit,然后每个bit是8个字节，直接乘起来就好了，然后25%的压缩率指的是原来的大小0.25 3.链接器的功能是“把机器指令组合成完整的可执行程序” 4.首先一个堆中的元素要变小边的大小次，然后查询最小值是对于每个点更新的时候才进行查询，所以时间复杂度是O(m+nlogn)O(m+nlogn)O(m+nlogn) 5.实际上深度优先遍历，找两个点是否存在边的时间复杂度是n，然后一共有n个点，所以时间复杂度为O(n2)O(n^2)O(n2) 6.快速排序和归并排序实际上都用到了分治的算法，只不过归并排序更加突出，而快速排序实际上用的是递归，也是分治；求二叉树的前序遍历，因为是根左右，根左右，所以我们直接把第一个节点当做根，然后对于接下来的区间直接处理两个子树就好了，也是分治，所以答案是D 7.前缀表达式涉及到一个表达式树的运用，也就是说，这就是一个树的前序遍历，我们把这个树还原出来，然后对于这个树进行中序遍历就是最终的答案了...
评论
公告
这里记录 AI 与开发工具、嵌入式实践、算法竞赛档案，以及偶尔的随笔与创作。
从专题开始阅读 →
从专题开始阅读 →
