她真好看（雾）

博主是真的菜，大一 $10$ 月份才开始学 $C++$ ，真正的零基础从入门到放弃。基本的编程能力是有的，算法纯蒟蒻。

起因是看到学校 $ACM$ 集训队有宣传，所以就想着也报一下，顺便提高一下个人的代码能力。

算法基础集训营第一场 2.03#

赛题：https://ac.nowcoder.com/acm/contest/120561 验题人题解：链接
第一场个人觉得发挥还行，题也比较偏数学推论，大体上找到规律就可以做了。只讲一讲调出来的题，其他太难的就不补了。

B - Card Game#

这题要发现一个规律，就是小苯一场总共得多少分和小红手牌顺序是没关系的。所以只需要对小苯出牌顺序进行讨论。。然后发现得最多分的牌序规律。
思路：因为牌的数字是排列所以每次比较都是会有胜负的，不会出现平局。那么如果想让小苯尽可能赢的话就一定要让大的牌在前面，小的牌在后面（因为一旦对手小红的牌出完了游戏就结束了），而这里你就会发现小苯的牌是大是小有一个临界点——那就是小红的最小牌。比如如果小苯所有的牌都比小红最小的牌小，那么小苯无论如何都无法得分。而如果小苯存在比小红最小的牌大的牌就一定能得到分。由此我们可以根据这个临界点来划分小苯的牌是大是小两部分，然后通过阶乘求出两个部分所有的排列组合数，最后再把它们相乘就是结果了。
这里我通过遍历小红的牌（ $b$ 数组）找出最小的牌的值。然后用 $cnt1$ 记录小苯的牌（ $a$ 数组）中比这个值大的数量， $cnt2$ 记录比这个值小的数量。分别求阶乘，然后再相乘。

NOTE
根据题目要求，因为数据会比较大，所以求阶乘的时候要对每一步进行取模操作防止整型溢出。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define mod 998244353
6
vector<ll> a;
7
vector<ll> b;
8
void solved(){
9
    int t;
10
    cin >> t;
11
    while(t--){
12
        int n;
13
        cin >> n;
14
        ll mi = 400010;
15
        ll cnt1 = 0,cnt2 = 0;
16
        a.resize(n + 1);
17
        b.resize(n + 1);
18
        for (int i = 1; i <= n;i++){
19
            cin >> a[i];
20
        }
21
        for (int i = 1; i <= n;i++){
22
            cin >> b[i];
23
            if(b[i] < mi) mi = b[i];
24
        }
25
        //cout << "mi:" << mi << '\n';
26
        for (int i = 1; i <= n;i++){
27
            if(a[i] < mi){
28
                cnt1++;
29
            }
30
            else{
31
                cnt2++;
32
            }
33
        }
34
        //cout << "cnt1:" << cnt1 << " " << cnt2 << '\n';
35
        ll ans1 = 1,ans2 = 1;
36
        for (int i = 1; i <= cnt1;i++){
37
            ans1 = ((ans1 % mod) * i) % mod;
38
        }
39
        for (int i = 1; i <=cnt2;i++){
40
            ans2 = ((ans2 % mod) * i) % mod;
41
        }
42
        cout << ((ans1 % mod) * (ans2 % mod)) % mod << '\n';
43
    }
44
}
45
int main(){
46
    solved();
47
    return 0;
48
}

C - Array Covering#

