专栏文章

题解：UVA13214 The Robot's Grid

BBobi2014
UVA13214题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minm60uh
此快照首次捕获于
2025/12/02 04:40
3 个月前
此快照最后确认于
2025/12/02 04:40
3 个月前
查看原文
这是一道可癌的数学题。

前置知识

思路

直接暴击会超时，考虑使用数学知识，我们发现它到达终点需要水平移动 c−1c - 1 次，竖直移动 r−1r - 1 次，一共需要移动 c+r−2c + r - 2 次，那么我们可以考虑使用组合数解决问题，我们需要预处理组合数，众所周知 C[i][j] = C[i - 1][j - 1] + C[i - 1][j]，特判 i=0i = 0 和 j=0j = 0 的情况，每次查询只需要输出 C[c + r - 2][c - 1] 即可，时间复杂度 O(q)O(q)。

Code

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int Q,n,m,C[51][51];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	for(int i = 0;i <= 50;i ++){
		C[i][0] = 1;
		for(int j = 1;j <= i;j ++){
			C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
		}
	}
	cin >> Q;
	while(Q --){
		cin >> n >> m;
		cout << C[n + m - 2][n - 1] << '\n';
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...