都给我去看创世纪的超神番超时空辉夜姬

突然发现小标题太多就无法伸缩了，所以又开了新的一篇。

算法基础集训营第四场 2.09#

赛题：https://ac.nowcoder.com/acm/contest/120564 出题人题解（出题人这次没在牛客写，不过有相应的文档）：文档链接
这场神了。。。看标题就知道了。不过由于刚开的时候还在外面吃饭，所以给了2小时，后面 $16$ 点到家之后才开始打。。整体难度还是有的，基本全是构造。

A - 本场比赛灵感来源于树状数组出题组#

签到题，数据比较小，可以暴力解决，不过要注意 $80%$ 是除了这个数本身之外的其他数的 $80%$ 。（没注意就 $WA$ 了。）
思路：双循环遍历，用 $cnt$ 记录每次遍历之后满足小于等于 $a_x$ 的总数量，循环结束后再判断是否满足入A组的条件，满足就加入 $sum$ 。
$tips$ ：这里在判断 $80%$ 的时候用了十字相乘的方法规避小数乘法精度的问题。

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

3
using namespace std;
4
using ll = long long;
5
int a[1010];
6
void solved(){
7
    int n;
8
    cin >> n;
9
    for (int i = 1; i <= n;i++){
10
        cin >> a[i];
11
    }
12
    int sum = 0;
13
    for (int i = 1; i <= n;i++){
14
        int cnt = 0;
15
        for (int j = 1; j <= n;j++){
16
            if(a[j] <= a[i] && i != j){
17
                cnt += 1;
18
            }
19
        }
20
        if(5 * cnt >= 4 * (n - 1)){
21
            sum += a[i];
22
        }
23
    }
24
    cout << sum;
25
}
26
int main(){
27
    solved();
28
    return 0;
29
}

B - 构造部落#

这题主要是要理顺时间线的关系，取决于你怎么判断首领最后一年的年份（取前还是取后，我是取前了）。
思路：分析完题目你会发现，输出的文物的年份需要根据前任首领的在位年份进行求和，所以我们需要知道每一个首领的前几任的一共在位多少年，也就是前缀和。我这里的想法是把第一年减 $1$ 再加 $s$ 年表示元年，可以保证后面每次用 $b$ 数组表示的前缀和都是前一任首领在位的最后一年，方便计算。不过这种方法输出第一位首领的数据要特判一下。

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

3
using namespace std;
4
using ll = long long;
5
ll a[200010];
6
ll b[200010];
7
void solved(){
8
    ll n, q;
9
    ll s;
10
    cin >> n >> q >> s;
11
    cin >> a[1];
12
    a[1] = a[1] - 1 + s;
13
    b[1] = b[0] + a[1];
14
    for (ll i = 2; i <= n;i++){
15
        cin >> a[i];
16
        b[i] = b[i - 1] + a[i];
17
        //cout << b[i] << '\n';
18
    }
19
    while(q--){
20
        ll x, y;
21
        cin >> x >> y;
22
        if(x == 1) cout << s - 1 + y << '\n';
23
        else cout << b[x - 1] + y<< '\n';
24
    }
25
}
26
int main(){
27
    solved();
28
    return 0;
29
}

C - 墨提斯的排列#

依旧神奇构造。。后来查资料的时候发现居然是格雷码，一种单步变换的二进制码。
思路：我们想要让每相邻的两个数异或值最小，就让它们之间不同的位数最小（只有一位不相同），我们这里可以手动推导演示一下。
构造: $0,1$ ： $00,01$ 相差一位，和为 $1$ 。
$0,1,3,2$ : $00,01,11,10$ 每相邻的一位都是相差一位，和为 $1 + 2 + 1 = 4$ 。
$0,1,3,2,6,7,5,4$ ： $000,001,011,010,110,111,101,100$ 和为 $1 \times 4 + 2 \times 2 + 4 \times 1 = 12$
这里基本上就可以看出规律了，然后可以通过 $i \bigoplus (i >> 1)$ 来构造符合条件的排列。（也是格雷码的转换方式）通过错位异或的方式构造出只有一位不相同的排列。

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
    for(int i = 0; i < (1 << n); i++){
9
        cout << (i ^ (i >> 1)) << " ";
10
    }
