CodeForces - 1301D Time to Run(构造+模拟)

题目链接：点击查看

题目大意：给出一个n*m的矩阵，现在每两个格子之间都有一条双向的通道，初始时有个人在左上角的格子中，现在要求这个人精确的走 k 条路，不过每条路只能走一次，但是每个格子可以走无限次，如果有解要求输出任意一种情况

题目分析：显然是个构造题，也没什么技巧，一开始盯着题目给的图老半天了，从回字形想到蛇形愣是没进展，快结束了突然灵光乍现，找到了一种方法可以将所有的路不重不漏的遍历一遍，写完之后交了一发在test15Wa了，打回来继续改，发现不是细节问题，最后还有三分钟找到了一组hack数据，手忙脚乱改完之后还剩八秒钟，网络原因没有交上，赛后交上1A，一套行云流水操作完成掉分，菜鸡的CF日常

说回这个题，我挂一张图应该就不用多bb了吧：

按照顺序走一遍就是答案了，别问我是怎么想出来的。。你看，就硬看，或许就能看出来了

这样剩下的就变成模拟题了，我这样构造有一组hack数据，就是2 1 1，也就是当只有一列的时候，我会输出诸如 0 R 这样奇怪的输出，所以最后需要将数字为 0 的答案删除掉，剩下的就是正确答案了

而题目要求最多只能输出3000行作为答案，我这样写的话极限数据下是会输出( 499 + 499 ) * 3 + 2 行 ，也就是 2996 行，符合题意

代码：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;int main() { //#ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); //#endif // ios::sync_with_stdio(false);int n,m,k;scanf("%d%d%d",&n,&m,&k);if(4*n*m-2*n-2*m<k)return 0*printf("NO");puts("YES");vector<string>ans;for(int i=1;i<m;i++)//处理第一行 {if(k>1){ans.push_back(to_string(1)+" R");k-=1;}else{ans.push_back(to_string(k)+" R");goto end;}if(k>n-1){ans.push_back(to_string(n-1)+" D");k-=n-1;}else{ans.push_back(to_string(k)+" D");goto end;}if(k>n-1){ans.push_back(to_string(n-1)+" U");k-=n-1;}else{ans.push_back(to_string(k)+" U");goto end;}}if(k>m-1){ans.push_back(to_string(m-1)+" L");k-=m-1;}else{ans.push_back(to_string(k)+" L");goto end;}for(int i=1;i<n;i++)//处理其余行{if(k>1){ans.push_back(to_string(1)+" D");k-=1;}else{ans.push_back(to_string(k)+" D");goto end;}if(k>m-1){ans.push_back(to_string(m-1)+" R");k-=m-1;}else{ans.push_back(to_string(k)+" R");goto end;}if(k>m-1){ans.push_back(to_string(m-1)+" L");k-=m-1;}else{ans.push_back(to_string(k)+" L");goto end;}} if(k>n-1){ans.push_back(to_string(n-1)+" U");k-=n-1;}else{ans.push_back(to_string(k)+" U");goto end;}end:for(int i=ans.size()-1;i>=0;i--)if(ans[i][0]=='0')ans.erase(ans.begin()+i);printf("%d\n",ans.size());for(int i=0;i<ans.size();i++)cout<<ans[i]<<endl;return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 1301D Time to Run(构造+模拟)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。