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)

  • 然后就是正解:

    分治算法

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

动态规划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]。求解将哪些物品装入背包可使价值总和最大。

Read More

动态规划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])

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


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

Read More

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;
}
Read More
汉诺塔问题

汉诺塔问题

题面

相传在古印度圣庙中,有一种被称为汉诺塔(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;
}
Read More

滑动窗口

思路:单调队列

以求最小值为例

  • 在读取每一个数 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,只能用来判断数组是否为空


Read More