peter专题

Peter算法小课堂—序列切割

讲序列切割之前，先来个铺垫高手集训题目描述：课程表里有连续的n天可以供你选择，每天都有专题课程。其中第i天的专题趣味程度为h[i]。假设你选择了其中连续的若干天，从第l天到第r天。那么，训练效果 = h[l]*1 + h[l+1]*2 + ... + h[r]*(r-l+1) 随着训练的深入进行，每天的趣味程度会得到更多倍数的效果。目前有m种训练方案，每种方案由起始时间和

Peter算法小课堂—动态规划斜率优化

大家来到这一堂课，就说明大家已经学过函数了直线方程：y=kx+b 大家可以算一算。其实，在数学上，这玩意要分类讨论那么，这唯一的交点就是我们要背出来的直线最值这像一个分段函数其实，只有部分直线能提供最小值，另外的，就可以省略当然，最大值也一样。看一下太戈编程第2627题题目在平面直角坐标系里，横坐标为x，纵坐标为y。有n条直线，第i

Peter算法小课堂—线性dp

今天，你读完这篇文章，普及组的动态规划已经可以秒了。最长公共子序列求两个数列的最长公共子序列（Longest Common Subsequence，LCS）的长度。数列 X 和 Y 的最长公共子序列 Z，是指 Z 既是 X 的子序列，又是 Y 的子序列，而且任意长度超过 Z 的数列 Z∗ 都不符合这个性质。状态定义 f[i][j]表示x[1]、x[2]……x[i]和y[1]、y[

Peter算法小课堂—树状数组

大家好，我是人见人爱，花见花开，车见车爆胎的树状数组Peter Pan，hhh 讲正文前，先来一个长文警告⚠很重要的知识点：L SB（SB？） LSB 怎么算呢？哦……懂了，代码应该长这样 int lowbit(int n){ return n&(-n);} 来，既然懂了，给大家做一道题吧答案应该是B啊二进制索引树（树状数组）那么，我们如果用我们学过的算法

Peter算法小课堂—最大边最短路

这一片文章把整个图论的知识都用上了，基础芝士如下 Peter算法小课堂—Dijkstra最短路算法-CSDN博客 Peter算法小课堂—拓扑排序与最小生成树-CSDN博客 Peter算法小课堂—贪心与二分-CSDN博客二话不说，题呢？罗密欧与朱丽叶你是罗密欧，要去找朱丽叶。共有n个城市，编号1到n，你在1号城市，朱丽叶在n号。城市间共有m条双向道路，路程长度都已知。求你去找朱

$Peter算法小课堂—动态规划$

Peter算法小课堂—动态规划

Peter来啦，好久没有更新了呢今天，我们来讨论讨论提高组的动态规划。动态规划动态规划有好多经典的题，有什么背包问题、正整数拆分、杨辉三角……但是，如果考到陌生的题，怎么办呢？比如说2000年提高组的乘积最大、石子合并……，所以说，我们要理解动态规划的本质。那么，我们动态规划的第一步就是状态定义 dp的第二步就是填表格、写状态转移方程。最后一步就是根据状态转移方程

Peter算法小课堂—哈希与哈希表

额……字符串我们是第一次学，给大家铺一些基础的不能再基础的基础，字符串比较大小字符串大小的比较，不是以字符串的长度直接决定，而是从最左边第一个字符开始比较，大者为大，小者为小，若相等，则继续按字符串顺序比较后面的字符（比的是ASCII码）字符串输入 cin 接受一个字符串，遇“空格”、“TAB”、“回车”都结束 cin.getline() 在一（二）维字符数组中，参数一即为字符

Peter算法小课堂—区间模型

Peter Pan来啦…… 最大不重叠区间数二话不说，先来一道题大家想想怎么贪心？我们可以将每一个美食摊位抽象成一个区间，区间左端点为开始排队时间，右端点为结束排队时间。其中，时间信息可以用数轴表示。额……我们先给出一个错误的贪心大家想想有没有反例？我将这种反例称之为“锁结构”，如下图按照上面的贪心法，我们应该选粉色的时间段，但是呢？我们能找到更优的选法，即两端红

Peter算法小课堂—背包问题

我们已经学过好久好久的动态规划了，动态规划_Peter Pan was right的博客-CSDN博客那么，我用一张图片来概括一下背包问题。大家有可能比较疑惑，优化决策怎么优化呢？答案是，滚动数组，一个神秘而简单的东西。 01背包题目：小偷来你家，他带的包只能装c斤的财务。你家有n种财务，分别重w1、w2......wn斤，价值分别为v1、v2......，请输出能拿走的最大总

Peter算法小课堂—单调队列

祝大家新年快乐！今天这一次有点简单。单调队列有两个要点，一个是单调，另一个就是我们的队列。听到队列，我相信大家一定会想到它的好朋友BFS吧。但是……今天……可……没……那么……简单哦。西佳佳偶像天团1 题目描述西佳佳偶像天团共k人，最近n年每年有一位歌手加入。当人数超过k人时老团员自动退团。第i人的颜值为x[i]，团内颜值最高者成为团长，求k人成团后每年的团长颜值是多少。

Peter算法小课堂—枚举优化

哈哈哈，新年快乐！这一次Peter将要给大家讲一讲轻松、摆烂的算法—枚举！咋就是说呀，枚举这个玩意我语法就会了。但大家想想，咱们CSP考试时（除了没过初赛的）只给1秒，大家想想，这出题老师得有多抠啊。大伙们信不信，就这种easy的题，都配出进普及组，不管大家信不信，例题给我搬上来 [NOIP2016 普及组] 回文日期题目描述在日常生活中，通过年、月、日这三个要素可以表示出一个唯一确

Peter算法小课堂—二叉堆（优先队列）

课前小视频：(7 封私信 / 62 条消息) 看动画，学算法，C++实现建立二叉堆，优先队列和堆排序的基础 - 知乎 (zhihu.com) 二叉堆（优先队列）大家想想，什么数据结构能做到插入（删除）一个数、询问最小（大）值、删除最小（大）值，时间复杂度最小。答案是：二叉堆！那么，我们介绍一下二叉堆。看下图。堆的定义 int h[MAXN],n;//用数组模拟堆堆的插入

Peter.Pan C 字符串处理库

Peter.Pan C 字符串处理库 void *memccpy (void *dest, const void *src, int c, size_t n);从src所指向的对象复制n个字符到dest所指向的对象中。如果复制过程中遇到了字符c则停止复制，返回指针指向dest中字符c的下一个位置；否则返回NULL。 void *memcpy (void *dest, con

Peter算法小课堂—拓扑排序与最小生成树

拓扑排序讲拓扑排序前，我们要先了解什么是DAG树。所谓DAG树，就是指“有向无环图”。请判断下列图是否是DAG图第一幅图，它不是DAG图，因为它形成了一个环。第二幅图，它也不是DAG图，因为它没有方向。第三幅图才叫真正的DAG图（DAG图不一定联通）。那什么叫DAG图的拓扑排序呢？排序大家都知道。拓扑排序指，按照一定次序（箭头方向）来遍历这幅图。我们看道题吧。太戈编

美国智库之彼得森国际经济研究所：Peter G. Peterson

彼得森国际经济研究所是由伯格斯滕（C. Fred Bergsten）成立于1981年一个私营的、非营利的、无党派的研究所，是非牟利无党派的美国两大智库之一。2006年，为了纪念其共同创始人彼得·乔治·彼得森（Peter G. Peterson），更名为“彼得·乔治·彼得森国际经济研究所”。官方网址：http://www.iie.com The Peterson Inst

Peter算法小课堂—并查集

我们先来看太戈编程467题攀亲戚题目描述：最近你发现自己和古代一个皇帝长得很像：都有两个鼻子一个眼睛，你想知道这皇帝是不是你的远方亲戚，你是不是皇亲国戚。目前你能掌握的信息有m条，关于n个人：第i条信息包含两个人的编号ai,bi，表示ai和bi是亲戚。你的编号是0，皇帝的编号是1，最大编号为n-1，请问能否通过信息推理出你和皇帝是不是亲戚？备注：众所周知，亲戚关系具有传递性。连通块

$Peter算法小课堂—浮点数危机$