首页 > 编程语言 >红温刷算法题(C/C++)

红温刷算法题(C/C++)

时间:2024-08-16 14:23:32浏览次数:15  
标签:格子 vis int 红温 C++ 条数 算法 坐标 地毯

此文章主要是给刷算法题的小萌新写的题解,博主每日刷题,把所刷的题以及所获都会发到博客里面,文章有详解思路,并且有对应的AC代码,希望我的博客对算法小萌新有所帮助。感谢CSDN平台给我这个机会,我会努力创作,创作高质量文章。 

P1002 [NOIP2002 普及组] 过河卒

题目描述

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

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

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

输入格式

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

输出格式

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

输入 

6 6 3 3

输出 

6

说明/提示

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

【题目来源】

NOIP 2002 普及组第四题


解题思路:

这道题初始位置是从 0 开始的,这样不是很利于我们解题,所以不如暂且把这题里涉及的坐标统统 +1,那么初始位置就从 (0,0) 变成了 (1,1)。

先考虑如果没有任何马的限制,卒子可以随便向右向下走,那么可以想到,一个卒子只能从 当前格子的左侧格子 和 当前格子的上方格子 上走到当前格子。那么假设从 (1,1) 走到 当前格子的左侧格子 的路径条数是 x,从 (1,1) 走到 当前格子的上方格子 的路径条数是 y,那么从 (1,1) 走到当前格子的路径条数就应该是 x+y。

其实我们已经得到了一个动态规划的转移方程,设 f(i,j) 表示从 (1,1) 格子走到当前格子的路径条数,那么根据上一段得到的结论,可以得到:

f(i,j)=f(i−1,j)+f(i,j−1)

(i,j) 是当前格子,那么 (i−1,j) 就是 当前格子的上方格子,(i,j−1) 就是 当前格子的左侧格子。我们只需要从小到大依次枚举 i 和 j 就能获得所有点的答案,可以想到,在这道题里我们要求的答案就是 f(n,m)(因为 B 点的坐标是(n,m))。

当然如果只是按照这个公式推肯定不行,因为 f 的初始数值都是 0,再怎么推也都是 0,我们要让 f(1,1) 能根据上面得到的式子推出答案是 1,这样才能有有意义的结果。根据 f(1,1)=f(0,1)+f(1,0),我们只需要让f(1,0)=1 或者f(0,1)=1 即可。

接下来考虑一下加入了 马 这道题该怎么做,假设 (x,y) 这个点被马拦住了,其实就是说这个点不能被卒子走到,那当我们枚举到这个点的时候,发现他被马拦住了,那就直接跳过这个点,让 f(x,y)=0 就行了。

具体写代码的时候我们注意到在判断一个点有没有被马拦住时,会用到 (i−2,j−1) 和 (i−1,j−2) 这两个位置,那如果不把所有的点的坐标都加上 2 (前面分析的时候只把所有的坐标加上 1),就会因为数组越界而 WA 掉一个点。

答案可能很大,所以记得开 long long


AC代码:

#include<iostream>
using namespace std;
const int N=30;
int n,m;
int mx,my;
bool vis[N][N];
long long dp[N][N];
int dx[]={1,1,-1,-1,2,2,-2,-2};
int dy[]={2,-2,2,-2,1,-1,1,-1};
void fun(int x,int y){
	vis[x][y]=true;
	for(int i=0;i<8;i++){
		int bx=x+dx[i];
		int by=y+dy[i];
		vis[bx][by]=true;
	}
}
int main(){
	cin>>n>>m>>mx>>my;
	fun(mx,my);
	dp[0][0]=1;
	for(int i=1;i<=max(n,m);i++){
		if(!vis[i][0]){
			dp[i][0]=dp[i-1][0];
		}
		if(!vis[0][i]){
			dp[0][i]=dp[0][i-1];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(!vis[i][j]){
				dp[i][j]=dp[i-1][j]+dp[i][j-1];
			}
		}
	}
	cout<<dp[n][m]<<endl;
	return 0;
}

P1003 [NOIP2011 提高组] 铺地毯

题目描述

为了准备一个独特的颁奖典礼,组织者在会场的一片矩形区域(可看做是平面直角坐标系的第一象限)铺上一些矩形地毯。一共有 n 张地毯,编号从 1 到 n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设,后铺的地毯覆盖在前面已经铺好的地毯之上。

地毯铺设完成后,组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意:在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

输入格式

输入共 n+2 行。

第一行,一个整数 n,表示总共有 n 张地毯。

接下来的 n 行中,第 i+1 行表示编号 i 的地毯的信息,包含四个整数 a,b,g,k,每两个整数之间用一个空格隔开,分别表示铺设地毯的左下角的坐标 (a,b) 以及地毯在 x 轴和 y 轴方向的长度。

第 n+2 行包含两个整数 x 和 y,表示所求的地面的点的坐标 (x,y)。

输出格式

输出共 1 行,一个整数,表示所求的地毯的编号;若此处没有被地毯覆盖则输出 -1

说明/提示

【样例解释 1】