这里最阴的其实是开区间这个条件。。喜提首发 $WA$ ，发现规律之后大胆写就是。
思路：题目说的是将选定区间两端内的数都变成两端值的较大者，然后你玩了几个数据之后就会发现，总有办法让整个数组里面除了两个端点外的其他值都变成数组的最大值。而数组两端的值（即 $a_1$ 和 $a_n$ 的值无论如何都不能变成数组的最大值，那么答案就很简单了。。找出最大值乘 $n-2$ ，然后再加上 $a_1$ 和 $a_n$ 的值就是答案了。
这里没开数组所以用了新变量 $t1$ 和 $t2$ 来存 $a_1$ 和 $a_n$ 的值。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
void solved(){
6
    int t;
7
    cin >> t;
8
    while(t--){
9
        ll n,ma = 0;
10
        ll ans = 0;
11
        ll t1, t2;
12
        cin >> n;
13
        for (int i = 1; i <= n;i++){
14
            int x;
15
            cin >> x;
16
            if(i == 1)
17
                t1 = x;
18
            if(i == n)
19
                t2 = x;
20
            if(x > ma)
21
                ma = x;
22
        }
23
        cout << ma * (n-2) + t1 + t2 << '\n';
24
    }
25
}
26
int main(){
27
    solved();
28
    return 0;
29
}

E - Block Game#

这题有环形链表内味了，不过其实可以简单实现。
思路：我们可以找几个数据来自己手动模拟一下这个插入挤出的过程。然后就会发现题目的意思可以转化为找数组所有元素加上 $k$ 共 $n+1$ 个数（ $k$ 算第一个数），每两个相邻的数的和的最大值是多少。那么我们就只需要遍历数组每两个相邻的数，然后取最大就可以了（首尾也算相邻也要判断）
初始化最大值记得设成-1e9，因为题目中每个数组元素最小值可以是-1e6。
我这里单独判断了首尾，也可以像题解那样取模判断。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
vector<ll> a;
6
void solved(){
7
    int t;
8
    cin >> t;
9
    while(t--){
10
        int n, k;
11
        cin >> n >> k;
12
        ll ans = -1e9;
13
        a.resize(n + 2);
14
        a[1] = k;
15
        for (int i = 2; i <= n + 1;i++){
16
            cin >> a[i];
17
        }
18
        for (int i = 1; i <= n + 1;i++){
19
            if(i <= n){
20
            ans = max(a[i] + a[i + 1],ans);
21
            }
22
        }
23
        ans = max(ans, a[1] + a[n + 1]);
24
        cout << ans << '\n';
25
    }
26
}
27
int main(){
28
    solved();
29
    return 0;
30
}

G - Digital Folding#

没错，这题调了一个多小时。。因为一直不知道怎么优化，后面发现还是直接找可能的最大值比较快，虽然实现比较复杂。。
思路：题意就是给你一个区间 $[l,r]$ ，让你找区间里面的数反转之后的最大值。一般来说直接构造一个反转数字的函数，然后在区间里面遍历判断，取最大值就可以了。。奈何这题的 $r$ 最大值开到了 $1e15$ ，直接遍历肯定超时了。这个时候我们通过观察可以注意到，最大的数一般是和 $r$ 同位数的，所以可能的最大值可以从 $r$ 右端点开始判断。并且要让小的位尽可能为 $9$ ，这样反转后的数才能尽可能大。然后还需要考虑端点取到最大的可能。
实现真的很复杂。。需要优化的技巧比较难想。。首先我们要判断一些经典的 $9,99,999$ 这种数是否在区间内（这是一种可能），记录最大值。然后我们开始构造可能的最大值。这里我的想法是从个位开始逐个判断能否取9，能取就记为最大值里。最后还要判断端点上的值 $l,r$ 是否可能是最大值。

