链接：codeforces.com/contest/8

A

原因：RE，fantasy 的字符串的长度可能大于原字符串。

B

题意：上下左右走，可能要避让障碍，问是否存在一个地图使得给定的路径为当前最短路径。

题型：构造，模拟

原因：map不熟，要判两个地方，一是不重复抵达，二是当前点除去前导点旁边的点不能事先经过。

解法：按照上面说的模拟一下就可以，这种方法相对来说效率高，但是代码写得多。可以直接遍历：一个点跟其后面步长大于1的点的距离不能小于1。

PS：make_pair的使用方法

map中key值为结构体的用法

#include <iostream>

#include <string.h>

#include <algorithm>

#include <stdio.h>

#include <string>

#include <map>

#include <vector>

#include <cmath>

#include <set>

#define ll long long

#define PI 3.1415926535

#define AC ios::sync_with_stdio(0)

using namespace std;

const int inf=1e5+;

#define u dit[1];

bool cmp(const string& a,const string& b)

{

  return a.length()<b.length();

}

struct pt{

    int x;

    int y;

    bool operator<(const pt&a)const{   //key为结构体时时要重载<

       if(x<a.x)

        return true;

       else if(x==a.x)

        return y<a.y;

       return false;

    }

};

map<pt,int>mp;

//int dit[4][2]={-1,0,0,1,1,0,0,-1};

string s;

int main()

{

      ios::sync_with_stdio();

      cin>>s;

      pt st;

      st.x=;

      st.y=;

      mp.insert(make_pair(st,));   //忘记了 wa了

      for(int i=;i<s.length();i++)

      {

            if(s[i]=='U')

          {

             st.x--;

             pt a={st.x-,st.y},b={st.x,st.y+},c={st.x,st.y-};

             if(mp.count(a)||mp.count(b)||mp.count(c))

             {

                cout<<"BUG"<<endl;

                 return ;

             }

          }

          if(s[i]=='D')

          {

             st.x++;

             pt a={st.x+,st.y},b={st.x,st.y+},c={st.x,st.y-};

             if(mp.count(a)||mp.count(b)||mp.count(c))

             {

                cout<<"BUG"<<endl;

                 return ;

             }

          }

          if(s[i]=='R')

          {

              st.y++;

              pt a={st.x+,st.y},b={st.x-,st.y},c={st.x,st.y+};

              if(mp.count(a)||mp.count(b)||mp.count(c))

            {

                cout<<"BUG"<<endl;

                 return ;

            }

          }

          if(s[i]=='L')

          {

             st.y--;

             pt a={st.x+,st.y},b={st.x-,st.y},c={st.x,st.y-};

             if(mp.count(a)||mp.count(b)||mp.count(c))

             {

                cout<<"BUG"<<endl;

                 return ;

             }

          }

          if(mp.count(st))

          {

                cout<<"BUG"<<endl;

              return ;

          }

            mp.insert(make_pair(st,));  //要用make_pair因为不会调用构造函数

      }

      cout<<"OK"<<endl;

}
/*下面是楼教主当年的代码*/

#include <vector>

#include <list>

#include <map>

#include <set>

#include <deque>

#include <queue>

#include <stack>

#include <bitset>

#include <algorithm>

#include <functional>

#include <numeric>

#include <utility>

#include <sstream>

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <cctype>

#include <string>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <ctime>

using namespace std;

//BEGINTEMPLATE_BY_ACRUSH_TOPCODER

#define SIZE(X) ((int)(X.size()))//NOTES:SIZE(

#define LENGTH(X) ((int)(X.length()))//NOTES:LENGTH(

#define MP(X,Y) make_pair(X,Y)//NOTES:MP(

typedef long long int64;//NOTES:int64

typedef unsigned long long uint64;//NOTES:uint64

#define two(X) (1<<(X))//NOTES:two(

#define twoL(X) (((int64)(1))<<(X))//NOTES:twoL(

#define contain(S,X) (((S)&two(X))!=0)//NOTES:contain(

#define containL(S,X) (((S)&twoL(X))!=0)//NOTES:containL(

const double pi=acos(-1.0);//NOTES:pi

const double eps=1e-;//NOTES:eps

template<class T> inline void checkmin(T &a,T b){if(b<a) a=b;}//NOTES:checkmin(

template<class T> inline void checkmax(T &a,T b){if(b>a) a=b;}//NOTES:checkmax(

template<class T> inline T sqr(T x){return x*x;}//NOTES:sqr

