xzm2019

北京理工大学第七届程序设计新生赛 题解(unofficial)
一直不敢写这场比赛的题解,感觉写的心痛 ::aru:shy:: 也许是因为早上一直忙着帮忙布置场地,比赛状态挺差的...
扫描右侧二维码阅读全文
12
2019/02

北京理工大学第七届程序设计新生赛 题解(unofficial)

一直不敢写这场比赛的题解,感觉写的心痛 也许是因为早上一直忙着帮忙布置场地,比赛状态挺差的,很多傻逼题在那里犯着傻逼错误,最终怼题怼的也开心。那还是写写自己对这些题的看法吧

SolvedABCDEFGHIJKLM
8/13ØO.OØOOØØOOOO
  • O for passing during the contest
  • Ø for passing after the contest
  • ! for attempted but failed
  • · for having not attempted yet

Problem A 自然语言处理 (Unsolved with 13 tries)

$T(T \leq 100)$组数据,每组数据给你$n(1 \leq n \leq 10)$个$m(1 \leq m \leq 4)$维向量,请判断他们是否线性相关。

哎呦我的妈啊……每年新生赛必考线代题,可啥是线性相关来着啊,真的不知道了啊(还好发了clarification告诉了我们一下),可我还是不记得怎么判啊,就记得应该高斯消元,从开场想抢一血写到终场,一直WA上天。

首先当向量组所含向量的个数多于向量的维数时,该向量组一定线性相关(强势怀疑自己没判这个导致WA上天),剩下的使用高斯消元找非零解。

#include <bits/stdc++.h>
using namespace std;

const int maxn=505;
const double eps=1e-8;
double A[maxn<<1][maxn],x[maxn];
int n,m;
int Guass(int n,int m)
{
    int i=1,j=1,k,r,c;
    while(i<=m && j<=n)
    {
        r=i;
        for(k=i+1;k<=m;k++)if(fabs(A[k][j])>fabs(A[r][j]))r=k;
        if(fabs(A[r][j])>=eps)
        {
            for(c=1;c<=n+1;c++)swap(A[i][c],A[r][c]);
            for(k=i+1;k<=m;k++)if(fabs(A[k][j])>=eps)
            {
                double f=A[k][j]/A[i][j];
                for(c=j;c<=n+1;c++)
                    A[k][c]-=f*A[i][c];
            }
            i++;
        }
        j++;
    }
    for(k=i;k<=m;k++)if(fabs(A[k][n+1])>=eps)return 0;
    if(i<=n)return 2;
    for(int i=n;i>=1;i--)
    {
        for(j=i+1;j<=n;j++)
            A[i][n+1]-=A[i][j]*x[j];
        x[i]=A[i][n+1]/A[i][i];
    }
    return 1;
}
int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d",&n,&m);
        memset(A,0,sizeof(A));
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=m;j++)
                scanf("%lf",&A[j][i]);
        }
        if (n>m)
        {
            printf("YES\n"); continue;
        }
        m++;
        A[m][1]=1; A[m][n+1]=1;
        if (Guass(n,m)>=1) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

高斯消元的板子可以在百度里查到,这里使用的是这个


Problem B The Secret of Time (Solved at 0:25 with 1 try)

要求找出一个八位数,使得他平方以后满足 x7x1 x8x0 x6x2 x9x1,其中$x$代表任意数字

本地for循环暴力找,找到答案以后print提交,满足条件的答案应该有两个,任选其一即可。


Problem C Lytchen loves JSON (Unattempted)

你需要编写一个程序,这个程序以一个合法的JSON文档作为输入,然后响应一系列查询。每个查询均会要求查询在这个JSON文档所包含的对象图上的一个值。

如果你们谁对大模拟感兴趣可以自己在这里补这个题,我是没什么可说的

#ifdef REDIRECT_INPUT
#include <cstdio>
#endif

#include <cctype>
#include <cassert>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <utility>
#include <iterator>
#include <string>
#include <vector>
#include <map>
#include <memory>
#include <stdexcept>

constexpr const char * const err_no_such_attr = "Error: no such attribute";
constexpr const char * const err_invalid_type = "Error: invalid type";
constexpr const char * const err_idx_overflow = "Error: index overflow";

#ifdef DEBUG

template <typename OutputStream, typename ...Args>
OutputStream & trace(OutputStream & os, Args... args)
{
    (os << ... << args);
    os << std::endl;
    return os;
}

#else
#define trace(...)        ((void)0)
#endif


