首页 > 代码库 > 2014-04-19编程之美初赛题目及答案解析
2014-04-19编程之美初赛题目及答案解析
第一题:
描写叙述
一般来说,我们採用针孔相机模型,也就是觉得它用到的是小孔成像原理。
在相机坐标系下,一般来说,我们用到的单位长度,不是“米”这种国际单位,而是相邻像素的长度。而焦距在相机坐标系中的大小,是在图像处理领域的一个很重要的物理量。
如果我们已经依据相机參数,得到镜头的物理焦距大小(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)
解析:
感觉这个题目可能须要用java的BigDecimal高精度计算,只是,看到20分的基础上,楼主果断没实用BigDecimal
代码:
//source here #include <iostream> #include <string> #include <stdio.h> using namespace std; int main(){ int icase; cin>>icase; double x,y,z; string a,b,c; for(int i= 1; i<= icase; ++i){ cin>>x>>a>>y>>b>>z>>c; if(a=="m"){ x*=1000; }else if(a=="dm"){ x*=100; }else if(a=="cm"){ x*=10; }else if(a=="um"){ x/=1000; }else if(a=="nm"){ x/=1000000; } if(b=="m"){ y*=1000; }else if(b=="dm"){ y*=100; }else if(b=="cm"){ y*=10; }else if(b=="um"){ y/=1000; }else if(b=="nm"){ y/=1000000; } double tt= x*z/y; printf("Case %d: %.2lfpx\n",i, tt); } }
第二题:
描写叙述
有一个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
果断地先依据根,进行广度遍历,求出层次,然后改动值的时候也是层次遍历,楼主当时没想过其他什么算法,感觉这样可能 AC,就写了例如以下代码:
//source here #include <iostream> #include <vector> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <queue> using namespace std; const int NODE_COUNT= 100001; vector<int> child[NODE_COUNT]; long long val[NODE_COUNT]; long long parent[NODE_COUNT]; int level[NODE_COUNT]; int node; long long MOD =1000000007; // 10^9 + 7 long long MAGIC= 12347; void BuildLevel(); void Change(int u,int r,int l, int delta); long long hash(); int main(){ int icase; cin>>icase; int c; for(int i= 1; i<= icase; ++i){ scanf("%d",&node); memset(val,0,NODE_COUNT*sizeof(int)); for(int l= 0; l< node; ++l){//empty child child[l].clear(); } level[0]= 1; for(int l= 1; l< node; ++l){ scanf("%d",&c); --c; parent[l]=c; child[c].push_back(l); } BuildLevel(); int r,l,delta,u; int x; scanf("%d",&x); while(x--){ cin>>u>>l>>r>>delta; --u; Change(u,l,r,delta); } cout<<"Case "<<i<<": "<<::hash()<<endl; } } void Change(int u,int l,int r, int delta){ queue<int> q; q.push(u); int now; while(!q.empty()){ now= q.front(); vector<int>& lhs= child[now]; q.pop(); if(level[now]>= l && level[now]<= r){//[l,r] val[now]+=delta; }else if(level[now]>r){ continue; } for(int i= 0; i< lhs.size();++i){ q.push(lhs[i]); } } } long long hash(){ long long s= 0; for(int i= 0; i< node; ++i){ s= (s*MAGIC+val[i])%MOD; } return s; } void BuildLevel(){ queue<int> q; level[0]= 1; q.push(0); int now; while(!q.empty()){ now= q.front(); q.pop(); vector<int>& lhs= child[now]; for(int i= 0; i< lhs.size(); ++i){ level[lhs[i]]= level[now]+1; q.push(lhs[i]); } } }
第三题:
描写叙述
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
果断地,求导数,导数为0的值就是我们要求的,我们会发现导数是单调的(导数的导数大于0),然后果断二分,代码例如以下:
//source here #include <iostream> #include <vector> #include <stdio.h> #include <utility> #include <algorithm> #include <string> #include <math.h> using namespace std; vector<pair<double,double> > point; const double EPSI= 0.000000001; bool operator < (const pair<double,double>& lhs, const pair<double,double>& rhs){ return lhs.first< rhs.first; } bool Check(double x); int main(){ int icase; cin>>icase; pair<double,double> pt; int ic; double l,h,mid; for(int i= 1; i<= icase; ++i){ cin>>ic; point.clear(); while(ic--){ cin>>pt.first>>pt.second; point.push_back(pt); } sort(point.begin(),point.end()); l= point[0].first; h= point[point.size()-1].first; while(fabs(l-h)>= EPSI){ mid= (l+h)/2; if(Check(mid)){//>=0 h= mid; }else{ l= mid; } } printf("Case %d: %.6lf\n",i,mid); } } bool Check(double x){ double sum= 0; int len= point.size(); double a,b; for(int i= 0; i< len; ++i){ a= x-point[i].first; b= sqrt(a*a+(point[i].second*point[i].second)); sum+=a/b; } return sum>= 0; }