NOTE
构造的时候有个小技巧，如果直接将对应的位数替换为 $9$ 肯定是大于 $r$ 的，所以可以先将对应位数归零，再减 $1$ ，这样就能尽可能大的取到9且小于 $r$ 了。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
ll hw(ll x){
6
    ll v = 0;
7
    ll s = x;
8
    while(s != 0){
9
        ll x = s % 10;
10
        v = v * 10 + x;
11
        s /= 10;
12
    }
13
    return v;
14
}
15
void solved(){
16
    int t;
17
    cin >> t;
18
    while(t--){
19
        ll l, r;
20
        cin >> l >> r;
21
        ll ans = 0;
22
        for (ll i = 9;i <= r;){
23
            if(i >= l){
24
            ans = max(ans, i);
25
            }
26
            i = i * 10 + 9;
27
        }
28
        for (ll i = 1; i <= r;){
29
            ll cnt = (r / i) * i - 1;
30
            if(cnt <= r&&cnt >= l){
31
                ans = max(ans, hw(cnt));
32
            }
33
            i *= 10;
34
        }
35
        if(hw(l) > ans) ans = hw(l);
36
        if(hw(r) > ans) ans = hw(r);
37
        cout << ans << '\n';
38
    }
39
}
40
int main(){
41
    solved();
42
    return 0;
43
}

K - Constructive#

这题也是妙手偶得。。三个字，大胆猜。
思路：我们取几个数来看：只有 $1$ 的时候，显然成立。 $n = 2$ 时， $1 \times 2 \neq 1 + 2$ 显然不成立。当 $n = 3$ 时， $1 \times 2 \times 3 = 1 + 2 + 3$ 显然成立。当 $n = 4$ 时， $1 \times 2 \times 3 \times 4 \neq 1 + 2 + 3 + 4$ ，显然不成立。并且你会发现 $n >= 4$ 之后的数相乘会越来越大，数组元素求和远远小于乘积，不满足题意。所以满足题意的数据只有 $n = 1$ 和 $n = 3$ 其他的都不符合题意。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
void solved(){
6
    int t;
7
    cin >> t;
8
    while(t--){
9
        int n;
10
        cin >> n;
11
        if(n == 1 || n == 3){
12
            cout << "YES" << '\n';
13
            for (int i = 1; i <= n;i++){
14
                cout << i << " ";
15
            }
16
            cout << '\n';
17
        }
18
        else{
19
            cout << "NO" << '\n';
20
        }
21
    }
22
}
23
int main(){
24
    solved();
25
    return 0;
26
}

L - Need Zero#

这题就是简单的数学。。自己拿几个数玩两下也明白了。
思路：想要个位数为 $0$ ，就单看个位数就行了。如果个位是非零偶数就乘 $5$ ，个位是 $5$ 就乘 $2$ ，个位是 $0$ 就乘 $1$ ，其他的（ $1$ ， $3$ ， $7$ ， $9$ ）就只能乘 $10$ 。
这里的判断其实还可以优化一下，不用像我这样一个个判断。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
void solved(){
6
    int n;
7
    cin >> n;
8
    n %= 10;
9
    if(n == 2 || n == 4 || n == 6 || n == 8)
10
        cout << 5;
11
    else if(n == 3 || n == 7 || n == 9 || n == 1)
12
        cout << 10;
13
    else if(n == 5)
14
        cout << 2;
15
    else if(n == 0)
16
        cout << 1;
17
}
18
int main(){
19
    solved();
20
    return 0;
21
}

算法基础集训营第二场 2.05#

赛题：https://ac.nowcoder.com/acm/contest/120562 验题人题解：链接
本场本蒟蒻只a出了A题。。。神秘B题被卡了一个小时，一开始看到这神奇的通过率还以为。。。结果被摆了一道。后续又做了F题和I题，都没调出来，已疾苦。所以下面就只复盘了一下比赛时看过的题。

A - 比赛安排#

一开始看错题了，以为是题意是两两不同。。首发两个 $WA$ ，后面注意到是连续三个不同就简单了。
思路：因为只能是连续三个不同的类型，那么就只能是 $ABCABC$ 或者 $BACBAC$ 这样固定的顺序了，最后顶多结尾其中两种类型各多出一个或一种类型多出一个，例如结尾 $A$ 或者 $AB$ ，因此只需要比较输入的三种类型比赛场数最大的和最小的差是否小于等于 $1$ ，小于等于就输出 $YES$ ，大于就输出 $NO$ 。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
void solved(){
6
    int t;
7
    cin >> t;
8
    while(t--){
9
        ll a, b, c;
10
        cin >> a >> b >> c;
11
        ll ma = max(a, max(b, c));
12
        ll mi = min(a, min(b, c));
13
        if(ma <= mi + 1){
14
            cout << "YES" << '\n';
15
        }
16
        else{
17
            cout << "NO" << '\n';
18
        }
19
    }
20
}
21
int main(){
22
    solved();
23
    return 0;
24
}

