題目鏈接：點擊查看

題目大意：給出一個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(构造+模拟)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。