如下图,1 号地毯用实线表示,2 号地毯用虚线表示,3 号用双实线表示,覆盖点 (2,2) 的最上面一张地毯是 3 号地毯。

【数据范围】

对于 30% 的数据,有 n≤2。
对于 50% 的数据,0≤a,b,g,k≤100。
对于 100% 的数据,有 0≤n≤104,0≤a,b,g,k≤105。

noip2011 提高组 day1 第 1 题。


解题思路:

我们先把每个地毯都存起来,直接考虑筛一遍所有毯子,每次判断有没有覆盖这个点,若覆盖就更新答案即可。


AC代码:

#include<iostream>
using namespace std;
int n,x,y;
const int N=1e4+5;
int vis[N][N];
int a[N],b[N],g[N],k[N];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i]>>g[i]>>k[i];
	}
	int x,y;
	cin>>x>>y;
	for(int i=1;i<=n;i++){
		if(a[i]<=x&&b[i]<=y&&(a[i]+g[i])>=x&&(b[i]+k[i])>=y){
			vis[x][y]=i;
		}
	}
	if(vis[x][y]==0){
		cout<<-1<<endl;
	}else{
		cout<<vis[x][y]<<endl;
	}
	return 0;
}

标签:格子,vis,int,红温,C++,条数,算法,坐标,地毯
From: https://blog.csdn.net/2401_86771711/article/details/141220840

相关文章

  • C++基础资料二
    C++等级考试资料二考试内容:选择题:进制转换、冒泡与选择排序、二分思想、链表与顺序表、二维数组初始化、函数阅读编程题:字符串操作、质数判断、排序、最小公倍数、最大公约数、百钱百鸡问题 考试资料:进制转换公式1.十进制转二进制整数部分:不断将十进制数除以2,记录余......
  • 《机器学习》 KNN算法、数据可视化 No.1
    一、了解机器学习1、什么是机器学习        机器学习是一种人工智能(AI)的分支,旨在让计算机通过数据自动学习和改进。机器学习算法被设计用于从数据中提取模式和规律,然后利用这些模式和规律来做出预测或做出决策,而无需明确的程序指令。        机器学习的基本......
  • 看demo学算法之 循环神经网络(RNN)
    今天我们来聊聊神经网络中的“记忆大师”——循环神经网络(RNN)。想象一下,你正在看电影,每一帧都连贯着前一帧的故事情节。RNN就像是这样一位观众,它能记住之前看到的内容,帮助理解当前的画面。是不是很酷?......
  • 【Python SHA256 摘要算法】
    SHA256是一种广泛使用的密码散列函数,用于生成数据的唯一指纹,即散列值。它属于SHA-2家族,该家族还包括SHA-384和SHA-512算法。SHA256算法在许多领域都有应用,例如:数据完整性验证:用于验证数据在传输或存储过程中是否被篡改。例如,在下载软件时,通常会提供软件的SHA256哈......
  • C++中的IO流
    目录1.C语言的输入与输出2.流是什么3.C++IO流标准IO流IO流的四个标志C++文件IO流4.stringstream的简单介绍1.C语言的输入与输出C语言中我们用到的最频繁的输入输出方式就是scanf()与printf()。scanf():从标准输入设备(键盘)读取数据,并将值存放在变量中。printf(......
  • C++之内存四区
    目录一、内存四区二、程序运行前三、程序运行后四、new操作符一、内存四区在计算机科学中,特别是在c或c++语言编程时,内存通常大致分为四个区域,而不同的区域存放的数据赋予不同的生命周期,给我们更大的灵活编程:代码区:存储程序的可执行代码(二进制代码),也就是程序编译后的......
  • 数据结构与算法详解
    目录一、引言二、数据结构1.数组(Array)定义特点应用场景总结表格2.链表(LinkedList)定义特点应用场景总结表格3.栈(Stack)定义特点应用场景总结表格4.队列(Queue)定义特点应用场景总结表格5.树(Tree)定义特点应用场景总结表格6.哈希表(HashTable)定......
  • Day31 贪心算法part5
    目录任务56.合并区间思路738.单调递增的数字思路968.监控二叉树思路任务56.合并区间以数组intervals表示若干个区间的集合,其中单个区间为intervals[i]=[starti,endi]。请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。思路......
  • SSM-国外鞋服代购平台-97782(免费领源码+开发文档)可做计算机毕业设计JAVA、PHP、爬虫、
    SSM国外鞋服代购平台摘 要随着科学技术的飞速发展,社会的方方面面、各行各业都在努力与现代的先进技术接轨,通过科技手段来提高自身的优势,鞋服代购平台当然也不例外。代购平台是以实际运用为开发背景,运用软件工程原理和开发方法,采用Java技术构建的一个管理系统。整个开发过......
  • 《密码保护升级指南:顶级哈希算法大比拼》
    密码哈希技术深度剖析:掌握MessageDigest、Bcrypt与PBKDF2一、为何探究密码哈希技术随着互联网的发展,网络安全变得越来越重要。密码哈希算法作为保护用户密码安全的关键技术之一,其重要性不言而喻。在数字时代,密码安全构成了保护用户隐私和资产的第一道防线。密码哈......