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]);
}

2018/12/8模拟赛

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

连线游戏

题目

连线游戏(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;
}