期末考试......

期末考试……

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

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

随机数基本使用方法

基本公式:

要取得[a,b)的随机整数,使用(rand() % (b-a))+ a;
要取得[a,b]的随机整数,使用(rand() % (b-a+1))+ a;
要取得(a,b]的随机整数,使用(rand() % (b-a))+ a + 1;
通用公式:a + rand() % n;其中的a是起始值,n是整数的范围。
要取得a到b之间的随机整数,另一种表示:a + (int)b * rand() / (RAND_MAX + 1)。
要取得0~1之间的浮点数,可以使用rand() / double(RAND_MAX)。

四子连棋

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


题意

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

分析

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

遇到的坑

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

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

STL

STL

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>类型的迭代器

SET

set的各成员函数列表

  1. begin()–返回指向第一个元素的迭代器
  2. clear()–清除所有元素
  3. count()–返回某个值元素的个数
  4. empty()–如果集合为空,返回true
  5. end()–返回指向最后一个元素的迭代器
  6. equal_range()–返回集合中与给定值相等的上下限的两个迭代器
  7. erase()–删除集合中的元素
  8. find()–返回一个指向被查找到元素的迭代器
  9. get_allocator()–返回集合的分配器
  10. insert()–在集合中插入元素
  11. lower_bound()–返回指向大于(或等于)某值的第一个元素的迭代器
  12. key_comp()–返回一个用于元素间值比较的函数
  13. max_size()–返回集合能容纳的元素的最大限值
  14. rbegin()–返回指向集合中最后一个元素的反向迭代器
  15. rend()–返回指向集合中第一个元素的反向迭代器
  16. size()–集合中元素的数目
  17. swap()–交换两个集合变量
  18. upper_bound()–返回大于某个值元素的迭代器
  19. value_comp()–返回一个用于比较元素间的值的函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstdio>
#include <set>

using namespace std;
set<int> s;
set<int>::iterator it_set;

int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int tmp;
scanf("%d",&tmp);
s.insert(tmp);
}
for(it_set=s.begin();it_set!=s.end();it_set++)
{
printf("%d\n",*it_set);
}
return 0;
}

链接

容器set和multiset

三角形牧场

P1284三角形牧场


题意

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

分析

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

  • f[i][j]=f[i−a[k]][j] || f[i][j−a[k]] || f[i][j]f[i][j]=f[i−a[k]][j] || f[i][j−a[k]] || f[i][j],相当于01背包,就不解释了……

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

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

    S=√p(p−a)(p−b)(p−c)S=p(p−a)(p−b)(p−c),p=12(a+b+c)p=12(a+b+c)

遇到的坑

好像没有什么

P1929 迷之阶梯

真的好坑,做了一下午……

题意

登上阶梯必须要按照它要求的方法, 否则就无法登上阶梯。它要求的方法有以下三个限制:

  1. 如果下一步阶梯的高度只比当前阶梯高 1,则可以直接登上。
  2. 除了第一步阶梯外,都可以从当前阶梯退到前一步阶梯。
  3. 当你连续退下 k 后,你可以一次跳上不超过当前阶梯高度 2^{k}2k的阶梯。比如说你现 在位于第 j 步阶梯,并且是从第 j+k 步阶梯退下来的,那么你可以跳到高度不超过当前阶 梯高度+2^{k}2k的任何一步阶梯。跳跃这一次只算一次移动。

开始时我们在第一步阶梯,由于时间紧迫,我们需要用最少的移动次数登上迷之阶梯。 请你计算出最少的移动步数。

分析

  • 定义状态为f[i]表示到第i个阶梯的最小步数
  • 由2可以直接得出if(h[i]==h[i-1]+1) f[i]=f[i-1]+1

遇到的坑

  • if(f[n]>=0x3f3f3f3f) f[n]=-1;在状态转移的过程中有可能比初始值更大,所以是大于等于

动态规划习题2

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
    • 通过以上两个判断不停地找波峰和波谷,记录答案就可以了

P1020 导弹拦截


*非常恶心的一道题,我已经被搞晕了*