11
    cout << '\n';
12
}
13
int main(){
14
    solved();
15
    return 0;
16
}

G - 真白的幻觉#

这题场上的时候没啥时间想了。。不过应该也是有规律的构造，所以赛后稍微补了一下。
思路：题目很好理解，就是在 $10^{18}$ 内找一个能让 $g(a)+g(b)$ 最大的值（ $f(x)$ 执行次数最大），那么我们可以发现数字中有 $0$ 和 $5$ 都是不合适的，因为这会快速导致数位出现 $0$ ， $1$ 的话不会影响最终结果。而像 $2,3,4,6,7,8,9$ 这些数则相对持久，在 $2$ 的倍数中我们可以尽量选择 $8$ ， $3$ 尽量选择 $9$ ，如果数位不足以构造 $8$ 或 $9$ ，就向下构造 $2,4$ 或者 $3,6$ 。最终找出数位最大的那两个就可以了。（题目要求不相等）
可以暴力枚举，也可以自己造。

NOTE
$277777788888899$ 是文献中著名的最小的持久性 $11$ 的数， $27777789999999999$ 是另一个在 $10^{18}$ 内的等价构造，在 $10^{18}$ 范围内能达到最大“乘数持久性”， $g(a) = g(b)=11$ ，使得 $g(a)+g(b)=22$ 达到最大。

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

3
using namespace std;
4
using ll = long long;
5
void solved(){
6
    cout << "27777789999999999 277777788888899";
7
}
8
int main(){
9
    solved();
10
    return 0;
11
}

I - 初华的扭蛋机#

这纯高中数学吧，数学期望这一块。。考验高中数学还记得多少的雷了。
思路：我们首先来分析颜色出现的概率，每个颜色出现的概率为 $\frac{1}{6}$ ，然后有 $3$ 次独立抽取，设某种颜色出现的概率为 $P_k$ ，则有 $P_k = C_3^k (\frac{1}{6})^k (\frac{5}{6})^{3-k}$ （这下看懂了）。我们可以算出对应 $k$ 的概率。
$P_1 = \frac{75}{216}$ ， $P_2 = \frac{15}{216}$ ， $P_3 = \frac{1}{216}$
然后我们可以算出数学期望。
$E_x = 2xP_1 + 3xP_2 + 10xP_3 = x \frac{2 \cdot 75 + 3 \cdot 15 + 10 \cdot 1}{216} = \frac{205}{216} x$
也就是每次在一个颜色下注后的期望是 $\frac{205}{216} < 1$ ，所以最好的选择就是 $6$ 次都保留原来的筹码 $6 > \frac{205}{36}$ 。

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

3
using namespace std;
4
using ll = long long;
5
void solved(){
6
    cout << "######" << endl;
7
}
8
int main(){
9
    solved();
10
    return 0;
11
}

算法基础集训营第五场 2.11#

赛题：https://ac.nowcoder.com/acm/contest/120565 出题人题解：题解链接
这场的基础题目就比较偏简单模拟和模板一点，简单的挺简单，有一些难度的就可能需要学过类似的解法才好做。。

B - 智乃的瓷砖#

这题是经典的生成字符矩阵，我觉得算是基础编程能力。
思路：直接根据行列和列的奇偶性分成四种情况，打表输出，这里要注意输出要用多用一个\来转义。

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