B - NCPC#

这题也调了很久没调出来，调了两次都是超时，看了题解之后发现思路只对了一半，说明原来不仅只是实现的问题，连思路都是错的。。
思路：实际上就只需要对美味值最大的人数进行判断。如果是奇数那么所有美味值最大的人都是 $1$ （可能获胜）。因为最后其他人都要和他比较大小，并且都会输。如果是偶数，那么除了美味值最大的那个人之外其他人都有可能赢。因为可以让其中一个最大美味值的人跟其他人都比较，然后只留下指定的那个人赢。
思路明确了之后其实实现对我来说也是一大难点，题解是使用了 $map$ 映射美味值 $x$ 和数组（用于存放下标），然后用了auto &[x, y] = *prev(mp.end());这个语法获取最大美味值的人的对应下标数组。然后根据下标数组元素的个数判断奇偶性和判断下标来构造字符串。

NOTE
auto &[x, y] = *prev(mp.end()); auto &[x,y] $C++17$ 的结构化绑定语法，将 $map$ 的键和值自动放入变量 $x,y$ 里。
prev(mp.end())是返回的mp.end()迭代器的上一个迭代器，也就是最后一个元素的迭代器，*就是解引用里面的值。

题解代码：

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
int main(){
6
   int T;
7
   cin >> T;
8
   while(T--){
9
       int n;
10
       cin >> n;
11
       map<int, vector<int>> mp;
12
       string s(n, '0');
13
       for(int i = 0; i < n; i++){
14
           int x;
15
           cin >> x;
16
           mp[x].push_back(i);
17
       }
18
       auto &[x, y] = *prev(mp.end());
19
       int t = 1;
20
       if(y.size() % 2 == 0){
21
           t = -1;
22
           s = string(n, '1');
23
       }
24
       for(auto &i : y){
25
           s[i] += t;
26
       }
27
       cout << s << endl;
28
   }
29
}

F - x?y?n!#

纯粹的数学与二进制，然而我并不会。。题解很详细，具体可以去看看，我这里就讲一下数学推导了。
思路：自己对样例里的一些数据玩一下就会发现一个规律： $x \bigoplus y = gcd(x,y) = n$ ，然后我们可以让 $y = x + n$ 保证 $y$ 是 $n$ 的倍数。我们可以通过两个数异或两次为本身的规律将 $x \bigoplus y = n$ 移项为 $x \bigoplus n = y$ ，所以目前我们需要满足 $y = x + n$ , $y = x \bigoplus n$ 这两个式子。继续展开：
$y = x + n = (x \mid n) + (x\& n)$
这个式子可以直观理解，位或就是所有单为 $1$ 的位加上多算的同为 $1$ 的位和，位与就是同为 $1$ 的位的和，它们加起来根据二进制进位就是原来的式子的和。
$y = x \bigoplus n = (x \mid n) - (x \& n)$
这个式子同上，位或减去位与就只剩下不相同的为1了即位异或。
根据式子我们发现只需要令 $x \& n = 0$ , $y = x \bigoplus n$ 就可以取到最大了。接下来我们就只需要构造满足条件的数就可以了。这里令 $x = n \times 2 ^ {32}$ 可以保证 $x$ 一定是 $n$ 的倍数。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
void solved(){
6
    int t;
7
    cin >> t;
8
    while(t--){
9
        ll n;
10
        cin >> n;
11
        cout << (n << 32) << " " << ((n << 32) + n) << '\n';
12
    }
13
}
14
int main(){
15
    solved();
16
    return 0;
17
}

