首页 > 其他分享 >chapter2-暴力求解

chapter2-暴力求解

时间:2024-02-04 21:01:20浏览次数:27  
标签:10 暴力 闰年 求解 复杂度 chapter2 数据量 图形 模拟

1、枚举

对所有可能的情况进行枚举。面对枚举类型的题目,在想到思路的时候,要习惯于分析一下这种方法的复杂度是多少,结合题目的数据量分析这样的方法是否可行,然后再动手写代码,节约时间。
计算机1000MS,大约可进行10^7次运算。所以,常见的代码时间复杂度,1秒内可接受的数据量如下表:

复杂度 数据量
O(n!) 10
O(2^n) 20
O(n^3) 200
O(n^2) 3000
O(nlogn) 10^6
O(n) 10^7
O(n^(1/2)) 10^14
O(logn) > 10^20

上表中,数据量就是n最多能取值多少,不会导致超时错误。

2、模拟

只需利用程序实现题目的要求。模拟总共可分为3大类,分别是图形排版、日期问题、其他模拟,学习基本的做题思路之后,多加练习,那么这类题目就不会有太多困难。

  • 图形排版:这种问题如果字符阵列的规律不太容易通过从上到下、从左到右的输出直接打印出来,那么思路是通过构造一个二维的字符数组,先根据题面要求画图形,总结规律并转换成数学公式,比如h+2*i这种,然后构造出图形保存到二维数组中,最后按顺序输出二维数组内容即可。如果图形可以直接打印出来的话,那么也要抽象出图形,标记边长、坐标什么的,总结出数学公式。
  • 日期问题:一个公式,包含3个关键变量,日期A,天数,日期B,一般都是给你其中的两个变量,求另外一个变量,这类问题注意预处理(用空间换时间) 的概念,定义一个dayTable[row][month]数组,保存平年、闰年每个月的天数(PS:平年共365天/年,闰年366天/年),接着写一个判断是不是闰年的函数,如果是闰年,2月有29天,愉快编写主函数。
  • 其他模拟:五花八门,只需根据题面要求进行模拟即可。同样可以采用预处理,用空间换时间的办法,简洁高效。

标签:10,暴力,闰年,求解,复杂度,chapter2,数据量,图形,模拟
From: https://www.cnblogs.com/paopaotangzu/p/18004856

相关文章

  • 洛谷暴力枚举
    暴力枚举一点也不暴力,洛谷题单最后三题还是没做出来,题解也没看懂讲的都是什么搜索七七八八的,看来只能后面学了回来补。个人感觉其实暴力枚举就是要尽可能地压榨运行时间,然后用的也是什么递归搜索for之类的1.统计方形a.如果只是单纯的数格子这种根本不可能做的出来,仔细发现若把......
  • 费用流求解二分图最大权匹配
    二分图最大权匹配问题:有\(n_1\)个左部点,\(n_2\)个右部点,\(m\)条边,边有边权\(w_i\),表示若选择这条边就会获得\(w_i\)的收益,求获得收益最大的一种图的匹配方案。若考虑用费用流求解,建立超级源点\(S\)和超级汇点\(T\),\(S\)向每个左部点连边,流量1费用0;每个右部点向\(......
  • 地铁最优线路算法的求解(三)-深度优先搜索java实现
    多的不说,showmethecode,先上一段java代码1/*2*深度优先算法(DFS)算法生成所有可能路径3*startId:出发站4*endId:到达站5*graph:辅助邻接矩阵,若99站与35站相邻,6*则graph[35][99]=1,graph[99][35]=17*8*......
  • 洛谷题单指南-暴力枚举-P2392 kkksc03考前临时抱佛脚
    原题链接:https://www.luogu.com.cn/problem/P2392题意解读:由于可以同时计算两道同一科的题目,只需要把某一科题目分两堆,使得两堆总时长之差最小,时长较大的一堆就是完成这一科的最短时间。解题思路:既然直到了要把一科题目分两堆,关键是如何分堆呢?比较容易犯的错是用贪心来解题:把......
  • 洛谷题单指南-暴力枚举-P3799 妖梦拼木棒
    原题链接:https://www.luogu.com.cn/problem/P3799题意解读:要选四根木棒拼成等边三角形,必然有两根长度相等,其余两根长度之和等于前两根解题思路:木棒总数最大100000,每根最长5000,因此通过枚举其中两根木棒的长度,计算出另外两根的长度,通过各个长度的木棒数进行选择。设数组h[n]保......
  • 洛谷题单指南-暴力枚举-P1149 [NOIP2008 提高组] 火柴棒等式
    原题链接:https://www.luogu.com.cn/problem/P1149题意解读:计算符合A+B=C时,火柴棍数量正好等于n,可以采用枚举A、B,然后计算出C,根据A、B、C计算出所有火柴棍数量,再加上4根加号、等号的,如果与n相等,即为一种合法等式。解题思路:题目的关键在于枚举A、B时,最大值的设定,不能超时。分析......
  • 洛谷题单指南-暴力枚举-P1217 [USACO1.5] 回文质数 Prime Palindromes
    原题链接:https://www.luogu.com.cn/problem/P1217题意解读:本题要找[a,b]范围内的所有回文质数,千万不要被题目提示所干扰,如果按照提示先产生各个长度的回文数,再依次判断是否是素数,程序写起来比较繁琐,需要根据a、b的长度,写8个判断是否产生1~8位回文数,最后做素数判断。换一个思路......
  • 洛谷题单指南-暴力枚举-P3654 First Step (ファーストステップ)
    原题链接:https://www.luogu.com.cn/problem/P3654题意解读:在r*c矩阵中,找连续k个.的总数。解题思路:本题直接枚举即可,在每一行中,以每一列为起点,连续判断k个元素,如果全为'.',则方案数加1在每一列中,以每一行为起点,连续判断k个元素,如果全为'.',则方案数加1注意:如果k=1,只有一个人......
  • 洛谷题单指南-暴力枚举-P3392 涂国旗
    原题链接:https://www.luogu.com.cn/problem/P3392题意解读:此题枚举白、蓝、红所有可能的行数组合,依次逐行判断每个方格,是否需要染色,计算最少的染色次数即可。解题思路:总行数是n,先考虑白色,第一行必是白色,最后一行必是红色,至少有一行蓝色,因此白色行数的范围是1~n-2再考虑蓝......
  • 洛谷题单指南-暴力枚举-P1088 [NOIP2004 普及组] 火星人
    原题链接:https://www.luogu.com.cn/problem/P1088题意解读:火星人的手指可以通过全排列来表示数字,全排列由小到大的顺序即为表示的数字大小,题目可以转化为:给定按顺序全排列中的某一个排列,求往后数m个排列的内容。解题思路:此题与经典全排列问题的差异在于,需要从指定一个排列开......