class json_object
{
    public: json_object() noexcept = default;
    public: virtual ~json_object() noexcept = default;

    public: json_object(const json_object &) noexcept = default;
    public: json_object(json_object &&) noexcept = default;

    public: json_object & operator = (const json_object &) noexcept = default;
    public: json_object & operator = (json_object &&) noexcept = default;

    public: virtual std::shared_ptr<json_object> operator [] (std::string attr_name) const
    { throw std::logic_error(err_no_such_attr); }

    public: virtual std::shared_ptr<json_object> operator [] (int index) const
    { throw std::logic_error(err_invalid_type); }

    public: virtual std::ostream & print(std::ostream & output) const noexcept
    { return serialize(output); }

    public: virtual std::ostream & serialize(std::ostream & output) const noexcept = 0;
};

class json_dict_object : public json_object
{
    public: void set_attr(std::string name, std::shared_ptr<json_object> value)
    { _attr[name] = value; }

    public: virtual std::shared_ptr<json_object> operator [] (std::string attr_name) const override
    {
        auto attr_iter = _attr.find(attr_name);
        if (attr_iter == _attr.end())
            throw std::logic_error(err_no_such_attr);
        return attr_iter->second;
    }

    public: virtual std::ostream & serialize(std::ostream & output) const noexcept override
    {
        output << '{';
        for (auto iter = _attr.begin(); iter != _attr.end(); ++iter)
        {
            output << " \"" << iter->first << "\": ";
            iter->second->serialize(output);
            
            if (std::next(iter) != _attr.end())
                output << ',';
        }
        output << " }";

        return output;
    }

    private: std::map<std::string, std::shared_ptr<json_object>> _attr;
};

class json_array_object : public json_object
{
    public: void append(std::shared_ptr<json_object> obj)
    { _arr.emplace_back(obj); }

    public: virtual std::shared_ptr<json_object> operator [] (int index) const override
    {
        if (index >= static_cast<int>(_arr.size()))
            throw std::logic_error(err_idx_overflow);
        return _arr[index];
    }

    public: virtual std::ostream & serialize(std::ostream & output) const noexcept override
    {
        output << '[';
        for (auto iter = _arr.begin(); iter != _arr.end(); ++iter)
        {
            output << ' ';
            (*iter)->serialize(output);
            if (std::next(iter) != _arr.end())
                output << ',';
        }
        output << " ]";

        return output;
    }

    private: std::vector<std::shared_ptr<json_object>> _arr;
};

class json_char_object : public json_object
{
    public: json_char_object(char ch)
        : _value(ch)
    { }

    public: virtual std::ostream & print(std::ostream & output) const noexcept override
    { return output << _value; }

    public: virtual std::ostream & serialize(std::ostream & output) const noexcept override
    { return output << '\"' << _value << '\"'; }

    private: char _value;
};

class json_str_object : public json_object
{
    public: json_str_object(std::string str)
        : _raw(str)
    { }

    public: virtual std::shared_ptr<json_object> operator [] (int index) const override
    { 
        auto unesc = unescaped();
        if (index >= static_cast<int>(unesc.length()))
            throw std::logic_error(err_idx_overflow);
        return std::make_shared<json_char_object>(unesc[index]);
    }

    public: virtual std::ostream & print(std::ostream & output) const noexcept override
    { return output << unescaped(); }

    public: virtual std::ostream & serialize(std::ostream & output) const noexcept override
    { return output << '\"' << _raw << '\"'; }

    private: std::string unescaped() const
    {
        // Do escaping work.
        std::string result;
        for (auto iter = _raw.begin(); iter != _raw.end(); ++iter)
        {
            auto ch = *iter;
            if (ch == '\\')
            {
                // Escape character found.
                assert(std::next(iter) != _raw.end());
                auto next_ch = *(++iter);
                char escaped;
                switch (next_ch)
                {
                    case 't':
                        escaped = '\t';
                        break;
                    
                    case '\\':
                        escaped = '\\';
                        break;
                    
                    case '/':
                        escaped = '/';
                        break;
                    
                    case '\"':
                        escaped = '\"';
                        break;

                    default:
                        result.push_back('\\');
                        result.push_back(next_ch);
                        continue;
                }

                result.push_back(escaped);
            }
            else
                result.push_back(ch);
        }

        return result;
    }

    private: std::string _raw;
};

class json_float_object : public json_object
{
    public: json_float_object(double value)
        : _value(value)
    { }

