某個下雨天,你盯著湖面,發現水面上因為下雨而有了一圈圈的漣漪。不知道為什麼的, 你突然想知道這片水面上共有幾個不同的產生了建設性干涉的位置。
講的稍微白話一點,假設整個水面是個無限寬廣的二維平面,而有個雨滴在時間 0 落在 (x, y) 的位置,則在時間 t 的時候,這個雨滴所產生的圓就是以 (x, y) 為圓心,半徑為 t 的圓。 而產生了建設性干涉的位置就是多於一個圓經過的點。
現在,給定了每個雨滴落在水面上的位置 (xi , yi),並假定每個雨滴都是在時間 0 碰到水面。在這無限可能的所有時間點當中,總會有個時間點 T 使得這個時間點的相異的產生建設性干涉的位置的數量是最多的,你想要知道這個最多的數量會是多少。 然而,因為誰也沒辦法預測雨滴的落點會在哪裡,所以我們會利用以下的 C 程式碼來產生每個雨滴的 xi , yi:
unsigned s = initSeed;
int left[30] = { 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1 };
int right[30] = { 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1 };
int gen(){
unsigned t = (s & 13) ^ (s << 13) ^ (s >> 16) ^ (s << 14) ^ (s >> 17) ^ (s << 3) ^ (s >> 6);
unsigned r = (t & 880301) ^ (t >> 11) ^ (t << 11) ^ (t >> 12) ^ (t << 12);
unsigned u = (t & 110029) ^ (t << 21) ^ (t << 14) ^ (t >> 11) ^ (t >> 9);
unsigned h = (s ^ t ^ r ^ u);
for (int i = 0; i < 30; i++) if (left[i]) h ^= (h << i);
for (int i = 0; i < 30; i++) if (right[i]) h ^= (h >> i);
return s = h % 1000000001;
}
int x[50], y[50];
void generateTestcase(int n) {
for (int i = 0; i < n; i++) {
x[i] = gen() ^ i;
y[i] = gen() ^ gen() ^ i;
}
}
陣列 x 跟 y 中分別存的就是每個點的 xi 跟 yi。
輸入共有一行,包含兩個整數,分別是 n 及 initSeed,代表雨滴的數量以及給以上程式用的初始種子。
1. 1 ≤ n ≤ 50
2. 0 ≤ initSeed ≤ 109
3. 保證輸入中不會有超過一個雨滴落在同一個位置
輸出共有一行,包含一個整數,為最大的產生建設性干涉的位置的數量。
#test input 1: 1 1 #test input 2: 2 998244353
#test output 1: 0 #test output 2: 2
greedy, math (CF 800)
對於凃某辰而言 (CF 3500)
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |