首页 > 魔改森林
开通博客写题解
头像 (́安◞౪◟排‵)
发表于 2020-06-01 08:12:29
T1 题目链接 分析 对于 n,m<=1000 的点直接使用DP即可 可得20分对于 n,m<=100000 的点我们可以发现k很小考虑使用容斥原理我们定义一个work函数work是指右移a次上移b次有多少种移法 work解决方法： 1.考虑把b次上移插入a次右移动的空中 a有a+1个空 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 shyyhs
发表于 2021-01-27 00:36:54
前言: 很久很久以前就看到这个题目.记得这题应该是小乔出的.当时我队友来问我,我跟他讲了一下35分的做法.因为那个时候太菜了,不会容斥原理. 思路: 这题前面1000个数据直接dp即可.后面1e5,直接组合数预处理+容斥原理即可. 代码: #include <bits/stdc++.h> 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 熠丶
发表于 2021-01-26 15:17:18
做法：动态规划，组合问题+容斥原理 前置芝士：容斥原理 思路： 1.当k很大，n和m很小时，可以考虑dp求解 2.当k很小，n和m很大时，可以采用组合问题+容斥原理从起点走到终点，只能向上或向右走，一共有多少种走法很容易联想到高中的组合问题，即(不考虑障碍点)又因为存在k个障碍点，应该减去起点到障 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 (́安◞౪◟排‵)
发表于 2020-06-01 17:27:27
T2 分析见代码 #pragma GCC optimize(2) #include<bits/stdc++.h> #define pass puts("pass") #define LL long long #define N 20 #define M 1000 using namesp 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 sunrise__sunrise
发表于 2021-01-26 15:35:38
题目描述 给你大小为的棋盘那就有个格点，你要从左下点走到右上点问方案数，每次只能往上或者往右走。而且这个棋盘里面存在个格点无法走入。 Solution 首先看，当，是可以通过二维的求解过程，这个过河卒问题很基础我就不多解释了，遇到障碍跳过即可。 重点看后面很大，但是会发现他们的很小很小，最多只有 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 VagrantAC
发表于 2020-12-15 15:20:35
魔改森林 题解 分组讨论，对于一个 n,m <= 1000,使用暴力枚举即可。 if (n <= 1000 && m <= 1000) { dp[0][0] = 1; memset(vis, false, sizeof(vis)); 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 hnust_yangyanjun
发表于 2021-01-26 18:32:47
题意：有一个n行m列的网格图，起点在格点(n+1，1), 终点在(1,m+1),有k个格点是不能走的障碍点。求从起点到终点的路线有多少种？（只能向上或向右） 思路：从数据范围看当n,m<=1000时我们可以用动态规划解决：dp[n+1][1]=1;dp[i][j]=dp[i+1][j]+dp[ 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 回归梦想
发表于 2021-01-28 12:13:31
题意： 曾经有一道叫做迷雾森林的题目，然而牛牛认为地图中的障碍太多，实在是太难了，所以删去了很多点，出了这道题。 牛牛给出了一个n行m列的网格图初始牛牛处在最左下角的格点上(n+1,1)，终点在右上角的格点(1,m+1)现在它想知道，从起点走到终点，只能向上或向右走，一共有多少种走法呢？ 需要注意的 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 hunxuewangzi
发表于 2021-01-27 15:21:21
题目链接 题目大意 给你一个n*m的方格图，中间有k个障碍，要你求从左下角到右上角有多少种方案mod 998244353 题目思路 这个题目真是很oi......首先 直接 如果方格数量很多，观察障碍物很少，则可以想到容斥的思维 然后再用组合数学预处理一下 一定要注意要预处理到2e5 wa了我一辈 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”