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

Author： xzm2019
发布时间：February 12, 2019
7197views
No comments
853字数
Categories：算法

一直不敢写这场比赛的题解，感觉写的心痛 <img src="http://xzm2001.cn/usr/themes/handsome/assets/img/emotion/aru/shy.png" class="emotion-aru"> 也许是因为早上一直忙着帮忙布置场地，比赛状态挺差的，很多傻逼题在那里犯着傻逼错误，最终怼题怼的也~~开心~~。那还是写写自己对这些题的看法吧

| Solved | A | B | C | D | E | F | G | H | I | J | K | L | M |
|:------:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|  8/13  | Ø | O | . | O | Ø | O | O | Ø | Ø | O | O | O | O |

- 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上天），剩下的使用高斯消元找非零解。

```cpp
#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;
}
```
高斯消元的板子可以在百度里查到，这里使用的是[这个][2]。

---
## 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文档所包含的对象图上的一个值。

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

```cpp
#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}})$
```cpp
#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`。

```cpp
#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][4]，下面附上出题人在知乎上发的题解：

> 然后再说一下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][5]
> 来源：知乎
> 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

当然也可以参照原题这个[题解][6]。

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

```cpp
#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][7]

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

注意特判$N=0,L=0,R=0$的情况~~（出题人挖的坑真多）~~。
  [1]: https://blog.csdn.net/xiaoming_p/article/details/79859769
  [2]: https://blog.csdn.net/xiaoming_p/article/details/79859769
  [3]: https://acm.bitnp.net/problem/139
  [4]: https://codeforces.com/contest/1088/problem/D
  [5]: https://www.zhihu.com/question/307440139/answer/563059887
  [6]: https://github.com/ustclug/hackergame2018-writeups/blob/master/official/RSA_of_Z/README.md
  [7]: http://xzm2001.cn/usr/uploads/2019/02/1266567141.png

Last modification：September 28th, 2019 at 11:15 am

If you think my article is useful to you, please feel free to appreciate

Comment *

私密评论

Name *

Email *

Site

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

xzm2019 • 2019 年 02 月 12 日