題目1 : 焦距

時間限制:2000ms 單點時限:1000ms 內(nèi)存限制:256MB

描述

一般來說，我們采用針孔相機模型，也就是認為它用到的是小孔成像原理。

在相機坐標系下，一般來說，我們用到的單位長度，不是“米”這樣的國際單位，而是相鄰像素的長度。而焦距在相機坐標系中的大小，是在圖像處理領(lǐng)域的一個非常重要的物理量。

假設(shè)我們已經(jīng)根據(jù)相機參數(shù)，得到鏡頭的物理焦距大小(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

現(xiàn)在，請您寫一段通用的程序，來求解焦距在相機坐標系中的大小。

輸入

多組測試數(shù)據(jù)。首先是一個正整數(shù)T，表示測試數(shù)據(jù)的組數(shù)。

每組測試數(shù)據(jù)占一行，分別為

鏡頭的物理焦距大小(focal length on earth)

相機膠片的寬度(CCD width on earth)

照片的橫向分辨率大小(image width in pixels)，單位為px。

之間用一個空格分隔。

輸出

每組數(shù)據(jù)輸出一行，格式為“Case X: Ypx”。 X為測試數(shù)據(jù)的編號，從1開始；Y為焦距在相機坐標系中的大小(focallength in pixels)，保留小數(shù)點后2位有效數(shù)字，四舍五入取整。

數(shù)據(jù)范圍

對于小數(shù)據(jù)：focal length on earth和CCD width on earth單位都是毫米(mm)

對于大數(shù)據(jù)：長度單位還可能為米(m), 分米(dm), 厘米(cm), 毫米(mm), 微米(um)，納米(nm)

樣例輸入

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

樣例輸出

Case 1: 1639.47px Case 2: 1639.47px

題目2 : 樹

時間限制:4000ms 單點時限:2000ms 內(nèi)存限制:256MB

描述

有一個N個節(jié)點的樹，其中點1是根。初始點權(quán)值都是0。

一個節(jié)點的深度定義為其父節(jié)點的深度+1,。特別的，根節(jié)點的深度定義為1。

現(xiàn)在需要支持一系列以下操作：給節(jié)點u的子樹中，深度在l和r之間的節(jié)點的權(quán)值（這里的深度依然從整個樹的根節(jié)點開始計算），都加上一個數(shù)delta。

問完成所有操作后，各節(jié)點的權(quán)值是多少。

為了減少巨大輸出帶來的開銷，假設(shè)完成所有操作后，各節(jié)點的權(quán)值是answer[1..N]，請你按照如下方式計算出一個Hash值（請選擇合適的數(shù)據(jù)類型，注意避免溢出的情況）。最終只需要輸出這個Hash值即可。

MOD =1000000007; // 10^9 + 7

MAGIC= 12347;

Hash =0;

For i= 1 to N do

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

EndFor

輸入

第一行一個整數(shù)T (1 ≤ T ≤ 5)，表示數(shù)據(jù)組數(shù)。

接下來是T組輸入數(shù)據(jù)，測試數(shù)據(jù)之間沒有空行。

每組數(shù)據(jù)格式如下：

第一行一個整數(shù)N (1 ≤ N ≤ 105)，表示樹的節(jié)點總數(shù)。

接下來N - 1行，每行1個數(shù)，a (1 ≤ a ≤ N)，依次表示2..N節(jié)點的父親節(jié)點的編號。

接下來一個整數(shù)Q(1 ≤ Q ≤ 105)，表示操作總數(shù)。

接下來Q行，每行4個整數(shù)，u, l, r, delta (1 ≤ u ≤ N, 1 ≤ l ≤ r ≤ N, -109?≤ delta ≤ 109)，代表一次操作。

輸出

對每組數(shù)據(jù)，先輸出一行“Case x:?”，x表示是第幾組數(shù)據(jù)，然后接這組數(shù)據(jù)答案的Hash值。

數(shù)據(jù)范圍

小數(shù)據(jù)：1 ≤ N, Q ≤ 1000

大數(shù)據(jù)：1 ≤ N, Q ≤ 105

樣例解釋

點1的子樹中有1,2,3三個節(jié)點。其中深度在2-3之間的是點2和點3。

點2的子樹中有2,3兩個節(jié)點。其中沒有深度為1的節(jié)點。

所以，執(zhí)行完所有操作之后，只有2,3兩點的權(quán)值增加了1。即答案是0 1 1。再計算對應(yīng)的Hash值即可。

樣例輸入

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

樣例輸出

Case 1: 12348

題目3 : 活動中心

時間限制:12000ms 單點時限:6000ms 內(nèi)存限制:256MB

描述

A市是一個高度規(guī)劃的城市，但是科技高端發(fā)達的地方，居民們也不能忘記運動和鍛煉，因此城市規(guī)劃局在設(shè)計A市的時候也要考慮為居民們建造一個活動中心，方便居住在A市的居民們能隨時開展運動，鍛煉強健的身心。

城市規(guī)劃局希望活動中心的位置滿足以下條件：

1. 到所有居住地的總距離最小。

2. 為了方便活動中心的資源補給和其他器材的維護，活動中心必須建設(shè)在A市的主干道上。

為了簡化問題，我們將A市擺在二維平面上，城市的主干道看作直角坐標系平的X軸，城市中所有的居住地都可以看成二維平面上的一個點。

現(xiàn)在，A市的城市規(guī)劃局希望知道活動中心建在哪兒最好。

輸入

第一行包括一個數(shù)T，表示數(shù)據(jù)的組數(shù)。

接下來包含T組數(shù)據(jù)，每組數(shù)據(jù)的第一行包括一個整數(shù)N，表示A市共有N處居住地

接下來N行表示每處居住地的坐標。

輸出

對于每組數(shù)據(jù)，輸出一行“Case X: Y”，其中X表示每組數(shù)據(jù)的編號(從1開始)，Y表示活動中心的最優(yōu)建造位置。我們建議你的輸出保留Y到小數(shù)點后6位或以上，任何與標準答案的絕對誤差或者相對誤差在10-6以內(nèi)的結(jié)果都將被視為正確。

數(shù)據(jù)范圍

小數(shù)據(jù)：1 ≤ T ≤ 1000, 1 ≤ N ≤ 10

大數(shù)據(jù)：1 ≤ T ≤ 10, 1 ≤ N ≤ 105

對于所有數(shù)據(jù)，坐標值都是整數(shù)且絕對值都不超過106

樣例解釋

樣例1：活動中心的最優(yōu)建造位置為(1.678787, 0)

樣例輸入

1 3 1 1 2 2 3 3

樣例輸出

Case 1: 1.678787

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的2014编程之美初赛第一场的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。