3
using namespace std;
4
using ll = long long;
5
void solved(){
6
    int n, m;
7
    cin >> n >> m;
8
    for (int i = 1; i <= n;i++){
9
        for (int j = 1; j <= m; j++){
10
            if(i % 2 == 1 && j % 2 == 1){
11
                cout << '/';
12
            }
13
            else if(i % 2 == 1 && j % 2 == 0){
14
                cout << '\\';
15
            }
16
            else if(i % 2 == 0 && j % 2 == 1){
17
                cout << '\\';
18
            }
19
            else if(i % 2 == 0 && j % 2 == 0){
20
                cout << '/';
21
            }
22
        }
23
        cout << '\n';
24
    }
25
}
26
int main(){
27
    solved();
28
    return 0;
29
}

D - 智乃的果子#

这题其实是哈夫曼树（最小生成树）的一个构建原理（可以了解一下），用优先队列直接模拟过程，但是会超时。。所以需要优化。
思路：想要最终的代价最小，其实就是要在每一次合并操作之后再找出最小的两个堆继续合并，这样不断操作到只剩最后一个堆时的代价就是最小的了。不过这题就阴在相同权重的果子并不唯一，最终一个一个模拟过程就会超时，我们需要对重复的堆进行合并。也就是当目前权重最小的堆的 $c$ 数量大于 $1$ 时，我们就取整半 $[\frac{p}{2}]$ 来合并， $[\frac{p}{2}] \times 2 w$ 加入总代价，然后加入新的权值为 $2w$ 的新堆。如果 $c$ 等于1，我们就按正常流程将它与次小权值的堆合并，生成新堆， $c$ 为 $0$ 就删除该堆，一直操作即可。
这里我是用 $map$ 自动排序和迭代器实现了优先队列（因为 $map$ 方便映射对应同权值的堆的数量）。

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

3
using namespace std;
4
using ll = long long;
5
#define mod 1000000007LL
6
void solved(){
7
    int n;
8
    cin >> n;
9
    map<ll, ll> mp;
10
    for (int i = 1; i <= n;i++){
11
        ll c, w;
12
        cin >> c >> w;
13
        mp[w] += c;
14
    }
15
    ll ans = 0;
16
    while(mp.size() > 1 || (mp.size() == 1 && mp.begin()->second > 1)){
17
        auto it = mp.begin();
18
        ll w1 = it->first;
19
        ll c1 = it->second;
20
        if(c1 >= 2){
21
            ll p = c1 / 2;
22
            ans = (ans + (p % mod) * ((2 * w1) % mod) % mod) % mod;
23
            ll w2 = w1 * 2;
24
            ll d = p;
25
            c1 %= 2;
26
            if(c1 == 0){
27
                mp.erase(it);
28
            }
29
            else{
30
                it->second = c1;
31
            }
32
            mp[w2] += d;
33
        }
34
        else{
35
            auto it2 = next(it);
36
            ll w2 = it2->first;
37
            ll c2 = it2->second;
38
            ans = (ans + (w1 % mod) + (w2 % mod)) % mod;
39
            ll w3 = w1 + w2;
40
            mp.erase(it);
41
            c2--;
42
            if(c2 == 0){
43
                mp.erase(it2);
44
            }
45
            else{
46
                it2->second = c2;
47
            }
48
            mp[w3]++;
49
        }
50
    }
51
    cout << ans << '\n';
52
}
53
int main(){
54
    solved();
55
    return 0;
56
}

F - 智乃的算法竞赛群友#

这题有点逆向思维内味了，通过反向枚举来将判断所有的情况，然后取出最优的（奈何场上的时候根本想不到）。
思路：这题其实子串所有可能出现的情况只有 $qcjjkkt$ ， $td$ ， $qcjjkktd$ 一共三种情况，而最先的想法肯定是尽可能地取 $qcjjkktd$ ，八个字符串双倍收益，也是贪心。而对于剩下不能再组成 $8$ 个字符的则枚举全为 $7$ 或者全为 $2$ 的情况，取其中一种快乐值较高的。而除此之外还有两种情况，一种是 $4$ 个 $td$ 比 $1$ 个 $qcjjkktd$ 高收益，另一种是 $8$ 个 $qcjjkkt$ 比 $7$ 个 $qcjjkktd$ 高收益，都进行一次反向枚举判断即可。
一共四种枚举情况，不过 $i$ 的最大值在这题中刚好取 $8$ 都能过（亲测），一般来说还是尽可能往大的取，不超时就行。

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, a, b;
10
        cin >> n >> a >> b;