typedef pair<int,int> ipair;//NOTES:ipair

template<class T> inline T lowbit(T n){return (n^(n-))&n;}//NOTES:lowbit(

template<class T> inline int countbit(T n){return (n==)?:(+countbit(n&(n-)));}//NOTES:countbit(

//Numberic Functions

template<class T> inline T gcd(T a,T b)//NOTES:gcd(

  {if(a<)return gcd(-a,b);if(b<)return gcd(a,-b);return (b==)?a:gcd(b,a%b);}

template<class T> inline T lcm(T a,T b)//NOTES:lcm(

  {if(a<)return lcm(-a,b);if(b<)return lcm(a,-b);return a*(b/gcd(a,b));}

template<class T> inline T euclide(T a,T b,T &x,T &y)//NOTES:euclide(

  {if(a<){T d=euclide(-a,b,x,y);x=-x;return d;}

   if(b<){T d=euclide(a,-b,x,y);y=-y;return d;}

   if(b==){x=;y=;return a;}else{T d=euclide(b,a%b,x,y);T t=x;x=y;y=t-(a/b)*y;return d;}}

template<class T> inline vector<pair<T,int> > factorize(T n)//NOTES:factorize(

  {vector<pair<T,int> > R;for (T i=;n>;){if (n%i==){int C=;for (;n%i==;C++,n/=i);R.push_back(make_pair(i,C));}

   i++;if (i>n/i) i=n;}if (n>) R.push_back(make_pair(n,));return R;}

template<class T> inline bool isPrimeNumber(T n)//NOTES:isPrimeNumber(

  {if(n<=)return false;for (T i=;i*i<=n;i++) if (n%i==) return false;return true;}

template<class T> inline T eularFunction(T n)//NOTES:eularFunction(

  {vector<pair<T,int> > R=factorize(n);T r=n;for (int i=;i<R.size();i++)r=r/R[i].first*(R[i].first-);return r;}

//Matrix Operations

const int MaxMatrixSize=;//NOTES:MaxMatrixSize

template<class T> inline void showMatrix(int n,T A[MaxMatrixSize][MaxMatrixSize])//NOTES:showMatrix(

  {for (int i=;i<n;i++){for (int j=;j<n;j++)cout<<A[i][j];cout<<endl;}}

template<class T> inline T checkMod(T n,T m) {return (n%m+m)%m;}//NOTES:checkMod(

template<class T> inline void identityMatrix(int n,T A[MaxMatrixSize][MaxMatrixSize])//NOTES:identityMatrix(

  {for (int i=;i<n;i++) for (int j=;j<n;j++) A[i][j]=(i==j)?:;}

template<class T> inline void addMatrix(int n,T C[MaxMatrixSize][MaxMatrixSize],T A[MaxMatrixSize][MaxMatrixSize],T B[MaxMatrixSize][MaxMatrixSize])//NOTES:addMatrix(

  {for (int i=;i<n;i++) for (int j=;j<n;j++) C[i][j]=A[i][j]+B[i][j];}

template<class T> inline void subMatrix(int n,T C[MaxMatrixSize][MaxMatrixSize],T A[MaxMatrixSize][MaxMatrixSize],T B[MaxMatrixSize][MaxMatrixSize])//NOTES:subMatrix(

  {for (int i=;i<n;i++) for (int j=;j<n;j++) C[i][j]=A[i][j]-B[i][j];}

template<class T> inline void mulMatrix(int n,T C[MaxMatrixSize][MaxMatrixSize],T _A[MaxMatrixSize][MaxMatrixSize],T _B[MaxMatrixSize][MaxMatrixSize])//NOTES:mulMatrix(

  { T A[MaxMatrixSize][MaxMatrixSize],B[MaxMatrixSize][MaxMatrixSize];

  for (int i=;i<n;i++) for (int j=;j<n;j++) A[i][j]=_A[i][j],B[i][j]=_B[i][j],C[i][j]=;

  for (int i=;i<n;i++) for (int j=;j<n;j++) for (int k=;k<n;k++) C[i][j]+=A[i][k]*B[k][j];}

template<class T> inline void addModMatrix(int n,T m,T C[MaxMatrixSize][MaxMatrixSize],T A[MaxMatrixSize][MaxMatrixSize],T B[MaxMatrixSize][MaxMatrixSize])//NOTES:addModMatrix(

  {for (int i=;i<n;i++) for (int j=;j<n;j++) C[i][j]=checkMod(A[i][j]+B[i][j],m);}

