博客

第一次写博客，有什么不足之处，请提意见。

题目1 : 焦距

时间限制:
2000ms

单点时限:
1000ms

内存限制:
256MB

描述

一般来说，我们采用针孔相机模型，也就是认为它用到的是小孔成像原理。

在相机坐标系下，一般来说，我们用到的单位长度，不是“米”这样的国际单位，而是相邻像素的长度。而焦距在相机坐标系中的大小，是在图像处理领域的一个非常重要的物理量。

假设我们已经根据相机参数，得到镜头的物理焦距大小(focal length)，和相机胶片的宽度(CCD width)，以及照片的横向分辨率(image width)，则具体计算公式为：

Focal length in pixels = (image width in pixels) * (focal length on earth) / (CCD width on earth)

比如说对于Canon PowerShot S100, 带入公式得

Focal length in pixels = 1600 pixels * 5.4mm / 5.27mm = 1639.49 pixels

现在，请您写一段通用的程序，来求解焦距在相机坐标系中的大小。

输入

多组测试数据。首先是一个正整数T，表示测试数据的组数。

每组测试数据占一行，分别为

镜头的物理焦距大小(focal length on earth)

相机胶片的宽度(CCD width on earth)

照片的横向分辨率大小(image width in pixels)，单位为px。

之间用一个空格分隔。

输出

每组数据输出一行，格式为“Case X: Ypx”。 X为测试数据的编号，从1开始；Y为焦距在相机坐标系中的大小(focallength in pixels)，保留小数点后2位有效数字，四舍五入取整。

数据范围

对于小数据：focal length on earth和CCD width on earth单位都是毫米(mm)

对于大数据：长度单位还可能为米(m), 分米(dm), 厘米(cm), 毫米(mm), 微米(um)，纳米(nm)

样例输入

2
5.4mm 5.27mm 1600px
5400um 0.00527m 1600px

样例输出

Case 1: 1639.47px
Case 2: 1639.47px

初看以为是个复杂的计算几何就直接跳过去了；只需要单位转换。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
using namespace std;

double get(char s[])
{
    double ans;
    sscanf(s, "%lf", &ans);
    int len = strlen(s);

    char c = s[len - 2];
    if(c == 'd')  ans *= 100;
    else
    if(c == 'c')    ans *= 10;
    else
    if(c == 'm')    ;
    else
    if(c=='u')  ans /= 1000;
    else
    if(c == 'n')    ans /= 1000000;
    else
        ans *= 1000;

    return ans;
}
int main()
{
    int T;
    scanf("%d", &T);
    for(int cas = 1; cas <= T; cas++)
    {
        char s[1000];

        scanf("%s", s);
        double focal = get(s);

        scanf("%s", s);
        double ccd = get(s);

        scanf("%s", s);
        double image;
        sscanf(s, "%lf", &image);

        //printf("{%lf %lf %lf}\n", focal, ccd, image);
        double ans = image * focal / ccd;
        printf("Case %d: %.2lfpx\n", cas, ans);
    }
    return 0;
}

题目2 : 树

时间限制:4000ms

单点时限:2000ms

内存限制:256MB

描述

有一个N个节点的树，其中点1是根。初始点权值都是0。

一个节点的深度定义为其父节点的深度+1,。特别的，根节点的深度定义为1。

现在需要支持一系列以下操作：给节点u的子树中，深度在l和r之间的节点的权值（这里的深度依然从整个树的根节点开始计算），都加上一个数delta。

问完成所有操作后，各节点的权值是多少。

为了减少巨大输出带来的开销，假设完成所有操作后，各节点的权值是answer[1..N]，请你按照如下方式计算出一个Hash值（请选择合适的数据类型，注意避免溢出的情况）。最终只需要输出这个Hash值即可。

MOD =1000000007; // 10^9 + 7

MAGIC= 12347;

Hash =0;

For i= 1 to N do

Hash = (Hash * MAGIC + answer[i]) mod MOD;

EndFor

输入

第一行一个整数T (1 ≤ T ≤ 5)，表示数据组数。

接下来是T组输入数据，测试数据之间没有空行。

每组数据格式如下：

第一行一个整数N (1 ≤ N ≤ 105)，表示树的节点总数。

接下来N – 1行，每行1个数，a (1 ≤ a ≤ N)，依次表示2..N节点的父亲节点的编号。

接下来一个整数Q(1 ≤ Q ≤ 105)，表示操作总数。

接下来Q行，每行4个整数，u, l, r, delta (1 ≤ u ≤ N, 1 ≤ l ≤ r ≤ N, -109 ≤ delta ≤ 109)，代表一次操作。

输出

对每组数据，先输出一行“Case x: ”，x表示是第几组数据，然后接这组数据答案的Hash值。

数据范围

小数据：1 ≤ N, Q ≤ 1000

大数据：1 ≤ N, Q ≤ 105

样例解释

点1的子树中有1,2,3三个节点。其中深度在2-3之间的是点2和点3。

点2的子树中有2,3两个节点。其中没有深度为1的节点。

所以，执行完所有操作之后，只有2,3两点的权值增加了1。即答案是0 1 1。再计算对应的Hash值即可。

样例输入

1
3
1
2
2
1 2 3 1
2 1 1 1

样例输出

Case 1: 12348

跟树相关的算法，树链剖分、树形dp、欧拉序列。都没用上，该题只需要dfs，然后再用树状数组统计下当前节点的祖先的影响就可以了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
using namespace std;

typedef long long ll;
const int maxn = 100010;
int first[maxn];
struct Arc
{
    int v, next;
}arc[maxn];
int first2[maxn];
struct Arc2
{
    int l, delta, next;
}query[maxn * 2];
int cnt;
int n;
ll answer[maxn], sum[maxn];

