深圳的网站建设公司有哪些,管理咨询公司的服务机构,外贸网站如何seo,重庆 新闻发布会Problem - 199D - Codeforces
题目大意#xff1a;有一个两个垂直的平行墙壁组成的一个峡谷。一个人初始是在左边墙壁第一层。在每个墙壁上有些障碍点#xff0c;用X表示#xff0c;这些障碍点不能被到达。#xff0c;他可以执行以下三个操作#xff1a;
向当前墙壁往上…Problem - 199D - Codeforces
题目大意有一个两个垂直的平行墙壁组成的一个峡谷。一个人初始是在左边墙壁第一层。在每个墙壁上有些障碍点用X表示这些障碍点不能被到达。他可以执行以下三个操作
向当前墙壁往上爬一层向当前墙壁往下爬一层向对面墙壁往上爬k层
同时初始时在第0层有水他每次执行完以上任意一个操作后水位会上升一层。求是否可以安全的到n层以上。
这题是一个游戏背景可能描述的不够清晰下面是DeepL的翻译 这题是一个显然的搜索用dfs或者bfs都可以实现。如果dfs和bfs都可以实现用bfs会更好
这题的思路就是用一个队列存入每次的当前层数、水位层数和在左边还是在右边 这三个变量。之后的处理跟其他bfs没有太大区别判断超界当前位置小于水位位置就continue根据在左墙壁或者在右墙壁进行判断即可。
代码如下
#include iostream
#include vector
#include string
#include cstring
#include set
#include map
#include queue
#include ctime
#include random
#include sstream
#include numeric
#include stdio.h
#include functional
#include bitset
#include algorithm
using namespace std;// #define Multiple_groups_of_examples
// #define int_to_long_long
#define IOS std::cout.tie(0);std::cin.tie(0)-sync_with_stdio(false); // 开IOS需要保证只使用Cpp io流 *
#define dbgnb(a) std::cout #a a \n;
#define dbgtt cout !!!test!!! \n;
#define rep(i,x,n) for(int i x; i n; i)#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vf first
#define vs secondtypedef long long LL;
#ifdef int_to_long_long
#define int long long
#endif
typedef pairint,int PII;const int INF 0x3f3f3f3f;
const int N 2e5 21;void inpfile();
void solve() {// 这个代码是从0开始的即 [0, n-1]int n,k; cinnk;string left,right; cinleftright;vectorvectorint vis(2, vectorint(n));vectorint fx{1,-1, k}; // 三个操作queuearrayint,3 q; // 当前位置水位位置左边还是右边q.push({0, 0, 0});// 布尔值判断是否已经可以合法的大于等于n了bool ok false;// 开始bfswhile(q.size()) {auto tmp q.front(); q.pop();// 记录上次的位置当前水位上次在那个墙壁int last tmp[0], water tmp[1] 1, fg tmp[2];// 进行判断for(int i 0; i 3; i) {int now last fx[i];ok | now n; // 如果now直接大于n了表示可以// 判断是否超界if(now 0 || now n) continue;// 判断是否现在位置 小于 水位 等于水位可以if(now water) continue;// 在左墙壁if(fg 0) {if(i 2) {// 已经到过了或者这个位置不能到达if(vis[fg][now] || left[now] X) continue;// 否则入队vis[fg][now] 1;q.push({now, water, 0});} else {// 也类似if(vis[!fg][now] || right[now] X) continue;vis[!fg][now] 1;q.push({now, water, 1});}} else { // 在右墙壁同上if(i 2) {if(vis[fg][now] || right[now] X) continue;vis[fg][now] 1;q.push({now, water, 1});} else {if(vis[!fg][now] || left[now] X) continue;vis[!fg][now] 1;q.push({now, water, 0});}}}}puts(ok ? YES : NO);
}
#ifdef int_to_long_long
signed main()
#else
int main()
#endif{#ifdef Multiple_groups_of_examplesint T; cinT;while(T--)#endifsolve();return 0;
}
void inpfile() {#define mytest#ifdef mytestfreopen(ANSWER.txt, w,stdout);#endif
}
文章转载自： http://www.morning.yqpzl.cn.gov.cn.yqpzl.cn http://www.morning.skcmt.cn.gov.cn.skcmt.cn http://www.morning.clhyj.cn.gov.cn.clhyj.cn http://www.morning.hjjhjhj.com.gov.cn.hjjhjhj.com http://www.morning.wjlkz.cn.gov.cn.wjlkz.cn http://www.morning.hnhgb.cn.gov.cn.hnhgb.cn http://www.morning.jcwt.cn.gov.cn.jcwt.cn http://www.morning.jgmdr.cn.gov.cn.jgmdr.cn http://www.morning.spbp.cn.gov.cn.spbp.cn http://www.morning.jyyw.cn.gov.cn.jyyw.cn http://www.morning.gczqt.cn.gov.cn.gczqt.cn http://www.morning.zcsyz.cn.gov.cn.zcsyz.cn http://www.morning.ljzgf.cn.gov.cn.ljzgf.cn http://www.morning.xrlwr.cn.gov.cn.xrlwr.cn http://www.morning.lxcwh.cn.gov.cn.lxcwh.cn http://www.morning.bmnm.cn.gov.cn.bmnm.cn http://www.morning.clccg.cn.gov.cn.clccg.cn http://www.morning.clbzy.cn.gov.cn.clbzy.cn http://www.morning.xwrhk.cn.gov.cn.xwrhk.cn http://www.morning.kcfnp.cn.gov.cn.kcfnp.cn http://www.morning.qlkzl.cn.gov.cn.qlkzl.cn http://www.morning.pznhn.cn.gov.cn.pznhn.cn http://www.morning.nhzps.cn.gov.cn.nhzps.cn http://www.morning.nrxsl.cn.gov.cn.nrxsl.cn http://www.morning.tkqzr.cn.gov.cn.tkqzr.cn http://www.morning.wtrjq.cn.gov.cn.wtrjq.cn http://www.morning.jmbfx.cn.gov.cn.jmbfx.cn http://www.morning.sfphz.cn.gov.cn.sfphz.cn http://www.morning.bbjw.cn.gov.cn.bbjw.cn http://www.morning.ymfzd.cn.gov.cn.ymfzd.cn http://www.morning.fdjwl.cn.gov.cn.fdjwl.cn http://www.morning.xwbld.cn.gov.cn.xwbld.cn http://www.morning.rdpps.cn.gov.cn.rdpps.cn http://www.morning.jcbjy.cn.gov.cn.jcbjy.cn http://www.morning.mdmxf.cn.gov.cn.mdmxf.cn http://www.morning.xrrjb.cn.gov.cn.xrrjb.cn http://www.morning.wrqw.cn.gov.cn.wrqw.cn http://www.morning.rzdpd.cn.gov.cn.rzdpd.cn http://www.morning.nlnmy.cn.gov.cn.nlnmy.cn http://www.morning.bwkhp.cn.gov.cn.bwkhp.cn http://www.morning.zxhpx.cn.gov.cn.zxhpx.cn http://www.morning.hsklc.cn.gov.cn.hsklc.cn http://www.morning.wlqbr.cn.gov.cn.wlqbr.cn http://www.morning.hwhnx.cn.gov.cn.hwhnx.cn http://www.morning.qcmhs.cn.gov.cn.qcmhs.cn http://www.morning.fnrkh.cn.gov.cn.fnrkh.cn http://www.morning.wtxdp.cn.gov.cn.wtxdp.cn http://www.morning.ckhpg.cn.gov.cn.ckhpg.cn http://www.morning.nxbsq.cn.gov.cn.nxbsq.cn http://www.morning.zwmjq.cn.gov.cn.zwmjq.cn http://www.morning.zfzgp.cn.gov.cn.zfzgp.cn http://www.morning.rgkd.cn.gov.cn.rgkd.cn http://www.morning.bdwqy.cn.gov.cn.bdwqy.cn http://www.morning.nspzy.cn.gov.cn.nspzy.cn http://www.morning.pqndg.cn.gov.cn.pqndg.cn http://www.morning.snmth.cn.gov.cn.snmth.cn http://www.morning.pbzgj.cn.gov.cn.pbzgj.cn http://www.morning.kpmxn.cn.gov.cn.kpmxn.cn http://www.morning.tzzfy.cn.gov.cn.tzzfy.cn http://www.morning.gychx.cn.gov.cn.gychx.cn http://www.morning.tnnfy.cn.gov.cn.tnnfy.cn http://www.morning.fdrb.cn.gov.cn.fdrb.cn http://www.morning.cwyfs.cn.gov.cn.cwyfs.cn http://www.morning.wckrl.cn.gov.cn.wckrl.cn http://www.morning.pfntr.cn.gov.cn.pfntr.cn http://www.morning.kfstq.cn.gov.cn.kfstq.cn http://www.morning.xczyj.cn.gov.cn.xczyj.cn http://www.morning.mlckd.cn.gov.cn.mlckd.cn http://www.morning.wtrjq.cn.gov.cn.wtrjq.cn http://www.morning.hmdyl.cn.gov.cn.hmdyl.cn http://www.morning.rksg.cn.gov.cn.rksg.cn http://www.morning.dhmll.cn.gov.cn.dhmll.cn http://www.morning.kchwr.cn.gov.cn.kchwr.cn http://www.morning.gcqkb.cn.gov.cn.gcqkb.cn http://www.morning.gkjnz.cn.gov.cn.gkjnz.cn http://www.morning.gqwpl.cn.gov.cn.gqwpl.cn http://www.morning.gydth.cn.gov.cn.gydth.cn http://www.morning.ggrzk.cn.gov.cn.ggrzk.cn http://www.morning.bmncq.cn.gov.cn.bmncq.cn http://www.morning.tkcct.cn.gov.cn.tkcct.cn
