长沙网站托管优化,哪个网站做视频钱多,网络营销推广方案模板,湖州哪里做网站先上题目#xff1a; https://icpcarchive.ecs.baylor.edu/external/67/6755.pdf 题目复制起来比较麻烦。 题意#xff1a;定义一种操作#xff1a;给出一个字符串#xff0c;然后手指就按照给出的字符串的字符出现顺序不离开触摸屏那样移动#xff0c;这样最后就会得到一…先上题目 https://icpcarchive.ecs.baylor.edu/external/67/6755.pdf 题目复制起来比较麻烦。 题意定义一种操作给出一个字符串然后手指就按照给出的字符串的字符出现顺序不离开触摸屏那样移动这样最后就会得到一个字符串(不一定等于给出的字符串)现在再给你一堆字符串问你这些字符串根据给你的顺序最先出现的是哪一个字符串是得到的那个字符串的子序列。如果没有出现的话就输出NO SOLUTION。 做法先求出那个字符串然后再逐个逐个字符串找。关于怎样求这个字符串说起来好像有点复杂大概的做法就是在判断划过某两个字符的过程中会有哪些字符的时候先缩小枚举的范围然后对于范围里面的每一个字符都进行一次判断判断的方法是使用叉积来判断如果这个判断的字符的四个角不都在原来的那两个字符连成的线段的一侧的话说明就是穿过的(注意刚好在线上的情况)。具体实现看代码。 上代码 1 #include cstdio2 #include cstring3 #include cmath4 #include algorithm5 #include iostream6 #include string7 #define APH 268 #define MAX 10029 using namespace std;10 11 12 typedef struct Point{13 int x,y;14 15 Point(int x0,int y0):x(x),y(y){}16 17 }Point;18 typedef Point Vector;19 Vector operator (Point A,Point B){ return Vector(B.xA.x,B.yA.y);}20 Vector operator - (Point A,Point B){ return Vector(B.x-A.x,B.y-A.y);}21 Vector operator * (Point A,int e){ return Point(A.x*e,A.y*e);}22 Vector operator / (Point A,int e){ return Point(A.x/e,A.y/e);}23 24 int Dot(Vector A,Vector B){ return A.x*B.x A.y*B.y;}25 inline int Cross(Vector A,Vector B){ return A.x*B.y - A.y*B.x;}26 27 int cx[]{-1,1,1,-1};28 int cy[]{1,1,-1,-1};29 30 string path[APH][APH];31 Point pos[APH];32 char ch[APH][APH];33 34 Point getPoint(char c){35 if(cE) return Point(c-A2,4);36 else{37 return Point((c-F)%71,3-(c-F)/7);38 }39 }40 41 bool check(Point A,Point B,Point C){42 bool b0,l0;43 A.x*2; A.y*2;44 B.x*2; B.y*2;45 C.x*2; C.y*2;46 Point u;47 for(int i0;i4;i){48 uPoint(C.xcx[i],C.ycy[i]);49 if(Cross(A-u,B-u)0) b|1;50 if(Cross(A-u,B-u)0) l|1;51 }52 return bl;53 }54 55 string GetPath(int a,int b){56 string ans;57 if(ab) return ans;58 int axpos[a].x,aypos[a].y;59 int bxpos[b].x,bypos[b].y;60 for(int i ax ; (ax bx ? ibx : ibx) ; (ax bx ? i : i--) ){61 for(int j ay ; (ay by ? jby : jby) ; (ay by ? j : j--)){62 if(ch[i][j]0) continue;63 if(check(pos[a],pos[b],pos[ch[i][j]-A])) ansch[i][j];64 }65 }66 //if(ans.length()1) return ;67 ans ans.substr(1,max((int)(ans.length()-2),0));68 //coutansendl;69 return ans;70 }71 72 void prepare(){73 memset(ch,0,sizeof(ch));74 for(int i0;iAPH;i){75 pos[i]getPoint(Ai);76 ch[pos[i].x][pos[i].y]Ai;77 // coutch[pos[i].x][pos[i].y] ;78 }79 // coutendl;80 for(int i0;iAPH;i){81 for(int j0;jAPH;j){82 path[i][j]GetPath(i,j);83 // coutpath[i][j]endl;84 }85 }86 }87 88 string connect(string st){89 string ans;90 ansst[0];91 for(unsigned int i1;ist.length();i){92 anspath[st[i-1]-A][st[i]-A];93 ansst[i];94 }95 //ansst[st.length()-1];96 return ans;97 }98 99 bool check_str(string s,string str){
100 unsigned i,j;
101 for(i0,j0;is.length();i){
102 if(s[i]str[j]){
103 j;
104 if(jstr.length()) return 1;
105 }
106 }
107 return 0;
108 }
109
110 int main()
111 {
112 int t,n;
113 string st,s,str;
114 //freopen(data.txt,r,stdin);
115 ios::sync_with_stdio(false);
116 prepare();
117 cint;
118 while(t--){
119 cinnst;
120 sconnect(st);
121 //cout* sendl;
122 bool f0;
123 for(int i0;in;i){
124 cinstr;
125 //coutstrendl;
126 if(!f check_str(s,str)){
127 f1;
128 coutstrendl;
129 }
130 }
131 if(!f) coutNO SOLUTIONendl;
132 }
133 return 0;
134 } /*6755*/ 转载于:https://www.cnblogs.com/sineatos/p/3969014.html