I - 01回文#

做这题的时候已经被B和F卡到爆了，想过 $0$ 和 $1$ 只出现过一次就 $Y$ 的情况，不过终究还是不知道怎么实现。后续看了一眼题解，发现居然是用字符串简化遍历的流程，受教了。。
思路：事实上就是只要 $0$ 和 $1$ 在所给的矩阵中出现的次数超过 $1$ 就一定可以形成 $01$ 回文。比如说从 $1$ 开始，然后走到另一个 $1$ 上就一定是回文的了， $0$ 也是同理。
后续补题的 $AC$ 代码：

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
void solved(){
6
    int t;
7
    cin >> t;
8
    while(t--){
9
        int n, m;
10
        cin >> n >> m;
11
        vector<string> s(n);
12
        unordered_map<char, int> mp;
13
        for (int i = 0; i < n;i++){
14
            cin >> s[i];
15
            for(char c: s[i]){
16
                mp[c]++;
17
            }
18
        }
19
        for (int i = 0; i < n;i++){
20
            for(char c:s[i]){
21
                if(mp[c] == 1){
22
                    cout << "N";
23
                }
24
                else{
25
                    cout << "Y";
26
                }
27
            }
28
            cout << '\n';
29
        }
30
    }
31
}
32
int main(){
33
    solved();
34
    return 0;
35
}

算法基础集训营第三场 2.07#

赛题：https://ac.nowcoder.com/acm/contest/120563 出题人题解：链接
这一场相对而言还好，有比较基础的思维题，也有构造与证明的难题，虽然本蒟蒻只a出了3题。。不过赛后还是把看过的6题都补一下了。

A - 宙天#

这题直接把所有情况列出来就可以了，妥妥签到题。
思路，因为 $x$ 最大取到 $100$ ，那么可以自己手动推导所有的可能性然后判断，也可以写个循环判断输入的 $x$ 是否满足 $x = k \times (k + 1)$ 。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
void solved(){
6
    int x;
7
    cin >> x;
8
    if(x == 2 || x == 6 || x == 12 || x == 20 || x == 30 || x == 42 || x == 56 || x == 72 ||
9
    x == 90){
10
        cout << "YES";
11
    }
12
    else{
13
        cout << "NO";
14
    }
15
}
16
int main(){
17
    solved();
18
    return 0;
19
}

B - Random#

这题想过用暴力找所有质因数来判断是否有最大公约数大于1的两个数，不过不会线性筛。。题解根据概率进行小范围枚举显然是更优的方案。。。
思路：可以从偶数这一块来入手。根据题目的数据说明，实际上数组元素都是均匀随机生成，那么偶数出现的概率就是 $\frac{1}{2}$ ，而根据题意，特殊情况下只要有两个偶数存在就一定满足。题目给到的数据 $n$ 最大可以取到 $2e5$ ，我们可以只取后 $30$ 个数与其进行比较，只要存在两个偶数就退出循环，输出结果。同理于质因数，我们用 $gcd$ 函数来判断，可以提高成功的概率。除非题目就是要卡死最坏情况（概率小到离谱的那种），一般这种情况下都可以过了。。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
int a[200010];
6
void solved(){
7
    int t;
8
    cin >> t;
9
    while(t--){
10
        int n;
11
        cin >> n;
12
        for (int i = 1; i <= n; i++)
13
        {
14
            cin >> a[i];
15
        }
16
        bool f = 0;
17
        for (int i = 1; i <= n;i++){
18
            for (int j = i + 1; j <= i + 31&& j <= n;j++){
19
                if(__gcd(a[i],a[j]) > 1){
20
                    cout << a[i] << " " << a[j] << '\n';
21
                    f = 1;
22
                    break;
23
                }
24
            }
25
            if(f == 1) break;
26
        }
27
        if(f == 0) cout << -1 << '\n';
28
    }
29
}
30
int main(){
31
    solved();
32
    return 0;
33
}

