CodeForces 321A Ciel and Robot[暴力]

題目連結：http://codeforces.com/problemset/problem/321/A

問題的意思很是簡單：給你一個字元串，長度最多100。每個字元代表一種操作。。一共4中操作。。

• 'U': go up, (x, y)  →  (x, y+1);
• 'D': go down, (x, y)  →  (x, y-1);
• 'L': go left, (x, y)  →  (x-1, y);
• 'R': go right, (x, y)  →  (x+1, y).

最初始的時候，在原點。。問你不管這個指令字元串循環幾次，能否達到 (a, b)。(  - 109 ≤ a, b ≤ 109)。。。

大家最開始的時候。。 肯定不會想暴力這種算法。。。。

想法總是被逼出來的。。不得不去想暴力的算法了。。

我們肯定不會從原點開始進行暴力的。。那麼，從哪裡開始暴力呢？？

我們知道他也就是最多100步，每個循環。。那麼我們可以從他達到目标前的100個循環處開始暴力。。。妥妥的就過暴力過了。。

Code：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <vector>
using namespace std;
#define CLR(arr, val) memset(arr, val, sizeof(arr))
#define INT long long

const int INF = 0x3f3f3f3f;
const int N = 105;
struct POINT
{
    int x, y;
    POINT() {}
    POINT(int a, int b)
    {
        x = a;
        y = b;
    }
} p[N];


int main()
{
//    freopen("1.txt", "r", stdin);
    int endx, endy;
    while(cin >> endx >> endy)
    {
        string str;
        cin >> str;
        int size = str.size();
        int top = 0, i;
        p[top ++] = POINT(0, 0);
        for(i = 0 ; i < size; i ++)
        {
            if(str[i] == 'U')
            {
                p[top ++] = POINT(p[top - 1].x, p[top - 1].y + 1);
            }
            else if(str[i] == 'D')
            {
                p[top ++] = POINT(p[top - 1].x , p[top - 1].y - 1);
            }
            else if(str[i] == 'L')
            {
                p[top ++] = POINT(p[top - 1].x - 1, p[top - 1]. y);
            }
            else
            {
                p[top ++] = POINT(p[top - 1].x + 1, p[top - 1].y);
            }
        }
        top --;
        int leastx , leasty, k;

        if(p[top].x == 0) leastx = INF;
        else leastx = endx / p[top].x;
        if(p[top].y == 0) leasty = INF;
        else leasty = endy / p[top].y;

        k = min(leastx, leasty);
        POINT o, now;
        if(k < 0) k = 0;
        if(k > 100) {
            int dd = (k / 100 - 1) * 100;
            o = POINT(dd * p[top].x, dd * p[top].y);
        }
        else o = POINT(0, 0);
        now = o;
        bool flag = false;
        for(int i = 1; i <= 200; i ++){
            for(int j = 0; j <= top; j ++){
                if(endx == now.x && endy == now.y){
                    flag = true;
                    break;
                }
                now.x = o.x + p[j].x;
                now.y = o.y + p[j].y;
            }
            o.x += p[top].x;
            o.y += p[top].y;
            if(flag) break;
        }
        if(flag) puts("Yes");
        else puts("No");
    }
    return 0;
}
           

寫這個問題的題解不是這道題有多難。。而是，這樣的問題我們不應該花費太長的時間來求解。。

不可想象的是，花了比較長的時間才正确的求解出來。。。WA了好多次。。這就比較悲傷了。。希望，随着自己的能力以達到理想的解題時間。。。