    public: virtual std::ostream & serialize(std::ostream & output) const noexcept override
    {
        auto old_fmt = output.flags();
        auto old_prec = output.precision();
        output.flags(std::ios_base::fixed);
        output.precision(2);
        output << _value;
        output.precision(old_prec);
        output.flags(old_fmt);
        return output;
    }

    private: double _value;
};

class json_bool_object : public json_object
{
    public: json_bool_object(bool value)
        : _value(value)
    { }

    public: virtual std::ostream & serialize(std::ostream & output) const noexcept override
    {
        if (_value)
            output << "true";
        else
            output << "false";
        return output;
    }

    private: bool _value;
};

class json_null_object : public json_object
{
    public: virtual std::ostream & serialize(std::ostream & output) const noexcept override
    { return output << "null"; }
};

class json_reader
{
    private: class json_token
    {
        public: json_token(std::string json)
            : _raw(json)
        { }

        private: std::shared_ptr<json_float_object> to_number() const
        {
            std::istringstream ss { _raw };
            double value;
            ss >> value;
            
            if (ss)
                return std::make_shared<json_float_object>(value);
            else
                return nullptr;
        }

        private: std::shared_ptr<json_bool_object> to_bool() const
        {
            if (_raw == "true")
                return std::make_shared<json_bool_object>(true);
            else if (_raw == "false")
                return std::make_shared<json_bool_object>(false);
            else
                return nullptr;
        }

        private: std::shared_ptr<json_null_object> to_null() const
        {
            if (_raw == "null")
                return std::make_shared<json_null_object>();
            else
                return nullptr;
        }

        public: std::shared_ptr<json_object> get_object() const
        {
            std::shared_ptr<json_object> obj_ptr;

            obj_ptr = to_number();
            if (obj_ptr)
                return obj_ptr;

            obj_ptr = to_bool();
            if (obj_ptr)
                return obj_ptr;

            obj_ptr = to_null();
            if (obj_ptr)
                return obj_ptr;

            return nullptr;
        }

        private: std::string _raw;
    };

    public: json_reader(std::istream & input)
        : _stream(input)
    { }

    // Discard any leading spaces currently under the stream pointer
    // and returns the first non-space character encountered.
    private: int discard_spaces()
    {
        while (std::isspace(_stream.peek()))
            _stream.get();

        if (!_stream)
            return 0;

        return _stream.peek();
    }

    private: std::shared_ptr<json_dict_object> read_next_dict()
    {
        int ch = discard_spaces();
        if (ch != '{')
            return nullptr;
        
        auto dict = std::make_shared<json_dict_object>();

        // Discard the left bracket.
        _stream.get();

        if (discard_spaces() != '}')
        {
            // The dictionary is not empty.
            while (true)
            {
                // Discard the left quote mark.
                discard_spaces();
                _stream.get();

                std::string attr_name;
                while (true)
                {
                    ch = _stream.get();
                    if (ch == '\"')
                        break;  // The right quote mark has been discarded here.
                    attr_name.push_back(static_cast<char>(ch));
                }

                // Discard the colon character.
                discard_spaces();
                _stream.get();

                auto attr_value = read_next();
                dict->set_attr(attr_name, attr_value);

                if (discard_spaces() == '}')
                    break;
                else
                {
                    // Discard the comma.
                    _stream.get();
                }
            }
        }

        // Discard the right bracket.
        _stream.get();

        trace(std::cerr, "read_next_dict");
        return dict;
    }

    private: std::shared_ptr<json_array_object> read_next_array()
    {
        int ch = discard_spaces();
        if (ch != '[')
            return nullptr;

        auto array = std::make_shared<json_array_object>();
        
        // Discard the left bracket.
        _stream.get();
        if (discard_spaces() != ']')
        {
            // The array is not empty.
            while (true)
            {
                array->append(read_next());
                if (discard_spaces() == ']')
                    break;
                else
                {
                    // Discard the comma.
                    _stream.get();
                }
            }
        }

        // Discard the right bracket.
        _stream.get();

        trace(std::cerr, "read_next_array");
        return array;
    }