F - Energy Synergy Matrix#

这题就是找规律构造，奈何我捣鼓了 $1$ 个小时都没找到。。。
思路：小红会尽可能缩短路径需要的长度，可以发现她在前5次都可以通过先手优势构造最短路 $n-1$ 步到达第 $n$ 列。而在第 $5$ 次后无论如何她都会被小紫逼到换一次行（增加 $1$ 步）,到了第 $10$ 次后又会增加 $1$ 次。所以结论就是最短路径 $n-1$ 加上 $[\frac{n}{5}]$ 。是的，就这样。。。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
void solved(){
6
    int t;
7
    cin >> t;
8
    while(t--){
9
        ll n;
10
        cin >> n;
11
        cout << n - 1 + n / 5 << '\n';
12
    }
13
}
14
int main(){
15
    solved();
16
    return 0;
17
}

G - スピカの天秤#

这题比较容易理解，想要改变状态就尽可能多地拿走较大的砝码，只不过因为时间复杂度问题要优化求和跟排序。题解直接用的排序，我用的优先队列。
思路：当重量相等的时候随便拿走一个就可以改变状态了，所以输出 $1$ 。当重量不等的时候就让重量较大的一方优先拿走较大的砝码（贪心），记录打破状态时拿走砝码的数量就可以了。
这里一开始以为优先队列有超时风险（因为加起来复杂度应该是 $O(T \cdot N \cdot log N)$ ，不过好在并没有。

NOTE
这里的优先队列 $priority\_queue$ 会将最大的值放在顶端pq.top()，剩下的值按从大到小依次向下排，所以拿走砝码时先减去pq.top()的值，再弹出值pq.pop()，下一次再调用pq.top()就会是第二大的值了。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
void solved(){
6
    int t;
7
    cin >> t;
8
    while(t--){
9
        priority_queue<ll> pq1;
10
        priority_queue<ll> pq2;
11
        int n, m;
12
        ll sum1 = 0, sum2 = 0;
13
        cin >> n >> m;
14
        for (int i = 1; i <= n;i++){
15
            ll x;
16
            cin >> x;
17
            sum1 += x;
18
            pq1.push(x);
19
        }
20
        for (int i = 1; i <= m;i++){
21
            ll x;
22
            cin >> x;
23
            sum2 += x;
24
            pq2.push(x);
25
        }
26
        int cnt = 0;
27
        if(sum1 == sum2){
28
            cout << 1 << '\n';
29
            continue;
30
        }
31
        else if(sum1 > sum2){
32
            while(sum1 > sum2){
33
                sum1 -= pq1.top();
34
                cnt++;
35
                pq1.pop();
36
            }
37
            cout << cnt << '\n';
38
            continue;
39
        }
40
        else if(sum1 < sum2){
41
            while(sum1 < sum2){
42
                sum2 -= pq2.top();
43
                cnt++;
44
                pq2.pop();
45
            }
46
            cout << cnt << '\n';
47
            continue;
48
        }
49
    }
50
}
51
int main(){
52
    solved();
53
    return 0;
54
}

H - Tic Tac DREAMIN’#

