Codeforces Round 271 Div.2 解題報告：A-D 四題完整分析與代碼

Codeforces Round 271 Div.2 解題報告：A-D 四題完整分析

A. Keyboard：鍵盤鄰鍵映射模擬

給定鍵盤行 "qwertyuiopasdfghjkl;zxcvbnm,./"，輸入 L/R 表示向左/右移一位，輸出映射後字符串。O(n) 直接查找替換。

B. Worms：前綴和 + 二分查找

n 堆蠕蟲，第 i 堆有 a[i] 條，編號連續。m 個查詢，給標號 q，輸出屬於哪堆。前綴和數組 + lower_bound 二分，O((n+m) log n)。

C. Captain Marmot：暴力枚舉旋轉判斷正方形

4 個點，每個點可繞中心旋轉 0/90/180/270 度（4⁴=256 種）。判斷 4 點是否成正方形：計算 6 條邊長（4 邊+2 對角線），排序，前 4 相等（邊），後 2 相等（對角線），且對角線² = 2×邊²。找最小總旋轉次數。

D. Flowers：DP + 前綴和（詳見專文）

dp[n]=dp[n-1]+dp[n-k]，前綴和答區間查詢。O(MAXN + t)。

C 題正方形判斷核心代碼

bool isSquare(node a,node b,node c,node d){
    vector dist;
    // 計算6條距離平方
    dist.push_back(dis2(a,b)); dist.push_back(dis2(a,c)); dist.push_back(dis2(a,d));
    dist.push_back(dis2(b,c)); dist.push_back(dis2(b,d)); dist.push_back(dis2(c,d));
    sort(dist.begin(),dist.end());
    return dist[0]>0 && dist[0]==dist[1] && dist[1]==dist[2] && dist[2]==dist[3] 
        && dist[4]==dist[5] && dist[4]==2*dist[0];
}