11
        ll ans = 0;
12
        for (int i = 0; i <= 60 &&i * 7 <= n;i++){
13
            ans = max(ans, i * a + (n - i * 7) / 8 * (a + b));
14
        }
15
        for (int i = 0; i <= 60 &&i * 2 <= n;i++){
16
            ans = max(ans, i * b + (n - i * 2) / 8 * (a + b));
17
        }
18
        for (int i = 0; i <= 60 &&i * 8 <= n;i++){
19
            ans = max(ans, i * (a + b) + (n - i * 8) / 7 * a);
20
        }
21
        for (int i = 0; i <= 60 &&i * 8 <= n;i++){
22
            ans = max(ans, i * (a + b) + (n - i * 8) / 2 * b);
23
        }
24
        cout << ans << '\n';
25
    }
26
}
27
int main(){
28
    solved();
29
    return 0;
30
}

G - 智乃的箭头魔术#

这题就纯粹的模拟，至少我是选择把全部情况列出来然后判断的。。
思路：根据题意描述，最初是状态是 $"0"$ ，然后可以通过 $6$ 种操作改变状态，让我们输出每一次改变后这个玩具的状态。其实实际上就是去根据每一种情况来判断与继承状态，我们可以把 $4 \times 6 = 24$ 种情况全部列出然后对每个字符串进行判断即可。
这里可能需要一点空间想象能力，如果感觉烧脑的话就自己做一张简单的小卡片来玩一下就好了。

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

3
using namespace std;
4
using ll = long long;
5
void solved(){
6
    char t = '0';
7
    string s = "0112233445142015320125410214530214510214102302142025101203201451451522302514203214510021454101002532";
8
    for(char c:s){
9
        if(t == '0' && c == '0'){t = '3';cout << t;}
10
        else if(t == '0' && c == '1'){t = '0';cout << t;}
11
        else if(t == '0' && c == '2'){t = '1';cout << t;}
12
        else if(t == '0' && c == '3'){t = '2';cout << t;}
13
        else if(t == '0' && c == '4'){t = '1';cout << t;}
14
        else if(t == '0' && c == '5'){t = '3';cout << t;}
15
        else if(t == '1' && c == '0'){t = '2';cout << t;}
16
        else if(t == '1' && c == '1'){t = '3';cout << t;}
17
        else if(t == '1' && c == '2'){t = '0';cout << t;}
18
        else if(t == '1' && c == '3'){t = '1';cout << t;}
19
        else if(t == '1' && c == '4'){t = '2';cout << t;}
20
        else if(t == '1' && c == '5'){t = '0';cout << t;}
21
        else if(t == '2' && c == '0'){t = '1';cout << t;}
22
        else if(t == '2' && c == '1'){t = '2';cout << t;}
23
        else if(t == '2' && c == '2'){t = '3';cout << t;}
24
        else if(t == '2' && c == '3'){t = '0';cout << t;}
25
        else if(t == '2' && c == '4'){t = '3';cout << t;}
26
        else if(t == '2' && c == '5'){t = '1';cout << t;}
27
        else if(t == '3' && c == '0'){t = '0';cout << t;}
28
        else if(t == '3' && c == '1'){t = '1';cout << t;}
29
        else if(t == '3' && c == '2'){t = '2';cout << t;}
30
        else if(t == '3' && c == '3'){t = '3';cout << t;}
31
        else if(t == '3' && c == '4'){t = '0';cout << t;}
32
        else if(t == '3' && c == '5'){t = '2';cout << t;}
33
    }
34
}
35
int main(){
36
    solved();
37
    return 0;
38
}

J - 智乃的幻方#

依旧简单模拟，直接判断。
思路：直接根据题意判断所有条件是否符合，注意不要漏掉 $0-9$ 是否只出现一次这个条件。

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

3
using namespace std;
4
using ll = long long;
5
int a[4][4];
6
map<int, int> mp;
7
void solved(){
8
    for (int i = 1; i <= 3;i++){
9
        for (int j = 1; j <= 3;j++){
10
            cin >> a[i][j];
11
            mp[a[i][j]]++;
12
        }
13
    }
14
    for(auto&it :mp){
15
        if(it.second > 1){
16
            cout << "No";
17
            return;
18
        }
19
    }
20
    int sum1 = a[1][1] + a[1][2] + a[1][3];
21
    int sum2 = a[2][1] + a[2][2] + a[2][3];
22
    int sum3 = a[3][1] + a[3][2] + a[3][3];
23
    int sum4 = a[1][1] + a[2][1] + a[3][1];
24
    int sum5 = a[1][2] + a[2][2] + a[3][2];
25
    int sum6 = a[1][3] + a[2][3] + a[3][3];
26
    int sum7 = a[1][1] + a[2][2] + a[3][3];
27
    int sum8 = a[1][3] + a[2][2] + a[3][1];
28
    if(sum1 == sum2 && sum2 == sum3 && sum3 == sum4 && sum4 == sum5 && sum5 == sum6 && sum6 == sum7 && sum7 == sum8){
29
        cout << "Yes";
30
    }
31
    else{
32
        cout << "No";
33
    }
34
}
35
int main(){
36
    solved();
37
    return 0;
38
}

算法基础集训营第六场 2.13#

赛题：https://ac.nowcoder.com/acm/contest/120566
出题人题解（这场也是只有文档）：文档链接
难难难。。第二道题就已经开始二分和简单的 $dp$ 了，后面更是烟斗不带烟，做不了一点。。

A - 小L的三角尺#

这题看出来是贪心，不过没推出来规律，思路是错的。。整体也比较难，后续简单补了一下这题。
思路：我们可以看看每次打磨之后斜边的减少情况是怎么样的，这里可以数学推导一下：
设剩余长度为 $r$ ，初始时， $r = y_i$ 。
$\Delta = \sqrt{x^2_i + r^2} - \sqrt{x^2_i + (r - 1) ^ 2}$ 。
我们可以发现随着 $r$ 减少， $\Delta$ 严格递减，也就是磨得越多，收益越小。那么我们就可以知道，想要每次磨得收益最大化，就要将每次斜边最大的尺子磨掉一个单位，最终的收益就可以最大化，这才是真正要贪心的地方。我们可以用优先队列模拟这个过程。
实现：这里由于数据非常多且杂乱，所以用了一个结构体来记录对应尺子的所有数据并计算， $t$ 代表磨掉的单位长度，内置 $g$ 函数代表计算对应的收益。（方便每一步的计算）然后我们使用了二元组记录收益和对应尺子的下标， $lambda$ 定义比较器来按收益排列的优先队列，以方便我们的操作。
第一次操作的时候，我们把每一个 $y$ 不为 $0$ 的尺子都计算收益然后加入队列中。然后我们开始循环执行打磨操作，用 $p$ 记录操作的次数，当达到 $w$ 或者队列为空的时候停止循环。每一次循环我们都取出堆顶的元素进行操作，如果收益为 $0$ 就终止，否则就定位到相应的 $r$ 数组下标的元素，对内置 $t$ 加一（打磨一个单位），记录斜边总长的 $sum$ 减去这个收益，然后计算新的收益 $g1$ 存入这个数组元素，重新入堆（队列）排列。