分析

  • 第一问就是求最长不上升子序列,想象有一个栈,如果当前数小于等于栈顶的数,则直接入栈;否则二分查找栈内第一个大于等于当前数的数并替换它,因为与当前数相等的数是有贡献的
  • 第二问就是求最长上升子序列,我不会证明,只能大概的胡诌,因为相当于我只关心子序列的长度,而只要有一个高度大于当前长度,就必须去新建一个序列,有点类似于木桶原理……

遇到的坑

  • 最长不下降子序列 等价于 倒序的最长不上升子序列
  • 最长下降子序列 等价于 倒序的最长上升子序列
  • lower_bound 二分查找第一个大于等于基准数的数(涵盖的范围更广)
  • upper_bound 二分查找第一个大于基准数的数

P1103 书本整理


*很有感触的一道题*

分析

  • 可以抽象为:给定一串数列,首先对数列进行排序然后从数列中删除K个数使得整个数列每相邻两个数的差的绝对值的和最小,输出最小的和,即最小不整齐度。好拗口

  • f[i][j]表示长度为j的数列,数列最后一个的位置标号为j

  • 假设当前状态数列长度为j,现在以第i位为数列的最后一个,即最后一个肯定留下的最小不整齐度。因为这一位肯定要保留,所以状态肯定是从j-1转移过来的。其次我们就要枚举数列长度为j-1时,数列最后一个保留的数到底是多少,由此我们可以计算出应该增加的不整齐度

  • 转移方程:

    1
    f[i][j]=min(f[t][j-1]+abs(a[i]-a[t]),f[i][j]);//最后一个保留a[i],数列长度为j的最小不整洁度
  • 接下来考虑边界问题

    • j<=i 序列里的数肯定不会超过所有当前的数
    • t>=j-1 由上式同理可以得出,状态中的第一维度肯定大于等于第二维度
    • t<i 数列里的最后一个数肯定不可能达到现在及以后的数
    • j<=n-K 由题意可得……

    分析最清晰的一回

遇到的坑

  • f[n][n-k]并不是最终答案!!!只要状态里最后一个位置编号大于n-K,并且序列里有n-K个数,就有可能成为答案,所以我们要扫一遍找到最终答案
  • 赋初值!!! 因为我们状态转移选择的是最小值,最开始所有状态都是0,无论怎么转移都是0。所以我们把所有初值赋值为无穷大?显然不可行。我们可以每当需要转移该状态时,在确定该状态一定会被改变的前提下提前赋值为无穷大****
  • 真的都是很深很深的坑

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//与前文所使用的变量名有所不同
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int N=110;
struct ty
{
int h,w;
};
ty b[N];
int n,K,f[N][N];//是否保留

bool operator < (const ty &a,const ty &b)
{
return a.h<b.h;
}

int main()
{
scanf("%d%d",&n,&K);
for(int i=1;i<=n;i++)
scanf("%d%d",&b[i].h,&b[i].w);

K=n-K;
sort(b+1,b+n+1);

//第i个数保留j个的最小整齐度,序列的最后一个数序号为i
for(int i=1;i<=n;i++)
{
for(int j=1;j<=K&&j<=i;j++)
{
if(j==1) continue;
f[i][j]=0x3f3f3f3f;
for(int t=j-1;t<i;t++)
{
f[i][j]=min(f[t][j-1]+abs(b[i].w-b[t].w),f[i][j]);
}
// printf("f[%d][%d]=%d\n",i,j,f[i][j]);
}
}

int ans=0x3f3f3f3f;
for(int i=K;i<=n;i++)
ans=min(ans,f[i][K]);
printf("%d\n",ans);
return 0;
}

我的2018

刷新


2018年,终是不平凡的一年。

身处在新旧交替的此刻,脑海里跃现着2018年的点点滴滴,汗水与泪水、希望与失望,成功与失败……仿佛都没有那么重要了,重要的是此刻,经历时间的冒险,我终于来到了这里,来到了2019年的启幕。

也许,我还是中考彻夜未眠的我,却也一笔一划地书写出了青春最美的篇章;也许,我还是电脑前苦思冥想的我,却一字一字敲击出了梦想坚强的力量;也许,我还是初次坐在高中教室里的我,满是对未来的憧憬。时间,总是动人的力量,一切仿佛都在上一秒刚刚发生,另一切却又像是在未知的下一秒即将发生。

