首页 > 其他分享 >2024年2月28号题解

2024年2月28号题解

时间:2024-02-28 22:03:42浏览次数:35  
标签:int 题解 ll 28 long 2024 include 地毯 define

P4994 终于结束的起点

解题思路

  1. 通过加法同余原理可以知道f[i] % m == 0,那么f[i - 1] % m = 1,所有把f[i + 1] % m = 1转换成了f[i - 1] % m = 1的问题
  2. 那么只需要填好斐波那契数列再判断就可以了,又因为斐波那契可能会超出int的范围那么我们对每一项斐波那契再取模就可以了

代码实现

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf 
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 10000001

ll m;
ll f[N];
ll i;

int main(int argc, char* argv[])
{
	sc("%lld", &m);
	
	f[1] = f[0] = 1;//初始化
	i = 2;//从第二项开始
	
	while(1) {
		f[i] = (f[i - 1] + f[i - 2]) % m;//对于每一项都取模
		if (f[i] % m == 0 && f[i - 1] % m == 1) {//如果满足条件代表找到了
			break;
		}
		i ++;//看下一项
	}
	
	pr("%lld", i + 1);//因为从0开始时数,所以要加一

	return 0;
}

P1025 [NOIP2001 提高组] 数的划分

解题思路

  1. 难点在于怎么不重复的选择方案的个数,那么我们可以通过在递归中使用一个变量来记录上一次选取的数,然后让选取的数从上一次选取的数开始选,就像算一个些数的组合一样来避免重复选取
  2. 可以通过i <= n - sum来进行剪枝,因为i的最大范围只能是n - sum

代码实现

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf 
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 10

int n, k;//整数n和被分成的份数 
int ans;//方案个数 

void dfs(int cur, int sum, int last) {//cur代表当前选择了几个数,sum代表选取数的累加和,last代表上一个选取的数 
	if (cur == k) {//如果选取了k个数了 
		if (sum == n) {//如果sum等于n满足条件,因为用了last变量所以不可能出现重复的方案,所以直接加 
			ans ++;//答案加一 
		}
		return ;
	}
	
	for (int i = last; i <= n - sum ; i ++) {//从上一个选取的数开始,i最大范围为n - sum来进行剪枝 
		dfs(cur + 1, sum + i, i);//递归调用 
	}
}

int main(int argc, char* argv[])
{
	sc("%d%d", &n, &k);
	
	dfs(0, 0, 1);//dfs求解方案数 
	
	pr("%d", ans);
	
	return 0;
}

P1003 [NOIP2011 提高组] 铺地毯

解题思路

  1. 用一个二维数组记录地毯的左下角和x轴和y轴的长度
  2. 从后开始遍历数组,因为后面的会覆盖前面的地毯,所以可以从后往前遍历
  3. 判断点在那个地毯里面,在就输出,访问完了所有地毯如果都没有在的话就输出-1

代码实现

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf 
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 10001

int a[N][4];//存储地毯的信息 
int t[2];//存储访问的位置 
int n;//地毯的个数 

int f() {//返回t位置被那个地毯覆盖 
	int ans = -1;//返回的地毯编号 
	
	for (int i = n - 1; i >= 0; i --) {//从后开始遍历,因为会被后面的地毯覆盖 
		if ((t[0] >= a[i][0] && t[0] <= a[i][0] + a[i][2]) && (t[1] >= a[i][1] && t[1] <= a[i][1] + a[i][3])) {//判断这个点在不在i号地毯里面 
			return i + 1;//在就直接返回 
		}
	}
	
	return ans;//如果没有在for循环里面返回代表没有在任何一个地毯里面,所有返回-1 
}

int main(int argc, char* argv[])
{
	sc("%d", &n);
	
	//读入地毯信息 
	for (int i = 0; i < n; i++) {
		sc("%d%d%d%d", a[i], a[i] + 1, a[i] + 2, a[i] + 3);
	}
	
	sc("%d%d", t, t + 1);//读入查询位置 
	
	pr("%d", f());//打印被覆盖的地毯 
	
	return 0;
}

总结

  1. 很自然的想法是用一个二维数组来模拟铺地毯的过程,但是因为0≤a,b,g,k≤10^5,所以开一个二维数组不行
  2. 那么下一个想法是存储地毯的信息,来遍历地毯看点在那个地毯里面来解决问题,然后刚开始是一个点一个点试,所以超时
  3. 那么有没有一种办法可以直接判断点在不在一个坐标系中的长方形中呢
  4. 有,用数学的知识就可以了,只要点的x和y坐标在长方形的中间,那么就代表在这个地毯中

