题目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)
样例输入
代码语言：javascript复制2
5.4mm 5.27mm 1600px
5400um 0.00527m 1600px样例输出
代码语言：javascript复制Case 1: 1639.47px
Case 2: 1639.47px代码
代码语言：javascript复制//source here
//题目1 : 焦距 by kryptosx
//字符串读入，识别长度单位，然后转换单位，计算即可。
//注意输出时小数点精确
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <vector>
#include <bitset>
#include <cmath>
#include <set>
using namespace std;
double change(char as[])
{
int len=strlen(as);
double ans=0;
if(as[len-1]=='m' && as[len-2]=='m') //mm
{
as[len-2]=' ';
sscanf(as,"%lf",&ans);
}
else if(as[len-1]=='m' && as[len-2]=='n') //nm
{
as[len-2]=' ';
sscanf(as,"%lf",&ans);
ans*=0.000001;
}
else if(as[len-1]=='m' && as[len-2]=='u') //um
{
as[len-2]=' ';
sscanf(as,"%lf",&ans);
ans*=0.001;
}
else if(as[len-1]=='m' && as[len-2]=='c') //cm
{
as[len-2]=' ';
sscanf(as,"%lf",&ans);
ans*=10;
}
else if(as[len-1]=='m' && as[len-2]=='d') //dm
{
as[len-2]=' ';
sscanf(as,"%lf",&ans);
ans*=100;
}
else //m
{
as[len-1]=' ';
sscanf(as,"%lf",&ans);
ans*=1000;
}
return ans;
}
int main()
{
int T;
cin>>T;
int js=0;
char as[100],bs[100];
double a,b,c,ans;
while(T--)
{
scanf("%s %s %lfpx",as,bs,&c);
a=change(as);
b=change(bs);
ans=c*a/b;
printf("Case %d: %.2lfpxn", js,ans);
}
return 0;
}题目2 : 树
时间限制:4000ms 单点时限:2000ms 内存限制:256MB
描述
有一个N个节点的树，其中点1是根。初始点权值都是0。
一个节点的深度定义为其父节点的深度 1,。特别的，根节点的深度定义为1。
现在需要支持一系列以下操作：给节点u的子树中，深度在l和r之间的节点的权值（这里的深度依然从整个树的根节点开始计算），都加上一个数delta。
问完成所有操作后，各节点的权值是多少。
为了减少巨大输出带来的开销，假设完成所有操作后，各节点的权值是answer[1..N]，请你按照如下方式计算出一个Hash值（请选择合适的数据类型，注意避免溢出的情况）。最终只需要输出这个Hash值即可。
代码语言：javascript复制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
代码语言：javascript复制//source here
//题目2 : 树 by kryptosx
//直接用vector建树，dfs进行遍历解决。比较暴力的方法，没想到能过大数据。
//最后一分钟提交的，能交上真是奇迹啊。
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <vector>
#include <bitset>
#include <cmath>
#include <set>
using namespace std;
struct Node
{
int deep;
long long val;
}p[100100];
vector<int>mpt[100100];
void xdfs(int x,int deep)
{
p[x].deep=deep;
p[x].val=0;
int len=mpt[x].size();
for(int i=0;i<len;i )
{
xdfs(mpt[x][i],deep 1);
}
return;
}
void dfs(int u,int l,int r,int d)
{
if(p[u].deep>=l && p[u].deep<=r)
{
p[u].val =d;
}
int len=mpt[u].size();
for(int i=0;i<len;i )
{
dfs(mpt[u][i],l,r,d);
}
return ;
}
int main(void)
{
int T,n,x,js=0;
cin>>T;
while(T--)
{
memset(mpt,0,sizeof mpt);
memset(p,0,sizeof p);
cin>>n;
for(int i=2;i<=n;i )
{
scanf("%d",&x);
mpt[x].push_back(i);
}
int m;
cin>>m;
xdfs(1,1);
int u,l,r,d;
while(m--)
{
scanf("%d%d%d%d",&u,&l,&r,&d);
dfs(u,l,r,d);
}
long long ans=0;
long long MOD =1000000007; // 10^9 7
long long MAGIC= 12347;
for(int i=1;i<=n;i )
{
ans = (ans * MAGIC p[i].val) % MOD;
}
printf("Case %d: %lldn", js,ans);
}
return 0;
}题目3 : 活动中心
时间限制:12000ms
单点时限:6000ms
内存限制:256MB
描述
A市是一个高度规划的城市，但是科技高端发达的地方，居民们也不能忘记运动和锻炼，因此城市规划局在设计A市的时候也要考虑为居民们建造一个活动中心，方便居住在A市的居民们能随时开展运动，锻炼强健的身心。
城市规划局希望活动中心的位置满足以下条件：
- 到所有居住地的总距离最小。
- 为了方便活动中心的资源补给和其他器材的维护，活动中心必须建设在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)
样例输入
代码语言：javascript复制1
3
1 1
2 2
3 3样例输出
代码语言：javascript复制Case 1: 1.678787代码
代码语言：javascript复制//source here
//题目3 : 活动中心 by kryptosx
//一开始考虑是否需要暴力什么的，一看数据范围，肯定不可能。
//后来考虑是不是可以三分，因为感觉距离和会随着x轴坐标变化而呈现一个
//凹形曲线。所以果断弄个三分的模板啥。
//优化了一下范围，因为估计范围一定在最左和最右的点之内。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps=1e-8;
struct node
{
double x,y;
};
node p[10000010];
int T,n;
double maxm;
double play(double x);
double dis(double x);
int js=1;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
double l=100000010,r=-100000010,m,ml,mr;
for(int i=0;i<n;i )
{
scanf("%lf%lf",&p[i].x,&p[i].y);
l=min(l,p[i].x);
r=max(r,p[i].x);
}
while(fabs(l-r)>eps)
{
m=(l r)/2.0;
ml=(l m)/2.0;
mr=(m r)/2.0;
if(play(ml)>play(mr))
l=ml;
else
r=mr;
}
printf("Case %d: ",js );
printf("%.6lfn",(ml mr)/2.0);
}
return 0;
}
double dis(node a,node b)
{
double c=(a.x-b.x)*(a.x-b.x) (a.y-b.y)*(a.y-b.y);
return sqrt(c);
}
double play(double x)
{
double sum=0.0;
node a;
a.x=x;
a.y=0;
for(int i=0;i<n;i )
{
sum =dis(a,p[i]);
}
return sum;
}
