勵志用少的代碼做高效表達

---

Problem describe

Today, Wet Shark is given n bishops on a 1000 by 1000 grid. Both rows and columns of the grid are numbered from 1 to 1000. Rows are numbered from top to bottom, while columns are numbered from left to right.

Wet Shark thinks that two bishops attack each other if they share the same diagonal. Note, that this is the only criteria, so two bishops may attack each other (according to Wet Shark) even if there is another bishop located between them. Now Wet Shark wants to count the number of pairs of bishops that attack each other.

Input

The first line of the input contains n (1?≤?n?≤?200?000) — the number of bishops.
Each of next n lines contains two space separated integers xi and yi (1?≤?xi,?yi?≤?1000) — the number of row and the number of column where i-th bishop is positioned. It’s guaranteed that no two bishops share the same position.

Output

Output one integer — the number of pairs of bishops which attack each other.

---

題意分析

題意：給定一個1000*1000的棋盤，主教棋子的數量n。 規則是若某一主教與其他主教出現在同一條對角線上， 就會互相攻擊。 問互相攻擊的主教棋子的對數。

首先思考：
若同一主對角線上有n個元素，則在這條對角線上互相攻擊棋子的對數為：n*(n-1)/2。（第一個棋子與其余n-1個互相攻擊，第二個棋子與其余n-2個互相攻擊…即：n-1+n-2+n-3+…+1最后使用等差數列求和公式）

因此問題轉化為求出棋盤中每條對角線上的棋子個數， 分別代入公式，將結果累加即可。

很容易推導出規則：同一主對角線的數相減相等； 同一副對角線的數相加相等；

注意：第一次嘗試時，我首先想到利用map容器的歸納性質做映射求解， 但其實直接用數組解即可（貌似大多數的map映射都可簡化為數組）。

---

#include<bits/stdc++.h> using namespace std; int main() {ios::sync_with_stdio(false);int n, a[4010]; //采用同一數組的不同區間表達兩組數cin>>n; memset(a,0,sizeof(a));for(int i=0;i<n;i++) {int x, y;cin>>x>>y;a[x+y]++;a[x-y+3000]++;} long long sum=0;for(int i = 0; i < 4000; i++) if(a[i]>1) sum+=(a[i]*(a[i]-1)/2);cout << sum << endl; return 0; }

---

天空不會永遠陰暗，當烏云退盡的時候，藍天上燦爛的陽光就會照亮大地。青草照樣會鮮綠無比，花朵仍然會蓬勃開放。?????????????????——《平凡的世界》

總結

以上是生活随笔為你收集整理的18行代码AC_Wet Shark and Bishops CodeForces - 621B(数学推导+映射)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。