8A用string.find即可，我比较sb的以为string.rfind()和reversestring.find()是一样的，怎么都过不去，被打击透了。
8B开始想的太简单，以为就判断终点是否在中途访问过即可。lur这种情况明显不符合，然后改成bfs，好久没写竟然忘记标记以访问过，搞的mle咯，想了半天才记起来这点...
8C 弱鸡又见dp，无从下手，看了看别人的代码，都说是状态dp，然后拿东西顺序无关，这得好好理解下咯。照例贴大牛代码琢磨...
#include<iostream> #include<string> using namespace std; int main() { string ostr,str1,str2; bool ff=false,bf=false; cin>>ostr>>str1>>str2; unsigned int s; if((s=ostr.find(str1))!=string::npos&&ostr.rfind(str2)>(s+str1.length()-1)) ff=true; unsigned int ss; string bostr(ostr.rbegin(),ostr.rend()); if((s=bostr.find(str1))!=string::npos&&bostr.find(str2,s+str1.length())!=-1) bf=true; if(ff&&bf) cout<<"both"<<endl; else if(ff&&!bf) cout<<"forward"<<endl; else if(!ff&&bf) cout<<"backward"<<endl; else cout<<"fantasy"<<endl; return 0; }
#include<iostream> #include<deque> using namespace std; int robotmap[201][201]; int main() { char str[110]={0}; cin>>str; int lc=0,rc=0,uc=0,dc=0; int x=100,y=100; for(int i=0;i<strlen(str);i++) { if(str[i]=='L') lc++; if(str[i]=='R') rc++; if(str[i]=='U') uc++; if(str[i]=='D') dc++; } if(lc==rc&&rc==dc&&dc==uc) { cout<<"BUG"<<endl; return 0; } else { robotmap[100][100]=1; for(int i=0;i<strlen(str);i++) { if(str[i]=='L') x--; if(str[i]=='R') x++; if(str[i]=='U') y--; if(str[i]=='D') y++; if(robotmap[x][y]==1) { cout<<"BUG"<<endl; return 0; } robotmap[x][y]=1; } } struct xy { int x,y; xy(int tx,int ty):x(tx),y(ty){} xy(){} }; deque<pair<xy,int> >deq; deq.push_back(make_pair(xy(100,100),0)); pair<xy,int> var; int tx,ty; while(!deq.empty()) { var=deq.front(); if(var.first.x==x&&var.first.y==y&&var.second<strlen(str)) { cout<<"BUG"<<endl; return 0; } if(var.first.x==x&&var.first.y==y&&var.second==strlen(str)) { cout<<"OK"<<endl; return 0; } deq.pop_front(); tx=var.first.x; ty=var.first.y; if(tx>0&&robotmap[tx-1][ty]==1) deq.push_back(make_pair(xy(tx-1,ty),var.second+1)),robotmap[tx-1][ty]=2; if(tx<200&&robotmap[tx+1][ty]==1) deq.push_back(make_pair(xy(tx+1,ty),var.second+1)),robotmap[tx+1][ty]=2; if(ty>0&&robotmap[tx][ty-1]==1) deq.push_back(make_pair(xy(tx,ty-1),var.second+1)),robotmap[tx][ty-1]=2; if(ty<200&&robotmap[tx][ty+1]==1) deq.push_back(make_pair(xy(tx,ty+1),var.second+1)),robotmap[tx][ty+1]=2; } cout<<"OK"<<endl; return 0; }
#include<iostream> #include<stdio.h> #include<string.h> #include<cmath> #include<queue> #include<stack> #include<set> #include<algorithm> #define ll long long #define oo 1000000007 #define pi acos(-1.0) #define MAXN 24 using namespace std; int girl[2],objects[MAXN][2],dp[1<<MAXN],pre[1<<MAXN]; int arc[MAXN+1][MAXN+1]; int dis(int ax,int ay,int bx,int by) { int x=ax-bx,y=ay-by; return x*x+y*y; } int main() { int n,i,x,t,p,goal; int temp; while (~scanf("%d%d",&girl[0],&girl[1])) { scanf("%d",&n); for (i=0;i<n;i++) scanf("%d%d",&objects[i][0],&objects[i][1]); for (i=1;i<=n;i++) arc[i][0]=arc[0][i]=dis(girl[0],girl[1],objects[i-1][0],objects[i-1][1]); for (i=1;i<=n;i++) for (x=i;x<=n;x++) arc[i][x]=arc[x][i]=dis(objects[i-1][0],objects[i-1][1],objects[x-1][0],objects[x-1][1]); memset(pre,-1,sizeof(pre)); dp[0]=0; goal=(1<<n)-1; for (t=1;t<=goal;t++) for (i=0;i<n;i++) if (t & (1<<i)) { temp=arc[0][i+1]<<1; p=(t^(1<<i)); if (pre[t]==-1 || dp[t]>dp[p]+temp) dp[t]=dp[p]+temp,pre[t]=p; for (x=i+1;x<n;x++) if (t & (1<<x)) { temp=arc[0][i+1]+arc[0][x+1]+arc[i+1][x+1]; p=t^(1<<i)^(1<<x); if (pre[t]==-1 || dp[t]>dp[p]+temp) dp[t]=dp[p]+temp,pre[t]=p; } break; //关键 } x=goal; printf("%d ",dp[x]); while (x) { printf("0 "); t=pre[x]; for (i=0;i<n;i++) if ((x & (1<<i)) && !(t & (1<<i))) printf("%d ",i+1); x=t; } printf("0 "); } return 0; } /* 0 0 24 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 3 0 3 1 3 2 3 3 3 4 */