期末考试……

 生活
 置顶

该来的终究还是来了,欠下的终究是要还的

同时祝大佬们冬令营集训顺利!

线段树基础

 OI

线段树是一种数据结构,主要用来解决区间相关问题

基本思路

我们把一个区间像归并排序一样构建一个完全二叉树,每一次修改或者查询区间都不需要全部修改,只需要改动上层包含这一子区间的区间即可

STL(持续更新)

 OI

C++ STL 之所以得到广泛的赞誉,也被很多人使用,不只是提供了像vector, string, list等方便的容器,更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。vector封装数组,list封装了链表,map和set封装了二叉树等,在封装这些数据结构的时候,STL按照程序员的使用习惯,以成员函数方式提供的常用操作,如:插入、排序、删除、查找等。让用户在STL使用过程中,并不会感到陌生。

迭代器

1
2
set<int>::iterator it_set//一个set<int>类型的迭代器
map<string,int>::iterator it_map//一个map<string,int>类型的迭代器

四子连棋

 OI

这是我到目前为止写过最长的代码之一……


题意

44的棋盘,一共有三种属性:白棋,黑棋,空格(有且仅有两个),每一次可以移动一颗棋子,黑白棋交替进行,只能移到空格的地方。求达成四子连棋局面(*横竖斜都算)所需的最小步数

分析

  • 广搜,和八数码问题差不多,但是更繁琐了。
  • 黑白棋交替进行,那么我们需要在搜索的时候除了当前地图和步数还需要保存当前该哪一方行棋
  • 广搜要搜两遍,分别是黑棋先走或白棋先走
  • 每一次需要考虑两个空格,所以从两个当前点搜状态

遇到的坑

  • 很多都是重复的代码,只要细心就好了,但有一个最坑的……

  • 黑棋先走和白棋先走走到的棋局相同的情况也是两种情况,不能判重删去!!!

三角形牧场

 OI

P1284三角形牧场


题意

现在有n段木棍,全部使用组成三角形的三条边,使三角形的面积最大

分析

  • 首先看数据范围,边长最大为40*40/3,并且因为要使用所有的木棍,所以只要两条边确定就可以知道第三条边的确定长度。因此我们可以设状态f[i][j]表示三角形的两条边分别是i,j的情况是否成立

  • ,相当于01背包,就不解释了……

  • 定义初始状态$f[0][0]=1$

  • 三条边都知道了,如何求面积呢?这里我们需要用到海伦公式

    ,$p=\frac{1}{2}(a+b+c)$

遇到的坑

~~好像没有什么~

动态规划习题2

 OI

P1970 花匠


分析

  • 第一次很容易就能想到转移方程:

    1
    2
    if(a[i]>a[i+1] && a[i]>a[i-1]) f[i]=f[i-1]+1;
    else if(a[i]<a[i+1] && a[i]<a[i-1]) f[i]=f[i-1]+1;

    但是这样做有一个很大的问题,无法确定最后一个状态的转移是否合法

    然后我就想找到最后一个状态是从哪里转移过来的,最后再额外判断一遍。虽然有点不像动态规划,只要用last1last2两个变量储存倒数第二个和第三个留下的点,但还是WA了2个点。

    原因好像是我丢掉了一些状态:我默认了只要这棵花能选就选,不满足无后效性

  • 动态规划

    正解:一维无法解决问题,那么就升一维。

    定义状态为f[i][j]表示第i个花处在上升或下降序列中能选的最多的花数

    状态转移方程为

    1
    2
    3
    4
    if(a[i]<a[i+1] && a[i]<a[i-1]) f[i][0]=f[i-1][1]+1;
    else f[i][0]=f[i-1][0];
    if(a[i]>a[i+1] && a[i]>a[i-1]) f[i][1]=f[i-1][0]+1;
    else f[i][1]=f[i-1][1];
  • 贪心

    为了方便我们设当前的花为A,下一盆花为B

    • 第一盆花肯定要选,如果不选的话第二盆就成了第一盆,花的总数就会减少,一定不会比选第一盆花更优
    • 如果B比A还高,那么一定会选择B,因为落差的区间变大了,能够容纳的合法的花也变多了;同理,如果BA还小,那么一定会选择B
    • 通过以上两个判断不停地找波峰和波谷,记录答案就可以了

动态规划习题1

 OI

P1504 积木城堡


分析

  • 最终的高度最高为所有城堡现有高度的最小值
  • 把每个城堡当做一个背包,每一块积木放入背包,求出该城堡能够组成的所有背包体积
  • 把背包体积进行统计,所有城堡统计完后扫一遍找到最大的都能满足的体积

遇到的坑

  • 高度重复累计
  • 枚举体积的循环从右往左枚举,每一次状态转移使用上一层左边的量,如果从右往左枚举就是相当于每个零件有无数个

题目

题目描述
给定平面上n个点,找出其中的一对点的距离,使得在这n个点的所有点对中,该距离为所有点对中最小的

输入输出格式
输入格式:
第一行:n;2≤n≤200000

接下来n行:每行两个实数:x y,表示一个点的行坐标和列坐标,中间用一个空格隔开。

输出格式:
仅一行,一个实数,表示最短距离,精确到小数点后面4位。

输入输出样例
输入样例#1:
3
1 1
1 2
2 2
输出样例#1:
1.0000