这题我只能说无敌了。。我用的数学公式是没问题的，只不过一直因为精度问题调不出来了，已疾苦。
思路：已知三个坐标求三角形面积公式： $S = \frac{1}{2} \mid x_1(y_2 - y_3) + x_2(y_3 - y_1) + x_3(y_1 - y_2) \mid$ ，然后根据题意知第三个点是 $(x,0)$ ，也就是 $y = 0$ 代入原式。可以得到有关 $x$ 的表达式子： $x = (2S - x_2 y_1 + x_1 y_2) \div (y_1 - y_2)$ 。满足误差时输出结果即可。
这里坑就坑在精度。。要保证面积精度为 $0.001$ ， $x$ 就须要更加精确，所以最保险是输出 $10$ 位小数。
同时对于无解的情况也要特判（ $y_1 - y_2$ 的时候无解），并且还有精度要到 $1e$ - $9$ （阴完了）。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
void solved(){
6
    int x1, y1, x2, y2;
7
    cin >> x1 >> y1 >> x2 >> y2;
8
    int q = y1 - y2;
9
    ll ans = (ll)(x1 * y2) - (ll)(x2 * y1);
10
    double x =(4.00000 - ans) / q;
11
    double m = 0.5 * abs(x * (y1 - y2) + x1 * y2 - x2 * y1);
12
    if(q == 0){
13
        double t = fabs(x1 * y2 - x2 * y1);
14
        if(fabs(t - 4.0) <= 1e-9) cout << 0 << '\n';
15
        else cout << "no answer" << '\n';
16
        return;
17
    }
18
    else{
19
        printf("%.10f\n",x);
20
    }
21
    //printf("%.2f", m);
22
}
23
int main(){
24
    solved();
25
    return 0;
26
}

J - Branch of Faith#

这题其实二叉树只是用来唬人的。。本质其实就是根据以

2

为公比，

1

为首项的等比数列进行判断和输出。
思路：根据我们自己画的图可以发现每一层的节点数其实就对应

2^n

的值（根节点为

0

，所以从

0

开始），我们要做的就是判断所给的数在哪一层（判断这个数是否大于等比数列前

n

项的和），在

n

对应的那一层判断是否填满，未填满的就用

n

减去前几层的和再加

1

（等比数列求和再加

1

）就是这一层所有的节点数了。查询的话同理判断就可以了，如果是最深层就输出未填满那一层的值。其他填满的层就直接输出对应层数的等比数列的值

2^n

。

NOTE
这里要注意长整型（ $long\ long$ ）最大值为 $2^{63}-1$ ，判断的时候只需要判断到是否大于 $2^{62}$ 就可以了，否则会溢出。
题目的输入 $n$ 最大取到 $1e18$ ，小于 $2^{63}-1$ （大约 $9e19$ ）。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
void solved(){
6
    int t;
7
    cin >> t;
8
    while(t--){
9
        ll n, q;
10
        cin >> n >> q;
11
        ll cnt = 0;
12
        for (ll i = 0; i <= 61;i++){
13
            if(n >= (1LL << (i + 1LL))){
14
                cnt++;
15
            }
16
            else{
17
                break;
18
            }
19
        }
20
        //cout << "cnt:" << cnt << '\n';
21
        while (q--){
22
            ll x;
23
            ll cnt1 = 0;
24
            cin >> x;
25
            for (ll i = 0; i <= 61;i++){
26
                //cout << "cnt1:" << cnt1 << '\n';
27
                if(cnt1 == cnt){
28
                    cout << n - ((1LL <<cnt)) + 1LL<< '\n';
29
                    break;
30
                }
31
                if(x >= (1LL << (i + 1LL))){
32
                    cnt1++;
33
                }
34
                else{
35
                    cout << (1LL << cnt1) << '\n';
36
                    break;
37
                }
38
            }
39
        }
40
    }
41
}
42
int main(){
43
    solved();
44
    return 0;
45
}

Mkrari的个人博客

算法基础集训营第一场 2.03#

B - Card Game#

C - Array Covering#

E - Block Game#

G - Digital Folding#

K - Constructive#

L - Need Zero#

算法基础集训营第二场 2.05#

A - 比赛安排#

B - NCPC#

F - x?y?n!#

I - 01回文#

算法基础集训营第三场 2.07#

A - 宙天#

B - Random#

F - Energy Synergy Matrix#

G - スピカの天秤#

H - Tic Tac DREAMIN’#

J - Branch of Faith#