UVAL - 6755 - Swyper Keyboard
2024-09-30 22:41:32
先上题目:
https://icpcarchive.ecs.baylor.edu/external/67/6755.pdf
题目复制起来比较麻烦。
题意:定义一种操作:给出一个字符串,然后手指就按照给出的字符串的字符出现顺序不离开触摸屏那样移动,这样最后就会得到一个字符串(不一定等于给出的字符串),现在再给你一堆字符串,问你这些字符串根据给你的顺序,最先出现的是哪一个字符串是得到的那个字符串的子序列。如果没有出现的话就输出"NO SOLUTION"。
做法:先求出那个字符串,然后再逐个逐个字符串找。关于怎样求这个字符串,说起来好像有点复杂,大概的做法就是在判断划过某两个字符的过程中会有哪些字符的时候,先缩小枚举的范围,然后对于范围里面的每一个字符都进行一次判断,判断的方法是使用叉积来判断,如果这个判断的字符的四个角不都在原来的那两个字符连成的线段的一侧的话说明就是穿过的(注意刚好在线上的情况)。具体实现看代码。
上代码:
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#define APH 26
#define MAX 1002
using namespace std; typedef struct Point{
int x,y; Point(int x=,int y=):x(x),y(y){} }Point;
typedef Point Vector;
Vector operator + (Point A,Point B){ return Vector(B.x+A.x,B.y+A.y);}
Vector operator - (Point A,Point B){ return Vector(B.x-A.x,B.y-A.y);}
Vector operator * (Point A,int e){ return Point(A.x*e,A.y*e);}
Vector operator / (Point A,int e){ return Point(A.x/e,A.y/e);} int Dot(Vector A,Vector B){ return A.x*B.x + A.y*B.y;}
inline int Cross(Vector A,Vector B){ return A.x*B.y - A.y*B.x;} int cx[]={-,,,-};
int cy[]={,,-,-}; string path[APH][APH];
Point pos[APH];
char ch[APH][APH]; Point getPoint(char c){
if(c<='E') return Point(c-'A'+,);
else{
return Point((c-'F')%+,-(c-'F')/);
}
} bool check(Point A,Point B,Point C){
bool b=,l=;
A.x*=; A.y*=;
B.x*=; B.y*=;
C.x*=; C.y*=;
Point u;
for(int i=;i<;++i){
u=Point(C.x+cx[i],C.y+cy[i]);
if(Cross(A-u,B-u)>) b|=;
if(Cross(A-u,B-u)<) l|=;
}
return b&&l;
} string GetPath(int a,int b){
string ans="";
if(a==b) return ans;
int ax=pos[a].x,ay=pos[a].y;
int bx=pos[b].x,by=pos[b].y;
for(int i= ax ; (ax < bx ? i<=bx : i>=bx) ; (ax < bx ? i++ : i--) ){
for(int j= ay ; (ay < by ? j<=by : j>=by) ; (ay < by ? j++ : j--)){
if(ch[i][j]==) continue;
if(check(pos[a],pos[b],pos[ch[i][j]-'A'])) ans+=ch[i][j];
}
}
//if(ans.length()<=1) return "";
ans = ans.substr(,max((int)(ans.length()-),));
//cout<<ans<<endl;
return ans;
} void prepare(){
memset(ch,,sizeof(ch));
for(int i=;i<APH;i++){
pos[i]=getPoint('A'+i);
ch[pos[i].x][pos[i].y]='A'+i;
// cout<<ch[pos[i].x][pos[i].y]<<" ";
}
// cout<<endl;
for(int i=;i<APH;i++){
for(int j=;j<APH;j++){
path[i][j]=GetPath(i,j);
// cout<<path[i][j]<<endl;
}
}
} string connect(string st){
string ans;
ans+=st[];
for(unsigned int i=;i<st.length();i++){
ans+=path[st[i-]-'A'][st[i]-'A'];
ans+=st[i];
}
//ans+=st[st.length()-1];
return ans;
} bool check_str(string s,string str){
unsigned i,j;
for(i=,j=;i<s.length();i++){
if(s[i]==str[j]){
j++;
if(j==str.length()) return ;
}
}
return ;
} int main()
{
int t,n;
string st,s,str;
//freopen("data.txt","r",stdin);
ios::sync_with_stdio(false);
prepare();
cin>>t;
while(t--){
cin>>n>>st;
s=connect(st);
//cout<<"* "<<s<<endl;
bool f=;
for(int i=;i<n;i++){
cin>>str;
//cout<<str<<endl;
if(!f && check_str(s,str)){
f=;
cout<<str<<endl;
}
}
if(!f) cout<<"NO SOLUTION"<<endl;
}
return ;
}
/*6755*/
最新文章
- CODEVS1090 加分二叉树
- In和Out指令
- 从Unity学UE(一)之蓝图类的使用----制作一个可控灯光
- java文件操作(读流)
- 查看SQL执行计划
- 【python】闰年规则
- 【动态页面】(二)Java反射
- 八 Appium常用方法介绍
- [转]tomcat部署
- AES高级加密标准简析
- android使用sharesdk的小感
- mpvue——API请求封装(小程序原生)
- bzoj1875 边点互换+矩乘
- 使用docker redis-cluster集群搭建
- WPF显示图片
- 生成一个文件夹中的所有文件的txt列表
- WorldWind源码剖析系列:插件列表视图类PluginListView和插件列表视图项类PluginListItem
- struts与ognl结合【重要】
- C语言中的序列点
- Hibernate_day04--HQL多表查询_Hibernate检索策略