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

刺骨的言语ヽ痛彻心扉 2022-05-27 02:07 172阅读 0赞

# 一、题目 #

[https://practice.contest.atcoder.jp/tasks/practice\_2][https_practice.contest.atcoder.jp_tasks_practice_2]

# 二、分析 #

这里有三组测试用例。

第一组N = 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个的位置关系。

# 三、代码 #

#include<bits/stdc++.h>
    using namespace std;
    
    char s[29], ans[29];
    int cmp['Z'+5]['Z'+5];
    int cnt = 0;
    
    
    // 比较两个字符，如果a>b返回true，如果a<b返回false
    bool cmp_char(const char a, const char b)
    {
        char cp;
        if(cmp[a][b] == -1)
        {
            printf("? %c %c\n", a, b);
            fflush(stdout);
            scanf(" %c", &cp);
            if(cp == '>')
            {
                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[2]<s[3], s[1]<s[3] * 还有两个问题： * s[5]放哪；s[2]与s[0]、s[1]谁大谁小 */
    
            char temp = s[2];
            if(cmp_char(s[4], s[1]))
            {
                // 若s[4]>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]<s[4]<s[3]
                    s[2] = s[4];
                    s[4] = s[3];
                }
            }
            else
            {
                // 若s[4]<s[1]，则比较s[4]与s[0]
                if(cmp_char(s[4], s[0]))
                {
                    // s[0]<s[4]<s[1]
                    s[2] = s[1];
                    s[1] = s[4];
                    s[4] = s[3];
                }
                else
                {
                    // s[4]<s[0]<s[1]
                    s[2] = s[1];
                    s[1] = s[0];
                    s[0] = s[4];
                    s[4] = s[3];
                }
            }
    
            sort_N5(temp);
    
            printf("! %s\n", s);
        }
    
        return 0;
    }

# 四、参考 #

[https://www.cnblogs.com/TheRoadToAu/p/8463454.html][https_www.cnblogs.com_TheRoadToAu_p_8463454.html]

> 更多内容请关注微信公众号  
> ![wechat\_public.jpg][wechat_public.jpg]**重点内容**

[https_practice.contest.atcoder.jp_tasks_practice_2]: https://practice.contest.atcoder.jp/tasks/practice_2
[https_www.cnblogs.com_TheRoadToAu_p_8463454.html]: https://www.cnblogs.com/TheRoadToAu/p/8463454.html
[wechat_public.jpg]: /images/20220527/684bd8bafd154fe6854e446646d5a7e0.png