补题链接:https://ac.nowcoder.com/acm/contest/110308


B 最大popcount

签到题,注意long long,以及不要直接用cout(大数会以科学计数法输出,痛吃一发WA)。

<code>#include &lt;bits/stdc++.h&gt;
using namespace std;
#define endl "\n"
#define ll long long

int main()
{
    int t;
    cin &gt;&gt; t;
    while (t--) {
        ll x;
        cin &gt;&gt; x;
        printf("%lld\n", (ll)pow(2, (ll)log2(x + 1)) - 1);
    }

    return 0;
}</code>

I 挡雨布

凸包板子题,不过我是自己用栈实现的。

<code>#include &lt;bits/stdc++.h&gt;
using namespace std;
#define endl "\n"
#define ll long long

set&lt;double&gt; xs;
map&lt;double, double&gt; a;

int main()
{
    int n;
    cin &gt;&gt; n;
    for (int i = 0; i &lt; n; i++) {
        double x, y;
        scanf("%lf %lf", &amp;x, &amp;y);
        if (y == 0.0) {
            continue;
        }
        xs.insert(x);
        a[x] = max(y, a[x]);
    }

    vector&lt;double&gt; xv(xs.begin(), xs.end());

    stack&lt;pair&lt;double, double&gt;&gt; p;
    stack&lt;double&gt; r;
    p.push(make_pair(xv[0], a[xv[0]]));
    for (int i = 1; i &lt; a.size(); i++) {
        pair&lt;double, double&gt; now = make_pair(xv[i], a[xv[i]]);
        double rate = (now.second - p.top().second) / (now.first - p.top().first);
        if (r.empty()) {
            r.push(rate);
            p.push(now);
        } else {
            while (!r.empty() &amp;&amp; r.top() &lt; rate) {
                r.pop();
                p.pop();
                rate = (now.first - p.top().first) / (now.second - p.top().second);
            }
            r.push(rate);
            p.push(now);
        }
    }

    pair&lt;double, double&gt; last = p.top();
    p.pop();
    if (p.empty()) {
        cout &lt;&lt; 0;
    } else {
        double s = 0;
        do {
            s += (last.first - p.top().first) * (last.second + p.top().second) / 2.0;
            last = p.top();
            p.pop();
        } while (!p.empty());
        cout &lt;&lt; s;
    }

    return 0;
}</code>

J 输入距离

也是签到,先排序,把相同的字母放在一起以尽量减少移动次数。

<code>#include &lt;bits/stdc++.h&gt;
using namespace std;
#define endl "\n"
#define ll long long

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    string s;
    cin &gt;&gt; s;
    sort(s.begin(), s.end());
    s = "a" + s;
    ll ans = 0;
    for (int i = 0; i &lt; s.length() - 1; i++) {
        ans += s[i + 1] - s[i];
        ans++;
    }

    cout &lt;&lt; ans;

    return 0;
}</code>

K 圆

数据范围很小,直接暴力,甚至不用手写dfs,用next_permutation()全排列就行了。因为输出任意情况即可,可以提前结束。

<code>#include &lt;bits/stdc++.h&gt;
using namespace std;
#define endl "\n"
#define ll long long

struct R {
    int id;
    double val;
};

bool cmp(const R&amp; a, const R&amp; b)
{
    return a.val &lt; b.val;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    int n;
    cin &gt;&gt; n;

    double a[n][2];
    for (int i = 0; i &lt; n; i++) {
        cin &gt;&gt; a[i][0] &gt;&gt; a[i][1];
    }

    double dis[n][n];
    for (int i = 0; i &lt; n - 1; i++) {
        for (int j = i + 1; j &lt; n; j++) {
            dis[i][j] = sqrt((a[i][0] - a[j][0]) * (a[i][0] - a[j][0]) + (a[i][1] - a[j][1]) * (a[i][1] - a[j][1]));
        }
    }

    R r[n];
    for (int i = 0; i &lt; n; i++) {
        r[i].id = i + 1;
        cin &gt;&gt; r[i].val;
    }

    bool flag;
    sort(r, r + n, cmp);
    do {
        flag = 1;
        for (int i = 0; i &lt; n - 1; i++) {
            for (int j = i + 1; j &lt; n; j++) {
                if (fabs(r[i].val - r[j].val) &lt; dis[i][j] &amp;&amp; dis[i][j] &lt; r[i].val + r[j].val) {
                    flag = 0;
                    i = n;
                    break;
                }
            }
        }
        if (flag) {
            break;
        }
    } while (next_permutation(r, r + n, cmp));

    if (flag) {
        for (int i = 0; i &lt; n; i++) {
            cout &lt;&lt; (i ? " " : "") &lt;&lt; r[i].id;
        }
    } else {
        cout &lt;&lt; -1;
    }

    return 0;
}</code>