征程总是在路上,希望总是在远方。犹记得备战中考的日子,犹记得与同学之间相互激励,相互进步的每一天。当记忆被时间模糊,历久弥新的是这美好的情谊,我相信,对我而言,这是一笔珍贵的财富,不再的财富。而如今,向往与憧憬变为了现实,我来到了这里,来到了高新一中。迎着改革开放四十周年的春风,我也踏上了新的征程,迎来了新的挑战。

热爱我的热爱。中考后的第二天,我来到了这里,结识了信息学竞赛的学长们,在教练的指导下开始了新的学习。计算机科学,像是一座冰山缓缓突破海平面,从视野里一个点到覆盖了整个视野,有如此多的新知等待我去探索,此刻,心潮澎湃。我的热爱,能够更深地热爱。我坚信,这份热爱终将成为梦想的锋芒。

道阻且长,行则将至。茫然,始终伴随着我;舍得,总是让我无措。我依旧在努力寻找那个最好的自己,在时间的平衡木上找到最佳的那一点,在情绪的池沼里小心前行,在思维的隧洞中向深处继续挖掘。需要去做的,还有很多很多,奔跑不能停止,生活不止眼前的苟且,还有诗和远方。

任何组织和个人,达到某个临界点时,都需要自我刷新。拥抱同理心,培养‘无所不学’的求知欲,以及建立成长型思维是拥抱智能时代自我刷新的三个重要步骤”。

这是我的偶像,微软CEO萨提亚·纳德拉在《刷新》一书中所提到的。

刷新,并不意味着推翻重来,而是有目的、有针对性地调整。2018年,微软公司通过“刷新”,超越苹果成为了全球市值最高的公司。2019年,更是我需要刷新的一年。

在这里,刷新态度,刷新认知,刷新属于我的未来。

李昊锦
2018年12月31日

P1429 平面最近点对(加强版)

P1429 平面最近点对(加强版)

题目

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

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

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

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

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

思路

  • 首先考虑暴力,枚举所有点对,复杂度为O(N^2)

  • 然后就是正解:

    分治算法

    • 每一次把平面分成两个部分,找出左边的最近点对,右边的最近点对以及穿越分割线的最近点对。
    • 在求穿越分割线的最近点对时,用左右已经算出的最小值作为参考,一旦大于就停止搜索

动态规划2-背包DP

动态规划2-背包DP

装箱问题

有一个箱子容量为V(正整数,0<=V<=20000),同时有n个物品(0<n<=30),每个物品有一个体积(正整数)。
要求n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。
输入描述:一个整数v,表示箱子容量;一个整数n,表示有n个物品;接下来n个整数,分别表示这n 个物品的各自体积
输出描述:一个整数,表示箱子剩余空间。
样例输入: 24 6
​ 8 3 12 7 9 7
样例输出:0

状态:f[i][j]表示前i个物品能否装满j的体积

1
2
3
4
5
for(int i=1;i<=n;i++)
for(int j=1;j<=v;j++)
f[i][j]=f[i-1][j] || f[i-1][j-v[i]];
for(int i=v;i>0;i++)
if(f[n][i]) printf("%d",v-i);

优化

  • 01滚动

    f[i][j]中每一次的状态转移只与上一行有关系,所以只需要一个2层的数组,可以用&1实现

  • 就地滚动

    每一次都会由左边的值转移到现在,所以每一次只要将循环从右往左就可以了


01背包

有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

##方法1:动态规划
状态:还是一样,每一个背包只有选或者不选两种决策,这道题多了一个条件,相当于状态多了一个维度
转移方程f[i][j][k]=f[i-1][j][k]||f[i-1][j-v[i]][k-c[i]]
*i维度可以01滚动*

动态规划1

笔记

最优子结构:子结构最优,全局一定最优
无后效性:各个决策部分单独存在,不会相互影响

  1. 确定状态
    • 维度从低往高试
  2. 确定转移方程
    • 每一个状态的决策
    • 初始值
    • 边界问题
  3. 是否可以降低维度或其他优化

