2018北大暑期学校学习大楼

admin

各位同学，北京大学暑期学校是我校的暑假期间的一个传统的项目，让NOIP200份左右的小孩学习OI知识，感受北大氛围。今年，大约有20多位同学报名，希望他们在北大学习生活期间顺顺利利，学有所成。这里我来统一发布北大的学习情况。

admin

这次去北大学习的同学的编程水平参差不齐，有的同学的状况我还不知道，今天晚上，我们来做四个题，检查大家的水平，你们把代码写在我的楼下，我看看大家的实际知识掌握情况。
1、分解质因数 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36235
2、模拟斗地主 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36236
3、蛇形填数 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36237   
4、分数化小数  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36238

admin

我们是高中搞信息学奥赛的学生，一般的高中的学习内容基本上是四大块，c++语言，常用算法，数据结构，综合运用等。那边北大，学习的内容主要是基础算法，基础数据结构。和我们的内容有重叠，所以可以去学习下，但是也有几个非常大的不同：
1、主要讲算法和数据结构，所以要求我们c++已经有了一定的基础。
2、主要对象是北大的本科生 ，比我们年长一点，知识积累自然强一些，而且还是PKU。所以我们每天听课不见得很容易接受，内容多，知识面广。课后要好好总结反思。
3、ACM和OI制式不同，注意区别，学习知识为主，技能训练还是要看我们的。
总之，我希望大家在这里认真学习新的知识，比如DFS BFS DP BST 线段树，网络流等。基本每天一个专题，下午上课，当天晚上，次日早上要认真消化总结反思，力争完全掌握！每个例题都要认真做，不懂的也要记下来，等我来解决，这样，在北大的知识结构的带领下我们可以完成我们自己OI知识结构的建立，争取本年NOIP2018拿到300分！

admin

这次去北大学习的同学的编程水平参差不齐，有的同学的状况我还不知道，今天晚上，我们来做四个题，检查大家的水平，你们把代码写在我的楼下，我看看大家的实际知识掌握情况。以后每天下午你们上课的时候我都在这里根据上课的内容挑选相关的题目给你们做，去年也是这样的，你看

admin

今天第一天，老师讲了贪心，二分，DP三个内容，但是DP还没有讲完，所以我们主要训练贪心和二分，贪心相对比较简单，。找到贪心的准则，然后按照规则排序一般就行了，但是如何找到准则是最重要的！二分用于递增或者递减的数列里面找到指定的元素，他首先要判断序列是单调的，然后按二分的方法做就是。

admin

贪心方法训练题:
P1016 旅行家的预算  http://www.hsyit.cn/forum.php?mod=viewthread&tid=35853
P1090 合并果子  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36224
P1056 排座位   http://www.hsyit.cn/forum.php?mod=viewthread&tid=35824
P1843 奶牛晒衣服   http://www.hsyit.cn/forum.php?mod=viewthread&tid=36248

admin

二分法训练题：
P1024   一元三次方程求解 https://www.luogu.org/problemnew/show/P1024 我的解法参考 http://www.hsyit.cn/forum.php?mo ... 5793&highlight=1024
P1163   银行贷款 https://www.luogu.org/problemnew/show/P1163 我的解法参考 http://www.hsyit.cn/forum.php?mo ... 5796&highlight=1163
P1281   书的复制 https://www.luogu.org/problemnew/show/P1281 我的解法参考 http://www.hsyit.cn/forum.php?mo ... hlight=%CA%E9%B8%E5
P1045   麦森数   https://www.luogu.org/problemnew/show/P1045
P1314    聪明的质监员  https://www.luogu.org/problemnew/show/P1314
P2678    跳石头 https://www.luogu.org/problemnew/show/P2678
盛夏的果实 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36200   
P1577 切绳子  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36242
P1824 进击的奶牛   http://www.hsyit.cn/forum.php?mod=viewthread&tid=36243  
P1542 包裹快递  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36218
P2985 [USACO10FEB]吃巧克力Chocolate Eating  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36245

admin

周三讲的主要是DP，DP的题目首先要证明是可以分阶段无后效性的吗，然后就是模拟填表过程，要求在EXCEL里面填出表，感受计算和决策的过程，找出关键的变量和它们的变化情况，最后就是写出程序，训练题：
P1077 摆花  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36070
P1057 传球游戏 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36069
连环炸弹  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36049
最长不下降序列LICS  导弹飞机  http://www.hsyit.cn/forum.php?mod=viewthread&tid=3659
筷子  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36143
P1233 木棍加工 LICS改进 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36205
P1650 田忌赛马 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36144
乘积最大  http://www.hsyit.cn/forum.php?mod=viewthread&tid=35999        
最大的算式  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36055
最长公子序列     回文串  最长公共子序列的变形使用  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36212

