刷新

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

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

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

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

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

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

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

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

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

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

李昊锦
2018年12月31日

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

装箱问题

有一个箱子容量为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. 确定状态
   • 维度从低往高试
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=362） 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]);
}

终于有一次能在考场上打出正解的模拟赛

连线游戏

题目

连线游戏（lines.cpp）
文件输入输出
时间限制：1s
空间限制：256M

【题目描述】
Farmer John最近发明了一个游戏，来考验自命不凡的贝茜。游戏开始的时候，FJ会给贝茜一块画着N (2 <= N <= 200)个不重合的点的木板，其中第i个点的横、纵坐标分别为X_i和Y_i (-1,000 <= X_i <=1,000； -1,000 <= Y_i <= 1,000)。
贝茜可以选两个点画一条过它们的直线，当且仅当平面上不存在与画出直线平行的直线。游戏结束时贝茜的得分，就是她画出的直线的总条数。为了在游戏中胜出，贝茜找到了你，希望你帮她计算一下最大可能得分。

【输入格式】
第1行: 输入1个正整数：N
第2..N+1行: 第i+1行用2个用空格隔开的整数X_i、Y_i，描述了点i的坐标

【输入样例】(lines.in):
4
-1 1
-2 0
0 0
1 1

【输出格式】
第1行: 输出1个整数，表示贝茜的最大得分，即她能画出的互不平行的直线数

【输出样例】 (lines.out):
4

【输出说明】

贝茜能画出以下4种斜率的直线：-1，0，1/3以及1。

思路

• 枚举两两构成直线的k值，如果k值不存在，则ans++。

遇到的坑

• 要考虑精度问题，考试的时候写了1e-5，结果炸了，改成1e-7就对了，甚至不加精度判断都能AC
• 特判分母为0的情况，本来以为Inf是无限大，所有Inf表示的都是一个意思，但实际炸了……
  ###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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N=210;
int x[N],y[N],n;
double ans[N*N];

int main()
{	
	freopen("lines.in","r",stdin);
	freopen("lines.out","w",stdout);
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&x[i],&y[i]);
	
	int cnt=0;
	for(int i=1;i<=n;i++)
	for(int j=i+1;j<=n;j++)
	{
		double sta;
		if(x[i]-x[j]==0) sta=0x3f3f3f3f;
		else sta=1.0*(y[i]-y[j])/(x[i]-x[j]);
		
		bool flag=1;
		for(int k=1;k<=cnt;k++)
		{
			if(ans[k]-sta<=1e-10 && ans[k]-sta>=-1e-10)
			{
				flag=0;
				break;	
			} 
		}
		if(flag) ans[++cnt]=sta;//printf("%lf\n",sta);
	}
	printf("%d\n",cnt);
	return 0; 
}

独木桥

题目

【问题描述】
战争已经进入到紧要时刻。你是运输小队长，正在率领运输部队向前线运送物资。运输任务像做题一样无聊。你希望找些刺激，于是命令你的士兵们到前方的一座独木桥上欣赏风景，而你留在桥下欣赏士兵们。士兵们十分愤怒，因为这座独木桥十分狭窄，只能容纳一个人通过。假如有两个人相向而行在桥上相遇，那么他们两人将无法绕过对方，只能由一个人回头下桥，让另一个人先通过。但是，可以有多个人同时呆在同一个位置。
突然，你收到从指挥部发来的信息，敌军的轰炸机正朝着你所在的独木桥飞来！为了安全，你的部队必须撤下独木桥。独木桥的长度为L，士兵们只能呆在坐标为整数的位置，所有士兵的速度都为1，当一个士兵某一时刻来到了坐标为0或L+1的位置时，他就离开了独木桥。
每个士兵都有一个初始面对的方向，他们会以匀速朝着这个方向行走，中途不会自己改变方向。但是，如果两个士兵面对面相遇，他们无法彼此通过对方，于是就分别转身，继续行走。转身不需要任何时间。
由于先前的愤怒，你已不能控制你的士兵。甚至，你连每个士兵初始面对的方向都不知道。因此，你想要知道你的部队最少需要多少时间就可能全部撤离独木桥。另外，总部也在安排阻拦敌人的进攻，因此你还需要知道你的部队最多需要多少时间才能全部撤离独木桥。