template<class T> inline void subModMatrix(int n,T m,T C[MaxMatrixSize][MaxMatrixSize],T A[MaxMatrixSize][MaxMatrixSize],T B[MaxMatrixSize][MaxMatrixSize])//NOTES:subModMatrix(

  {for (int i=;i<n;i++) for (int j=;j<n;j++) C[i][j]=checkMod(A[i][j]-B[i][j],m);}

template<class T> inline T multiplyMod(T a,T b,T m) {return (T)((((int64)(a)*(int64)(b)%(int64)(m))+(int64)(m))%(int64)(m));}//NOTES:multiplyMod(

template<class T> inline void mulModMatrix(int n,T m,T C[MaxMatrixSize][MaxMatrixSize],T _A[MaxMatrixSize][MaxMatrixSize],T _B[MaxMatrixSize][MaxMatrixSize])//NOTES:mulModMatrix(

  { T A[MaxMatrixSize][MaxMatrixSize],B[MaxMatrixSize][MaxMatrixSize];

  for (int i=;i<n;i++) for (int j=;j<n;j++) A[i][j]=_A[i][j],B[i][j]=_B[i][j],C[i][j]=;

  for (int i=;i<n;i++) for (int j=;j<n;j++) for (int k=;k<n;k++) C[i][j]=(C[i][j]+multiplyMod(A[i][k],B[k][j],m))%m;}

template<class T> inline T powerMod(T p,int e,T m)//NOTES:powerMod(

  {if(e==)return %m;else if(e%==){T t=powerMod(p,e/,m);return multiplyMod(t,t,m);}else return multiplyMod(powerMod(p,e-,m),p,m);}

//Point&Line

double dist(double x1,double y1,double x2,double y2){return sqrt(sqr(x1-x2)+sqr(y1-y2));}//NOTES:dist(

double distR(double x1,double y1,double x2,double y2){return sqr(x1-x2)+sqr(y1-y2);}//NOTES:distR(

template<class T> T cross(T x0,T y0,T x1,T y1,T x2,T y2){return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);}//NOTES:cross(

int crossOper(double x0,double y0,double x1,double y1,double x2,double y2)//NOTES:crossOper(

  {double t=(x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);if (fabs(t)<=eps) return ;return (t<)?-:;}

bool isIntersect(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4)//NOTES:isIntersect(

  {return crossOper(x1,y1,x2,y2,x3,y3)*crossOper(x1,y1,x2,y2,x4,y4)< && crossOper(x3,y3,x4,y4,x1,y1)*crossOper(x3,y3,x4,y4,x2,y2)<;}

bool isMiddle(double s,double m,double t){return fabs(s-m)<=eps || fabs(t-m)<=eps || (s<m)!=(t<m);}//NOTES:isMiddle(

//Translator

bool isUpperCase(char c){return c>='A' && c<='Z';}//NOTES:isUpperCase(

bool isLowerCase(char c){return c>='a' && c<='z';}//NOTES:isLowerCase(

bool isLetter(char c){return c>='A' && c<='Z' || c>='a' && c<='z';}//NOTES:isLetter(

bool isDigit(char c){return c>='' && c<='';}//NOTES:isDigit(

char toLowerCase(char c){return (isUpperCase(c))?(c+):c;}//NOTES:toLowerCase(

char toUpperCase(char c){return (isLowerCase(c))?(c-):c;}//NOTES:toUpperCase(

template<class T> string toString(T n){ostringstream ost;ost<<n;ost.flush();return ost.str();}//NOTES:toString(

int toInt(string s){int r=;istringstream sin(s);sin>>r;return r;}//NOTES:toInt(

int64 toInt64(string s){int64 r=;istringstream sin(s);sin>>r;return r;}//NOTES:toInt64(

double toDouble(string s){double r=;istringstream sin(s);sin>>r;return r;}//NOTES:toDouble(

template<class T> void stoa(string s,int &n,T A[]){n=;istringstream sin(s);for(T v;sin>>v;A[n++]=v);}//NOTES:stoa(

template<class T> void atos(int n,T A[],string &s){ostringstream sout;for(int i=;i<n;i++){if(i>)sout<<' ';sout<<A[i];}s=sout.str();}//NOTES:atos(

template<class T> void atov(int n,T A[],vector<T> &vi){vi.clear();for (int i=;i<n;i++) vi.push_back(A[i]);}//NOTES:atov(

