传送带(三分查找)

题目描述:

在一个二维平面上有两条传送带,每一条传送带可以看成是一条线段。两条
传送带分别为线段 AB 和线段 CD。小 y 在 AB 上的移动速度为 P,在 CD 上的
移动速度为 Q,在平面上的移动速度 R。现在,小 y 想从 A 点走到 D 点,请问
他最少需要走多长时间。

输入格式:

第一行是4个整数,表示A和B的坐标,分别为Ax,Ay,Bx,By。
第二行是4个整数,表示C和D的坐标,分别为Cx,Cy,Dx,Dy。
第三行是3个整数,分别是P,Q,R。

输出格式:

输出一行一个数,表示小 y 从 A 点走到 D 点的最短时间,保留到小数点后
2位。

样例输入:

0 0 0 100
100 0 100 100
2 2 1

样例输出:

136.60

数据范围:

对于30%的数据满足:
1<=Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=10
1<=P,Q,R<=5
对于100%的数据满足:
1<=Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=1000
1<=P,Q,R<=10

继续阅读传送带(三分查找)

Day12

【质数生成器】
题意:询问区间[m,n]里的质数,1<=m<=n<=10^9,n-m<=1000000。
显然线筛过不了1e9的数据,只能对[m,n]区间求质数。
一个数n如果是合数,那么必定会被sqrt(n)中的质数整除,考虑普通筛(233)。对于[m,n]中的数,只需枚举每个质数,将其在这个区间中的倍数筛去即可。
正确性:线筛只要将sqrt(n)中的质数筛出,大概是1e5左右,明显不会超时。[m,n]区间的普通筛是用质数去筛,比用每个数筛的时间大大减少。
【魔法树】
题意:一棵树,每个点有一种属性。一条路径上的魔法值是这样计算的:在起点的时候,魔法值为 1,每经过一条边,假设这条边拥有的魔法属性是 ci,如果这是奇数次经过带有 ci 魔法属性的边,则将魔法值乘上 ci 对应的魔法系数,否则将魔法值除以 ci 对应的魔法系数。
简化题目,即如果奇数次经过ci的点,那么答案就乘上di,否则这个ci对答案没用贡献。
考虑用二进制来表示每种属性的贡献,对于询问的两个点,只需以任意的点为树根,求出每个点的二进制数,在询问使^即可。
【hill】
题意:给出一座山,求一个最低的点能够看到所有地方。
简单的三分题。

2017长乐集训day2

首先是其实是A+组的B组

T1      今天唯一的得分项也是这几天第一次A的题,题目要求区间[0...1000]一些二次函数的最大值中的最小值,注意区间可取的数可为实数(刚开始被这个卡样例),因为二次函数的a总是大于零,即开口向上,可知F[x]在区间内定有最小值,画图可知。于是便可用三分查找的方法不断逼近最小值(要注意精度)。

 

T2        字符串分块,动态规划,不是很清楚

 

T3        非常强势的暴力,同样需要非常强势的预处理。。用线段树什么的

--------------------------------------下面是萌萌的分割线----------------------------------

继续阅读2017长乐集训day2

Day2

【曲线】
题意:令f(x)为多个二次(一次)函数的最大值,求f(x)的最小值。
画图可以发现两个二次函数取最大值的图像形状类似二次函数,可得f(x)的图像也类似二次函数。那么,可以在所给区间内用三分求出答案。
二分也可完成此题,二分答案ans,暴力判断每个二次函数<=ans的区间是否有交集,若有,则答案可行,反之答案不可行。

【挑战】

题意:将字符串分块,使每个块中的字母都在下一个块中出现过。(即下一块每个字母的出现次数比当前块多)。求最多的分块。
令f[i][j]表示在i位是最后一个块的长度为j的答案。可由f[i - j][k]转移得到。时间复杂度为O(n ^ 3)。可得70分。
改进这个算法,因为要求块最多,应用贪心的思想,每个块的长度越少,块的数量越多。令f[i]表示以i为结尾最后一块的长度最短是多少。可以由f[i - f[i]]转移得到。

【序列】