L 编辑器

大模拟,不难,就是麻烦,非常需要注意细节(我就是比赛一直过不了,回来后发现就错了一句代码,痛心)。

官方题解的实现太麻烦了,我的是直接用vector<string>去模拟多行。

<code>#include &lt;bits/stdc++.h&gt;
using namespace std;
#define endl "\n"
#define ll long long

string cs = ")!@#$%^&amp;*(";
vector&lt;string&gt; a;

void print()
{
    for (int i = 0; i &lt; a.size(); i++) {
        cout &lt;&lt; (i ? "\n" : "") &lt;&lt; a[i];
    }
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    string s;
    cin &gt;&gt; s;

    int li = 0;
    int ind = 0;
    a.emplace_back("");

    bool sft = 0;
    for (int i = 0; i &lt; s.length(); i++) {
        char c = s[i];
        if (c &gt;= 'a' &amp;&amp; c &lt;= 'z') {
            a[li].insert(ind, string(1, (sft ? c + 'A' - 'a' : c)));
            ind++;
        } else if (c &gt;= '0' &amp;&amp; c &lt;= '9') {
            a[li].insert(ind, string(1, (sft ? cs[c - '0'] : c)));
            ind++;
        } else {
            if (c == 'S') {
                sft ^= 1;
                i += 4;
            } else if (c == 'E' &amp;&amp; s[i + 2] == 'T') {
                string s1 = a[li].substr(0, ind);
                string s2 = a[li].substr(ind);
                a[li] = s1;
                a.insert(a.begin() + li + 1, s2);
                li++;
                ind = 0;
                i += 4;
            } else if (c == 'B') {
                if (ind &gt; 0) {
                    a[li].erase(ind - 1, 1);
                    ind--;
                } else if (li &gt; 0) {
                    ind = a[li - 1].length();
                    a[li - 1] += a[li];
                    a.erase(a.begin() + li);
                    li--;
                }
                i += 8;
            } else if (c == 'D' &amp;&amp; s[i + 1] == 'E') {
                if (ind &lt; a[li].length()) {
                    a[li].erase(ind, 1);
                } else if (li &lt; a.size() - 1) {
                    a[li] += a[li + 1];
                    a.erase(a.begin() + li + 1);
                }
                i += 2;
            } else if (c == 'L') {
                if (ind &gt; 0) {
                    ind--;
                } else if (li &gt; 0) {
                    li--;
                    ind = a[li].length();
                }
                i += 3;
            } else if (c == 'R') {
                if (ind &lt; a[li].length()) {
                    ind++;
                } else if (li &lt; a.size() - 1) {
                    li++;
                    ind = 0;
                }
                i += 4;
            } else if (c == 'U') {
                if (li &gt; 0) {
                    ind = min((int)a[li - 1].length(), ind);
                    li--;
                }
                i += 1;
            } else if (c == 'D' &amp;&amp; s[i + 1] == 'O') {
                if (li &lt; a.size() - 1) {
                    ind = min((int)a[li + 1].length(), ind);
                    li++;
                }
                i += 3;
            } else if (c == 'H') {
                ind = 0;
                i += 3;
            } else if (c == 'E' &amp;&amp; s[i + 2] == 'D') {
                ind = a[li].length();
                i += 2;
            }
        }
    }

    print();

    return 0;
}</code>

M 内存溢出

这才是真的签到题。

<code>#include &lt;bits/stdc++.h&gt;
using namespace std;
#define endl "\n"
#define ll long long

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    int x;
    string s;
    cin &gt;&gt; x &gt;&gt; s;
    if (s == "MiB") {
        cout &lt;&lt; x * 1024 &lt;&lt; " KiB";
    } else {
        cout &lt;&lt; x * 1000 &lt;&lt; " KB";
    }

    return 0;
}</code>

剩下的题还没补(前面的区域,以后再来探索吧~