P1179 [NOIP2010 普及组] 数字统计

解题思路

  1. 遍历区间中的每一个数,并对区间中的每一个分离它的每一位并且判断是不是2,是2就让计数器加一,不是就去看下一个数

代码实现

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf 
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 10

int l;
int r;
int ans;//答案 

void f(int n) {//判断一个数中2的个数 
	while(n) {
		if (n % 10 == 2) {//如果一个数有二 
			ans ++;//计数器加一 
		}
		n /= 10;//看下一位 
	}
}

int main(int argc, char* argv[])
{
	sc("%d%d", &l, &r);//读入左端点和右端点 
	
	while(l <= r) {//遍历区间中的每一个数 
		f(l++);//累加遍历数中2的个数 
	}
	
	pr("%d", ans);///打印结果 
	
	return 0;
}

 

标签:int,题解,ll,28,long,2024,include,地毯,define
From: https://www.cnblogs.com/lwj1239/p/18041391

相关文章

  • 2.28
    一、 数据结构分析:(1)京津冀三省的2015年度的科技成果数据原始表,为Access数据库,; (2)要求将三省的科技成果数据汇总到同一表中(要求结果表为MySql数据表);(3)三个原始数据表结构不一致,要求结果表中包括所有的字段,表达意思相同或相似的字段要进行合并,不允许丢失字段(若只有本表独有字段,......
  • 旅游景点 Tourist Attractions (壮压 DP)题解
    简化题意题目链接——不卡内存班题目链接——卡内存版给定\(n\)个点和\(m\)条边组成的无向图,按照一定限制要求停留\(2\simk+1\)共\(k\)个点(可以经过但不停留),求最短的从\(1\)出发到\(n\)的路径长。限制情况如下:共有\(q\)个限制,接下来\(q\)行,每行两个数\(x......
  • 2.28
    Vsinger_洛天依:我奖励名额紧张个jb啊Vsinger_洛天依:不是,我体验名额奖励个jb啊Vsinger_洛天依:不是,我体验名额紧张个jb啊......
  • 2.28
    今天上午上的刘老师的python课然后再课上我知道了很多关于python的基本知识还有就是,认识了一些Python的基础代码像乘法要用两个*还有就是在进行运算时只要不是自带的基本函数就要导入库.紧接着就是关于Python的特点,高级的动态语言.对比c,c++还有Java的一些不同.zaipython中数据......
  • 1.28
    今天学习一下小程序对应的一些基础知识,其中小程序开发和网页开发还是存在一些区别的,比如运行环境、API、开发模式不同等不同。 接下来我们注册微信小程序开发账号 注册完后登录开发主页面,获取到创建项目时所需要的微信小程序ID 然后我们安装开发小程序工具--微信开发者工......
  • HEOI2024 退役记
    这篇游记打算用一些比较不魔怔的方式写。Day-3倒数第三天,这天写了闲话所以把一些不想再写一遍的东西粘上来:哎昨天晚上我还久违做梦了,我梦到我场上还在写defineLOCAL然后#ifdefLOCAL后面freopen啥的。然后最后我不知道我咋想的我把所有的ifdef改成了ifndef,但是我还......
  • 闲话2.28
    今天咋摆了一天......
  • CF1408H Rainbow Triples 题解
    Description给定长度为\(n\)的序列\(p\)找出尽可能多的三元组\((a_i,b_i,c_i)\)满足:\(1\lea_i<b_i<c_i\len\)\(p_{a_i}=p_{c_i}=0\),\(p_{b_i}\ne0\)\(p_{b_i}\)互不相同。所有的\(a_i,b_i,c_i\)互不相同。输出最多可以选出多少个三元组,多组数据。\(\sumn\le......
  • 1.28
     CSS用于控制HTML文档的样式和布局,实现页面的外观设计。样式定义可以通过内联样式、内部样式表和外部样式表来实现。了解CSS选择器,它用于选择文档中的HTML元素,从而应用样式。 常见选择器包括标签选择器、类选择器、ID选择器、后代选择器等。学习常用的CSS样式属性,如`color`、......
  • HEOI 2024 游记
    Day-2流沙-陶喆昨天晚上的事我看没有什么好谈的吧我看就这样吧Ohyeahoh并不是真的路过而已也不是真的不会想你全部不是真的是骗自己其实还爱你爱着你我以为我早想清楚不由自主恍恍惚惚又走回头路再看一眼有过的幸福爱情好像流沙我不挣扎随它去吧我不害怕爱......