CF-1358C Celex Update 题解

题目大意

如图表格，左上角坐标为（1,1），给你两个点的坐标，你只能往右走或者往下走，求不同路径和的路径数量。

解题思路

刚开始想了好久了，想到了一个思路，能保证是正解，但是不够快，只能爆搜。

以最上面的那一条路径为基础，每往下走就算是加一，向右走就保持不动，每个点的权值就靠这个确定。

（其实和正解很相似了。。只是根本没想到。。

这样可以靠爆搜的代码来跑出规律，答案就是$dx* dy+1$。

但是正解应该是以最上面那一条路为基础，每把右上角一个点掰到左下角就相当于是加了一，保证了每条路径的和不同，这样获得的路径数就是除去第一条路左下角的格子数量，即$dx\times dy$。

再加上原本的路径便是正确答案。

完整代码

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

int main() {
	int t; cin >> t;
	while (t--) {
		int x1, x2, y1, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		ll dx = abs(x1 - x2), dy = abs(y1 - y2);
		ll ans = dx * dy + 1;
		cout << ans << endl;
	}
}