template<class T> void vtoa(vector<T> vi,int &n,T A[]){n=vi.size();for (int i=;i<n;i++)A[i]=vi[i];}//NOTES:vtoa(

template<class T> void stov(string s,vector<T> &vi){vi.clear();istringstream sin(s);for(T v;sin>>v;vi.push_bakc(v));}//NOTES:stov(

template<class T> void vtos(vector<T> vi,string &s){ostringstream sout;for (int i=;i<vi.size();i++){if(i>)sout<<' ';sout<<vi[i];}s=sout.str();}//NOTES:vtos(

//Fraction

template<class T> struct Fraction{T a,b;Fraction(T a=,T b=);string toString();};//NOTES:Fraction

  template<class T> Fraction<T>::Fraction(T a,T b){T d=gcd(a,b);a/=d;b/=d;if (b<) a=-a,b=-b;this->a=a;this->b=b;}

  template<class T> string Fraction<T>::toString(){ostringstream sout;sout<<a<<"/"<<b;return sout.str();}

  template<class T> Fraction<T> operator+(Fraction<T> p,Fraction<T> q){return Fraction<T>(p.a*q.b+q.a*p.b,p.b*q.b);}

  template<class T> Fraction<T> operator-(Fraction<T> p,Fraction<T> q){return Fraction<T>(p.a*q.b-q.a*p.b,p.b*q.b);}

  template<class T> Fraction<T> operator*(Fraction<T> p,Fraction<T> q){return Fraction<T>(p.a*q.a,p.b*q.b);}

  template<class T> Fraction<T> operator/(Fraction<T> p,Fraction<T> q){return Fraction<T>(p.a*q.b,p.b*q.a);}

//ENDTEMPLATE_BY_ACRUSH_TOPCODER

int main()

{

#ifdef _MSC_VER

    freopen("input.txt","r",stdin);

#endif

    int x[],y[];

    x[]=y[]=;

    int n=;

    char s[];

    scanf("%s",s);

    for (int i=;s[i];i++)

    {

        x[n]=x[n-];

        y[n]=y[n-];

        if (s[i]=='L') x[n]--;

        if (s[i]=='R') x[n]++;

        if (s[i]=='U') y[n]--;

        if (s[i]=='D') y[n]++;

        n++;

    }

    bool isGood=true;

    for (int i=;i<n;i++)

        for (int j=i+;j<n;j++)

            if (abs(x[i]-x[j])+abs(y[i]-y[j])<=)

                isGood=false;

    if (isGood)

        printf("OK\n");

    else

        printf("BUG\n");

    return ;

}

最新文章

  1. Sql Server R2还有备份数据库错误
  2. 从零开始，做一个NodeJS博客（一）：Heroku上的最简NodeJS服务器
  3. SQLLDR 教程
  4. 智能车学习（一）&mdash;&mdash; 硬件准备
  5. Asp.net Core WebApi 全局异常类
  6. 关于java中普通代码块、构造代码块与静态代码块
  7. POJ 3734
  8. Egret index.html设置
  9. JavaScript设计模式--简单工厂模式例子---XHR工厂
  10. Mysql执行计划说明
  11. (链表 importance) leetcode 2. Add Two Numbers
  12. Java利用ShutDownHook关闭系统资源
  13. 查找单链表中倒数第K个位置上的结点，若查找成功返回该节点的data域，若不成功只返回0
  14. BZOJ2223[Coci 2009]PATULJCI——主席树
  15. Fix Corrupt Blocks on HDFS
  16. 怎么让win7右下角只显示时间不显示日期 ？(可行）
  17. .NET 中使用 TaskCompletionSource 作为线程同步互斥或异步操作的事件
  18. 【转】python基础-编码与解码
  19. angular基于ui-router实现系统权限控制
  20. SQL Server 中SELECT INTO 和 INSERT INTO SELECT 两种表复制语句

热门文章

  1. worker pool Handling 1 Million Requests per Minute with Golang
  2. 刷榜中ASO优化中下载量与评论之间的对应比
  3. synchronized和Lock复习
  4. NoSQL入门
  5. Elasticsearch学习笔记（五）索引元数据和集群元数据
  6. Spark入门到精通--（第八节）环境搭建（Hadoop搭建）
  7. numpy（一）
  8. springcloud第二步：发布服务提供者
  9. Random-Forest-Python
  10. 原生js 基于canvas写一个简单的前端 截图工具