最简单的是递推，后面的由前面的几个计算得到，比如：等差等比数列，二阶等差，斐波那契，杨辉三角，卡特兰数，斯特林数等，不涉及比较，直接硬推。   
注意这个推的过程，有的是一次就可以搞定，有的需要几轮。
P1077 摆花  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36070
P1057 传球游戏 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36069
连环炸弹  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36049
比这难一点的是每次决策过程中不是简单的累加而是有比较，比如
最长不下降序列LICS  导弹飞机  http://www.hsyit.cn/forum.php?mod=viewthread&tid=3659
筷子  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36143
P1233 木棍加工 LICS改进 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36205
P1650 田忌赛马 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36144
极简单的背包  贴邮票问题

再复杂一点的就是二维表DP  要多次扫描，一轮轮的，简单的就是填一个表的过程，注意细节。当然有的可以迭代或者使用滚动数组变成一维数组但是本质还是多轮推。  
     杨辉三角 （滚动DP） 这里要认真体会二维数组做法，滚动数组，和反向数组递推的做法 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36058
     数字三角形
     乘积最大  http://www.hsyit.cn/forum.php?mod=viewthread&tid=35999        
     最大的算式  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36055
     最长公子序列     回文串  最长公共子序列的变形使用  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36212
    相似基因
   

经典背包问题  它也算二维表型DP，注意我的那个推导过程， 特别是如何用一维数组的。

基础背包采药  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36061
疯狂的采药  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36000
开心的金明  http://www.hsyit.cn/forum.php?mod=viewthread&tid=35890
金明的预算 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36060

背包加强版
P1794 装备运输  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36146
P1509 找啊找啊找GF http://www.hsyit.cn/forum.php?mod=viewthread&tid=36134
氧气瓶氮气瓶    http://www.hsyit.cn/forum.php?mod=viewthread&tid=36015
P2736 “破锣摇滚”乐队 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36147
P1095 守望者的逃离  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36003
P2725 邮票 Stamps http://www.hsyit.cn/forum.php?mod=viewthread&tid=36027

  P1782 旅行商的背包 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36002

很难的背包P1757 通天之分组背包  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36148
区间DP
   P1063 能量项链 http://www.hsyit.cn/forum.php?mod=viewthread&tid=3669
   P1880 [NOI1995]石子合并 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36126

   

admin

周三讲的主要是DP，DP的题目首先要证明是可以分阶段无后效性的吗，然后就是模拟填表过程，要求在EXCEL里面填出表，感受计算和决策的过程，找出关键的变量和它们的变化情况，最后就是写出程序，训练题：
P1077 摆花  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36070
P1057 传球游戏 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36069
连环炸弹  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36049
最长不下降序列LICS  导弹飞机  http://www.hsyit.cn/forum.php?mod=viewthread&tid=3659
筷子  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36143
P1233 木棍加工 LICS改进 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36205
P1650 田忌赛马 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36144
乘积最大  http://www.hsyit.cn/forum.php?mod=viewthread&tid=35999        
最大的算式  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36055
最长公子序列     回文串  最长公共子序列的变形使用  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36212

最简单的是递推，后面的由前面的几个计算得到，比如：等差等比数列，二阶等差，斐波那契，杨辉三角，卡特兰数，斯特林数等，不涉及比较，直接硬推。   
注意这个推的过程，有的是一次就可以搞定，有的需要几轮。
P1077 摆花  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36070
P1057 传球游戏 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36069
连环炸弹  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36049
比这难一点的是每次决策过程中不是简单的累加而是有比较，比如
最长不下降序列LICS  导弹飞机  http://www.hsyit.cn/forum.php?mod=viewthread&tid=3659
筷子  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36143
P1233 木棍加工 LICS改进 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36205
P1650 田忌赛马 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36144
极简单的背包  贴邮票问题

再复杂一点的就是二维表DP  要多次扫描，一轮轮的，简单的就是填一个表的过程，注意细节。当然有的可以迭代或者使用滚动数组变成一维数组但是本质还是多轮推。  
     杨辉三角 （滚动DP） 这里要认真体会二维数组做法，滚动数组，和反向数组递推的做法 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36058
     数字三角形
     乘积最大  http://www.hsyit.cn/forum.php?mod=viewthread&tid=35999        
     最大的算式  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36055
     最长公子序列     回文串  最长公共子序列的变形使用  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36212
    相似基因
   

经典背包问题  它也算二维表型DP，注意我的那个推导过程， 特别是如何用一维数组的。

基础背包采药  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36061
疯狂的采药  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36000
开心的金明  http://www.hsyit.cn/forum.php?mod=viewthread&tid=35890
金明的预算 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36060

背包加强版
P1794 装备运输  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36146
P1509 找啊找啊找GF http://www.hsyit.cn/forum.php?mod=viewthread&tid=36134
氧气瓶氮气瓶    http://www.hsyit.cn/forum.php?mod=viewthread&tid=36015
P2736 “破锣摇滚”乐队 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36147
P1095 守望者的逃离  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36003
P2725 邮票 Stamps http://www.hsyit.cn/forum.php?mod=viewthread&tid=36027

  P1782 旅行商的背包 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36002

很难的背包P1757 通天之分组背包  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36148
区间DP
   P1063 能量项链 http://www.hsyit.cn/forum.php?mod=viewthread&tid=3669
   P1880 [NOI1995]石子合并 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36126