    private: std::shared_ptr<json_str_object> read_next_str()
    {
        int ch = discard_spaces();
        if (ch != '\"')
            return nullptr;
        
        // Discard the opening quote mark.
        _stream.get();

        std::string json;
        while (true)
        {
            ch = _stream.get();
            if (ch == '\"')
                break;      // The closing quote mark has been discarded here.
            
            if (ch == '\\')
            {
                // Read escape sequence.
                ch = _stream.get();
                json.push_back('\\');
                json.push_back(ch);
                if (ch == 'u')
                {
                    // Unicode escape sequence consists of 4 hexadecimal digits.
                    json.push_back(static_cast<char>(_stream.get()));
                    json.push_back(static_cast<char>(_stream.get()));
                    json.push_back(static_cast<char>(_stream.get()));
                    json.push_back(static_cast<char>(_stream.get()));
                }
            }
            else
                json.push_back(ch);
        }

        trace(std::cerr, "read_next_str: raw = ", json);
        return std::make_shared<json_str_object>(json);
    }

    private: json_token read_next_token()
    {
        discard_spaces();

        std::string token_json;
        int ch;

        while (true)
        {
            ch = _stream.peek();
            
            // Allowed characters in a token are:
            // Digits(0-9), English letters (a-zA-Z), and "+", "-", ".".
            if (!std::isdigit(ch) && 
                !std::isalpha(ch) && 
                ch != '+' &&
                ch != '-' &&
                ch != '.')
                break;
            
            _stream.get();      // Consume the character.
            token_json.push_back(ch);
        }

        trace(std::cerr, "read_next_token: ", token_json);
        return json_token { token_json };
    }

    public: std::shared_ptr<json_object> read_next()
    {
        auto ch = discard_spaces();
        assert(_stream);

        switch (ch)
        {
            case '{':
                // Dictionary object definition.
                return read_next_dict();

            case '[':
                // Array object definition.
                return read_next_array();

            case '\"':
                // String object definition.
                return read_next_str();
                
            default:
                // Primitive object (bools, numbers and null) definition.
                return read_next_token().get_object();
        }
    }

    private: std::istream & _stream;
};


using query_data = std::vector<
    std::pair< std::string, std::vector<int> >
>;

std::vector<std::string> strsplit(const std::string & s, char sep) noexcept
{
    std::vector<std::string> result;

    std::string::size_type l = 0;
    for (std::string::size_type i = 0; i < s.size(); ++i)
    {
        if (s[i] == sep)
        {
            result.emplace_back(s.substr(l, i - l));
            l = i + 1;
        }
    }
    result.emplace_back(s.substr(l));

    return result;
}

query_data parse_query(const std::string & query) noexcept
{
    query_data qd;
    auto path = strsplit(query, '.');
    
    for (const auto & path_com : path)
    {
        auto sub_start = path_com.find('[');
        if (sub_start == std::string::npos)
            sub_start = path_com.length();

        std::string attr_name = path_com.substr(0, sub_start);

        std::vector<int> subs;
        int idx = 0;
        for (auto i = sub_start; i < path_com.length(); ++i)
        {
            char ch = path_com[i];
            if (std::isdigit(ch))
                idx = idx * 10 + ch - '0';
            else if (ch == ']')
            {
                subs.push_back(idx);
                idx = 0;
            }
        }

        qd.emplace_back(std::move(attr_name), std::move(subs));
    }

    return qd;
}


