首页 > 其他分享 >洛谷p1002题解

洛谷p1002题解

时间:2024-04-04 17:32:50浏览次数:28  
标签:le 洛谷 int 题解 p1002 abs && 20 pan

[NOIP2002 普及组] 过河卒

题目描述

棋盘上 A A A 点有一个过河卒,需要走到目标 B B B 点。卒行走的规则:可以向下、或者向右。同时在棋盘上 C C C 点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示, A A A 点 ( 0 , 0 ) (0, 0) (0,0)、 B B B 点 ( n , m ) (n, m) (n,m),同样马的位置坐标是需要给出的。

现在要求你计算出卒从 A A A 点能够到达 B B B 点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。

输入格式

一行四个正整数,分别表示 B B B 点坐标和马的坐标。

输出格式

一个整数,表示所有的路径条数。

样例 #1

样例输入 #1
6 6 3 3
样例输出 #1
6

提示

对于 100 % 100 \% 100% 的数据, 1 ≤ n , m ≤ 20 1 \le n, m \le 20 1≤n,m≤20, 0 ≤ 0 \le 0≤ 马的坐标 ≤ 20 \le 20 ≤20。

【题目来源】

NOIP 2002 普及组第四题

题解

这道题在排列组合的题目中很常见,我们用数学思想即可。
∫ ( i , j ) = ∫ ( i − 1 , j ) + ∫ ( i , j − 1 )   . \int(i,j) = \int(i-1,j)+\int(i,j-1) \,. ∫(i,j)=∫(i−1,j)+∫(i,j−1).
所以,我们就可以写代码了

#include<iostream>
#include<math.h> 
#include<bits/stdc++.h>
using namespace std;//by 爱玩游戏的jason
long long pan[40][40];
int main(){
	int n,m,a,b;
	cin>>n>>m>>a>>b;//n,a为行,m,b为列 
	n++;
	m++;
	memset(pan,0,sizeof(pan));
	pan[0][0]=1;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if((abs(i-a)==2&&abs(j-b)==1)||(abs(i-a)==1&&abs(j-b)==2)||(i==a&&j==b)){//超出地图范围的情况
				;
			}
			else{//分类讨论
				if((i==0&&j==0)){
					;//已定义
				}
				else if(i==0){
					pan[i][j]=pan[0][j-1];
				}
				else if(j==0){
					pan[i][j]=pan[i-1][0];
				}
				else{
					pan[i][j]=pan[i][j-1]+pan[i-1][j];
				}
			}
		}
	}
	cout<<pan[n-1][m-1];//结果
	return 0;//水题
}

标签:le,洛谷,int,题解,p1002,abs,&&,20,pan
From: https://blog.csdn.net/2401_84097311/article/details/137352407

相关文章

  • CF371E Subway Innovation 题解
    题目链接:CF或者洛谷对于绝对值的几何意义来说,这题是在直线上的两点间的距离,为了总的距离和最下,首先最好让它们两两之间最好都紧挨着。由于询问的是\((i,j)\)不重不漏的对有关,即\((i<j)\+\(i>j)\+\(i=j)=all(i,j)\),又因为,\((i,j)\)的贡献和\((j,i)\)相同且重复,所以我......
  • 洛谷p1002(过河卒)
    题目描述 如图,A点有一个过河卒,需要走到目标B点。卒行走规则:可以向下、或者向右。同时在棋盘上的任一点有一个对方的马(如上图的C点),该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如下图C点上的马可以控制9个点(图中的P1,P2…P8和C)。卒不能通过对方马的控......
  • [ABC223F] Parenthesis Checking 题解
    [ABC223F]ParenthesisChecking题解思路解析在开始之前,首先我们需要知道合法括号序列的判断方法。我们可以给每个括号打上权值,设左括号权值为\(1\),右括号权值为\(-1\),这样一个\(\texttt{(()())}\)括号串用数字存下就是\(1,1,-1,1,-1,-1\),这时我们再给序列计算一下前缀和......
  • 洛谷 P1004 [NOIP2000 提高组] 方格取数
    题意:n*n的方格,从左上角到右下角两次。每一次经过的路径中,如果有数字,数字都会变成0并计数。求两次路径的最大计数。思路:线性dp,从左上角到右下角步数固定为2*n-2步。初始时0步dp[0][1][1]=grid[1][1],知道了x1和x2可以确定对应的y,可以直接进行状态转移。可以增加剪枝:x<=m......
  • [ABC211F] Rectilinear Polygons 题解
    [ABC211F]RectilinearPolygons题解思路什么的上一篇题解已经写的非常明白了,这里只是提供一个补充&另一个实现的方法。思路解析先说结论:扫描线。顾名思义,扫描线的本质就是用一条线沿着\(x\)或\(y\)轴扫过去,每碰到一条边就记录一下加边后是面积是增加还是减少,然后用树状......
  • [ABC211D] Number of Shortest paths 题解
    [ABC211D]NumberofShortestpaths题解思路解析题目其实说得很明白了,就是最短路计数。我们可以用一个\(s_i\)表示从起点到\(i\)的最短路计数,然后进行bfs,由于边权为\(1\),所以可以使用bfs求最短路。如果\(u\tov\)是\(v\)的最短路的其中一段,就把\(s_u\tos_v\)......
  • [ABC221D] Online games 题解
    [ABC221D]Onlinegames题解思路解析可以发现题目就是单纯区间加和查询每一个值有多少次出现。首先看到区间修改加结束时查询可以想到差分,但是通过\(A_i\le10^9\)发现值域很大没法直接根据值差分。于是想到离散化,将每个点离散下来,统计每两个离散的时间之间在线的人乘上时间......
  • [ABC223E] Placing Rectangles 题解
    [ABC223E]PlacingRectangles题解思路解析根据题目可知,其实三个长方形无非只有以下两种摆放方式。若大长方形长为\(y\),宽为\(x\),则我们对于第一种情况就固定住宽,判断能否使长度小于等于长;对于第二种情况同样固定住宽,此时A长方形右边空间的长就确定了,就只需要判断B,C......
  • [ABC221E] LEQ 题解
    [ABC221E]LEQ题解思路解析很有思维量的一道题。首先根据题目要求发现,新求的子序列只跟子序列的头尾有关,而在确定头尾之后中间的元素选或不选没有任何关系。也就是确定新子序列的头尾下标分别为\(i,j\),那么以当前头尾的可行子序列个数就是\(2^{j-i-1}=2^j\div2^{i+1}\)种......
  • 洛谷 P1196 [NOI2002] 银河英雄传说
    题意:30000列军队,每列初始有1个。编号从1~30000.每次操作有两种,将现在第i列所在的列合并到第j列所在列的末尾。或者查询第i列举例第j列的距离。思路:带权并查集。合并时将第i列头节点接到第j列头节点上。然后直接查询dist取绝对值相减就好。总结:一开始没看清题,以为要把从i列从当......