最大子串和


题意:给你一个有正有负的序列,求一个=子串(连续的一段),使其和最大!
样例输入: -5 6 -1 5 4 -7
样例输出: 14

状态:f[i]表示前i个数的最大子串和,每个状态只有两种决策:1. 与前面构成一个子串 2. 单独成为一个子串的开头
转移方程: f[i]=max(f[i−1]+a[i],a[i])f[i]=max(f[i−1]+a[i],a[i])

不相交的两个子串的最大和


给你一个有正有负的序列,求两个不重叠的子串,使其和最大!

方法一

两个不重叠的子串中间一定有一个分界点,我们可以枚举这个分界点,分别求出这个点左边的最大子串和以及右边的最大子串和

方法二

定义状态f[i][j]为前i个数组成了j个子串的最大值,当前状态下有两种选择,一种是与前面组成子串,一种是单独成为一个子串,但是需要枚举这个数前面的串的结尾在哪里
状态转移方程为f[i][j]=max(f[i−1][j]+a[i],f[k][j−1]+a[i],0<k<if[i][j]=max(f[i−1][j]+a[i],f[k][j−1]+a[i],0<k<i​
优化:可以用前缀和维护k维度,算出前k个数的最大和

最大子矩形


在一个矩阵中找到一个子矩阵,该子矩阵和最大!!输出最大和即可。

从暴力的角度考虑,这道题需要枚举矩形的两个顶点,也就是O(n^4)
我们可以只枚举两个顶点的行坐标,即找到这个矩形的高度所在的位置,然后把每一列的数之和求出来当做一个数,可以提前求出每一列前缀和,也就转化成了求最大子串和。

最长公共子序列


给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。
最长公共子序列:公共子序列中长度最长的子序列。
给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…, yn},找出X和Y的一个最长公共子序列。

状态f[i][j]表示X的前i位与Y的前j位最长公共子序列的长度
转移方程

1
2
3
4
5
6
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
if(X[i]==Y[j]) f[i][j]=f[i-1][j-1]+1;
else f[i][j]=max(f[i-1][j],f[i][j-1]);
}

回文词


回文词是一种对称的字符串——也就是说,一个回文词,从左到右读和从右到左读得到的结果是一样的。任意给定一个字符串,通过插入若干字符,都可以变成一个回文词。你的任务是写一个程序,求出将给定字符串变成回文词所需插入的最少字符数。比如字符串“Ab3bd”,在插入两个字符后可以变成一个回文词(“dAb3bAd”或“Adb3bdA”)。然而,插入两个以下的字符无法使它变成一个回文词。
给出一个字符串求出使其变为回文串需要插入的最少字符数。

思路:需要添加的字符的长度为原字符串的总长度减去现有的回文串长度,所以只要求出原字符串的回文串的长度就可以解决了
回文串的定义是正串与反串一样,那么正串与反串的最长公共子序列长度就是回文串的长度
为什么不是最长公共子串长度?* 在添加字符的时候可以在任意位置插入,所以不必要求连续。所以如果只能从左右两边加入,那么就是最长公共子串长度*

乘积最大


设有一个长度为N的数字串,要求选手使用K个乘号将它分成K+1个部分,找出一种分法,使得这K+1个部分的乘积能够为最大。
如:有一个数字串:312, 当N=3,K=1时会有以下两种分法: 1) 312=36 2) 312=62
这时,符合题目要求的结果是:31*2=62

状态:f[i][j]表示前i位使用k个乘号的最大乘积
决策

  1. 这个数与前面的数组成更大的数,需要枚举这个数的起点
  2. 单独成为一个新数

*在算乘积的时候可以先算出前缀‘乘’*
转移方程:

1
2
3
4
5
6
7
8
9
10
11
for(int i=1;i<=n;i++)
muti[i]*=muti[i-1]*a[i];
muti[0]=1;

for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++)
{
f[i][j]=f[i-1][j-1]*a[i];
for(int k=1;k<i;k++)
f[i][j]=f[k][j-1]*(muti[i]/muti[k-1]);
}