int main(int argc, char * argv[])
{
#ifdef REDIRECT_INPUT
    freopen("input.in", "r", stdin);
#endif

    auto root_object = json_reader(std::cin).read_next();
    assert(root_object);

    std::string query;
    while (std::cin >> query)
    {
        auto qdata = parse_query(query);
        auto obj = root_object;

        try
        {
#if __cplusplus >= 201700L
            for (const auto & [attr, subs] : qdata)
            {
#else
            for (const auto & qnode : qdata)
            {
                const auto & attr = qnode.first;
                const auto & subs = qnode.second;
#endif
                obj = (*obj)[attr];
                for (auto idx : subs)
                    obj = (*obj)[idx];
            }
        }
        catch (std::exception & err)
        {
            std::cout << err.what() << std::endl;
            continue;
        }

        obj->print(std::cout) << std::endl;
    }

    return 0;
}

Problem D 元素周期表 (Solved at 2:13 with 1 try)

$T(1 \leq T \leq 200)$组数据,每组数据给你一个长度小于1000分子式(分子式只包含元素和元素个数,没有括号、前导数字、点等),请求出它的相对分子质量。题目给出了一张元素周期表的图片。

其实我只有一句话想说,哪个出题人这么狠。

明显这题使用map存储每个元素的相对原子质量比较方便,但是敲起来会有些费劲,不过由于化学元素的首字母均为大写,所以比较好做判断,一个个字符读入即可。


Problem E 龙语魔法 (Unattempted)

给一个长度为$n(n \leq 10^5)$的每个数在$10^9$以内的序列,求第$k(1 \leq k \leq \frac{n(n+1)}{2})$小的区间和。

赛时看出来了这个是二分答案(甚至觉得这是个原题),可是在那里怼高斯消元就一直咕咕咕,咕到了比赛结束(

明显二分答案即可,对于每一个答案,统计区间和小于他的个数。统计的时候使用双指针的思路进行即可。

时间复杂度:$O(n \log{\sum{a_i}})$

#include <bits/stdc++.h>
using namespace std;

int a[100005];
int n;
long long k,all;
int check(long long x)
{
    long long tmp1=0,tmp2=0,now=a[1];
    int l=0,r=1;
    while (l<=r&&r<=n)
    {
        if (now>=x)
        {
            if (now==x) tmp2++; else tmp1++;
            tmp1+=n-r;
            l++; now-=a[l];
        }
        else {r++; now+=a[r];}
    }
    if (all-tmp1-tmp2<k&&all-tmp1>=k) return 0;
    if (all-tmp1-tmp2>=k) return 1;
    else return -1;
}
int main()
{
    scanf("%d%lld",&n,&k);
    long long sum=0;
    all=1LL*n*(n+1)/2;
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=n;i++) sum+=a[i];
    long long l=1,r=sum;
    while (l<=r)
    {
        long long mid=(l+r)/2;
        int flag=check(mid);
        if (flag==0) return printf("%lld\n",mid),0;
        if (flag==1) r=mid-1;
        else l=mid+1;
    }
    return 0;
}

Problem F 浴缸 (Solved at 0:37 with 3 tries)

给出浴缸每个点的深度,问注入$n$升水以后从浴缸顶部到水面的距离有多长(保证答案是整数)。

简单的一个前缀和处理,求出每个距离要的水的总量,一开始看错了题WA了两发,后来数据出锅RE了两发然后rejudge了


Problem G 伙伴系统 (Solved at 1:48 with 2 tries)

$k(k \leq 10^5)$次操作,每次操作获得一块内存或者请求划分内存。内存要划分成二的次幂的内存块。每次划分不能把小的拼接,只能从大的再划分。

其实是一个很简单的二进制处理问题,划分内存,找到最接近他的二的次幂的数划分然后删去他需要的内存块即可。只需要每个数求二进制即可。


Problem H 白学串 (Unattempted)

给一个长度为$n(n \leq 10^5,\sum{n} \leq 5*10^5)$的序列,每个数小于$10^8$,$m(m \leq 2*10^6, \sum{m} \leq 10^6)$组查询,每次询问一个区间是否存在三个数可以构成三角形。

赛时没想到斐波拉契速度增长,然后就不会了。现在想想,不能组成三角形的最极限情况就是斐波拉契数列,而这个数列增长很快,到40项就可以超过$10^8$,因此,可以粗略的判断,如果区间过长,直接答案是yes。否则对区间排序,如果有相邻的三个数能构成三角形,就是yes,反之为no

#include <bits/stdc++.h>
using namespace std;

int a[100005];
int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);
        while (m--)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            if (r-l+1>=40) {printf("yes\n"); continue;}
            vector<int> tmp;
            for (int i=l;i<=r;i++)
                tmp.emplace_back(a[i]);
            sort(tmp.begin(),tmp.end());
            bool flag=false;
            for (int i=0;i<(int)tmp.size()-2;i++)
                if (tmp[i]+tmp[i+1]>tmp[i+2])
                {
                    flag=true; break;
                }
            if (flag) printf("yes\n"); else printf("no\n");
        }
    }
    return 0;
}

Problem I Integer Factorization (Unattempted)

$a=(p*q)\ xor\ (p+q),b=(p*q)\ xor\ (p-q)$,$T(T \leq 3000)$组数据,给出$a,b(-2^{63} \leq a,b \leq 2^{63})$,求均为质数的$p,q$。

知道是按位去算,本来后期想莽一莽,但是思路不清晰,而且对于负数不知道怎么考虑,就放弃了。当时想到的是cf上的1088D,下面附上出题人在知乎上发的题解:

