一般来说，我们采用针孔相机模型，也就是认为它用到的是小孔成像原理。
在相机坐标系下，一般来说，我们用到的单位长度，不是“米”这样的国际单位，而是相邻像素的长度。而焦距在相机坐标系中的大小，是在图像处理领域的一个非常重要的物理量。
假设我们已经根据相机参数，得到镜头的物理焦距大小(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
解题思路：
为了方便，我们可以用stringstream字符串流进行string流的读入。
我们需要用long double避免double不够位数的问题。
格式输出：
cout<<setiosflags(ios::fixed)<<setprecision(2)<<ans<<"px"<<endl;
|
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124 |
#include <set>#include <map>#include <list>#include <cmath>#include <queue>#include <stack>#include <string>#include <vector>#include <cstdio>#include <cstring>#include <complex>#include <fstream>#include <iostream>#include <algorithm>#include<iomanip>using
namespace std;typedef
long long ll;typedef
unsigned long
long ull;#define debug puts("yejinru")#define rep(i,n) for(int i=0;i<n;i++)#define rep1(i,n) for(int i=1;i<=n;i++)#define REP(i,a,b) for(int i=a;i<=b;i++)#define foreach(i,vec) for(int i=0;i<(int)vec.size();i++)#define pb push_back#define RD(n) scanf("%d",&n)#define RD2(x,y) scanf("%d%d",&x,&y)#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)#define All(vec) vec.begin(),vec.end()#define MP make_pair#define PII pair<int,int>#define PQ priority_queue#define cmax(x,y) x = max(x,y)#define cmin(x,y) x = min(x,y)#define Clear(x) memset(x,0,sizeof(x))#define lson rt<<1#define rson rt<<1|1#define SZ(x) x.size()/*#pragma comment(linker, "/STACK:1024000000,1024000000")int ssize = 256 << 20; // 256MBchar *ppp = (char*)malloc(ssize) + ssize;__asm__("movl %0, %%esp\n" :: "r"(ppp) );*/char
IN;bool
NEG;inline
void Int(int
&x){ NEG = 0; while(!isdigit(IN=getchar())) if(IN==‘-‘)NEG = 1; x = IN-‘0‘; while(isdigit(IN=getchar())) x = x*10+IN-‘0‘; if(NEG)x = -x;}inline
void LL(ll &x){ NEG = 0; while(!isdigit(IN=getchar())) if(IN==‘-‘)NEG = 1; x = IN-‘0‘; while(isdigit(IN=getchar())) x = x*10+IN-‘0‘; if(NEG)x = -x;}/******** program ********************/long
double in(string a){ int
id = 1; if( !isdigit(a[ a.size()-2 ]) ) id = 2; stringstream ccin(a.substr(0,a.size()-id)); long
double d; ccin>>d; if(id==1) d *= 1000; else{ id = a.size()-2; if(a[id]==‘d‘) d *= 100; else
if(a[id]==‘c‘) d *= 10; else
if(a[id]==‘m‘) d *= 1; else
if(a[id]==‘u‘) d *= 0.001; else d /= 1000*1000; } return
d;}int
main(){#ifndef ONLINE_JUDGE freopen("sum.in","r",stdin); //freopen("sum.out","w",stdout);#endif int
ncase,cnt = 0; RD(ncase); while(ncase--){ string a,b,c; cin>>a>>b>>c; long
double x = in(a); long
double y = in(b); stringstream dd(c.substr(0,c.size()-2)); long
double z; dd>>z; long
double ans = x/y*z; printf("Case %d: ",++cnt); cout<<setiosflags(ios::fixed)<<setprecision(2)<<ans<<"px"<<endl; } return
0;} |
有一个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
比赛时想到正解前，交了一发爆搜，最后大数据都能过，数据也够弱的，囧。
后来在比赛中想到如下思路，最后也A了。
解题思路如下：
首先遍历整棵树，记录下每个节点的高度。
对于询问(x,l,r,delta)，我们把该操作(l,r,delta)放进vector[x]中。
最后，我们遍历一遍整棵树，对于节点x，我们用差分数列、树状数组或线段树进行维护。
差分数列维护的话：
先遍历一遍vector[x]，把操作(l,r,delta)添加到深度为[l,r]的区间
foreach(i,vec[x]){ node now = vec[x][i]; int l = now.l; int r = now.r; ll val = now.val; a[l] += val; a[r+1] -= val; }
因为是dfs，所以递归到下一层时，直接累和即为当前节点的值，累和：
a[depth] += a[depth-1];
然后递归遍历x节点的子节点
消除当前节点对其他非子节点的影响，最后把加上的给减掉：
a[depth] = (a[depth]-a[depth-1]+3LL*MOD)%MOD; foreach(i,vec[x]){ node now = vec[x][i]; int l = now.l; int r = now.r; ll val = now.val; a[l] -= val; a[r+1] += val; }
最后代码如下：
|
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171 |
#include <set>#include <map>#include <list>#include <cmath>#include <queue>#include <stack>#include <string>#include <vector>#include <cstdio>#include <cstring>#include <complex>#include <fstream>#include <iostream>#include <algorithm>#include<iomanip>using
namespace std;typedef
long long ll;typedef
unsigned long
long ull;#define debug puts("yejinru")#define rep(i,n) for(int i=0;i<n;i++)#define rep1(i,n) for(int i=1;i<=n;i++)#define REP(i,a,b) for(int i=a;i<=b;i++)#define foreach(i,vec) for(int i=0;i<(int)vec.size();i++)#define pb push_back#define RD(n) scanf("%d",&n)#define RD2(x,y) scanf("%d%d",&x,&y)#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)#define All(vec) vec.begin(),vec.end()#define MP make_pair#define PII pair<int,int>#define PQ priority_queue#define cmax(x,y) x = max(x,y)#define cmin(x,y) x = min(x,y)#define Clear(x) memset(x,0,sizeof(x))#define lson rt<<1#define rson rt<<1|1#define SZ(x) x.size()/*#pragma comment(linker, "/STACK:1024000000,1024000000")int ssize = 256 << 20; // 256MBchar *ppp = (char*)malloc(ssize) + ssize;__asm__("movl %0, %%esp\n" :: "r"(ppp) );*/char
IN;bool
NEG;inline
void Int(int
&x){ NEG = 0; while(!isdigit(IN=getchar())) if(IN==‘-‘)NEG = 1; x = IN-‘0‘; while(isdigit(IN=getchar())) x = x*10+IN-‘0‘; if(NEG)x = -x;}inline
void LL(ll &x){ NEG = 0; while(!isdigit(IN=getchar())) if(IN==‘-‘)NEG = 1; x = IN-‘0‘; while(isdigit(IN=getchar())) x = x*10+IN-‘0‘; if(NEG)x = -x;}/******** program ********************/const
int MAXN = 1e5+5;struct
node{ int
l,r; ll val; node(){} node(int
_l,int
_r,ll _val){ l = _l; r = _r; val = _val; }};vector<int> adj[MAXN];vector< node > vec[MAXN];ll delta[MAXN];int
dep[MAXN];const
int MOD =1000000007; // 10^9 + 7const
int MAGIC= 12347;void
dfs_init(int
x,int d){ // 初始化每个节点的深度 dep[x] = d; foreach(i,adj[x]) dfs_init(adj[x][i],d+1);}ll a[MAXN];void
dfs(int
x,int depth){ foreach(i,vec[x]){ node now = vec[x][i]; int
l = now.l; int
r = now.r; ll val = now.val; a[l] += val; // 添加 a[r+1] -= val; } a[depth] = (a[depth]+a[depth-1]+3LL*MOD)%MOD; // 差分数列 delta[x] = a[depth]; foreach(i,adj[x]) dfs(adj[x][i],depth+1); a[depth] = (a[depth]-a[depth-1]+3LL*MOD)%MOD; foreach(i,vec[x]){ node now = vec[x][i]; int
l = now.l; int
r = now.r; ll val = now.val; a[l] -= val; // 消除对后面影响 a[r+1] += val; }}int
main(){#ifndef ONLINE_JUDGE freopen("sum.in","r",stdin); //freopen("sum.out","w",stdout);#endif int
ncase,cnt = 0; RD(ncase); while(ncase--){ printf("Case %d: ",++cnt); int
n,pa,q; RD(n); rep1(i,n){ adj[i].clear(); vec[i].clear(); } memset(delta,0,sizeof(delta)); for(int
i=2;i<=n;i++){ RD(pa); adj[pa].pb(i); } dfs_init(1,1); RD(q); int
l,r,x,d; while(q--){ RD4(x,l,r,d); vec[x].pb( node(l,r,d) ); } memset(a,0,sizeof(a)); dfs(1,1); ll ans = 0; rep1(i,n) ans = (ans*MAGIC+delta[i]+3LL*MOD)%MOD; cout<<ans<<endl; } return
0;} |
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
解题思路：
三分，跟去年编程之美这题2013編程之美 集会 三分基本一样。注意下迭代次数。
|
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 <set>#include <map>#include <cmath>#include <queue>#include <stack>#include <string>#include <vector>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include<iomanip>using
namespace std;typedef
long long ll;typedef
unsigned long
long ull;#define lx(x) (x<<1)#define rx(x) (x<<1|1)#define debug puts("here")#define rep(i,n) for(int i=0;i<n;i++)#define rep1(i,n) for(int i=1;i<=n;i++)#define REP(i,a,b) for(int i=a;i<=b;i++)#define foreach(i,vec) for(unsigned i=0;i<vec.size();i++)#define pb push_back#define RD(n) scanf("%d",&n)#define RD2(x,y) scanf("%d%d",&x,&y)#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)/******** program ********************/const
int MAXN = 1e5+5;const
int INF = 1e8;struct
node{ double
x,y;}p[MAXN];int
n;long
double dis(long
double x,long
double y){ return
sqrt( x*x+y*y );}long
double cal(long
double now){ long
double tmp = 0; rep(i,n) tmp += dis(p[i].x-now,p[i].y); return
tmp;}int
main(){#ifndef ONLINE_JUDGE freopen("sum.in","r",stdin); //freopen("sum.out","w",stdout);#endif int
ncase; RD(ncase); rep1(Ncase,ncase){ printf("Case %d: ",Ncase); RD(n); long
double L = INF,R = -INF; rep(i,n){ scanf("%lf%lf",&p[i].x,&p[i].y); L = min(L,(long
double)p[i].x); R = max(R,(long
double)p[i].x); } long
double l = 0,r = 1; long
double px1,px2; rep(step,50){ long
double m1 = (2*l+r)/3; long
double m2 = (l+2*r)/3; px1 = L*(1-m1)+R*m1; px2 = L*(1-m2)+R*m2; long
double tmp = cal(px1); long
double ret = cal(px2); if(tmp>ret) l = m1; else r = m2; } if(px1<0&&fabs(px1)<1e-9) // 判斷是否會出現-0.000000 px1 *= -1.0; cout<<setiosflags(ios::fixed)<<setprecision(8)<<px1<<endl; } return
0;} |
原文：http://www.cnblogs.com/yejinru/p/3675218.html