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

一、题目

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

原文发布于微信公众号 - 海天一树(gh_de7b45c40e8b)

原文发表时间:2018-04-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏章鱼的慢慢技术路

浅谈main(),int main(),void main(),int main(void)四者之间的区别

13830
来自专栏chenjx85的技术专栏

leetcode-58-Length of Last Word

22060
来自专栏恰童鞋骚年

剑指Offer面试题:13.调整数组顺序使奇数位于偶数前面

  例如有以下一个整数数组:12345,经过调整后可以为:15342、13542、13524等等。

12560
来自专栏Python爬虫与算法进阶

说一道排序题

关于Python的sorted排序算法,这篇文章讲的比较详细:python sort函数内部实现原理,说到Python使用的是著名的Timesort算法。

9320
来自专栏数据结构与算法

计数排序

算法思想 编辑 计数排序对输入的数据有附加的限制条件: 1、输入的线性表的元素属于有限偏序集S; 2、设输入的线性表的长度为n,|S|=k(表示集合S中元素...

308100
来自专栏用户2442861的专栏

NumPy简明教程(二、数组1)

http://blog.csdn.net/sunny2038/article/details/9002531

11610
来自专栏mathor

KMP(4)

15250
来自专栏Jack-Cui

第七天、判断三角形的类型

    根据输入的三角形的三条边判断三角形的类型,并输出它的面积和类型。 C代码: /*第七天、判断三角形的类型*/ #include <stdio.h> ...

23000
来自专栏Python小屋

Python中lambda表达式的常见用法

非常抱歉,昨天发的代码中有一处小错误,已通过留言的方式进行了纠正,详情请见【详解Python列表推导式】 lambda表达式常用来声明匿名函数,即没有函数名字的...

38190
来自专栏五分钟学算法

每天一算:Evaluate Reverse Polish Notation

我们会在每天早上8点30分准时推送一条LeetCode上的算法题目,并给出该题目的动画解析以及参考答案,每篇文章阅读时长为五分钟左右。

8410

扫码关注云+社区

领取腾讯云代金券