然后再说一下I题,它其实来源于今年中科大举办的hakergame2018(对是ctf),几乎就是原题了,连题面背景都差不多,当然原题要算1024位的$pq$,为了不让你们算高精度把$pq$砍到了32位,但是核心的想法(和坑点)都没有变。
加,乘,异或三个操作都有一个特性,高位不会影响低位,所以可以从低到高按位搜索。如果有$a+b=c$,那么就有$(a\%2+b\%2)\%2=c\%2,\%4,\%8$等也依然成立,所以可以先枚举$pq$的最低位,再合法解的基础上再枚举下一位,其实就是一个搜索。因为每次枚举都会有$00,01,10,11$四个结果,又有两个式子进行剪枝,所以它并不会指数爆炸,按照数学期望应该算个线性的复杂度。
坑点在减法,由于不保证$p>q$所以$p-q$可能是负数,负数遇到模运算会出现很炸裂的情况,所以正确的方法是把$\%2,\%4$换成$\&(2^1-1),\&(2^2-1)$。具体推理在这里不过多的解释了,大家可以验证一下。
作者:匿名用户
链接:https://www.zhihu.com/question/307440139/answer/563059887
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

当然也可以参照原题这个题解

好吧,刚才补了下没想象中的那么难剪枝,直接按位枚举就可以了,一开始TLE了是因为用的set不是vector,后来仔细想想根本不会重复的。

#include <bits/stdc++.h>
using namespace std;

inline long long f1(long long p,long long q)
{
    return (p*q)^(p+q);
}
inline long long f2(long long p,long long q)
{
    return (p*q)^(p-q);
}
int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        long long a,b;
        scanf("%lld%lld",&a,&b);
        vector<pair<long long,long long>> ans,tmp;
        ans.emplace_back(0,0);
        for (int i=0;i<64;i++)
        {
            long long base=(2LL<<i)-1;
            bool flag=false;
            tmp.clear();
            for (auto &p: ans)
            {
                long long tx=p.first,ty=p.second;
                if (f1(tx,ty)==a&&f2(tx,ty)==b)
                {
                    printf("%lld %lld\n",tx,ty);  flag=true; break;
                }
                for (long long x=0;x<=1;x++)
                    for (long long y=0;y<=1;y++)
                    {
                        long long nx=tx+(x<<i),ny=ty+(y<<i);
                        if ((f1(nx,ny)&base)!=(a&base)) continue;
                        if ((f2(nx,ny)&base)!=(b&base)) continue;
                        tmp.emplace_back(nx,ny);
                    }
            }
            if (flag) break;
            ans=tmp;
        }
    }
    return 0;
}

Problem J 机房的圣诞礼物 (Solved at 0:20 with 1try)

一个人拿礼物拿了编号为$x$的就不能拿$2x$的了,求他拿的礼物的编号和的最大值。

虽然不会证,但感觉就是贪心,从大往小,选了$x$,就不选$x/2$。


Problem K X-Window System (Solved at 3:41 with 3 tries)

模拟窗口点击,求每次需要重绘的屏幕面积。坐标范围最大$2000*2000$。

按照题意模拟即可,因为坐标范围很小,可以直接开一个int数组记录每个点当前最顶端窗口。小模拟题,而我一开始找了想了半天矩形交怎么写


Problem L Bonus Quiz (Solved at 4:13 with 2 tries)

$1-n(n \leq 10^6)$中有$m$个中奖号码,每次选择一个区间,区间里正好含有$k$个中奖号码的时候记为中奖,求中奖的期望。

首先总区间数是确定的$\frac{n(n+1)}{2}$,而可中奖方案数的记录可以先把中奖号码排序,然后考虑长度为$k$的连续区间,可以向左右两边分别延伸到下一个中奖号码前面。

注意特判$k=0$的情况。


Problem M 长安街的华灯 (Solved at 1:25 with 5 tries)

$N(0 \leq N \leq 10^9)$个半径为$R(0 \leq R \leq 10^9)$的圆,圆心距为$L(0 \leq L \leq 10^9)$,求总覆盖面积。

首先对于$L \geq 2R$的情况,可以直接判断,总面积等于$N$的圆的面积之和。

否则,如图所示

无标题.png

重叠的面积等于圆弧的面积减去三角形的面积的二倍,圆弧的面积可以通过$S=\frac{\alpha}{2}r^2$计算,三角形的面积可以通过正弦定理$S=ab\ sin\alpha$计算,角度可以通过反三角函数和计算。

注意特判$N=0,L=0,R=0$的情况(出题人挖的坑真多)

Last modification:September 28th, 2019 at 11:15 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment