首页 > 代码库 > NOIP2017模拟赛 senior 6.29 T2 小T的钢琴（piano）
NOIP2017模拟赛 senior 6.29 T2 小T的钢琴（piano）
NOIP2017模拟赛 senior 6.29 T2 小T的钢琴（piano）
Description
Input
Output
这道题思路还是比较好想的，因为题目中已经提到公共子序列长度，所以咯，最长公共子序列好不好！
But，这里我们如果只使用LCS的话那么，这里我们的时间复杂度是O(n^2)。爆了对不对？
怎么优化呢？
对于我们的比较，在这里是比较的字符串对吧，即每一坨音符。使用string可直接比较，所以常数会小一点。
更好一点的优化就是使用哈希表，我们将乐谱Little_T中的字符串哈希，转成数值，然后通过哈希值判断，将乐谱B中的无效的音符去除。这里直接比较哈希值，常数更小。
但是，我们还是不能拿满分对吧。
我们再来优化！
题目中有提到：因为小T是一个放荡不羁的作曲家，所以保证他的乐谱中每个音符都不会重复出现。
看到这里我们是不是还可以优化呢？
有了这个条件，我们可以把LCS问题传唤成LIS（最长上升子序列）问题。
预处理还是一样的，哈希，不过我这里较为简便的直接将每一个字符转换为数值后，如果继续有字符需要加入，那么我们将先前数值乘10再相加。
我们使用二分查找，将乐谱B中数值拿入Little_T中去找，找不到，跳过。
找到了，我们从这里开始使用LIS求解就好了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<string> 7 #define INT_MAX_ 0x7fffffff 8 #define LONG_MAX_ 0x7fffffffffffffffll 9 #define pi acos(-1) 10 #define N 100010 11 #define M 200010 12 using namespace std; 13 14 inline int read() 15 { 16 int data=http://www.mamicode.com/0,w=1; 17 char ch=0; 18 while(ch!=‘-‘ && (ch<‘0‘ || ch>‘9‘)) ch=getchar(); 19 if(ch==‘-‘) w=-1,ch=getchar(); 20 while(ch>=‘0‘ && ch<=‘9‘) data=http://www.mamicode.com/data*10+ch-‘0‘,ch=getchar(); 21 return data*w; 22 } 23 24 inline void write(int x) 25 { 26 if(x<0) putchar(‘-‘),x=-x; 27 if(x>9) write(x/10); 28 putchar(x%10+‘0‘); 29 } 30 31 struct Data 32 { 33 int value,number; 34 } data[N]; 35 inline bool my_comp(const Data &a, const Data &b) 36 { 37 return a.value < b.value; 38 } 39 40 int b[M],ans[N]; 41 char Little[25]; 42 char str[25]; 43 int n,r; 44 45 int main() 46 { 47 freopen("piano.in","r",stdin); 48 freopen("piano.out","w",stdout); 49 50 n = read(); 51 r = read(); 52 for(int i = 1; i <= n; i++) 53 { 54 scanf("%s",Little); 55 int lenth = strlen(Little); 56 data[i].number = i; 57 data[data[i].number].value = http://www.mamicode.com/(Little[0] - ‘A‘ + 1) * 10 + Little[1] - ‘0‘; 58 if(lenth > 2 && Little[2] == ‘.‘) 59 { 60 for(int j = 3; j < lenth; j++) 61 { 62 if(Little[j] == ‘(‘ || Little[j] == ‘[‘ || Little[j] == ‘{‘) break; 63 data[i].value = http://www.mamicode.com/data[i].value * 10 + Little[j] - ‘0‘; 64 } 65 } 66 } 67 sort(data+1,data+1+n,my_comp); 68 while(r--) 69 { 70 int li = read(); 71 for(int i = 1; i <= li; i++) 72 { 73 scanf("%s",str); 74 int lenth = strlen(str); 75 b[i] = (str[0] - ‘A‘ + 1) * 10 + str[1] - ‘0‘; 76 if(lenth > 2 && str[2] == ‘.‘) 77 { 78 for(int j = 3; j < lenth; j++) 79 { 80 if(str[j] == ‘(‘ || str[j] == ‘[‘ || str[j] == ‘{‘) break; 81 b[i] = b[i] * 10 + str[j] - ‘0‘; 82 } 83 } 84 } 85 ans[0] = 0; 86 for(int i = 1; i <= li; i++) 87 { 88 int left = 1, right = n; 89 while(left < right) 90 { 91 int mid = (left + right) / 2; 92 if(data[mid].value >= b[i]) 93 { 94 right = mid; 95 } 96 else 97 { 98 left = mid + 1; 99 }100 }101 if(data[left].value != b[i]) continue;102 if(ans[ans[0]] < data[left].number) ans[++ans[0]] = data[left].number;103 else104 {105 int aider = lower_bound(ans+1,ans+1+ans[0],data[left].number) - ans;106 ans[aider] = data[left].number;107 }108 }109 printf("%.6lf\n",ans[0] * 1.0 / li);110 }111 112 return 0;113 }
NOIP2017模拟赛 senior 6.29 T2 小T的钢琴（piano）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。