广搜变形
发表于|更新于
|浏览量:
题目描述:
在正常的广搜上加一个条件:每个点有开放时间,在开放之前禁止更新
方法:实际上,当开放后,第一个来更新他的点,是他周围第一个被更新过的点,所以距离直接标为min(dist[nowx][nowy]+1,open[nowx][nowy]+1)
然后加上一个优先队列就行了
这里提一下二维的优先队列写法:
1 | priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>,greater<>> q; |
这样就不用依赖tuple了
文章作者: ZestfulYK
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 ZestfulYK的Blog！
相关推荐
2025-02-12
格雷码及其应用
题目输入n,构造长度为$2^n-1$的序列,使得下面在这个式子的值最小 \sum_{i=1}^{2^n-1}a_{i-1} \oplus a_i方法:每组相邻元素最好二进制中只有一位不一样 打表结果: 1234n=1 0 1n=2 0 1 3 2n=3 0 1 3 2 6 7 5 4 1 0 2 3 7 6 4 5 所以暴力或者按结论使用格雷码 12345678910111213#include <iostream>using namespace std;int main() { int n; cin >> n; int m = 1 << n; for (int i = 0; i < m; ++i) { cout << (i ^ (i >> 1)); if (i < m - 1) cout << ' '; } cout << endl; return 0...
2025-12-07
ACM训练
简单题 对于简单题目，最好还是仔细一点，或者使用最暴力的解法，而不是投机取巧，或者构造高级方法，通常样例数据都是片面的，常常会有坑。 sleeping through classes 比如这一题，数据没有包含i+k中间有1的情况，直接i+=k导致错误。 中等题目 中等题目就需要强观察力和trick技巧了 Niko’s Tactical Cards 这一道题目是动态规划的变种，虽然要求每一步最优，但是可能发生最小值突然转变成最大值的情况，因此，计算最小值也是必要的。只要计算这两个值就行了。 Kanade’s Perfect Multiples 这题希望我们构造一个满足要求的B，这个就有点类似于筛法求素数了，实际上两者的代码几乎是一样的，但是在做的时候要注意区分原始数据和v数组，一个一个遍历就行了，找不到就可以直接退出，因为不然当前确定的最小值就无法被覆盖了。 Merging the Sets 你想选择其中的一些集合（可能一个都不选，也可能全部都选），使得 1 和 m 之间的每个整数都包含在个所选集合中的至少一个中。思维误区，不用一边读入一边判断，因为数据保证$l\leq 2*1...
2025-02-12
Abel公式
公式S=\sum_{i=1}^{m}a_ib_i=a_mB_m-\sum_{i-1}^{m-1}(a_{i+1}-a_i)B_i
2025-12-23
C++几何计算(保姆级教程)
版权说明此文章的所有代码均由qinye_leaf 勤叶大佬收集整理，感谢喵Orz Orz Orz 初始化由于双精度和单精度存在精度问题，所以补能直接判断是否为0或者相等，那么怎么办呢？我们可以取绝对值，然后和一个非常小的数字比较 代码示例：12// 浮点数精度阈值(根据题目要求调整，通常1e-8)const double EPS = 1e-8; 符号函数判断正负号的函数，但是是浮点数数版本的 12345// 符号函数：判断浮点数正负int sgn(double x) { if (fabs(x) < EPS) return 0; return x > 0 ? 1 : -1;} 构造函数介绍解释一下构造函数的用法，这里可以直接赋初始值，方便初始化 1234Point(double x_ = 0, double y_ = 0) : x(x_), y(y_) {}//那么我们可以这么来定义一个变量Point p1(2.0,3.0);Point p2; 如果不传参数，那么就是直接得到初始值0,0,要是有值的化就是直接赋值，这样...
2025-02-12
DP(01)最长不下降子序列及其变种
变种一就是01串,方法在下面,懒得解释了,自己看注释吧题目:问最少能把01串划成几个0101…类型的字符串12345678910111213//关键点,类似最长不下降子序列的题目,但是由于是01串,只要管有几个0结尾和1结尾的串就好了ll c0=0,c1=0;for(int i=0;i<t.length();i++){ if(t[i]=='1'){ if(c0) c0--;//接到0结尾的后面 c1++;//多了一个以1结尾的串 } else{ if(c1) c1--;//接到1结尾的后面 c0++;//多了一个以0结尾的串 } } return c0+c1; 变种二是有有限个结尾的dp 例如牛客周赛题目:把字符串变成相邻字母的ASCALL码之差都一样,求最小操作次数 因为只有26个字母,所以可以直接滚动数组+dp,然后设dp[i][j]表示以第i位结尾改成char('a'+j)的最少修改次数,或者也可以设成改为char('...
2025-02-24
DP习题笔记-二进制拆分
题目描述给定一个非负整数 $n(0\leq n \leq 10^7)$，求有多少个长为 30 的非负整数序列 a ,满足 $\sum_{i=0}^{29}2^i*a_i=n$由于答案可能很大，请将结果对 998244353 取模后再输出。 解法看到题目，第一反应就是一个完全背包的动态规划题目，所以直接打表解决，不过发现超时了，那么怎么办呢？ 输出前30个数得到如下结果：1231 2 2 4 4 6 6 10 10 14 14 20 20 26 26 36 36 46 46 60 60 74 74 94 94 114 114 140 140 166观察得到，每两个数是一样的，如果去重的话得到： 11 2 4 6 10 14 20 26 36 46 60 每一次的差正好都在前面出现过且这个差的位置刚好是n/2，那么可以得到递推式子：$$\begin{cases}dp[i]=dp[i-1]\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{i为奇数}\dp[i]=dp[i-1]+dp[i/2]\ \ \ \ \ \ \text{i为偶...