【输入文件】
第一行：一个整数L，表示独木桥的长度。桥上的坐标为1..L
第二行：一个整数N，表示初始时留在桥上士兵的数目。
第三行：有N个整数，分别表示每个士兵的初始坐标。初始时，没有两个士兵在同一坐标。

【输出文件】只有一行，输出两个整数，分别表示部队撤离独木桥的最小时间和最大时间。两个整数用一个空格分开。

【样例输入】
4
2
1 3

【样例输出】
2 4

【数据规模及约定】
N≤L≤1000

思路

两个人遇见并分别掉头与两个人继续往前走是等价的，因为人与人之间不存在差异。

每个士兵只有两种选择，向左或向右

最大值就是每个士兵的最长选择的集合中的最大值

最小值就是每个士兵的最短选择的集合中的最大值

遇到的坑

• 最外一层都是max，满足木桶原理

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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int l,n,ans1,ans2;//max,min

int main()
{
	freopen("bridge.in","r",stdin);
	freopen("bridge.out","w",stdout);
	
	scanf("%d%d",&l,&n);
	while(n--)
	{
		int x;
		scanf("%d",&x);
		ans1=max(ans1,min(x,l-x+1));//min
		ans2=max(ans2,max(x,l-x+1));//max
	}
	printf("%d %d\n",ans1,ans2);
	return 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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N=110;
int mp[N],c,p,ans;

int main()
{
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	
	scanf("%d%d",&c,&p);
	for(int i=1;i<=c;i++)
		scanf("%d",&mp[i]);

	if(p==1)
	{
		for(int i=1;i<=c-3;i++)
			if(mp[i]==mp[i+1] && mp[i+1]==mp[i+2] && mp[i+2]==mp[i+3]) ans++;
		printf("%d\n",c+ans);
		return 0;
	}
	if(p==2)
	{
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]) ans++;
		printf("%d\n",ans);
		return 0;
	}
	if(p==3)
	{
		for(int i=1;i<=c-2;i++)
			if(mp[i]==mp[i+1] && mp[i+1]==mp[i+2]-1) ans++;
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]+1) ans++;
		printf("%d\n",ans);
		return 0;
	}
	if(p==4)
	{
		for(int i=1;i<=c-2;i++)
			if(mp[i]==mp[i+1]+1 && mp[i+1]==mp[i+2]) ans++;
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]-1) ans++;
		printf("%d\n",ans);
		return 0;
	}
	if(p==5)
	{
		for(int i=1;i<=c-2;i++)
			if(mp[i]==mp[i+1] && mp[i+1]==mp[i+2]) ans++;
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]-1) ans++;
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]+1) ans++;
		for(int i=1;i<=c-2;i++)
			if(mp[i]==mp[i+1]+1 && mp[i]==mp[i+2]) ans++;
		printf("%d\n",ans);
		return 0;
	}
	if(p==6)
	{
		for(int i=1;i<=c-2;i++)
			if(mp[i]==mp[i+1] && mp[i+1]==mp[i+2]) ans++;
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]) ans++; 
		for(int i=1;i<=c-2;i++)
			if(mp[i]==mp[i+1]-1 && mp[i+1]==mp[i+2]) ans++;
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]+2) ans++; 
		printf("%d\n",ans);
		return 0;
	}
	if(p==7)
	{
		for(int i=1;i<=c-2;i++)
			if(mp[i]==mp[i+1] && mp[i+1]==mp[i+2]) ans++;
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]) ans++; 
		for(int i=1;i<=c-2;i++)
			if(mp[i]==mp[i+1] && mp[i+1]==mp[i+2]+1) ans++;
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]-2) ans++; 
		printf("%d\n",ans);
		return 0;
	}
	return 0;
}

/*
5 7
2 0 3 1 2
*/

题面

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

自己汉诺塔问题晕了很久，但搜索写多了至少也有一些通悟

不妨假设：

• 当只有

  1

  1个盘子

  时

  1. 把盘子从A直接移到C

• 当只有

  1

  2个盘子

  时

  1. 将上面的盘子从A移动到B
  2. 将下面的盘子从A移动到C
  3. 将B上的盘子从B移动到C

• 当有

  1

  3个盘子

  时

  1. 将上面的盘子从A移动到C
  2. 将中间的盘子从A移动到B
  3. 将C上的盘子从C移动到B
  4. 将下面的盘子从A移动到C
  5. 将B上面的盘子从B移到A
  6. 将B上的盘子从B移到C
  7. 将A上的盘子从A移到C

可以发现当有3个盘子时，中间就会转化成2个盘子的情况，2个盘子最后就会转化成1个盘子的情况，显然可采用递归的方法

思路

把n-1个盘子移到B，再把最下面的盘子移到C，再把B上的n-1个盘子移到C

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

#include <iostream>
#include <cstdio>
using namespace std;

int ans,n;

void dfs(int x,int a,int b,int c)// num from  trans   end
{
    if(x==1)
    {
        printf("move from %d to %d\n",a,c);
        ans++;
     	return;   
    }
    dfs(x-1,a,c,b);
    printf("move from %d to %d\n",a,c);
    ans++;
    dfs(x-1,b,a,c);
}

int main()
{
    scanf("%d",&n);
    dfs(n,1,2,3);
    printf("need %d steps\n",ans);
	return 0;
}

自己遇到的坑

• a,b,c三个柱子没有搞清楚，递归函数里到底四个参数分别代表什么要搞清楚

其他一些……

• f[n]=f[n-1]*2+1

  本次的次数就等于把n-1个盘子移动了两回，加上剩下的最大的盘子移动的一次

思路：单调队列

以求最小值为例

• 在读取每一个数 ai 的过程中，判断队尾的数是否大于ai,如果大于则证明队尾的数已经没有意义了，因为*它已经不可能成为现在及以后所有窗口内的最小值*，不妨弹出，重复以上操作，直到ai小于队尾的数，再把ai放到队尾
• 当现在的长度已经达到窗口的长度时，每一次都会输出最小值，因为队列是单调递减的，第一个数一定是现在窗口内最小的数，直接输出
• 在队尾添加的过程中，*要始终保证队列里的数都在窗口内*，当区间长度大于窗口长度时，要从队首弹出

自己遇到的坑

• 队列内存储的是这个数的位置，不是这个数的大小\，大小通过数组类似映射表示

• 要考虑好整个过程的先后顺序\

  1. 先确保队列内的数都在范围内
  2. 把所有比ai小的队尾数依次弹出
  3. 将ai入队
  4. 如果达到滑动窗口范围，输出值

• 两个数的编号相减加1代表该闭区间的长度\

• 当算完最小值时队列不一定是空的，要先清空队列

C++ STL 双端队列 deque

q.push_back: 从后端加入 q.pop_back: 从后端弹出
从前端就是front
q.clear: 清空队列
q.size(): 读取队列的长度，但是好像类型不是int，只能用来判断数组是否为空

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

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

const int N=1e6+5;
int a[N];
deque<int> q;

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    
//	q.push_back(1);
    //minn
    for(int i=1;i<=n;i++)
    {
        if(q.size() && i-k>=q.front()) q.pop_front();
        while(q.size() && a[i]<=a[q.back()]) q.pop_back();
        q.push_back(i);
        if(i>=k) printf("%d ",a[q.front()]);
    }
    
//	return 0;
    printf("\n");
    q.clear();
//	q.push_back(1);
    //maxn
    for(int i=1;i<=n;i++)
    {
        if(q.size() && i-k>=q.front()) q.pop_front();
        while(q.size() && a[i]>=a[q.back()]) q.pop_back();
        q.push_back(i);
        if(i>=k) printf("%d ",a[q.front()]);
    }
    
    return 0;
}