void addQuery(int u, int l, int delta)
{
    query[cnt].l = l;
    query[cnt].delta = delta;
    query[cnt].next = first2[u];
    first2[u] = cnt++;
}

void add(int i, int delta)
{
    for(; i <= n; i += i & (-i))
        sum[i] += delta;
}

ll ask(int i)
{
    ll ans = 0;
    for(; i > 0; i-= i & (-i))
        ans += sum[i];

    return ans;
}

void dfs(int u, int deep)
{
   // printf("(%d %d)\n", u, deep);
    for(int i = first2[u]; i + 1; i = query[i].next)
    {
        int l = query[i].l, delta = query[i].delta;
        add(l, delta);
    }

    answer[u] = ask(deep);
    for(int i = first[u]; i + 1; i = arc[i].next)
    {
        int v = arc[i].v;
        dfs(v, deep + 1);
    }

    for(int i = first2[u]; i + 1; i = query[i].next)
    {
        int l = query[i].l, delta = query[i].delta;
        add(l, -delta);
    }
}
int solve()
{
    ll MOD =1000000007; // 10^9 + 7
    ll MAGIC= 12347;
    ll Hash =0;
    for(int i= 1; i <= n; i++)
       Hash = (Hash * MAGIC + answer[i]) % MOD;

    return (int)Hash;
}
int main()
{
    int T;
    scanf("%d", &T);
    for(int cas = 1; cas <= T; cas++)
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
            first[i] = first2[i] = -1;

        cnt = 0;
        for(int i = 2; i <= n; i++)
        {
            int fa;
            scanf("%d", &fa);
            arc[cnt].v = i;
            arc[cnt].next = first[fa];
            first[fa] = cnt++;
        }

        int Q;
        scanf("%d", &Q);
        cnt = 0;
        for(int i = 1; i <= Q; i++)
        {
            int u, l, r, delta;
            scanf("%d%d%d%d", &u, &l, &r, &delta);

            addQuery(u, l, delta);
            addQuery(u, r + 1, -delta);
        }

        dfs(1, 1);
        printf("Case %d: %d\n", cas, solve());
    }
    return 0;
}

题目3 : 活动中心

时间限制:
12000ms

单点时限:
6000ms

内存限制:
256MB

描述

A市是一个高度规划的城市，但是科技高端发达的地方，居民们也不能忘记运动和锻炼，因此城市规划局在设计A市的时候也要考虑为居民们建造一个活动中心，方便居住在A市的居民们能随时开展运动，锻炼强健的身心。

城市规划局希望活动中心的位置满足以下条件：

1. 到所有居住地的总距离最小。

2. 为了方便活动中心的资源补给和其他器材的维护，活动中心必须建设在A市的主干道上。

为了简化问题，我们将A市摆在二维平面上，城市的主干道看作直角坐标系平的X轴，城市中所有的居住地都可以看成二维平面上的一个点。

现在，A市的城市规划局希望知道活动中心建在哪儿最好。

输入

第一行包括一个数T，表示数据的组数。

接下来包含T组数据，每组数据的第一行包括一个整数N，表示A市共有N处居住地

接下来N行表示每处居住地的坐标。

输出

对于每组数据，输出一行“Case X: Y”，其中X表示每组数据的编号(从1开始)，Y表示活动中心的最优建造位置。我们建议你的输出保留Y到小数点后6位或以上，任何与标准答案的绝对误差或者相对误差在10-6以内的结果都将被视为正确。

数据范围

小数据：1 ≤ T ≤ 1000, 1 ≤ N ≤ 10

大数据：1 ≤ T ≤ 10, 1 ≤ N ≤ 105

对于所有数据，坐标值都是整数且绝对值都不超过106

样例解释

样例1：活动中心的最优建造位置为(1.678787, 0)

样例输入

1
3
1 1
2 2
3 3

样例输出

Case 1: 1.678787

刚开始也想不出来。如果是绝对值之和最小，只需要中位数就可以了；如果是使最大距离最小，只需要二分+线段覆盖统计；后来觉得每个点都有个最近距离点，沿着x轴变化，距离之和可能是个凹函数，就想到三分，太久没写，有点抠不出来。可以求导验证
三分需要注意限制次数，不然容易超时。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
using namespace std;

double eps = 1e-10;

int sgn(double x)
{
    return x < -eps ? -1 : x > eps;
}

int n;
struct Point
{
    double x, y;
    void input()
    {
        scanf("%lf%lf", &x, &y);

        y *= y;
    }

    double cal(double xx)
    {
        return sqrt(y + (xx - x) * (xx - x));
    }
}p[100010];

double cal(double x)
{
    double ans = 0;
    for(int i = 0; i < n; i++)
        ans += p[i].cal(x);

    return ans;
}
double solve()
{
    double l = 1e100, r = -1e100;
    for(int i = 0; i < n; i++)
    {
        double  x = p[i].x;
        l = min(l, x);
        r = max(r, x);
    }

    double x1 = l,x2, x3, x4 = r, ans;
    for(int i = 0; i <= 100 && sgn(x4 - x1) > 0; i++)
    {
        x2 = x1 + (x4 - x1) / 3;
        x3 = x2 + (x4 - x1) / 3;

        double f2 = cal(x2), f3 = cal(x3);
        ans = x2;
        if(sgn(f2 - f3) > 0)
            x1 = x2;
        else
            x4 = x3;
    }

    return ans;
}

int main()
{
    int T;
    scanf("%d", &T);
    for(int cas = 1; cas <=T; cas++)
    {
        scanf("%d", &n);
        for(int i = 0; i < n; i++)
            p[i].input();

        printf("Case %d: %.10lf\n", cas, solve());
    }
    return 0;
}