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了好多次。。这就比较悲伤了。。希望，随着自己的能力以达到理想的解题时间。。。