AtCoder入门练习题B--题解报告

一、题目

​​= 26, Q = 1000。因为N * N < Q，所以可用冒泡排序法。具体代码参考官方给的Sample Code。

第二组N = 26, Q = 100，由于询问次数只有100次，可用插入排序法处理。每插入一个数据前，先用二分查找法查找插入的位置，这样可提升排序速度。但是这样需要询问26log226次，还是不能通过所有的数据。这就要求我们需要对每一次询问的答案做一个记忆化处理，记录下小球的质量关系，然后根据这个质量关系就可以得出有序的数列，从而降低时间复杂度。

第三组N=5, Q=7。先比较第0个和第1个，第2个和第3个，第1个和第3个，再求第5个的位置，最后求第2个和第0个、第1个、第5个的位置关系。

三、代码

#includeusing namespace std;char s[29], ans[29];int cmp['Z'+5]['Z'+5];int cnt = 0;// 比较两个字符，如果a>b返回true，如果a') { cmp[a][b] = true; cmp[b][a] = false; return true; } else { cmp[a][b] = false; cmp[b][a] = true; return false; } } return cmp[a][b];}// N为5时，调用此方法进行排序void sort_N5(char c){ if(cmp_char(c, s[1])) { if(cmp_char(c, s[2])) { s[3] = c; } else { s[3] = s[2]; s[2] = c; } } else { if(cmp_char(c, s[0])) { s[3] = s[2]; s[2] = s[1]; s[1] = c; } else { s[3] = s[2]; s[2] = s[1]; s[1] = s[0]; s[0] = c; } }}// N为26时，调用此方法进行排序void sort_N26(char c){ int l = 0, r = cnt; while(l < r) { int mid = (l + r) >> 1; if(cmp_char(c, ans[mid])) { l = mid + 1; } else { r = mid; } } cnt++; // 在新加入的c比原先的所有字符都大时，if条件成立 // 比如原先的顺序为"AB"，新加和的"C"比"B"大，即"AB"变为"ABC"时 if(cmp_char(c, ans[r])) { r++; } for(int i = cnt; i >= r + 1; i--) { ans[i] = ans[i-1]; } ans[r] = c;}int main(){ int N, Q; scanf("%d%d", &N, &Q); for(int i = 0; i < 26; i++) { s[i] = (char)(i + 'A'); } s[N] = '\0'; memset(cmp, -1, sizeof(cmp)); if(N == 26) // Q=1000, 或Q=100 { cnt = 0; ans[0] = s[0]; ans[N] = '\0'; for(int i = 1; i < N; i++) { sort_N26(s[i]); } printf("! %s\n", ans); } else // N=5, Q=7 { if(cmp_char(s[0], s[1])) { swap(s[0], s[1]); } if(cmp_char(s[2], s[3])) { swap(s[2], s[3]); } if(cmp_char(s[1], s[3])) { swap(s[0], s[2]); swap(s[1], s[3]); } /* * 至此，s[0]s[1]，则比较s[4]与s[3] if(cmp_char(s[4], s[3])) { // s[4]>s[1], s[4]>s[3] // 把0、1、2、5这四个位置填满，便于调用sort_N5() s[2] = s[3]; } else { // s[1]

四、参考

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。