1301D - Time to Run（思维、模拟）

╰+哭是因爲堅強的太久メ 2021-07-16 20:00 249阅读 0赞

[题目][Link 1]

思路：先进行一遍全部过程的模拟储存下来，为了方便模拟尽量先将相同的方向走完，而对于多少步step，将连续的相同方向当作一步，如DDDDDULLL->5D1U3L，只需判别存储好的全部模拟字符串前后不同步数+1即可，细节见代码。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]

#include<iostream>
    #include<string>
    #include<map>
    #include<algorithm>
    #include<memory.h>
    #include<cmath>
    #include<vector>
    #define pii pair<int,int>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    string ans[Max];
    int s[Max];
    
    int main()
    { 
    	int n, m, k;cin >> n >> m >> k;
    	if (k > n * m * 4 - 2 * n - 2 * m)cout << "NO" << endl;
    	else
    	{ 
    		string str="";
    		for (int i= 1;i <= n;i++)
    		{ 
    			for (int j = 1;j <= m - 1;j++)str += 'R';
    			if (i != n)
    			{ 
    				for (int i = 1;i <= m - 1;i++)str += 'L';
    				str += 'D';
    			}
    		}
    		for (int i = 1;i <= m;i++)
    		{ 
    			for (int j = 1;j <= n - 1;j++)str += 'U';
    			if (i != m)
    			{ 
    				for (int j = 1;j <= n - 1;j++)
    				{ 
    					str += 'D';
    				}
    				str += 'L';
    			}
    		 }
    		int sum = 1;ans[sum] = str[0];s[sum] = 1;
    		for (int i = 1;i <k;i++)
    		{ 
    			if (str[i] == str[i - 1])s[sum]++;
    			else
    			{ 
    				ans[++sum] = str[i];
    				s[sum] = 1;
    			}
    		}
    		cout << "YES" << endl << sum << endl;
    		for (int i = 1;i <= sum;i++)
    		{ 
    			cout << s[i] << " " << ans[i] << endl;
    		}
    	}
    }

[Link 1]: https://codeforces.ml/problemset/status?my=on
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]: /images/20210716/527ade0041c74814b090a31bfed2a94f.png