首页 > 代码库 > UVAL - 6755 - Swyper Keyboard
UVAL - 6755 - Swyper Keyboard
先上题目：
https://icpcarchive.ecs.baylor.edu/external/67/6755.pdf
题目复制起来比较麻烦。
题意：定义一种操作：给出一个字符串，然后手指就按照给出的字符串的字符出现顺序不离开触摸屏那样移动，这样最后就会得到一个字符串(不一定等于给出的字符串)，现在再给你一堆字符串，问你这些字符串根据给你的顺序，最先出现的是哪一个字符串是得到的那个字符串的子序列。如果没有出现的话就输出"NO SOLUTION"。
做法：先求出那个字符串，然后再逐个逐个字符串找。关于怎样求这个字符串，说起来好像有点复杂，大概的做法就是在判断划过某两个字符的过程中会有哪些字符的时候，先缩小枚举的范围，然后对于范围里面的每一个字符都进行一次判断，判断的方法是使用叉积来判断，如果这个判断的字符的四个角不都在原来的那两个字符连成的线段的一侧的话说明就是穿过的(注意刚好在线上的情况)。具体实现看代码。
上代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #include <iostream> 6 #include <string> 7 #define APH 26 8 #define MAX 1002 9 using namespace std; 10 11 12 typedef struct Point{ 13 int x,y; 14 15 Point(int x=0,int y=0):x(x),y(y){} 16 17 }Point; 18 typedef Point Vector; 19 Vector operator + (Point A,Point B){ return Vector(B.x+A.x,B.y+A.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(c<=‘E‘) return Point(c-‘A‘+2,4); 36 else{ 37 return Point((c-‘F‘)%7+1,3-(c-‘F‘)/7); 38 } 39 } 40 41 bool check(Point A,Point B,Point C){ 42 bool b=0,l=0; 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 i=0;i<4;++i){ 48 u=Point(C.x+cx[i],C.y+cy[i]); 49 if(Cross(A-u,B-u)>0) b|=1; 50 if(Cross(A-u,B-u)<0) l|=1; 51 } 52 return b&&l; 53 } 54 55 string GetPath(int a,int b){ 56 string ans=""; 57 if(a==b) return ans; 58 int ax=pos[a].x,ay=pos[a].y; 59 int bx=pos[b].x,by=pos[b].y; 60 for(int i= ax ; (ax < bx ? i<=bx : i>=bx) ; (ax < bx ? i++ : i--) ){ 61 for(int j= ay ; (ay < by ? j<=by : j>=by) ; (ay < by ? j++ : j--)){ 62 if(ch[i][j]==0) continue; 63 if(check(pos[a],pos[b],pos[ch[i][j]-‘A‘])) ans+=ch[i][j]; 64 } 65 } 66 //if(ans.length()<=1) return ""; 67 ans = ans.substr(1,max((int)(ans.length()-2),0)); 68 //cout<<ans<<endl; 69 return ans; 70 } 71 72 void prepare(){ 73 memset(ch,0,sizeof(ch)); 74 for(int i=0;i<APH;i++){ 75 pos[i]=getPoint(‘A‘+i); 76 ch[pos[i].x][pos[i].y]=‘A‘+i; 77 // cout<<ch[pos[i].x][pos[i].y]<<" "; 78 } 79 // cout<<endl; 80 for(int i=0;i<APH;i++){ 81 for(int j=0;j<APH;j++){ 82 path[i][j]=GetPath(i,j); 83 // cout<<path[i][j]<<endl; 84 } 85 } 86 } 87 88 string connect(string st){ 89 string ans; 90 ans+=st[0]; 91 for(unsigned int i=1;i<st.length();i++){ 92 ans+=path[st[i-1]-‘A‘][st[i]-‘A‘]; 93 ans+=st[i]; 94 } 95 //ans+=st[st.length()-1]; 96 return ans; 97 } 98 99 bool check_str(string s,string str){100 unsigned i,j;101 for(i=0,j=0;i<s.length();i++){102 if(s[i]==str[j]){103 j++;104 if(j==str.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 cin>>t;118 while(t--){119 cin>>n>>st;120 s=connect(st);121 //cout<<"* "<<s<<endl;122 bool f=0;123 for(int i=0;i<n;i++){124 cin>>str;125 //cout<<str<<endl;126 if(!f && check_str(s,str)){127 f=1;128 cout<<str<<endl;129 }130 }131 if(!f) cout<<"NO SOLUTION"<<endl;132 }133 return 0;134 }
UVAL - 6755 - Swyper Keyboard
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。