NOTE
auto cmp = [](const pair<double, int> &p1, const pair<double, int> &p2){return p1.first < p2.first;};是一种 $Lambda$ 的表达式来定义比较器，指定了p2的优先级高于p1，所以在进入队列之后，p2就会排在p1前面。
decltype(cmp)由于cmp是 $Lambda$ ，所以需要decltype获取其比较器类型。
pq(cmp)构造函数，将cmp传入队列，让其使用该比较器。

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

3
using namespace std;
4
using ll = long long;
5
struct Ruler{
6
    ll x, y;
7
    int t;
8
    double g() const{
9
        ll r = y - t;
10
        if(r == 0) return 0.0;
11
        double a = sqrt(x * x + r * r);
12
        double b = sqrt(x * x + (r - 1) * (r - 1));
13
        return a - b;
14
    }
15
};
16
void solved(){
17
    ll n, w;
18
    cin >> n >> w;
19
    vector<Ruler> r(n);
20
    double sum = 0.0;
21
    auto cmp = [](const pair<double, int> &p1, const pair<double, int> &p2)
22
    {
23
        return p1.first < p2.first;
24
    };
25
    priority_queue < pair<double, int>, vector<pair<double, int>>, decltype(cmp)> pq(cmp);
26
    for (int i = 0; i < n;i++){
27
        ll x, y;
28
        cin >> x >> y;
29
        r[i] = {x, y, 0};
30
        sum += sqrt(x * x + y * y);
31
        if(y > 0){
32
            double g = r[i].g();
33
            pq.emplace(g, i);
34
        }
35
    }
36
    int p = 0;
37
    while(p < w && !pq.empty()){
38
        auto [g, x] = pq.top();
39
        pq.pop();
40
        if(g <= 0) break;
41
        auto &r1 = r[x];
42
        r1.t++;
43
        sum -= g;
44
        p++;
45
        if(r1.y - r1.t > 0){
46
            double g1 = r1.g();
47
            pq.emplace(g1, x);
48
        }
49
    }
50
    printf("%.10f", sum);
51
}
52
int main(){
53
    solved();
54
    return 0;
55
}

G - 小L的散步#

这题很好理解，我们每次都对小 $L$ 附近的石块进行判断是否踩中缝隙就好了。
思路：我们首先要用前缀和记录每块石块距离起点的长度，方便我们每次根据对应走出的总距离判断是否踩中缝隙。然后我们要找到离小 $L$ 最近的裂缝进行判断是否踩到。这里的查询我使用了二分查找（ $lower\_bound$ 函数），在 $b$ 数组中找到第一个比总步数 $ans$ 大的数，然后判断是否踩中了缝隙。
这里注意要特判是否还没开始走就踩缝隙了，因为后续的判断都是走了一步的。

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

3
using namespace std;
4
using ll = long long;
5
ll a[200010];
6
ll b[200010];
7
void solved(){
8
    ll n, m, l;
9
    cin >> n >> m >> l;
10
    ll ans = 0;
11
    for (int i = 1; i <= n;i++){
12
        cin >> a[i];
13
        b[i] = b[i - 1] + a[i];
14
    }
15
    if(b[1] < ans + l){
16
        cout << "YES" << '\n';
17
        return;
18
    }
19
    for (int i = 1; i <= m;i++){
20
        ll x;
21
        cin >> x;
22
        ans += x;
23
        auto it = lower_bound(b + 1, b + 1 + n, ans + 1);
24
        if(it != b + n + 1 && *it < ans + l){
25
            cout << "YES" << '\n';
26
            return;
27
        }
28
    }
29
    cout << "NO" << '\n';
30
}
31
int main(){
32
    solved();
33
    return 0;
34
}

H - 小L的数组#