题意:判断序列的所有子序列是否都有数只出现一次。
暴力枚举每个子序列,判断是否符合条件,可得30分。
改进暴力,对于一个a[i],前一次出现记为pre[i],后一次出现记为nex[i]。那左端点l在pre[i]+1..i,右端点在i..nex[i]-1都是合法的。如果判定一个区间[l,r],a[i]是其中唯一出现过的数字。那这个区间就可以切割成判定2个区间[l,i - 1],[i + 1, r]。那对于一个区间[l,r],i,j同时从左边和右边开始扫,碰到第一个唯一出现的数字就切割。直到l>=r。
这种做法看起来很像暴力,但实际上跑得飞快。时间复杂度证明:T(n) = T(k) + T(n-k)+min(n, n - k)。一种直观的想法就是,每次复杂度都是较小的那个区间。倒过来看相当于较小的合并到较大的。那就是启发式合并。O(nlogn)。

主要代码如下:

继续阅读Day2

[BZOJ 1038] [ZJOI 2008] 瞭望塔

三分。

首先根据题意,一个点能看到一条线段上的所有点当且仅当这个点在这条线段所在直线的上方。

故建出塔的最高点必须在所有线段所在直线上方,即所有直线上方的半平面区域交集内。显然在交集平面边界取塔最高点取得高度最小。

并且有这么一个性质:对于单条线段,塔的高度对于横坐标满足单峰性(证明见 Reference)。

那么就可以根据这个性质三分横坐标,搜索交集平面边界在当前横坐标的纵坐标值与当前线段上的纵坐标差最小值即可。

注意精度。

Reference:

http://blog.leanote.com/post/wearry/1c21a8bdd41e

http://blog.csdn.net/Fuxey/article/details/50528819

代码如下:

继续阅读[BZOJ 1038] [ZJOI 2008] 瞭望塔

BZOJ【1038】瞭望塔

题意:

给出许多线段,要求找出一个位置,使其可以看到所有线段,并且长度最短。

我们可以发现,要使其能看到所有线段,相当于求看到每条线段的最小长度的最大值,于是我们可以用三分

三分每条线段上的一个位置,再求其最小值。由于点是连续的,就可以与每条线段分别求解。

正解是模拟退火或半平面交

BZOJ【1857】传送带

描述

在平面上给出两条线段AB,CD,再给出在线段、平面的速度,求出从A走到D最短的时间。

从题意上看,我们很(ping)容(zhi)易(jue)得出答案是单峰的,也就是对于AB上的点E,在从A到B的过程中,答案是先变小,再变大。于是就用三分来求峰值。

单峰证明:对于AB上的点E,到CD上的点F。当EF⊥CD时,E到CD的距离最短,而时间也最短。 否则的话E到CD的距离一定大于EF。


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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<climits>

using namespace std;

struct node
{
    double x, y;
}A, B, C, D, T;

double p, r, q;
double ans = INT_MAX;

double dir(node a, node b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

node tri(node a, node b, int t)
{
    T.x = a.x + (b.x - a.x) * t *1.0 / 3;
    T.y = a.y + (b.y - a.y) * t *1.0 / 3;
    return T;
}

double ANS(node a, node b)
{
    return dir(a, A) / p + dir(b, D) / q + dir(a, b) / r;
}

double Ans(node t)
{
    node c = C, d = D, x, y;
    double time_x, time_y, times = INT_MAX;
    do
    {
       x = tri(c, d, 1);
       time_x = ANS(t, x);
       y = tri(c, d, 2);
       time_y = ANS(t, y);
       times = min(times, min(time_x, time_y));
       if (time_x > time_y) c = x;
       else d = y;
    }while (dir(c, d) >= 0.0000001);
    return times;
}

int main(void)
{
    freopen("walk.in","r",stdin);
    freopen("walk.out","w",stdout);
   
    cin >> A.x >> A.y >> B.x >> B.y >> C.x >> C.y >> D.x >> D.y;
    cin >> p >> q >> r;
    node x, y;
    double time_x, time_y;
    do
    {
       x = tri(A, B, 1);
       time_x = Ans(x);
       y = tri(A, B, 2);
       time_y = Ans(y);
       ans = min(ans, min(time_x, time_y));
       if (time_x > time_y) A = x;
       else B = y;
    }while (dir(A, B) >= 0.0000001);
    printf("%.2f", ans);
   
    fclose(stdin);
    fclose(stdout);
    return 0;
}