ABC160 D - Line++

题意

输入N,X,Y。 $i (1 \leq N \leq 2 e 3)$
给你一个由N个结点组成的图，连接第 $i$ 和第 $i + 1$ 个点，一共构成了N-1条边。
连接X，Y，输出两节点间最短距离长度为 $i (1 \leq i \leq N - 1)$ 的边一共有多少条。

思路

再一次强调读题要注意数据范围，因为数据范围会暗示算法的复杂度大概在什么程度，然后再思考相关算法。
我比赛的时候没注意N的范围，因而在思考最优解法，当然到最后也没思考出来。
这道题我们先看一眼N最大2e3，显然可以 $O (N^{2})$ 去做，即遍历两个不同的点，记录他们的路径长度的对应个数+1。
X，Y的连接使得可以经由X或Y为中转站。
故两个点的最小距离为 $m i n (a b s (i - j), m i n (a b s (x - i) + a b s (y - j) + 1, a b s (y - i) + a b s (x - j) + 1))$
这一场我第一次比赛中做出ABC的E，不过却没能注意数据范围而错过了D，而且做的很慢。
快一点，再快一点，罚时再少一点！

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 2e3 + 5;

int n,x,y,a[maxn];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>x>>y;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			a[min(abs(i-j),min(abs(x-i)+abs(y-j)+1,abs(y-i)+abs(x-j)+1))]++;
		}
	}
	for(int i=1;i<n;i++){
		cout<<a[i]<<'\n';
	}
	return 0;
}

ABC160D

ABC160 D - Line++

题意

思路