得亏于数据只开到 $2047$ ，如果你意识到事实上结果也就最大取到 $2047$ 那就好做了。
思路：因为两个数组最大的数只能取到 $2047$ ，而无论是减法操作还是两数异或都不会让这个数更大了（不会超过 $2047$ ），那么你就只需要记录在 $[0,2047]$ 这个范围内，哪些数是取过的，然后遍历找出最大的就行了。我这里开辟了两个 $bool$ 数组 $c$ 和 $d$ 用来记录这种状态。然后用嵌套循环分别对 $A$ 和 $B$ 数组中每一个能取到的数进行记录，而取到的数在新的内层循环可以继续取新的数（其实就是 $dp$ ），由此可以把所有可能的结果都记录到 $c$ 中。
这里提一下：只用 $c$ 数组更新状态会导致本来只能执行一次的操作内执行了多次（反复增加新状态），所以要把下次要变换的状态用 $d$ 数组先储存，等这一轮的所有可能操作结束后再更新到 $c$ 数组里面。

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

3
using namespace std;
4
using ll = long long;
5
int a[2055];
6
int b[2055];
7
vector<bool> c(2055,0);
8
void solved(){
9
    int n;
10
    cin >> n;
11
    for (int i = 0; i < n;i++){
12
        cin >> a[i];
13
    }
14
    for (int i = 0; i < n;i++){
15
        cin >> b[i];
16
    }
17
    c[0] = 1;
18
    for (int i = 0; i < n;i++){
19
        vector<bool> d(2055,0);
20
        for (int j = 0; j < 2048;j++){
21
            if(c[j] == 0){
22
                continue;
23
            }
24
            if(j - a[i] >= 0){
25
                d[j - a[i]] = 1;
26
            }
27
            else{
28
                d[0] = 1;
29
            }
30
        }
31
        for (int j = 0; j < 2048;j++){
32
            if(c[j] > 0){
33
                d[j ^ b[i]] = 1;
34
            }
35
        }
36
        c.swap(d);
37
    }
38
    int ans = 0;
39
    for (int i = 2047; i >= 0;i--){
40
        if(c[i] > 0){
41
            ans = i;
42
            break;
43
        }
44
    }
45
    cout << ans << '\n';
46
}
47
int main(){
48
    solved();
49
    return 0;
50
}

K - 小L的游戏1#

签到题，不过刚开始打没睡醒。用了 $while$ 嵌套去模拟，结果超时了。。
思路：对 $z$ 取模 $(m + n)$ ，然后判断取模后的数落在哪个区间。在 $(1,m]$ 区间内小 $L$ 最后一手，输出 $0$ ，在 $\lbrace 1 \rbrace \cup (m,m+n)$ 中， $fallleaves01$ 是最后一手，输出 $1$ 。

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 x = 0;
10
        ll i = 1;
11
        ll m, n, z;
12
        cin >> m >> n >> z;
13
        ll x1 = z % (m + n);
14
        if((x1 > m && x1 < m + n) || x1 == 0){
15
            cout << 1;
16
        }
17
        else if(x1 <= m && x1 > 0){
18
            cout << 0;
19
        }
20
    }
21
}
22
int main(){
23
    solved();
24
    return 0;
25
}

后记#

随着最后一场比赛结束，寒假的算法学习就暂告一段落了。至少后续过年这段时间不会再学了。 $very\ painful\ ,\ bro$ 。不过新年期间应该还会写篇有关拜年祭的杂谈来练一下笔。

Mkrari的个人博客

算法基础集训营第四场 2.09#

A - 本场比赛灵感来源于树状数组出题组#

B - 构造部落#

C - 墨提斯的排列#

G - 真白的幻觉#

I - 初华的扭蛋机#

算法基础集训营第五场 2.11#

B - 智乃的瓷砖#

D - 智乃的果子#

F - 智乃的算法竞赛群友#

G - 智乃的箭头魔术#

J - 智乃的幻方#

算法基础集训营第六场 2.13#

A - 小L的三角尺#

G - 小L的散步#

H - 小L的数组#

K - 小L的游戏1#

后记#