❌

阅读视图

发现新文章，点击刷新页面。
☑️ ☆

Codeforces Round 942 (Div. 2)

✇Shiroha白羽的博客
Shiroha

A. Contest Proposal

大致题意

有两个数组 $a, b$，已经从小到大排序好了，现在往 $a$ 数组最前面再塞入几个值，同时从最后面删除相同数量的值，使得 $\forall i \in [1, n], a_i \leq b_i$

思路

简单题，由于数据量很小，甚至可以暴力

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (auto &i: a) cin >> i;
    for (auto &i: b) cin >> i;
    int l = 0, r = 0, ans = 0;
    while (l < n && r < n) {
        if (a[l] <= b[r]) {
            ++l;
            ++r;
        } else {
            ++ans;
            ++r;
        }
    }
    cout << ans << endl;
}

B. Coin Games

大致题意

有两个人做游戏，有几个英镑再桌面上，有些正面朝上有些背面朝上。

每次操作，允许移走一个正面朝上的，然后连续选择两个剩下的影片进行翻转

问谁会操作到最后一次

思路

翻转两个硬币等于没有翻转

AC code

1
2
3
4
5
6
7
8
9
10
void solve() {
    int n;
    cin >> n;
    string str;
    str.resize(n);
    cin >> str;
    int cnt = 0;
    for (const auto& c: str) cnt += c == 'U';
    cout << (cnt % 2 ? "YES" : "NO") << endl;
}

C. Permutation Counting

大致题意

有 $n$ 种卡片，每种都有一定数量，现在允许额外再增加 $k$ 张，使得这些卡片可以组成一个数组，数组种的存在的 $[1, n]$ 的排列的子串尽可能多，问可以有多少个

思路

只需要 $1, 2, 3, \dots, n, 1, 2, 3, \dots n$ 类似这样排列即可，通过二分找出每个数值都能到达的数量，然后排列起来

然后是剩下的那部分，比如多了一个 $1$，那么按照上面的排列方式，将 $1$ 放在最后面还能再多一次，即每有一个多出来的种类，就能增加一个子串

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#define int long long

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> data(n);
    for (auto &i: data) cin >> i;
    auto check = [&](int x) {
        int use = 0;
        for (const auto &v: data) {
            if (v < x) use += x - v;
            if (use > k) break;
        }
        return use <= k;
    };

    int l = 0, r = 1e15;
    while (l + 1 < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) l = mid;
        else r = mid;
    }
    int ans = 0, use = k;
    for (const auto& v: data) {
        if (v > l) ++ans;
        else use -= l - v;
    }
    ans = min(n, use + ans);

    cout << ans + (l - 1) * n + 1 << endl;
}

D1. Reverse Card (Easy Version)

大致题意

给出 $n, m$，求满足条件的 $a, b$ 对

  • $1 \leq a \leq n, 1 \leq b \leq m$
  • $(a + b) \space mod \space b \times gcd(a, b) = 0$

思路

假定 $a = x \times y, b = x \times z$，且 $gcd(y, z) = 1$
则可以得到

$$ & (a + b) \space mod \space b \times gcd(a, b) = 0 \\\rightarrow & x \times y + x \times z = t \times (x \times z \times x) \\\rightarrow & y + z = t \times x \time z \\\rightarrow & 1 + \frac{y}{z} = t \times x \\$$

容易得到，必然 $\frac{y}{z}$ 是整数，而 $gcd(y, z) = 1$，所以 $z = 1$，故 $1 + y = t \times x$

所以很容易得到公式进行计算

AC code

1
2
3
4
5
6
7
8
9
10
11
#define int long long

void solve() {
    int n, m, ans = 0;
    cin >> n >> m;
    for (int i = 1; i <= n && i <= m; ++i) {
        int my = n / i;
        ans += (my + 1) / i;
    }
    cout << ans - 1 << endl;
}

D2. Reverse Card (Hard Version)

大致题意

给出 $n, m$，求满足条件的 $a, b$ 对

  • $1 \leq a \leq n, 1 \leq b \leq m$
  • $b \times gcd(a, b) \space mod \space (a + b) = 0$

思路

假定 $a = x \times y, b = x \times z$，且 $gcd(y, z) = 1$
则可以得到

$$ & b \times gcd(a, b) \space mod \space (a + b) = 0 \\\rightarrow & x \times z \times x = t \times (x \times y + x \times z) \\\rightarrow & x \times z = t \times (y + z) \\\rightarrow & x \times = \frac{t}{z} \times (y + z)$$

容易得到，必然 $\frac{y}{z}$ 是整数，而 $gcd(y, z) = 1$，所以必然只能用 $t$ 来承接除过来的 $z$，即上述公式中的表达

所以可以根据公式得到，只需要找到合理的互质数 $y, z$，即可找出有多少个 $x$ 满足条件，因为 $t$ 可以是任意值，即 $x$ 是 $y + z$ 的倍数

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#define int long long

void solve() {
    int n, m, ans = 0;
    cin >> n >> m;
    if (n < 2 || m < 2) {
        cout << 0 << endl;
        return;
    }

    function<int(int, int)> gcd = [&](int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    };

    for (int i = 1; i * i <= n; ++i) {
        for (int j = 1; j * j <= m; ++j) {
            if (gcd(i, j) != 1) continue;

            ans += min(n / i, m / j) / (i + j);
        }
    }
    cout << ans << endl;
}
☑️ ☆

Codeforces Round 926 (Div. 2)

✇Shiroha白羽的博客
Shiroha

A. Sasha and the Beautiful Array

大致题意

有一个数组，现在允许你任意排序它，使得其所有的相邻对之差之和最小，问如何操作

思路

排序一下就行，这样就等于最大的那个值减去最小的那个

AC code

1
2
3
4
5
6
7
8
9
10
11
12
void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        vector<int> data(n);
        for (auto &i: data) cin >> i;
        sort(data.begin(), data.end());
        cout << data.back() - data.front() << endl;
    }
}

B. Sasha and the Drawing

大致题意

有一个正方形，其上有 $4 \times n - 2$ 条对角线，现在要你染黑一些格子，使得这些对角线至少有 $x$ 个被覆盖，问最少染黑几个

思路

只要染黑第一行和最下面一行即可，显然，除了四个角落，其他几个点染了就是影响两条对角线

AC code

1
2
3
4
5
6
7
8
9
10
11
void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n, m;
        cin >> n >> m;
        if (m <= 4 * n - 4) cout << (m + 1) / 2 << endl;
        else if (m == 4 * n - 3) cout << 2 * n - 1 << endl;
        else if (m == 4 * n - 2) cout << 2 * n << endl;
    }
}

C. Sasha and the Casino

大致题意

在赌场赌博，已知每次可以下注任意合理的钱 $y$，赢了就收回 $k \times y$，输了就没了，且最多连续输 $x$ 场，问是否赚到任意数量的钱

思路

根据赌徒原理做，要保证你每次下注的时候，如果赢了能把之前输的钱全都赚回来，且还要多赚一点

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#define int long long

void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int k, x, a;
        cin >> k >> x >> a;
        int ca = a, lose = 0;
        bool flag = true;
        for (int i = 0; i < x; ++i) {
            int cur = (lose + k - 1) / (k - 1);
            if (ca < cur) {
                flag = false;
                break;
            }
            ca -= cur;
            lose += cur;
        }
        if (ca * k <= a) flag = false;
        cout << (flag ? "YES" : "NO") << endl;
    }
}

D. Sasha and a Walk in the City

大致题意

有一棵树，现在要选择一定数量的节点染色，使得任意两个节点之间的路径最多只经过两个染黑节点，问如何操作

思路

树上 dp 即可，关注当前节点到所有下面的子节点中，染色数量最多的路径染色了多少个，可以枚举 1 个和 2 个的情况（0 个一定只有一种）

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#define int long long

void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        constexpr int mod = 998244353;
        vector<pair<int, int>> edges((n - 1) * 2);
        vector<int> head(n + 1, -1);
        for (int i = 0; i < n - 1; ++i) {
            int u, v;
            cin >> u >> v;
            edges[i << 1] = {v, head[u]};
            edges[i << 1 | 1] = {u, head[v]};
            head[u] = i << 1;
            head[v] = i << 1 | 1;
        }

        function<pair<int, int>(int, int)> dfs = [&](int u, int p) {
            int a = 1, b = 0;
            for (int e = head[u]; ~e; e = edges[e].second) {
                if (edges[e].first == p) continue;
                auto [na, nb] = dfs(edges[e].first, u);
                a = (a * (1 + na)) % mod;
                b = (b + na + nb) % mod;
            }

            return make_pair(a, b);
        };

        auto [a, b] = dfs(1, 0);
        cout << (a + b + 1) % mod << endl;
    }
}
☑️ ☆

我的ACM脚印

✇Shiroha白羽的博客
Shiroha

2020年12月20日，南京区域赛结束，同时结束的，还有我的两年多的ACM生涯
接下来的寒假重心会向着找实习的方向努力，当然明年还有线下的区域赛、EC-finial以及明年的省赛等等，我都会去认真准备。

这篇文章会写什么

  • 关于我
    • 我的ACM简单的回顾
    • 我的ACM成绩
  • 写给新人
    • ACM到底和数学建模、挑战杯等等的其他竞赛有什么区别
    • ACM到底带给我什么了
    • 为什么要打ACM
    • 什么样的人适合去打ACM，什么样的人不适合去打ACM
  • 写给已经进入了ACM的人
    • 我在ACM的训练计划
    • 除了ACM之外的计划
  • 关于ACM写题
    • ACM算法的学习规划
    • 我的一些经验之谈

这篇文章更多的是想来自我总结一下历史，如果与你的理解有出入也请见谅

关于我

我的ACM简单的回顾

进入大学之前

我是2018年进入的大学，在这之前，我压根没有听说过ACM，也完全不知道这类竞赛，高中也是没有打过OI，也就是真正的纯粹的小白。当然，我的高中压根就不知道有什么叫OI的比赛，可能这就是所谓的省B类学校吧

但是我有优势，我从高一开始自学了程序，我当时想自己写游戏，然后学起来Unity了，也就顺便学了C#。至于优势，大概就是对程序有了自己的理解吧。如果让我对代码理解这个事情上进行一个分级的话，我会这样分：

  • 完全不会程序（基本上就是那些完全没有学过代码的人）
  • 学会了顺序、选择、循环语句（一般是刚刚开始学程序的人，对程序是万能的这条表示怀疑的人）
  • 能够灵活的运用上述三种语句（突然发现仅使用这三种语句居然可以实现一切逻辑，相信代码是万能的，只是需要写代码的。通常这类人同样相信代码是高效的，认为所有的事情基本上都可以在电脑上花费一小段的时间就能得出结果）
  • 知道了代码是非常局限的，计算机能计算的速度是非常有限的，在解决一个问题前会思考这个问题的逻辑，对这个问题进行优化以适合计算机去运行，这类人也就是一个ACMer的入门点

而那时候的我，大概就是第三类的人，比起同时期的同学，只能说我拥有着非常好的起点

但是，实际上，通过一个学期的学习，基本上所有的学生都能到达这个水平

大一

大学的第一个学期，课程安排是学C语言，但是我其实并不需要，因为这些东西只需要我把我学C#的知识转成C就行了

而这个学期，校集训队也联系上了我，只不过因为我有提前的知识了，虽然我在那个时候还完全不知道对于代码还有第四层理解
当然，慢慢的我也接触到了很多算法，例如dfs、bfs之类的，只能说我在那个时候对ACM的理解还存在于ACM是提供更多的解决问题的办法而已
后来，学到了在ACM中最重要的东西：复杂度
也慢慢的开始学习到各种基础的算法：gcd、最短路、背包问题、KMP等等之类的

后来，我在大一快结束的时候，和另外两位大一参加了西安邀请赛，然后成功打铁……
紧接着是校赛，但是那次校赛的难度太高，导致全场只有20个人过题，我有幸过了两题。但是我和之前组队的两个大一的同学分开了队伍。
然后是浙江省省赛，和两个大二的人组队，然后继续打铁
再接下来是南昌邀请赛，我终于拿到了人生以来的第一个奖牌：铜

然后就是整整一个暑假的集训，杭电的多校、牛客的多校，题目的难度对于当时我而言，未免是过高了一些。那两个月，可谓是绝对的自闭

大二

大二开始，大概是因为经历了暑假的自闭式训练，拿下了一个ICPC的区域赛银牌，虽然是银川偷鸡，但基本上是我一个人完成的比赛，而且其实本来很有希望冲击金牌

大二下半学期，因为疫情的原因，荒废了很久，没有出去打比赛，只能说是不断的学习吧。
也趁着疫情，顺便把CodeForces上把我的两个账号都刷到了紫名

当然，因为写的题多了，代码写的多了，感觉自己写题目的习惯开始发生了改变，特别是经常打CodeForces后，感觉自己对很多思维的理解在不断的加深。大一选择了图论方向，大二开始学数据结构，然后再学了字符串，稍微了解了dp，队内也把构造题的任务分配给了我

大三

这个学期难得有了好多场比赛，而我们原来参加了西安邀请赛的三个人，我们重新组成了完整的队伍，也夺下了省赛银牌、CCPC威海铜牌、ICPC南京银牌这样三个牌。

我的ACM成绩

到目前为止，总共拿下了两个ICPC区域赛银牌，一个CCPC的铜牌，一个浙江省省赛银牌，一个ICPC邀请赛铜牌，Codeforces两个账号都是紫名，准备寒假冲击橙名。接下来会参加一场线下的ICPC比赛以及EC-finial。未来可能在能够拿到offer的情况下，继续回来参加ACM竞赛

写给新人

ACM到底和数学建模、挑战杯等等的其他竞赛有什么区别

如果你是计算机学院的，那么你需要追求的、考虑的唯一的竞赛就是ACM

ACM是一个非常全面的竞赛，如果你说你只是喜欢数学，那么ACM比数学建模之类的数学竞赛更加具有挑战性，同样，难度更高。对的，在我的认知中，ACM对数学的要求甚至远远高于数学竞赛。因为ACM和其他比赛不一样的一点，便是ACM不设置任何的知识点上界，越新的知识点，越高级的知识点，ACM都可以考。甚至任何一道数学竞赛的题，如果你在ACM中见到，都是合情合理的。在打ACM的时候，这个知识点不会的情况是很正常的，是所有参加了ACM竞赛的人可以深切感受到的。而如果你只是去打数学之类的竞赛，如果你不能到达一个很高的层次，你可能很难体会到那种，自己完全不会，完全是毫无能力的那种绝望感。而在ACM，你可以在任何一场比赛中见到，甚至是随便在点开的一场比赛。

其次，ACM是一个非常公平、公正同时也是非常严格、残酷的比赛，甚至因为它的机制，你可以认为它是你整个大学生涯中见到过，最公平，也是唯一一个能够让参赛选手心服口服的比赛。因为ACM几乎不存在任何的主观因素，你只有准确完整的解决这个问题，你才能拿到那么一点成绩分。而且ACM系列竞赛结束，如果这场比赛有任何一道题有一些问题，通常出题人都会出面道歉。这也是我第一次知道，原来负责出题的人也是要道歉的。从那样的高考制度过来，我们甚至都不会去关心出题人是谁，即使他出了岔子，也会有专门的公关来解决。ACM却没有这些无聊的内容。

数学建模也好，挑战杯也罢，评委老师评分制意味着主观可以胜过客观，甚至，到最后可能变成了PPT大赛。如果说这类竞赛的好处，我觉得除了给你提高了拿到奖学金的可能性，对于自身能力的提升以及后续的工作而言甚至意义并不大。而奖学金，能比得上你找到一个好工作后在一个月内赚的钱多吗？你难道能一辈子拿奖学金过日子吗？当然这样的人是存在的，但是我相信大多数读者也和我一样，觉得这是一种奢望。

ACM到底带给我什么了

知识

我在ACM集训队的第一周，我所得到的知识，是我的室友们在大学四年内都可能会学不清楚、理不通的知识，而那些知识点，在我经历了两年多的ACM训练后觉得，这些只不过应该是理所当然会的、最基本的知识。这些知识点带给我的财富，是我在经历了四五个项目后，才意识到的我们与其他人的差距。ACM的知识点，只要你未来是做计算机行业的，那么它一定会在每一个角落里发挥着它的作用。

思维

ACM的题，对一个人的思维能力的提升有着非常恐怖的作用。特别是当你频繁的打Codeforces比赛时，你会深切的体会到自己的思维能力在以非常恐怖的速度进步。而与思维能力直接挂钩的，便是逻辑思路以及问题的敏感性。如果有人去看过杜老师的Codeforces录播视频，看过tourist的比赛视频，你会发现他们基本上并不会去论证一个方法的可行性，他们通常在读到这道题的时候，会反应过来这题“好像这样搞搞”、“在随便暴力一下”、“应该就对了”。这样的思路也正是我现在打Codeforces的一种感觉，当然我还不能到达杜老师这样对于这么难的题也可以如此轻松的想出解法，但是我仍然觉得我思考问题的思路和方向变得非常的开阔，而且思考问题的逻辑自然变得严谨合理。

代码实现能力

ACM的题，难度较高的题，有些需要各种数据结构的嵌套，需要各种开辟各种奇奇怪怪的数组。而你需要在短时间内完成代码的编写和调试，这无疑是对代码能力的直接挑战。例如Codeforces，5道题目只有两个小时，除掉读题（纯英文题面）和思考问题的时间，你又有多少时间可以来写代码调试代码呢？当室友还在为编译出错烦恼时，我们基本就不需要调试百行代码以下的程序，因为只需要简单的测试证明其确实没有错误即可。

ACM朋友圈

ACM届有一个最高级别的竞赛，被称为WF（world finial）——世界总决赛。这场比赛的含金量有多高？也许有人会说，最多也就是拿到金牌可以全球500强随意挑。但是，实际上只需要你碰到了这个比赛的边界，你只要有幸被邀请参加了这场比赛，不论你的名次，这个星球上的企业你已经可以随意选了，而且本科毕业就可以去工作的那种。而我们平时聊天水群，里面有的是因为ACM成绩优异而进入Google中国、微软亚洲研究院的人。而对于正常学业而言，各位也应该知道你需要读多少年的书才有胆量往这些企业中投递一份简历

学长学姐

通常能坚持下来打ACM的都是能够在思维、能力、勤奋或者智商上略胜一筹的人，那么和这样的学长学姐在同一个实验室的屋檐下打比赛，你能得到的帮助和支持，远远超过参加社团带来的收益。

直面清北复交

ACM竞赛是所有队伍在相同地点使用相同设备在相同的时间内解决相同的题目。

而你的对手则是来自全国的大学，对，北大清华每年都会来，而且非常重视。

ACM从来就没有院赛、校赛、省赛等等一大堆乱七八糟的东西，虽然他们确实存在但是他们并不是被官方承认的。ACM只有区域赛，（比如Asia-East东亚地区），区域总决赛（比如EC-finial，东亚地区总决赛），和世界总决赛（WF）。无论在哪个比赛，你都可能会遇到任何一个学校的队伍。所以在这样的比赛中，你可以很清楚的知道自己的水平在全地区范围内的位置，对自己的能力有一个更好的评估，能够看到外面更加广阔的天空。而不是拘泥于那么小的一个地区，争夺那么毫无意义的第一名

为什么要打ACM

因为我要证明我自己

在ACM比赛中，你会真实的，亲身和北大清华等等高校在同一个体育馆里，使用相同的设备相同的时间来解决相同的问题。那么你为什么不去证明自己比他们强？我知道这通常不可能，因为他们也会派出他们最强的队伍来与你们竞技。但是我们需要的就是在这么多的强队中，证明我们自己的能力。在计算机领域内最有影响力的比赛中，证明自己而已

什么样的人适合去打ACM，什么样的人不适合去打ACM

ACM竞赛是一个需要大量的时间去投入，但是到很久之后才会有结果的产出。这和其他竞赛不同，数学建模通常你只需要很短的时间训练就能拿出成绩，而一个ACMer，在大三之前甚至可能都没有一点点成果。但是你在大一大二的投入终将会给你在大二下至大三上的时候带来丰富的回报。

这样的回报，需要愿意投资的人耐心投资才有可能赚得盆满钵满，一旦出现懈怠都有可能颗粒无收。耐心、专注、勤奋、自觉这些是一个ACMer必须要具备的因素。

写给已经进入了ACM的人

我在ACM的训练计划

  • 保持在Codeforces的个人刷题，最好是现场比赛，其次是复现比赛。Codeforces对训练一个人的思维能力有者极大的帮助作用，而且其出题非常的新颖，是我认为最适合ACMer进行个人训练的平台。Codeforces的思维题数量非常庞大，而且非常的有趣。正式的区域赛等比赛，通常思维题也会占据很大一部分比重。
  • 队伍内保持至少一周一场往年比赛的复现赛，我们队在长达几个月的集训时间内保持了一周两场比赛且不耽误正常课程。
  • 当你决定要写ACM题时，请不要断开，也尽可能避免使用碎片化的时间学习，这对学习的进度没有任何帮助，除非你只是突然需要回忆一个知识点。
  • 在实验室内写题而不是在寝室或者图书馆或者其他任何地方写题。

除了ACM之外的计划

ACM毕竟只是我们大学的一个工具，我们希望它能够服务于我们找工作、服务于我们在其他领域的发展。不可以把ACM当成是自己在大学里唯一执着的对象，甚至把它树立为人生目标，这不合实际也没有意义，反而会影响你的正常社交与生活，这不应该是一个人的目标。

关于ACM写题

ACM算法的学习规划

在经历了两年多的学习之后我发现，其实很多的算法并没有太多的学习意义，或者说不必要为其投入过多的经历去学习。
我是负责队伍内的图论+字符串，以及构造题思维题，会数据结构，了解dp和树上问题。
另外一位队友负责计算几何和博弈论，以及数论，会dp，了解图论和树上问题
还有一位队友负责了数据结构和dp，以及树上问题，会数论，了解图论
基本上可以说是覆盖了所有的知识面，而且大部分知识面都是有多个人会。

我以我熟悉的图论为例，诸如“最大流”这些个算法，通常对于一个银牌队伍而言，其实学习的意义并不大。因为我至今未见到过最大流题的难度低于金牌题的（按照实际区域赛出题情况）相反，灵活的结合思维和拓扑排序，你会发现图论问题变得非常简单。很多区域赛的图论的铜牌题在你眼里变成了暴力傻逼题。这是对于一个图论选手在频繁使用图论相关的知识点的时候自然而然形成的。

我认为把学习那些过高的知识点重要性低于去熟练掌握最基本的算法的内容。

对于字符串也一样，上一次看到“回文树”是在复现赛上看到的，是一道金牌题，虽然对于会“回文树”的队伍而言相对简单很多，但是作为一道金牌题，很多时候在比赛现场可能根本没有时间去看这样一道题。

当然你的队伍是为了冲金牌的，这些知识点当然也应该成为你的必须知识点之一。

我的一些经验之谈

  • 看题一定要看数据，通过数据大小猜测算法的复杂度，再去考虑可能的算法逻辑。通常为了卡掉错误的算法，正确算法的复杂度应该在$1e6-1e8$之间，前者考虑可能有很大的常数的复杂度，后者则是最差的不可能发生的情况下的复杂度。
  • 队伍内除了在最后冲刺的时候，其他时间内务必保证多开，无论何时也不要三个人讨论同一个问题，即使你们现在被榜丢下了。甚至很多时候可以尝试三开
  • 队伍中每个人都应该具备非常良好的代码能力，除非你们队伍中专门有数学专业的人帮忙

Shiroha @2020.12.21凌晨1点30分

☑️ ☆

Summer Pockets 动画完结

✇Shiroha白羽的博客
Shiroha

无论怎么说，恭喜最终是完结了。作为一个原作党，对于剧情什么的，也没有什么特别能够想表达的内容，毕竟剧本已经放在那边，给制作组能够自由发挥的空间也很少。

不过原作的文本量巨大，虽然已经作为半年番的方式播出，但个人感觉还是不够长，很多原作中的剧情并没有很好的表现出来，很多感情的递进都没有很恰当的表达，这也是导致我看番的时候有一种比较割裂又自然能够衔接上的点。这里说几个个人很遗憾的细节场景，如果有兴趣的话建议还是玩一下原作

羽未回忆自己的原来生活的片段

原文大概是这样的

  • 晚上，我做了两人份的饭
  • 一份是给我的
  • 一份是给爸爸的
  • 我将他们分装在盘子里，然后盖上了保鲜膜
  • 一个人吃完饭，洗好自己的胖子，做完作业……
  • 然后去洗个澡，就准备睡觉了
  • 我钻进被子里闭上了眼睛
  • 没过多久，玄关就传来了开门的声音
  • 是爸爸他回来了
  • 但是他什么都没有说。我能听到的，就只有他那在地上拖着的，疲惫的脚步声
  • 这是我司空见惯的事情
  • 餐桌上传来了塑料袋被放下的声音
  • 那里面，装着的一定是他在便利店里买来的酒和下酒菜
  • 这也是我司空见惯的事情
  • 所以，我就直接这样睡了过去
  • 早上醒来的时候，家里就只剩下我一个人了
  • 我走进厨房
  • 发现之前分装在盘子里的饭还是还是原模原样地被放在那里
  • 所以，我就将它放进了微波炉
  • 等待了两分钟
  • 这样，早饭就做好了
  • 这还是我司空见惯的事情

还有一些别的场景，我也打算后面再补充一些，个人感觉这一幕被压缩了太多时间，这里感觉更适合花费更长的时间去表达这种生活，就像 CLANNAD 中因为渚离开后，男主那种颓废状态，似乎就是一个很好的参考

☑️ ☆

香港银行开卡记-1

✇Shiroha白羽的博客
Shiroha

本文内嵌了 Google Map，请考虑当前的网络环境是否支持查看

背景

前段时间前往了香港一趟，主要是因为我妈想要换手机了，所以只能打算把我现在的手机给她，然后我自己再去买个新的。考虑到现在 Apple Intelligence 也没有打算在国内上线，所以打算去一趟香港买手机，顺便办下卡

由于自己早就有了别的港卡，所以这次去香港主要是想要办一张中国银行的卡。虽然中资银行的服务不咋滴，同时背景也不好，但是给的汇率确实令人欣喜

安排

考虑到中国银行周六只上半天班，周日不上班的情况，所以如果要办理的话，推荐周五或者其他工作日去办理，大概办理一次的时间要 1-2 个小时

我的方案是周四晚就飞到深圳，然后在福田站附近先睡一晚，第二天一大早起来赶火车去火车站，福田站有一条直达的火车线路，虽然一般地图会告诉你需要 1 小时左右，但是实际上过去大概只需要 15 分钟，这里预估的时间应该都是加上了过海关之类的时间

火车线路

如果打算的是 walk-in，由于开户需要很早过去排队，所以推荐尽可能早的火车班次，然后直接去银行门口排队等开门，特别是西九龙这块的银行，比如中港城的

这家银行一天只给 25 个开户名额，所以基本上只要超过 9 点到，就赶不上了。这里推荐一家我去开的分行，在九龙城区

这家在西九龙下火车后，直接做地铁就可以直达，非常快，而且人比较少，一般 14 点 walk-in 都能进去开户。特别的一点是，这里附近 100米就有一家图书馆，香港的图书馆提供打印服务，所以如果缺少什么文件的话，就可以来这里打印，虽然开门有点晚

当然也可以考虑走预约开户，地址是 这里，但是预约其实挺难预约到好的分行，基本上提前一周进去开，还是不一定能抢到西九龙的预约名额。所以如果真的要推荐的话，可以先看看能不能预约上，即使是北区也凑合，然后再 walk-in 这家试试能成就行，不能成再去北区

注意事项

中银香港开户是需要准备纸质材料的，但是最终他们不收材料，只会拿你的材料复印一份存档。我这边推荐带上以上材料

  • 身份证（原件，无需复印，必须）
  • 港澳通行证/护照（原件，无需复印，必须）
  • 过关小票（原件，无需复印，必须）
  • 最近的信用卡账单，要求上面必须要有一个居住地址，作为地址证明（如果没有的话，那就用身份证上的地址作为居住地址吧）
    • 国内的信用卡现在都是用电子账单，不一定有居住地址，很多银行是支持开带有居住地址的信用卡账单的，可以问下客服
    • 因为国内的信用卡账单填写的实际上是通讯地址，也不怎么检查地址的真实性，所以实际上可以通过国内信用卡地址来把你银行登记的居住地址改为任意地址
    • 如果给不出信用卡账单之类的东西，那就乖乖填身份证上的地址吧，记得跟柜员说你的通讯地址和居住地址不同，这样后续寄送材料的时候，就可以问问是否会寄送到通讯地址而不是居住地址
    • 因为很多寄送的卡片都是平邮，如果你的居住地址比较偏僻，可能会导致丢件，所以推荐还是通讯地址填写一个比较可靠一点的地方
  • 公司内提供的收入证明，用来证明你的收入资产，开户会方便很多
  • 最近半年的银行卡流水，同上，也是为了财产证明，毕竟国外的银行让你来开户都是希望从你身上赚点钱，而不是就白白让你开个户然后里面一分钱都不留
  • 找一个过去的证券账户的结单，一般不推荐最近的结单，可以早半年甚至一年的结单
  • 如果希望开通中银香港的美元证券账户的话，需要地址证明是英文的，但好像大家都不会去用他们的美元证券账户，所以好像也没啥用
  • 另外请务必保证手机号在香港能够正常收到短信，否则开户的手机号你只能临时找别人的手机号顶替了
☑️ ☆

《黑神话:悟空》游玩评测

✇Shiroha白羽的博客
Shiroha

开篇

首先还是恭喜悟空在发售后四天内完成了 1000万份的销售

在经历了 73 个小时的游玩之后，最终达成了九九八十一难的全成就，虽然没有完成二周目的探索，但是也算是经历了几乎全部的游戏内容

成就

个人评价

石刻

首先是非常巧的一点，在今年 6 月底的时候，恰好去到了大足石刻现场，也拍了不少照片，这里放一张大足的千手观音照片

千手观音(大足石刻宝顶山景区)

所以在看到黑神话第三章开始的大片的石雕的时候，也感受到了一种非常熟悉的感觉。和现场不同的一点是，现场的很多石刻，几乎没有太多的保护措施， 以至于漆画掉落严重，但是游戏中似乎都被比较好的进行重新上色了

大足石刻(大足石刻宝顶山景区)

可以说在建模方面（虽然大部分应该都是扫描的）确实做了不少功夫

购买之前

接着来说说游戏本身。我并不是第一时间购买游戏的玩家，相反，我直到 23 号晚上才购买下游戏，且直到 24 号才开始游玩，有两个方面

  • 游戏本身被认为是是更接近于魂系游戏，而我个人并不是对这类游戏很感兴趣
  • 国产游戏带来的失望太多，更何况是一个从 7 个人的小团队开始开发的游戏。个人并不希望无脑的对国产游戏而进行购买，反而是希望能够将自己的支持有意义

最后决定购买的核心因素，一方面确实没有出现与最初的预告片的效果差距较大的心理落差的讨论，另一方面则是整体的游戏难度和一般的魂系游戏而言，确实较为简单

游玩评测

画面与地图设计(9.5/10)

游戏的画面确实值得相当高的评分，无论是森林、沙地、雪山等等的画面确实值得评价为难以挑剔，在第三章的小西天土地将天命人带去湖上的过程，一路的雪景确实给我带来了不小的震撼

整体的地图设计也相对合理，虽然游戏没有给出地图，但是在游戏内容的指引还是相当清晰的，特别是在主要路线上安置了相当多的火盆火把用来提示路线

但是有个别地方还是缺少一些对于无地图的游戏的设计，比如在花果山的时候拿到筋斗云之后，反而不知道应该去哪里，特别是当我拿到筋斗云之后乱飞了一阵子，就彻底迷了路，我甚至都不知道自己在哪里
有人说可以跟着雷声走，起码能找到一个 BOSS，但是我当时所在的地方完全听不到雷声，同时更可怕的是，我无法降落，也无法传送，只能退出游戏重新进入的方式来回到土地庙。而回到土地庙之后，本来应该依靠打完 BOSS 后的剧情朝向来了解下一步应该去哪，变成了完全不知道接下来应该去哪了
如果说前 5 章的地图像是有过完整的地图设计，确实值得无地图的话，而第六章的地图可以说是完全没有设计，把所有的 BOSS 都堆积在一个圆形的大平台上一样

音乐音效(8.5/10)

音乐方面，可以很容易听出有不少的老板西游记电视剧里的音乐或者是变奏版本，这确实带来了不少好感，但是整体游玩过程中，音乐的体验似乎有点缺失，很难让你能分别出来，这个时候你应该注意安全，还是应该继续前进
在音乐方面一个非常典型的例子是《塞尔达传说荒野之息》中的沙漠地区，当 BOSS 吃到炸弹然后倒地的时候，背景音乐会立刻变奏来提醒你应该上前进攻了，或者 BOSS 瘫痪了。

故事情节(8.5/10)

如果这个游戏是一个纯粹的魂系游戏，那我会给故事情节打 9.5 分甚至更高，但是既然制作者都说这不是魂系游戏了，那我只能给出 8.5 的评分
也许可能是我很小的时候就没有再看《西游记》了，其中对很多很多的故事情节反而没有任何印象，难以和游戏情节搭上，比如猪八戒什么时候和蜘蛛精有过关系了？我好像没有印象，再比如牛魔王的女儿萍萍有什么什么故事情节，猪八戒又什么时候杀了她的家人？我好像也没有印象，反而让人更加困惑
甚至红孩儿什么时候变成了夜叉？我越来越疑惑，在一路疑惑中继续打下去，似乎也没有给出太多的答案
当然你也可以说我没有认真看过《西游记》不知道故事情节，但如果这不是一部粉丝向作品的话，那我只了解其中的大致情节似乎也情有可原

游戏性(9/10)

游戏性方面基本没有太多令人不舒服的地方，无论是技能加点还是四个技能 + 两个饰品的效果，也没有太多值得特别称赞的，所以还是可以给一个中规中矩的 9 分

最终评价

个人而言，我会给黑神话打 9.0/10 的分数，整体上也是一块非常出色的 3A 游戏，但是作为一个只需要 48 个小时就能在无跳剧情的情况下通关一周目全部支线任务和主线剧情，整体内容还是欠了一些，似乎地图和画风有了 268 的价位，但是内容却稍有不值这个价位。但是整体上还是属于值得购买的水平

☑️ ☆

Golang 踩坑 —— interface 为参数的时候传 nil 指针

✇Shiroha白羽的博客
Shiroha

问题

这两天踩了一个奇怪的坑，抽出核心逻辑可以得到这样一段代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
type V interface {
}

type T struct {
V
next V
}

func NewT(t V) *T {
return &T{next: t}
}

func TestName(t *testing.T) {
var tmp *T = nil
newT := NewT(tmp)
if newT.next == nil {
t.Log("newT.next is nil as expected.")
} else {
t.Errorf("newT.next should be nil, but got %v", newT.next)
}
}

此时，输出的内容是：newT.next should be nil, but got <nil>

是不是挺疑惑的，稍做修改，将 var tmp *T = nil 改成 var tmp V = nil

此时，运行得到的结果是：newT.next is nil as expected.

原因

最终在 Google Groups 上找到了相关说明：

I’m trying to understand why a nil pointer when converted to an interface produces a non-nil value.

Because different nil pointers can have different types, and the
interface remembers the type of the (nil) pointer (that it is converted from):
that remembering means that the interface value isn’t nil.

Is this a bug?

No.

(It’s a mild confusion based on the overloading of nil to mean the
zero value for pointers of any type and for interfaces — it’s not obvious
from the text of a program that the nils are of different types.)

Chris

简单来说就是为了满足类似 C++ 的 RTTI 的特性，因为转为 interface 必然会丢失掉原来的类型信息，需要保存下原来的类型

这就导致了一个具体的变量传递给一个 interface 参数的函数的时候，因为会丢失掉原始的类型，所以将其包装成一个特殊的 struct。我们可以用 unsafe 的方式来获取到相关的信息

因为样例的 interface 在 golang 中使用类似如下的结构进行存储

1
2
3
4
type eface struct {
_type *_type
data  unsafe.Pointer
}

所以我们可以使用如下方案提取具体的变量值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
type InterfaceStruct struct {
pt uintptr
pv uintptr
}

type V interface {
}

type T struct {
V
next V
}

func NewT(t V) *T {
return &T{next: t}
}

func TestName(t *testing.T) {
var tmp *T = nil
newT := NewT(tmp)
pointer := *(*InterfaceStruct)(unsafe.Pointer(&newT.next))
fmt.Println(pointer)
}

就可以得到执行结果为 {4309258112 0}

也就是实际上 data 字段确实是 0，也就是 nil，但是其类型则存在一个 _type 的指针用来描述，所以在程序层面又不能说是 nil

☑️ ☆

Codeforces Round 940 (Div. 2) and CodeCraft-23

✇Shiroha白羽的博客
Shiroha

A. Stickogon

大致题意

有 $n$ 根木棍，问最多可以构成多少个等边的多边形，要求每一条边只能用一根木棍

思路

构建成三角形就行，统计一下，每种边的数量整除 $3$ 即可

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        map<int, int> mp;
        for (int i = 0; i < n; ++i) {
            int tmp;
            cin >> tmp;
            ++mp[tmp];
        }

        int ans = 0;
        for (auto &[a, b]: mp) ans += b / 3;
        cout << ans << endl;
    }
}

B. A BIT of a Construction

大致题意

给出一个整数 $k$，要求构造一个数组，其长度为给出的 $n$，每一项都不是负数，且满足 $\sum^n_{i=1} a_i = k$

问如何使得整个数组的 $a_1 | a_2 | \dots | a_n$ 的数中，比特位为 $1$ 数量最多

思路

由于求和为 $k$，且每一项都不是负数，那么必然可以得到所有值都比 $k$ 小，最大起码也是等于

而题目要求比特位为 $1$ 尽可能多，而尽可能多的值必然是 $2^x - 1$，所以找最大的 $x$ 使得 $2^x \leq k$，然后剩下的数值不重要了，补充满 $k$ 即可

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n, k;
        cin >> n >> k;
        if (n == 1) {
            cout << k << endl;
            continue;
        }
        int a = 0;
        for (int i = 31; i >= 0; --i) {
            if (k >= (1 << i) - 1) {
                a = (1 << i) - 1;
                break;
            }
        }
        cout << a << ' ' << k - a;
        for (int i = 2; i < n; ++i) cout << ' ' << 0;
        cout << endl;
    }
}

C. How Does the Rook Move?

大致题意

有一个棋盘，现在黑白两方轮着下，其中玩家使用白棋，电脑使用黑棋

电脑下棋的位置固定是根据用户下的位置的相反位置，例如玩家这一步下了 $(i, j)$，那么电脑则会下 $(j, i)$。
如果 $i = j$，那么就跳过电脑的回合

现在下的每一个棋都是城堡（类似中国象棋中的车），需要保证任何一步下的位置都必定不会被出现相互吃的情况，且目前已经有几个位置已经下好了，问剩下的还有几种可能下法

思路

容易猜出这是一个递推的题，类似斐波那契数列。当然可以仔细来看

首先，已经下了几步这件事是无意义的，因为去掉已经下的那些行/列，就会回到一个普通的没有下的棋盘，
说白了就是个干扰项，只需要把给出的棋盘大小减去已经下过的位置的行数，就可以得到新的棋盘行数

同样的，不仅是已经下的位置，你现在下的位置也是如此，一旦下好了+电脑下好，再把下好的那几行/列删掉，就是一个新的空棋盘，所以这是一个递推

接下来是如何得到递推公式了，因为下哪一行都一样，删掉之后就是空白的，且根据要求，每一行必定有一个城堡，且求算的总数并不关系下的顺序，只看最后的样子，
那么我们可以只考虑第一行（因为第一行必定有一个城堡，可能是白的也可能是黑的）

如果第一行，我下了最左上角的位置，那么就会得到一个 $n - 1$ 的棋盘（$i = j$，机器人没有地方下）

如果第一行，我下了不是第一个位置，那么机器人必定会下对角线位置，即得到一个 $n - 2$ 的棋盘。因为这样的位置有 $n - 1$ 个，
且第一行可能是黑的也可能是白的，所以递推公式就是

$a_n = a_{n-1} + 2 \times (n - 1) \times a_{n - 2}$

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#define int long long

void solve() {
    vector<int> ans(3e5 + 10);
    ans[0] = 1;
    ans[1] = 1;
    constexpr int mod = 1e9 + 7;
    for (int i = 2; i < ans.size(); ++i) {
        ans[i] = (ans[i - 1] + (ans[i - 2] * (i - 1) * 2) % mod) % mod;
    }

    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n, k;
        cin >> n >> k;
        set<int> st;
        for (int i = 0; i < k; ++i) {
            int u, v;
            cin >> u >> v;
            st.insert(u);
            st.insert(v);
        }
        cout << ans[n - st.size()] << endl;
    }
}

D. A BIT of an Inequality

大致题意

给出一个数组，要求找到一个元祖 $(x, y, z)$，满足 $0 \leq x \leq y \leq z \leq n, f(x, y) \oplus f(y, z) > f(x, z)$

其中 $f(l, r) = a_l \oplus a_{l+1} \oplus a_{l+2} \oplus \dots \oplus a_{r}$

问有多少个不同的元组

思路

很容易得到，$f(x, z) \oplus a_y = f(x, y) \oplus f(y, z)$，就是再异或上一边 $a_y$ 能让值变大

那么必然，原来 $a_y$ 中，最大的为 $1$ 那个比特位，$f(x, z)$ 为 $0$，毕竟如果是 $1$ 的话，肯定就变小了

接下来从这个角度分析，由于 $x \leq y \leq z$，所以 $f(x, z)$ 中一定已经异或过一次 $a_y$ 了，
而已知一个比特位 $a_y$ 是 $1$ 但是 $f(x, z)$ 是 $0$，那么必然在 $[x, z]$ 中，这个比特位为 $1$ 的，出现了偶数次，且至少 $2$ 次

所以只需要对于每一个可能的 $y$，找这个 $y$ 最大的为 $1$ 的那个比特位，为 $1$ 的次数恰好为偶数，且包含 $y$ 的区间数量即可。我采用了双向的奇偶标记

例如第三个例子，可以得到如下的表格

indexorigin2^2forwardback2^1forwardback2^0forwardback
071oddeven1oddeven1oddeven
130oddodd1evenodd1evenodd
271evenodd1oddeven1oddeven
320eveneven1evenodd0oddodd
410eveneven0eveneven1evenodd

这个表格的制作方式：

  • 先计算出每个值的每个比特位，放在 $2^x$ 列上
  • 单独计算每一列 forward，从上往下走，初始值为 even，如果当前的 $2^x$ 是 $1$，则将前一个 forward 翻转后填入，反之则超过来
  • 然后单独计算每一列 back，从下往上走，初始值为 forward 最后的值，填入逻辑同上

然后统计某个位置，左边的 back 下不同类型的数量和右边的 forward 不同的类型数量，再做乘法即可

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#define int long long

void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        vector<int> data(n);
        for (auto &i: data) cin >> i;
        vector<bool> flag[32][2];
        int cntR[32][2] = {}, cntL[32][2] = {}, ans = 0;
        bool cf[43] = {};
        for (auto &i: flag) i[0].resize(n);
        for (auto &i: flag) i[1].resize(n);
        for (int v = 0; v < n; ++v) {
            for (int i = 0; i < 32; ++i) {
                if (data[v] & (1ll << i)) cf[i] = !cf[i];
                flag[i][0][v] = cf[i];
                ++cntR[i][cf[i]];
            }
        }
        for (int v = n - 1; v >= 0; --v) {
            for (int i = 0; i < 32; ++i) {
                if (data[v] & (1ll << i)) cf[i] = !cf[i];
                flag[i][1][v] = cf[i];
            }
        }
        for (int v = 0; v < n; ++v) {
            for (int i = 0; i < 32; ++i) ++cntL[i][flag[i][1][v]];
            for (int i = 31; i >= 0; --i) if (data[v] & (1ll << i)) {
                ans += cntL[i][0] * cntR[i][0] + cntL[i][1] * cntR[i][1];
                break;
            }
            for (int i = 0; i < 32; ++i) --cntR[i][flag[i][0][v]];
        }
        cout << ans << endl;
    }
}
☑️ ☆

Codeforces Round 939 (Div. 2)

✇Shiroha白羽的博客
Shiroha

A. Nene’s Game

大致题意

有一排士兵，按照 $1,2,3,4 \dots n$ 的顺序喊，每次喊道 $a_i$ 的位置就踢出队伍，问最后剩下几个人

思路

只需要关注第一个被踢出去的人就行了

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int k, q, s;
        cin >> k >> q;
        cin >> s;
        for (int i = 1; i < k; ++i) {
            int tmp;
            cin >> tmp;
        }
        for (int i = 0; i < q; ++i) {
            int n;
            cin >> n;
            cout << min(n, s - 1) << " \n"[i == q - 1];
        }
    }
}

B. Nene and the Card Game

大致题意

有一组牌，每种数字只出现在两张牌上

现在将这组牌打散后分给两个人，并进行游戏。游戏的每一轮，当前的出牌手需要出一张牌，如果这张牌上的数值的另外一张已经在场上了，那么就会获得 1 份

现在给你其中一个人的手牌，问最多可以得到多少分

思路

两边的牌是映射的，所以先手出一张，后手跟一张，这样是刚刚好的，所以先手只能赚到那些两张牌都在自己手里的分数

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        set<int> st;
        for (int i = 0; i < n; ++i) {
            int tmp;
            cin >> tmp;
            st.insert(tmp);
        }
        cout << n - st.size() << endl;
    }
}

C. Nene’s Magical Matrix

大致题意

有一个矩阵，现在允许每次往一行或者一列上覆盖写 $1, 2, 3 \dots n$ 的某一个排列，问最终的整个矩阵的求和是多少

思路

每个位置都能变成它的横坐标和纵坐标里的较大者，简单模拟即可

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        int ans = 0;
        for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) ans += max(i, j) + 1;
        cout << ans << ' ' << 2 * n << endl;
        for (int i = n - 1; i >= 0; --i) {
            cout << 1 << ' ' << i + 1;
            for (int j = 0; j < n; ++j) cout << ' ' << j + 1;
            cout << endl;
            cout << 2 << ' ' << i + 1;
            for (int j = 0; j < n; ++j) cout << ' ' << j + 1;
            cout << endl;
        }
    }
}

D. Nene and the Mex Operator

大致题意

有一个初始数组，允许你每次选择一个子串，将其的每一个值变成这个子串的 $MEX$，问可以让整个数组的所有位置之和最大是多少

思路

注意这个数组最大只能是 18 个数值，所以可以随意暴力

容易得到，最终一定可以把选择的区间都变成和当前区间长度相同的那个值，比如区间长度为 $3$，那么最终这个区间可以变成三个 $3$

首先通过 dp 计算出哪些区间要进行上面的操作，然后再递归构建即可

比如我通过一定手段能够构建 $0, 1, 2, 3, 4, x$，就能通过一次 $MEX$ 得到 $5, 5, 5, 5, 5, 5$，
这个时候如果我再去尝试构建 $0, 1, 2, 3, 4$ 就可以重复之前的构建过程了，重复构建前五个值，相当于递归两次即可

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
void solve() {
    int n;
    cin >> n;
    vector<int> data(n), dp(n), dr(n);
    for (auto &i: data) cin >> i;
    dp[0] = data[0] >= 1 ? data[0] : 1;
    dr[0] = data[0] >= 1 ? -1 : 0;
    for (int i = 1; i < n; ++i) {
        dp[i] = dp[i - 1] + data[i];
        dr[i] = -1;
        for (int j = i; j >= 1; --j)
            if (dp[j - 1] + (i - j + 1) * (i - j + 1) > dp[i]) {
                dp[i] = dp[j - 1] + (i - j + 1) * (i - j + 1);
                dr[i] = j;
            }
        if ((i + 1) * (i + 1) > dp[i]) {
            dr[i] = 0;
            dp[i] = (i + 1) * (i + 1);
        }
    }
    vector<pair<int, int>> ans;
    ans.reserve(2e5);

    auto zero = [&](int l, int r) {
        bool flag = true;
        for (int i = l; i <= r; ++i) if (data[i] == 0) flag = false;
        if (flag) ans.emplace_back(l, r);
        else {
            ans.emplace_back(l, r);
            ans.emplace_back(l, r);
        }
        for (int i = l; i <= r; ++i) data[i] = 0;
    };
    function<void(int, int)> dfs = [&](int l, int r) {
        if (l == r) {
            if (data[l] == 0) return;
            ans.emplace_back(l, l);
            return;
        }
        dfs(l, r - 1);
        ans.emplace_back(l, r);
        ans.emplace_back(l, r - 1);
        data[r] = r - l;
        dfs(l, r - 1);
    };

    auto f = [&](int l, int r) {
        zero(l, r);
        dfs(l, r);
        ans.emplace_back(l, r);
    };
    vector<pair<int, int>> lr;
    for (int i = n - 1; i >= 0; --i) {
        if (dr[i] == -1) continue;
        f(dr[i], i);
        i = dr[i];
    }

    cout << dp[n - 1] << ' ' << ans.size() << endl;
    for (auto &[a, b]: ans) cout << a + 1 << ' ' << b + 1 << endl;
}
☑️ ☆

Codeforces Round 924 (Div. 2)

✇Shiroha白羽的博客
Shiroha

A. Rectangle Cutting

大致题意

有一个矩型，将其切割成两半，然后再拼接起来，问是否可能得到另外一个矩型

思路

简单题，直接尝试一下就行了

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int a, b;
        cin >> a >> b;
        bool flag = false;
        if (a % 2 == 0) {
            int ra = a / 2, rb = b * 2;
            if (ra != b || rb != a) flag = true;
        }
        if (b % 2 == 0) {
            int ra = a * 2, rb = b / 2;
            if (ra != b || rb != a) flag = true;
        }
        cout << (flag ? "YES" : "No") << endl;
    }
}

B. Equalize

大致题意

已知一个数组，现在将一个等长的排列加到这个数组上，问最多出现多少个相同的值

思路

等价于在长度为 $n$ 的值范围内，原始数组有多少个不同的值

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        vector<int> data(n);
        for (auto& i: data) cin >> i;
        sort(data.begin(), data.end());
        int end = (int)(unique(data.begin(), data.end()) - data.begin());
        int l = 0, ans = 0;
        for (int r = 0; r < end; ++r) {
            while (data[r] - data[l] >= n) ++l;
            ans = max(ans, r - l + 1);
        }
        cout << ans << endl;
    }
}

C. Physical Education Lesson

大致题意

有一个数组，其值类似一个波长为 $x$ 的波，从 $1 \rightarrow k \rightarrow 1$，现在只知道第 $n$ 的位置是 $x$，问有多种不同的波的可能

思路

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int x, n, v[2];
        cin >> x >> n;
        // upside
        v[0] = x - n;
        // downside
        v[1] = x + n - 2;
        set<int> st;

        auto add = [&](int x) {
            if (x % 2 || x < n * 2 - 2) return;
            st.insert(x);
        };
        auto cal = [&](int x) {
            int r = min((int)sqrt(x) + 10, x);
            for (int i = 1; i < r; ++i) if (x % i == 0) {
                add(i);
                add(x / i);
            }
        };

        cal(v[0]);
        cal(v[1]);

        cout << st.size() << endl;
    }
}

D. Lonely Mountain Dungeons

大致题意

有 $n$ 个不同的种族，每个种族有不同数量的士兵，现在需要将它们组成 $k$ 只军队，每个士兵必定属于某一个军队

每多创建一个军队，其就要减少 $x$ 的战斗力，而当同一个种族的两个士兵被分配到不同的队伍的情况下，则会增加 $b$ 单位的战斗力

问最大的战斗力可能是多少

思路

三分一下队伍数量即可

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#define int long long

void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n, b, x;
        cin >> n >> b >> x;
        vector<int> c(n);
        for (auto &i: c) cin >> i;
        int l = 1, r = 2e5 + 10;

        auto check = [&](int mid) {
            int res = -x * (mid - 1);
            for (const auto &i: c) {
                int v = i / mid, c1 = i % mid, c2 = mid - c1;
                res += b * c1 * (v + 1) * (i - v - 1) / 2;
                res += b * c2 * v * (i - v) / 2;
            }
            return res;
        };

        while (l + 10 < r) {
            int ml = (2 * l + r) / 3, mr = (l + 2 * r) / 3;
            int rl = check(ml), rr = check(mr);
            if (rl < rr) l = ml;
            else r = mr;
        }

        int ans = 0;
        for (int i = l; i <= r; ++i)
            ans = max(ans, check(i));
        cout << ans << endl;
    }
}

E. Modular Sequence

大致题意

有一个数组，第一个值已经确定，其后的每一个值的，等于前一个值 $+ y$ 或者等于 $mod \space y$，且已知长度和总和，问是否存在这样的数组

思路

容易得到，最终因为变化都和 $y$ 有关，所以 $x \space y$ 这部分的值，必然会被每一个单位所保留，即每一个值必定等价于 $t \times y + x \space mod \space y$

所以可以先 $s \leftarrow $，那么所有值就等于 $t \times y$

再统一除以 $y$ 可以得到 $s \leftarrow \frac{s - n \times (x \space mod \space y)}{y}$ 而数组则是几个递增的阶梯（$0, 1, 2, \dots$）组成

所以只需要求解阶梯的数量和每个阶梯的长度即可

容易得到一个简单的结论：最长的阶梯不超过 $650$，因为 $(1 + 650) \times 650 / 2 = 211575$，所以可以通过暴力的手段解决

定义 dp[i] 表示当前 $s$ 还剩下 $i$ 个值需要处理的时候，已经消耗了多少个位置，对于每一个 $i$，暴力遍历 $650$ 种可能性即可

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n, x, y, s;
        cin >> n >> x >> y >> s;

        if ((s - n * (x % y)) % y || (x % y) * n > s || x > s) {
            cout << "NO" << endl;
            continue;
        }
        int rs = (s - n * (x % y)) / y;
        int st = x / y - 1;
        if (x / y > rs) {
            cout << "NO" << endl;
            continue;
        }

        vector<pair<int, int>> dp(rs + 1, {0x3fffffff, -1});
        dp[rs] = {0, -1};
        for (int i = st + 1, tmp = 0; i <= s; ++i) {
            tmp += i;
            if (tmp == 0) continue;
            if (rs - tmp < 0) break;
            dp[rs - tmp] = {i, rs};
        }
        for (int i = rs - 1; i >= 1; --i)
            for (int j = 1; j < 623; ++j) {
                if (i - (1 + j) * j / 2 < 0) break;
                if (dp[i - (1 + j) * j / 2].first <= dp[i].first + j + 1) continue;
                dp[i - (1 + j) * j / 2] = {dp[i].first + j + 1, i};
            }
        if (st + n < dp[0].first) {
            cout << "NO" << endl;
            continue;
        }
        cout << "YES" << endl;
        int cur = 0;
        vector<int> res;
        while (~cur) {
            if (dp[cur].second != -1) res.push_back(dp[cur].second - cur);
            cur = dp[cur].second;
            if (res.size() > 100) {
                cerr << 1;
            }
        }
        reverse(res.begin(), res.end());
        int index = 0;
        for (int i = 0; i < res.size(); ++i) {
            int cost = 0, j = i == 0 ? st + 1 : 0;
            while (cost <= res[i]) {
                cout << j * y + x % y << ' ';
                ++index;
                ++j;
                cost += j;
            }
        }
        while (index < n) {
            cout << x % y << ' ';
            ++index;
        }
        cout << endl;
    }
}
☑️ ☆

Codeforces Round 921 (Div. 2)

✇Shiroha白羽的博客
Shiroha

A. We Got Everything Covered!

大致题意

有一个字符串长度为 $n$，其最多包含 $k$ 种不同的字母，你需要给出一个序列，使得这个字符串一定是你给出的序列的子序列

思路

就是要满足 $k$ 种字母，长度为 $n$ 下的所有可能的组合，即每一个位置都可能是 $k$ 个值

所以最简单的方式就是把 $k$ 个字母依次输出，重复 $n$ 次即可

AC code

1
2
3
4
5
6
7
8
9
10
void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n, m;
        cin >> n >> m;
        for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) cout << static_cast<char>('a' + j);
        cout << endl;
    }
}

B. A Balanced Problemset?

大致题意

把一个数值 $x$，拆成 $n$ 份，问它们的 gcd 最大可以是多少

思路

因为 gcd 意味着所有值都有这个因子，那么它们加起来之后，也一定有这个因子。故这个值必定是最初的值的因子

所以找一个够分成 $n$ 份的即可，不需要均分

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n, m;
        cin >> n >> m;
        const int r = static_cast<int>(sqrt(n)) + 1;
        int ans = 1;
        for (int i = 1; i <= min(r, n); ++i) {
            if (n % i != 0) continue;
            if (i >= m) ans = max(ans, n / i);
            else if (n / i >= m) ans = max(ans, i);
        }
        cout << ans << endl;
    }
}

C. Did We Get Everything Covered?

大致题意

和 A 题刚好相反，找一个不满足的字符串，使得不是给出的字符串的子序列即可

思路

考虑最差的情况，即每次都取从左到右最后出现的那个字母的值，即可尽可能的往后选取

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n, k, m;
        cin >> n >> k >> m;
        string str;
        str.resize(m);
        cin >> str;
        set<char> st;
        int tot = 0;
        vector<char> ans;
        for (const auto& c: str) {
            if (c < 'a' || c >= 'a' + k) continue;
            st.insert(c);
            if (st.size() == k) {
                st.clear();
                ++tot;
                ans.push_back(c);
            }
        }
        if (tot >= n) cout << "YES" << endl;
        else {
            cout << "NO" << endl;
            char c = 'a';
            for (char i = 0; i < k; ++i) if (!st.count(i + 'a')) c = i + 'a';
            for (int i = 0; i < n; ++i) if (i < ans.size()) cout << ans[i]; else cout << c;
            cout << endl;
        }
    }
}

D. Good Trip

大致题意

有 $n$ 个人，其中有 $m$ 对朋友，每对朋友都有一个亲密度 $f_i$。

每次随机选择两个人，如果它们是朋友，则得到对应亲密度的积分，然后使得他们的亲密度 +1

选择 $k$ 次后，期望积分是多少

思路

容易得到任何一种组合的选取的概率是 $\frac{2}{n \times (n-1)}$，故单次提供的共享应该是 $f_i \times \frac{2}{n \times (n-1)}$

而每次结束之后，被选中的朋友的积分会加一，而对于期望而言，相当于每一对朋友的积分都增加 $\frac{2}{n \times (n-1)}$

依次可以得到，最终每一对的共享就是 $f_i \times \frac{2}{n \times (n-1)} + (f_i + \frac{2}{n \times (n-1)}) \times \frac{2}{n \times (n-1)} + \dots + (f_i + (k - 1) \times \frac{2}{n \times (n-1)}) \times \frac{2}{n \times (n-1)}$

再化简一下，取一下逆元即可

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#define int long long
 
void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        constexpr int mod = 1e9 + 7;
        auto qp = [&](int a, int p) {
            int ans = 1;
            while (p) {
                if (p & 1) ans = ans * a % mod;
                a = a * a % mod;
                p >>= 1;
            }
            return ans;
        };
        int n, m, k;
        cin >> n >> m >> k;
        const int i = qp(n * (n - 1) / 2 % mod, mod - 2);
        vector<tuple<int, int, int>> data(m);
        for (auto& [l, r, v]: data) cin >> l >> r >> v;
        int ans = 0;
        for (const auto [_l, _r, v]: data) {
            const int l = v * k % mod;
            const int r = i * ((k - 1) * k / 2 % mod) % mod;
            const int t = (l + r) * i % mod;
            ans = (ans + t) % mod;
        }
        cout << ans << endl;
    }
}
☑️ ☆

Educational Codeforces Round 161 (Rated for Div. 2)

✇Shiroha白羽的博客
Shiroha

A. Tricky Template

大致题意

设定一种模式串，对于模式串中的每一个字符，如果是小写，则表示必须匹配这个小写字母，如果是大写，则表示必定不匹配对应的那个小写字母

再给出三个字符串，问是否存在一个模式串，恰好匹配前面两个字符串，同时不匹配第三个字符串

思路

只要有一个位置的字母，前两个字符串和第三个字符串都不同即可，这样只要那个位置的模式串是大写的第三个字符串的字符即可

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        string a, b, c;
        a.resize(n);
        b.resize(n);
        c.resize(n);
        cin >> a >> b >> c;
        bool flag = false;
        for (int i = 0; i < n; ++i) if (a[i] != c[i] && b[i] != c[i]) flag = true;
        cout << (flag ? "YES" : "NO") << endl;
    }
}

B. Forming Triangles

大致题意

有 n 条边，每条边的长度都是 $2^x$，问可以组成多少个使用了不同边的三角形

思路

因为 $2^x$ 恰好满足一个特点：$2^{a} + 2^{b} < 2^c$，当 $a < b < c$ 时，也就是容易得到，至少有两条边相同才有可能

所以只需要讨论一下两条边相同和三条边相同的情况即可，当然也可以一起讨论了

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#define int long long

void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        map<int, int> cnt;
        for (int i = 0; i < n; ++i) {
            int tmp;
            cin >> tmp;
            ++cnt[tmp];
        }
        int tot = 0, ans = 0;
        for (const auto [fst, snd]: cnt) {
            if (snd == 2) ans += tot;
            else if (snd > 2) ans += tot * snd * (snd - 1) / 2 + snd * (snd - 1) * (snd - 2) / 6;
            tot += snd;
        }
        cout << ans << endl;
    }
}

C. Closest Cities

大致题意

有一排城市，每个城市都有一个坐标，每个城市都可以前往其他的城市。而一个城市距离较近的那个城市的花费成本为 1，而前往其他城市的成本就是距离

计算任意两个城市之间的距离

思路

因为移动移动是从左移动到右边，或者从右边移动到左边，路径只有一条，所以可以前后做两次前缀和解决

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        vector<int> data(n), cl(n), cr(n);
        for (auto& i: data) cin >> i;
        cl[0] = cr[n - 1] = 0;
        for (int i = 1; i < n; ++i) {
            if (i == 1 || data[i - 1] - data[i - 2] >= data[i] - data[i - 1]) cl[i] = cl[i - 1] + 1;
            else cl[i] = cl[i - 1] + data[i] - data[i - 1];
        }
        for (int i = n - 2; i >= 0; --i) {
            if (i == n - 2 || data[i + 2] - data[i + 1] >= data[i + 1] - data[i]) cr[i] = cr[i + 1] + 1;
            else cr[i] = cr[i + 1] + data[i + 1] - data[i];
        }
        int m;
        cin >> m;
        for (int i = 0; i < m; ++i) {
            int u, v;
            cin >> u >> v;
            if (u <= v) cout << cl[v - 1] - cl[u - 1] << endl;
            else cout << cr[v - 1] - cr[u - 1] << endl;
        }
    }
}

D. Berserk Monsters

大致题意

有一排怪物，每一个怪物都有一定攻击力和防御力，当一个怪物一次性受到的攻击大于其防御力的时候，将会死亡

现在每个怪物将会同时攻击它相邻的两个怪物，经过 $n$ 轮次后，问每一轮死了多少怪物

思路

首先是非常容易计算是否会死亡，即只要相邻两个怪物的攻击力高于其防御力即可，由于不是生命值，所以很容易统计

而每轮只有死亡怪物后，其相邻的怪物才会有可能死亡，所以只需要考虑每次发生变化的怪物附近即可，不需要考虑全部怪物

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        vector<int> a(n), d(n);
        for (auto& i: a) cin >> i;
        for (auto& i: d) cin >> i;
        map<int, pair<int, int>> mp;
        for (int i = 0; i < n; ++i) mp[i] = {a[i], d[i]};
        auto check = [&](map<int, pair<int, int>>::iterator& cur) {
            int cost = 0;
            if (cur != mp.begin()) {
                --cur;
                cost += cur->second.first;
                ++cur;
            }
            ++cur;
            if (cur != mp.end()) cost += cur->second.first;
            --cur;

            return cost > cur->second.second;
        };

        set<int> s[2];
        for (auto iter = mp.begin(); iter != mp.end(); ++iter) if (check(iter)) s[0].insert(iter->first);
        int cur = 0, nxt = 1, tot = 0;
        vector ans(n, 0);
        while (!s[cur].empty()) {
            for (const int& c: s[cur]) {
                ++ans[tot];
                mp.erase(c);
            }
            for (const int& c: s[cur]) {
                auto iter = mp.upper_bound(c);
                if (iter != mp.end()) if (check(iter)) s[nxt].insert(iter->first);
                if (iter != mp.begin()) {
                    --iter;
                    if (check(iter)) s[nxt].insert(iter->first);
                }
            }
            s[cur].clear();
            swap(cur, nxt);
            ++tot;
        }
        for (int i = 0; i < n; ++i) cout << ans[i] << " \n"[i == n - 1];
    }
}

E. Increasing Subsequences

大致题意

请构造一个字符串，使其内部的递增子序列的数量恰好是 $n$ 个

思路

容易得到，如果是简单的递增序列，其长度子序列数量的关系是

lencountaddition
01-
121
242
384
4168

很明显与 $2^x$ 有关，如果已经存在一个从 1 开始的递增序列，往其后面添加一个数值 $x$，则可以带来 $2^{x-1}$ 个数量的增加

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#define int long long

void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        --n;
        vector<int> ans;
        int cur = 62;
        while (n < (1LL << cur) - 1) --cur;
        for (int i = 1; i <= cur; ++i) ans.push_back(i);
        n -= (1LL << cur) - 1;
        while (n) {
            while (n >= 1LL << cur - 1) {
                n -= 1LL << cur - 1;
                ans.push_back(cur);
            }
            --cur;
        }
        cout << ans.size() << endl;
        for (int i = 0; i < ans.size(); ++i) cout << ans[i] << " \n"[i == ans.size() - 1];
    }
}
☑️ ☆

Hello 2024

✇Shiroha白羽的博客
Shiroha

A. Wallet Exchange

大致题意

Alice 和 Bob 博弈，有两个钱包，每次可以选择一个钱包取走一块钱，问谁会没有办法操作

思路

求和对 2 取模就行了

AC code

1
2
3
4
5
6
7
8
9
void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int a, b;
        cin >> a >> b;
        cout << ((a + b) % 2 ? "Alice" : "Bob") << endl;
    }
}

B. Plus-Minus Split

大致题意

有一个 -+ 组成的字符串，允许将其拆成任意数量段，将 - 视为 -1 然后将 + 视为 1，然后对每一段单独求和

再将每一段的和乘上其长度，得到段的成本，所有段的成本之和就是总成本，问让成本最低怎么办

思路

易得，除了之和等于 0 的情况，其他情况都不要合成一个段，所以最终就是求和成 0 的段以外部分成本

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        string str;
        str.resize(n);
        cin >> str;
        int cnt[2] = {};
        for (const auto& c: str) ++cnt[c == '+'];
        cout << abs(cnt[0] - cnt[1]) << endl;
    }
}

C. Grouping Increases

大致题意

将一个字符串拆成两个子序列，每个子序列内，每有一对相邻的正序对就算一个成本，问如何拆让拆成本最小

思路

贪心模拟即可

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        int data[2] = {0, 0};
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int tmp;
            cin >> tmp;
            if (tmp > data[0] && tmp > data[1]) {
                data[data[0] > data[1] ? 1 : 0] = tmp;
                ++ans;
            } else if (tmp <= data[0] && tmp <= data[1])
                data[data[0] > data[1] ? 1 : 0] = tmp;
            else data[data[0] > data[1] ? 0 : 1] = tmp;
        }
        cout << max(ans - 2, 0) << endl;
    }
}

D. 01 Tree

大致题意

有一个 01 字典树，已知每个叶子节点的值中 1 的数量，以及所有叶子节点的顺序

问是否存在这样的字典树

思路

因为每个值必然有一个相邻的节点和它差 1（那个节点不一定是叶子节点）

所以可以从最大值开始，每次找它相邻的值上是否有一个恰好比它小 1 的值，那么可以删除这两个值，把他们的父节点的值加进去（恰好就是它们两个中的较小者）

注意相邻的两个相同相邻的值的时候，它们可以合并

整个过程有点类似哈夫曼编码的过程

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        map<int, int> mp;
        vector<vector<int>> index(n);
        for (int i = 0; i < n; ++i) {
            int tmp;
            cin >> tmp;
            mp.emplace(i, tmp);
            index[tmp].push_back(i);
        }
        for (int t = n - 1; t > 0; --t) {
            auto& v = index[t];
            if (v.empty()) continue;
            for (int i: v) {
                const auto iter = mp.find(i);
                // check near same
                auto riter = iter;
                ++riter;
                if (riter != mp.end() && riter->second == t) {
                    mp.erase(iter);
                    continue;
                }
                // check near - 1
                if (riter->second == t - 1) {
                    mp.erase(iter);
                    continue;
                }
                if (auto liter = iter; liter != mp.begin()) {
                    --liter;
                    if (liter->second == t - 1) {
                        mp.erase(iter);
                        continue;
                    }
                }
            }
        }
        cout << (mp.size() == 1 && mp.begin()->second == 0 ? "YES" : "NO") << endl;
    }
}
☑️ ☆

CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)

✇Shiroha白羽的博客
Shiroha

A. Jagged Swaps

大致题意

有一个数组，允许选择一个值，其左右两边都是大于当前值的情况下，将当前值和后面的那个值交换一下位置。问是否可能把整个数组排序好

思路

可以从插入排序的方式去考虑，只需要第一个值是对的就行了

AC code

1
2
3
4
5
6
7
8
9
10
11
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<int> data(n);
        for (auto& i: data) cin >> i;
        cout << (data.front() == 1 ? "YES" : "NO") << endl;
    }
}

B. AB Flipping

大致题意

有一个 AB 组成的数组，若存在 AB 这样的子字符串，则翻转 AB，且每个下标只能被翻转一次，问最多可以翻转多少次

思路

若存在一堆连续的 AAAABBB 这样的字符串，那么仅最后一个不能进行翻转，其他所有位置都能发生翻转，所以只需要找出这样的连续对数量即可

需要注意的是，如果是 AABBAABB 这种两组的，虽然对于每一个单独的组而言，最后一个不能翻转，但是整体上，除了最后的最后那个，其他也都可以翻转

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        string str;
        str.reserve(n);
        cin >> str;
        int ans = 0, cntB = 0, flag = 0;
        for (auto iter = str.rbegin(); iter != str.rend(); ++iter) {
            if (*iter == 'B') {
                flag = 1;
                cntB++;
            } else {
                ans += flag + cntB;
                cntB = 0;
            }
        }
        cout << max(ans - 1, 0) << endl;
    }
}

C. Matching Arrays

大致题意

有 AB 两个数组，每次任意排序 B 数组，问是否存在一个排列，使得 $a_i > b_i$ 的 $i$ 的数量恰好是 $x$

思路

很简单的一个想法：两个数组排序后，然后将 B 数组的前 $x$ 个值放到后面去即可。然后再判断是否符合预期

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, x;
        cin >> n >> x;
        vector<pair<int, int>> a(n);
        vector<int> b(n);
        for (auto& [fst, snd]: a) cin >> fst;
        for (int i = 0; i < n; ++i) a[i].second = i;
        for (auto& i: b) cin >> i;
        sort(b.begin(), b.end());
        sort(a.begin(), a.end());
        int res = 0;
        for (int i = 0; i < n; ++i) {
            res += a[i].first > b[(i + x) % n];
        }
        if (res == x) {
            cout << "YES" << endl;
            for (int i = 0; i < n; ++i) a[a[i].second].first = b[(i + x) % n];
            for (int i = 0; i < n; ++i) cout << a[i].first << " \n"[i == n - 1];
        } else cout << "NO" << endl;
    }
}

D. Ones and Twos

大致题意

有一个仅有 $1, 2$ 组成数组，每次有两种操作：将其中一个值改成 $1, 2$，问是否存在一个子串，满足求和等于 $x$（x 是每次询问给出的值）

思路

因为数组仅有 $1, 2$ 组成，那么必然，如果总值是 $s$，那么必然可以得到 $s - 2$ 的字串（删掉一侧的值或者删掉两侧的值），
同理也可以得到 $s-4, s-6, \dots$ 直到等于 $0 or 1$

所以只需要维护总和就能解决一般的值了。

而如果需要奇偶性和之和不同，那么必然需要减去一个 $1$，那么只需要找到左右两边最近的 $1$，
然后减去那一侧的 $2$ 和第一个 $1$，就可以得到最大可以满足的和全部之和奇偶性不同的值了，然后可以继续按照上面的推论

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, q;
        cin >> n >> q;
        vector<int> data(n);
        for (auto& i: data) cin >> i;
        int sum = 0;
        set<int> s;
        for (const auto& i: data) sum += i;
        for (int i = 0; i < n; ++i) if (data[i] == 1) s.insert(i);
        for (int qs = 0; qs < q; ++qs) {
            int op;
            cin >> op;
            if (op == 1) {
                int x;
                cin >> x;
                if (x > sum) cout << "NO" << endl;
                else if ((x & 1) == (sum & 1)) cout << "YES" << endl;
                else {
                    if (s.empty()) {
                        cout << "NO" << endl;
                        continue;
                    }
                    const int m = min(*s.begin(), n - *s.rbegin() - 1);
                    const int tmp = sum - m * 2 - 1;
                    cout << (x <= tmp ? "YES" : "NO") << endl;
                }
            } else {
                int a, b;
                cin >> a >> b;
                if (data[a - 1] == 1) s.erase(a - 1);
                if (b == 1) s.insert(a - 1);
                sum -= data[a - 1] - b;
                data[a - 1] = b;
            }
        }
    }
}

E. Permutation Sorting

大致题意

有一个 $n$ 的排列的数组，每次按照如下操作进行

  • 选出其中 $a_i \neq i$ 的 $i$，得到一个由 $i$ 组成的数组 $s$
  • $a_{s_{i \space mod \space k+1}} \leftarrow a_{s_i}$

重复进行后，直到整个数组排序完成，问每一个下标完成排序需要操作几次

思路

从题意来看，其实就是每次将没有满足条件的值，右移一格，直到大家都满足了

由于在正常情况下，每次只移动一格，所以需要的成本就等于位置差值

但是因为有别的值会因为满足位置了，就不需要再路过这个节点了，也就可以省去一次移动成本，例如

index12345
start35412
turn 1235(4)1
turn 2(1)(2)(3)(4)(5)

注意到，本来初始为 $5$ 的值，本应该走 $3$ 次才能到目标地点的，但是因为 $4$ 提前到达目标地点，
所以 $5$ 只需要走两次即可，为了方便表示，我们把 $4$ 的移动描述成 $[3,4]$，同理，那么 $5$ 就是 $[2,5]$

故我们需要找到的是，每个值要进行横跨的时候，会同时跨越的其他区间数量，即有哪些节点，他们开始的位置比当前值晚的同时，结束位置还比当前值早

我们可以用线段树来维护这样的值，如果存在一个 $[l,r]$，那么必然可以对所有 $[r]$ 的区间产生减少一次移动成本的效果
那么我们可以将 $[r+1,n]$ 的区间都 $+1$，而如何表示 $<l$，则可以通过访问顺序来控制，我们保证从左往右访问即可，
每次访问后，将当前节点带来的区间进行删除

需要注意的是，因为移动是环形的，所以需要维护两倍区间长度，不然可能会出错

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
struct SegTree {
    vector<int> s, laz;

    explicit SegTree(int n): s((n << 1) + 10), laz((n << 1) + 10) {}

    int static get(const int l, const int r) {
        return (l + r) | (l != r);
    }

    void up(const int l, const int r) {
        const int mid = (l + r) >> 1;
        s[get(l, r)] = s[get(l, mid)] + s[get(mid + 1, r)];
    }

    void build(const int l, const int r) {
        laz[get(l, r)] = 0;
        if (l == r) {
            s[get(l, r)] = 0;
            return;
        }
        const int mid = (l + r) >> 1;
        build(l, mid);
        build(mid + 1, r);
        up(l, r);
    }

    void push(const int l, const int r) {
        const int k = get(l, r);
        if (laz[k]) {
            const int mid = (l + r) >> 1;
            s[get(l, mid)] += laz[k] * (mid - l + 1);
            s[get(mid + 1, r)] += laz[k] * (r - mid);
            laz[get(l, mid)] += laz[k];
            laz[get(mid + 1, r)] += laz[k];
            laz[k] = 0;
        }
    }

    void update(const int l, const int r, const int x, const int y, const int w) {
        if (l == x && y == r) {
            s[get(l, r)] += w * (r - l + 1);
            laz[get(l, r)] += w;
            return;
        }
        push(l, r);
        if (const int mid = (l + r) >> 1; y <= mid) {
            update(l, mid, x, y, w);
        } else if (x > mid) {
            update(mid + 1, r, x, y, w);
        } else {
            update(l, mid, x, mid, w);
            update(mid + 1, r, mid + 1, y, w);
        }
        up(l, r);
    }

    int query(const int l, const int r, const int x) {
        if (l == r) {
            return s[get(l, r)];
        }
        push(l, r);
        const int mid = (l + r) >> 1;
        if (x <= mid) {
            return query(l, mid, x);
        }

        return query(mid + 1, r, x);
    }
};

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<int> data(n), ans(n);
        SegTree tree(2 * n);
        for (auto& i: data) cin >> i;
        for (int i = 0; i < n; ++i) {
            const int target = data[i] > i ? data[i] : data[i] + n;
            tree.update(1, 2 * n, target, 2 * n, 1);
            if (target < n) tree.update(1, 2 * n, target + n, 2 * n, 1);
        }
        for (int i = 0; i < n; ++i) {
            const int target = data[i] > i ? data[i] : data[i] + n;
            tree.update(1, 2 * n, target, 2 * n, -1);
            ans[data[i] - 1] = target - (i + 1) - tree.query(1, 2 * n, target);
        }
        for (int i = 0; i < n; ++i) cout << ans[i] << " \n"[i == n - 1];
    }
}
☑️ ☆

Educational Codeforces Round 158 (Rated for Div. 2)

✇Shiroha白羽的博客
Shiroha

A. Line Trip

大致题意

有一辆车，需要开到某个目的地，然后再回来，路上有几个加油站，初始的时候或者经过加油站的时候，油可以加满，问油箱的容量最小为多少

思路

注意一下最后回来那段是两段折返的路就行了

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, x;
        cin >> n >> x;
        vector<int> data(n);
        for (auto& i: data) cin >> i;
        int ans = max(data.front(), 2 * (x - data.back()));
        for (int i= 1; i < n; ++i) ans = max(ans, data[i] - data[i - 1]);
        cout << ans << endl;
    }
}

B. Chip and Ribbon

大致题意

有一个数组，开始的每一个值都是 0，除了第一个值是 1，有一个指针指向其中一个数值

每次允许将当前指针指到下一个值，或者直接传送到另外一个任意位置，必须要进行一次移动，然后将移动后的值 $+1$

问最小的传送次数

思路

注意每次移动只能移动到下一个值，也就是要回来删必须传送

所以对于每一个递减的子串，只取决于第一个值的代价，而第一个值的代价又和它前一个值相关，因为只要减少到和前一个值一样就行了

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define int long long

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<int> data(n);
        for (auto& i: data) cin >> i;
        int begin = data[0], ans = data[0] - 1;
        for (int i = 1; i < n; ++i)
            if (data[i] > data[i - 1])
                ans += data[i] - data[i - 1];
        cout << ans << endl;
    }
}

C. Add, Divide and Floor

大致题意

有一个数组，每次允许将每一个值都加上任选的一个 $x$，然后再向下取整的方式除以 $2$。问最少需要操作多少次才能让所有值一样

思路

其实只需要考虑最大和最小的那两个值即可

考虑公式$\left \lfloor \frac{a+x}{2} \right \rfloor = \left \lfloor \frac{a}{2} + \frac{x}{2} \right \rfloor$ 可以得到
实际上 $x$ 应该尽可能小才是，否则差值并不能很快缩小

因为是向下取整，所以当最小的值是奇数的时候，且最大值是偶数的时候，这个时候全部的值加上 $1$ 就可以非常有效的降低差值，
而在其他的时候 $x$ 取 $0$ 即可

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        int mi = INT_MAX, ma = 0;
        for (int i = 0; i < n; ++i) {
            int tmp;
            cin >> tmp;
            mi = min(mi, tmp);
            ma = max(ma, tmp);
        }
        vector<int> ans;
        while (mi != ma) {
            if (mi % 2 && !(ma % 2)) {
                mi = (mi + 1) / 2;
                ma = (ma + 1) / 2;
                ans.push_back(1);
            } else {
                mi /= 2;
                ma /= 2;
                ans.push_back(0);
            }
        }
        cout << ans.size() << endl;
        if (ans.size() <= n) {
            for (const auto& i: ans) cout << i << ' ';
        }
        cout << endl;
    }
}

D. Yet Another Monster Fight

大致题意

有一组怪物，允许选择一个初始的怪物进行攻击，

攻击后，伤害会连锁伤害到其他的怪物上，连锁的顺序是随机选择一个被攻击过的怪物附近的一个没有被攻击的怪物，最终所有怪物都会被连锁到。
而连锁的伤害则是逐步递减

问在可以指定直接攻击的怪物的情况下，最小的初始攻击应该是多少，才能将所有怪都干掉

思路

由于连锁的顺序是随机的，所以对于每一个怪物而言，它的最晚承受伤害的时间就是它左边的所有怪都受到过伤害了，或者是它右边所有的怪都受到过伤害了，
至于应该是左边还是右边，那就取决于第一个怪是在它左边还是右边。
那么对于它而言，无论选择哪一个初始的怪，其需要的初始伤害是确定的，即它自身的生命值 + 它左边/右边的怪的数量

那么就可以枚举所有的初始的怪，然后找出左边所有怪里面，最大的需要是多少，和其右边里面，最大的需要是多少，然后在和当前怪的生命值取较大值即可

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve() {
    int n;
    cin >> n;
    vector<int> data(n);
    for (auto& i: data) cin >> i;
    map<int, int> l, r;
    int ans = INT_MAX;
    for (int i = 0; i < n; ++i) ++r[data[i] + i];
    for (int i = 0; i < n; ++i) {
        if (const auto iter = r.find(data[i] + i); iter->second == 1) r.erase(iter);
        else --iter->second;
        if (i != 0) ++l[data[i - 1] + n - i];
        const int ls = l.empty() ? 0 : l.rbegin()->first, rs = r.empty() ? 0 : r.rbegin()->first;
        ans = min(ans, max(data[i], max(ls, rs)));
    }
    cout << ans << endl;
}
☑️ ☆

Codeforces Round 910 (Div. 2)

✇Shiroha白羽的博客
Shiroha

A. Milica and String

大致题意

有一个 A/B 组成的字符串，每次允许选择前 $n$ 个字母，将他们都变成 A/B，问最少的操作次数

思路

简单题，最简单的方式就是枚举每一种可能，计算结果是否符合预期就行

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, k;
        cin >> n >> k;
        string str;
        str.reserve(n);
        cin >> str;
        int cntB = 0;
        for (int i = 0; i < n; ++i) cntB += str[i] == 'B';
        if (cntB == k) {
            cout << 0 << endl;
            continue;
        }

        const bool useA = cntB > k;
        for (int i = 0; i < n; ++i) {
            if (cntB > k) {
                cntB -= str[i] == 'B';
            } else {
                cntB += str[i] != 'B';
            }

            if (cntB == k) {
                cout << 1 << endl;
                cout << i + 1 << ' ' << (useA ? 'A' : 'B') << endl;
                break;
            }
        }
    }
}

B. Milena and Admirer

大致题意

允许不断的差分一个数组中的值，问至少需要拆多少次，才能让数组非递减

思路

也比较简单，从后往前遍历，如果当前值比后面的值大，则均匀的拆成 $x$ 份，使得恰好比后面的值小或者相同即可

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define int long long

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<int> data(n);
        for (auto& i: data) cin >> i;
        int ans = 0;
        for (int i = n - 2; i >= 0; --i) {
            if (data[i] > data[i + 1]) {
                const int cut = data[i] / data[i + 1] + (data[i] % data[i + 1] == 0 ? 0 : 1);
                data[i] /= cut;
                ans += cut - 1;
            }
        }
        cout << ans << endl;
    }
}

C. Colorful Grid

大致题意

有一个棋盘，允许在棋盘的边上染色，然后使得从最左上角到最右下角的某一条路径长度恰好为 $k$ 的同时，路径上一定上红蓝间隔染色的

思路

即然可以重复点，那么最好的办法是找一个可以旋转的环，在里面转到足够多次就行。

因为需要红蓝间隔，那么必然最小的环就是 $4$ 个单位长度的格子，所以如果 $k$ 恰好是最短的距离加上 $4n$ 的话，就可以这样解决

但是还有一种情况，也就是不满足 $4n$ 的时候，例如 $3 \times 2$ 的方格，走 5 步，也是可以到达的（可以自己绘制一下）

故所以需要兼容上面的两种情况，我给出的一种解法如下

C1

首先根据矩形的长边，旋选择左边或者右边的，然后固定将左上角绘制成上述形状，然后再补充移动到右下角的路径即可

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, m, k;
        cin >> n >> m >> k;
        const int mi = n - 1 + m - 1;
        if (k < mi) {
            cout << "NO" << endl;
            continue;
        }

        if (const int cut = k - mi; cut != 0 && cut % 2 == 1) {
            cout << "NO" << endl;
            continue;
        }

        if (n == 2 && m == 2) {
            if (k % 4 != 2) cout << "NO" << endl;
            else cout << "B\nB\nR R" << endl;
            continue;
        }

        vector<vector<char>> a(n), b(n - 1);
        for (auto& i: a) i.resize(m - 1);
        for (auto& i: b) i.resize(m);

        if (n >= m) {
            a[0][0] = a[1][0] = a[2][0] = b[0][0] = 'B';
            b[0][1] = b[1][0] = b[1][1] = 'R';
            for (int i = 1; i < m - 1; ++i) a[2][i] = a[2][i - 1] == 'R' ? 'B' : 'R';
            const char last = b[1][m - 1];
            b[1][m - 1] = a[2][m - 2];
            for (int i = 2; i < n - 1; ++i) b[i][m - 1] = b[i - 1][m - 1] == 'R' ? 'B' : 'R';
            b[1][m - 1] = last;
        } else {
            a[0][0] = b[0][0] = b[0][1] = b[0][2] = 'R';
            a[0][1] = a[1][0] = a[1][1] = 'B';
            for (int i = 1; i < n - 1; ++i) b[i][2] = b[i - 1][2] == 'R' ? 'B' : 'R';
            const char last = a[n - 1][1];
            a[n - 1][1] = b[n - 2][2];
            for (int i = 2; i < m - 1; ++i) a[n - 1][i] = a[n - 1][i - 1] == 'R' ? 'B' : 'R';
            a[n - 1][1] = last;
        }
        cout << "YES" << endl;
        for (const auto& i: a) {
            for (const auto& j: i) cout << (j ? j : 'R') << ' ';
            cout << endl;
        }
        for (const auto& i: b) {
            for (const auto& j: i) cout << (j ? j : 'R') << ' ';
            cout << endl;
        }
    }
}

D. Absolute Beauty

大致题意

有两个数组，允许交换 $b$ 数组中的两个值一次，问使得 $\sum^n_{i=1} \left | a_i - b_i \right |$ 最大的可能是多少

思路

首先得画几个图来理解，为了方便，此处先假定 $a_i < b_i$（后续可以证明可以恒定满足此等式）

那么可以得到主要有两种情况

D1

可见，只有右边的情况是能够真正有意义的，有意义的部分是 $a_j - b_i$

那么就需要找到最大的 $a_j - b_i$ 即可

然后我们再来看看如何证明最开始说的 $a_i < b_i$。你可以尝试将图里的 $a,b$ 交换位置，你会发现对最终的结果没有影响

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#define int long long

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<int> a(n), b(n);
        for (auto& i: a) cin >> i;
        for (auto& i: b) cin >> i;
        for (int i = 0; i < n; ++i) if (a[i] > b[i]) swap(a[i], b[i]);

        int mib = 0, maa = 0;
        for (int i = 0; i < n; ++i) {
            if (b[i] < b[mib]) mib = i;
            if (a[i] > a[maa]) maa = i;
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) ans += abs(a[i] - b[i]);
        ans += max(0LL, 2 * (a[maa] - b[mib]));
        cout << ans << endl;
    }
}

E. Sofia and Strings

大致题意

有一个字符串 $a$，允许你无数次操作如下的两个方法其中之一

  • 选择其中一个片段，进行排序
  • 删掉一个指定的字符

问是否能够变成 $b$ 字符串

思路

这里的选择片段排序，实际上最有用的就是选择两个相邻的字母排序，这样就可以最小的改动的情况下，将一个值往前移动

而需要达成这个目标，就意味着每次移动的时候，前面的值都需要比当前值大，否则前面的值只能删除。

故可以考虑遍历 $b$ 的字母，找到当前可用的最小的在 $a$ 中的位置，并将前面的那些字符移动到后面（比当前字母大），或者删除

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, m;
        cin >> n >> m;
        string sn, sm;
        sn.reserve(n);
        sm.reserve(m);
        cin >> sn >> sm;
        vector<queue<int>> v(26);
        for (int i = 0; i < n; ++i) v[sn[i] - 'a'].push(i);

        bool flag = true;
        for (int i = 0; i < m; ++i) {
            if (v[sm[i] - 'a'].empty()) {
                flag = false;
                break;
            }

            int t = v[sm[i] - 'a'].front();
            v[sm[i] - 'a'].pop();

            for (int j = 0; j < sm[i] - 'a'; ++j) while (!v[j].empty() && v[j].front() < t) v[j].pop();
        }

        cout << (flag ? "YES" : "NO") << endl;
    }
}
☑️ ☆

Codeforces Round 909 (Div. 3)

✇Shiroha白羽的博客
Shiroha

A. Game with Integers

大致题意

有两个人 A/B 博弈，每次操作可以使一个值 $+1/-1$

问在 A 先操作的情况下，A 操作后恰好值可以被 3 整除，则 A 获胜，给出初始值，问 A 是否可能获胜

思路

初始是 3 的倍数就不能获胜，很简单

AC code

1
2
3
4
5
6
7
8
9
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        cout << (n % 3 ? "First" : "Second") << endl;
    }
}

B. 250 Thousand Tons of TNT

大致题意

有 $n$ 箱 TNT，不同重量但顺序固定，有 $k$ 辆卡车，每辆卡车从第一箱 TNT 开始取，每辆车恰好分到 $\frac{n}{k}$ 个 TNT 箱。

问在所有可能的 $k$ 下，什么时候可以使得最重的卡车和最轻的卡车差值最大。

(不过，题意中题到了 MrBeast，有意思)

思路

在可能的 $k$ 下，说明必须是 $n$ 的因子，因为一个数的因子不可能很多，所以暴力扫就行了

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#define int long long

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<int> data(n);
        for (auto& i: data) cin >> i;

        auto cal = [&](const int x) {
            int mi = LONG_LONG_MAX, ma = 0;

            for (int i = 0; i < n; i += x) {
                int tmp = 0;
                for (int j = 0; j < x; ++j) tmp += data[i + j];
                mi = min(mi, tmp);
                ma = max(ma, tmp);
            }

            return ma - mi;
        };

        int ans = 0;
        for (int i = 1; i < n; ++i) {
            if (n % i) continue;
            ans = max(cal(i), ans);
        }
        cout << ans << endl;
    }
}

C. Yarik and Array

大致题意

类似最大的连续字串和，只不过还要求必须奇偶间隔开

思路

稍微改一下 dp 转移方程即可，非常简单

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<int> data(n);
        for (auto& i: data) cin >> i;
        vector<int> ans(n);
        ans[0] = data[0];
        int res = ans[0];
        for (int i = 1; i < n; ++i) {
            if (abs(data[i]) % 2 ^ abs(data[i - 1]) % 2) ans[i] = max(data[i], ans[i - 1] + data[i]);
            else ans[i] = data[i];
            res = max(res, ans[i]);
        }

        cout << res << endl;
    }
}

D. Yarik and Musical Notes

大致题意

有一个数组，问有多少个对满足 $(2^{b_i})^{2^{b_j}} = (2^{b_j})^{2^{b_i}}$

思路

$$\begin{cases}& (2^{b_i})^{2^{b_j}} & = & (2^{b_j})^{2^{b_i}} \\\Rightarrow & 2^{b_i \times 2^{b_j}} & = & 2^{b_j \times 2^{b_i}} \\\Rightarrow & b_i \times 2^{b_j} & = & b_j \times 2^{b_i} \\\Rightarrow & \frac{b_i}{b_j} & = & \frac{2^{b_i}}{2^{b_j}} \\\Rightarrow & \frac{b_i}{b_j} & = & 2^{b_i - b_j}\end{cases}$$

设 $x = b_i - b_j$，得 $b_i = x + b_j$

得到

$$\begin{cases}& \frac{b_j + x}{b_j} & = & 2^x \\\Rightarrow & b_j + x & = & b_j \times 2^x \\\Rightarrow & x & = & b_j \times (2^x - 1) \\\Rightarrow & b_j & = & \frac{x}{2^x - 1} \\\end{cases}$$

绘图可以得到

D1

仅有 $x=0,x=1$ 有正整数解，所以显然，只能恰好相同或者恰好为 $1, 2$ 可以成对

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define int long long

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        map<int, int> cnt;
        for (int i = 0; i < n; ++i) {
            int tmp;
            cin >> tmp;
            ++cnt[tmp];
        }

        int ans = 0;
        for (auto [fst, snd]: cnt) ans += snd * (snd - 1) / 2;
        ans += cnt[1] * cnt[2];
        cout << ans << endl;
    }
}

E. Queue Sort

大致题意

每次可以把第一个值，从后往前找到第一个严格小于它的值，然后放到它后面，问操作几次可以让数组有序

思路

如果说当前值已经是最小的那个，那么每次移动一定会回到第一个，所以就会无法操作，即需要保证最小的那个出现的时候，后面的都得是有序的即可

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<int> data(n);
        for (auto& i: data) cin >> i;
        int mi = INT_MAX;
        for (const auto& i: data) mi = min(mi, i);
        int t = 0;
        while (data[t] != mi) ++t;
        bool flag = true;
        for (int i = t + 1; i < n; ++i) if (data[i] < data[i - 1]) flag = false;
        cout << (flag ? t : -1) << endl;
    }
}

F. Alex’s whims

大致题意

有一棵树，每次允许操作其中一条边（保证还是树的情况下）使得每次操作后，存在两个叶子节点（仅有一条边即为叶子节点）的距离恰好为给出的值

给出一种初始的树以及相关的操作方式

思路

简单题，都串成链，然后把最后的一个点，要多少，就连到哪，这样距离 $1$ 节点的距离恰好就是给出的值

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, q;
        cin >> n >> q;
        vector<int> data(q);
        for (auto& i: data) cin >> i;
        for (int i = 1; i < n; ++i) cout << i << ' ' << i + 1 << endl;
        int cur = n - 1;
        for (const auto& i: data) {
            if (i == cur) {
                cout << "-1 -1 -1" << endl;
                continue;
            }

            cout << n << ' ' << cur << ' ' << i << endl;
            cur = i;
        }
    }
}

G. Unusual Entertainment

大致题意

有一个 $n$ 的排列的数组 $p$，以及一棵节点数为 $n$ 的树，根为 $1$ 节点

每次询问 $l, r, x$，数组中 $[l, r]$ 区间内，是否存在至少一个点 $y$，满足 $y$ 是 $x$ 的一个孩子节点或者是 $x$ 本身

思路

我的思路和大部分人的思路不太一样，有一点比较暴力的味道。 看起来这道题就要离线处理了，那么可以考虑在树上做一遍操作把所有答案都算出来

首先，如何找到一个节点全部的孩子节点，那么就可以考虑使用树上 dfs 的方式来查找，在进入 dfs 到离开 dfs 的期间，那么遇到的点都是它的孩子

如果说此时在遍历到某个节点 $n$，这个节点在上面的数组 $p$ 的位置是 $m$，且这个 $m$ 恰好出现在了它的父节点的某个询问中，即父节点询问的区间包含 $m$
那么这个父节点的这个询问就是成功的，命中的。

那么我们需要维护的就是这个节点上面所有的父节点的询问。由于询问都是区间的模式，那么可以考虑用线段树维护，每个线段树的节点保存所遇到的询问的集合。

当遍历到某个树上的节点 $n$ 的时候，找出它所在 $p$ 中的 $m$，然后再看看这个 $m$ 在哪些父节点的询问中，对遇到的询问都标记为有结果即可。

通过这个方式，在进入某个节点的时候，将对这个节点的询问都放进线段树，离开的时候，都从线段树里取走，就可以实现在树上 dfs 期间，通过线段树完成搜索

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, q;
        cin >> n >> q;
        struct node {
            int v, n;
        };
        vector<node> edge(n * 2 - 2);
        vector<int> head(n + 1, -1), pos(n + 1);;
        vector<vector<tuple<int, int, int>>> query(n + 1);
        vector<pair<int, int>> qs;
        for (int i = 0; i < n - 1; ++i) {
            int u, v;
            cin >> u >> v;
            edge[i << 1] = {v, head[u]};
            edge[i << 1 | 1] = {u, head[v]};
            head[u] = i << 1;
            head[v] = i << 1 | 1;
        }
        for (int i = 1; i <= n; ++i) {
            int tmp;
            cin >> tmp;
            pos[tmp] = i;
        }
        for (int i = 0; i < q; ++i) {
            int l, r, x;
            cin >> l >> r >> x;
            qs.emplace_back(l, r);
            query[x].emplace_back(l, r, i);
        }

        vector<set<int>> tree(n * 2 + 10);
        auto get = [](const int l, const int r) {
            return (l + r) | (l != r);
        };
        function<void(int, int, int, int, int)> _add = [&](const int l, const int r, const int x, const int y, const int v) {
            const int mid = l + r >> 1;
            if (x == l && y == r) {
                tree[get(l, r)].insert(v);
                return;
            }

            if (y <= mid) _add(l, mid, x, y, v);
            else if (x > mid) _add(mid + 1, r, x, y, v);
            else {
                _add(l, mid, x, mid, v);
                _add(mid + 1, r, mid + 1, y, v);
            }
        };
        function<bool(int, int, int, int, int)> _del = [&](const int l, const int r, const int x, const int y, const int v) {
            const int mid = l + r >> 1;
            if (x == l && y == r) {
                return tree[get(l, r)].erase(v) ? true : false;
            }

            if (y <= mid) return _del(l, mid, x, y, v);
            if (x > mid) return _del(mid + 1, r, x, y, v);
            return _del(l, mid, x, mid, v) && _del(mid + 1, r, mid + 1, y, v);
        };
        function<void(int, int, int, vector<int>&)> _find = [&](const int l, const int r, const int v, vector<int>& res) {
            for (const auto& i: tree[get(l, r)]) res.push_back(i);
            if (l == r) return;

            if (const int mid = l + r >> 1; v <= mid) {
                _find(l, mid, v, res);
            } else if (v > mid) {
                _find(mid + 1, r, v, res);
            }
        };

        vector ans(q, false);
        vector<int> res;
        res.reserve(n);

        function<void(int, int)> dfs = [&](const int u, const int p) {
            for (const auto [l, r, i]: query[u]) _add(1, n, l, r, i);
            _find(1, n, pos[u], res);
            for (const auto& i: res) {
                ans[i] = true;
                _del(1, n, qs[i].first, qs[i].second, i);
            }
            res.clear();

            for (int i = head[u]; ~i; i = edge[i].n) {
                if (edge[i].v == p) continue;
                dfs(edge[i].v, u);
            }

            for (const auto [l, r, i]: query[u]) if (_del(1, n, l, r, i)) ans[i] = false;
        };

        dfs(1, 0);

        for (const auto& i: ans) cout << (i ? "YES" : "NO") << endl;
        cout << endl;
    }
}
☑️ ☆

Codeforces Round 903 (Div. 3)

✇Shiroha白羽的博客
Shiroha

A. Don’t Try to Count

大致题意

给出两个字符串 $n, m$，允许 $n$ 每次往自己拼接在自己后面，使得 $n$ 中出现 $m$ 字符串，问最少需要几次操作

思路

因为 $n, m$ 都很小，所以直接保留就行了

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, m;
        string str1, str2;
        str1.reserve(25);
        str2.reserve(25);
        cin >> n >> m >> str1 >> str2;
        int i = 0, flag = false;
        for (i = 0; i <= 5; ++i) {
            if (str1.find(str2) != -1) {
                flag = true;
                break;
            }
            str1 += str1;
        }
        cout << (flag ? i : -1) << endl;
    }
}

B. Three Threadlets

大致题意

有三根木棍，允许最多切三刀，问能否使得所有木棍都一样长

思路

因为只能切三刀，所以就很局限了

  • 如果一个棍子切一刀的方案下，那么必然只能中间切开，那么肯定最初大家都是一样的，故不可能存在这个情况
  • 如果分别为切 $0, 1, 2$ 的方案下，那么必然第二根棒子的长度得是第一根的两倍，第三根则为三倍
  • 如果分别为切 $0, 0, 3$ 的方案下，那么必然第三个棒子的长度得是前两根的四倍，同时第二根和第一个等长
  • 如果分别为切 $0, 1, 1$ 的方案下，那么必然第二个和第三个棒子的长度得是第一根的两倍
  • 如果分别为切 $0, 0, 2$ 的方案下，那么必然第三个棒子的长度得是前两根的三倍，同时第二根和第一个等长
  • 如果分别为切 $0, 0, 1$ 的方案下，那么必然第三个棒子的长度得是前两根的两倍，同时第二根和第一个等长

嗯，枚举所有情况即可

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        vector<int> data(3);
        cin >> data[0] >> data[1] >> data[2];
        sort(data.begin(), data.end());
        if (data[0] == data[2]) {
            cout << "YES" << endl;
            continue;
        }

        if (data[0] == data[1])
        cout << (data[2] == data[0] * 2 || data[2] == data[0] * 3 || data[2] == data[0] * 4 ? "YES" : "NO") << endl;
        else
        cout << (data[1] == data[0] * 2 && (data[2] == data[0] * 2 || data[2] == data[0] * 3) ? "YES" : "NO") << endl;
    }
}

C. Perfect Square

大致题意

矩阵旋转 $90$ 度后仍然相同，每次允许把矩阵中的一个值加一，问最少需要改多少次

思路

搞清楚旋转后，的每个位置映射的地方即可，很简单

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<string> data(n);
        for (auto &item : data) item.resize(n);
        for (auto &item : data) cin >> item;

        auto trans = [&](int &x, int &y) {
            swap(x, y);
            y = n - y - 1;
        };

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                char tmp[4];
                int x = i, y = j;
                for (int l = 0; l < 4; ++l) {
                    tmp[l] = data[x][y];
                    trans(x, y);
                }
                sort(tmp, tmp + 4);
                ans += tmp[3] * 3 - tmp[0] - tmp[1] - tmp[2];
            }
        }

        cout << ans / 4 << endl;
    }
}

D. Divide and Equalize

大致题意

有 $n$ 个数字，每次允许你从中挑选两个数字，将其中一个数字除以 $x$，另外一个数字乘以 $x$。注意操作后两数仍然是正整数，问是否能让所有数字相同

思路

简单题，把所有数字质因子分解了，然后看看每个质因子的出现次数是不是数组长度的倍数就行了

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#define int long long

void solve() {
    vector<bool> notPrime(1e6 + 10, false);
    vector<int> prime;
    notPrime[1] = true;
    for (int i = 2; i < 1e6 + 10; ++i) {
        if (notPrime[i]) continue;
        prime.push_back(i);
        for (int j = i * i; j <= 1e6 + 10; j += i) notPrime[j] = true;
    }

    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<int> data(n);
        for (auto &item: data) cin >> item;
        map<int, int> mp;
        for (auto item: data) {
            for (auto p : prime) {
                while (item % p == 0) {
                    mp[p]++;
                    item /= p;
                }
                if (item == 1) break;
                if (!notPrime[item]) {
                    mp[item]++;
                    break;
                }
            }
        }

        bool flag = true;
        for (auto iter = mp.begin(); iter != mp.end(); ++iter)
        if (iter->second % n != 0) flag = false;

        cout << (flag ? "YES" : "NO") << endl;
    }
}

E. Block Sequence

大致题意

有一个数组，希望能删掉一些值，使得整个数组满足一个特征：

整个数组可以拆分成几个连续的块，每个块第一个数字表示这个块内后面的数字个数

问最少需要删掉几个

思路

很容易想到用 dp 解决

假定当前位置为某个块的开头，那么带来的价值就是 dp[i + a[i]] = dp[i]

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve() {
    int _;
    cin >> _;
    for (int i = 0; i < _; ++i) {
        int n;
        cin >> n;
        vector<int> data(n), ans(n + 1, INT_MAX);
        for (auto &item : data) cin >> item;
        ans[0] = 0;
        if (data[0] + 1 <= n) ans[data[0] + 1] = 0;
        for (int i = 1; i < n; ++i) {
            ans[i] = min(ans[i], ans[i - 1] + 1);
            if (i + data[i] + 1 <= n) ans[i + data[i] + 1] = min(ans[i], ans[i + data[i] + 1]);
        }
        ans[n] = min(ans[n], ans[n - 1] + 1);
        cout << ans[n] << endl;
    }
}

F. Minimum Maximum Distance

大致题意

有一棵树，有些节点是红色的。求算树上的每一个节点到达最远的那个红色节点所需要的距离中，最小的那个值是多少

思路

树上做两次 dfs 就行了，第一次求出每个节点它下面最深的红色节点距离的位置，第二次做类似换根操作即可

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, k, ans = INT_MAX;
        cin >> n >> k;
        vector<int> deep(n + 1), mDeep(n + 1);
        set<int> mark;
        vector<vector<int>> edge(n + 1);
        for (int i = 0; i < k; ++i) {
            int tmp;
            cin >> tmp;
            mark.insert(tmp);
        }
        for (int i = 0; i < n - 1; ++i) {
            int u, v;
            cin >> u >> v;
            edge[u].push_back(v);
            edge[v].push_back(u);
        }

        if (n == 1) {
            cout << 0 << endl;
            continue;
        }
        function<void(int, int)> dfs1 = [&](int x, int p) {
            for (auto &i: edge[x]) {
                if (p == i) continue;
                deep[i] = deep[x] + 1;
                dfs1(i, x);
            }
            mDeep[x] = mark.count(x) ? 0 : INT_MIN;
            for (auto &i: edge[x]) {
                if (p == i) continue;
                mDeep[x] = max(mDeep[x], mDeep[i] + 1);
            }
        };
        function<void(int, int, int)> dfs2 = [&](int x, int p, int v) {
            ans = min(ans, max(v, mDeep[x]));
            if (edge[x].size() == 1 && p != -1) return;
            if (p != -1 && edge[x].size() == 2) {
                dfs2(edge[x][0] == p ? edge[x][1] : edge[x][0], x, mark.count(x) ? max(v + 1, 1) : v + 1);
                return;
            }
            if (p == -1 && edge[x].size() == 1) {
                dfs2(edge[x][0], x, mark.count(x) ? max(v + 1, 1) : v + 1);
                return;
            }
            sort(edge[x].begin(), edge[x].end(), [&](const int &u, const int &v) {
                if (u == p) return false;
                if (v == p) return true;
                return mDeep[u] > mDeep[v];
            });
            int base = mark.count(x) ? 1 : INT_MIN;
            for (int i = 0; i < edge[x].size() - 1; ++i)
            dfs2(edge[x][i], x, max(base, max(v, mDeep[(i == 0 ? edge[x][1] : edge[x][0])] + 1) + 1));
        };

        deep[1] = 0;
        dfs1(1, -1);
        dfs2(1, -1, INT_MIN);
        cout << ans << endl;
    }
}

G. Anya and the Mysterious String

大致题意

有一个字符串，每次可以选择其中一段区间，为每一个字母加上一个值，即 a + 1 = b, b + 2 = d 这种循环编码，然后同时询问某一段内是否存在回文串

思路

回文串可以考虑最小单位，即两个相邻的相同字母就是回文，或者间隔一个的相同字母，目的就是查找到这些

由于有区间加法操作，所以考虑到线段树

在线段树上每个节点，都记录它下面最前面两个字母和最后两个字母，然后合并的时候可以计算因为合并，贴在一起的那一段内是否出现了回文即可

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
struct SegTree {
    vector<int> data1, data2, data3, data4, lazy;
    vector<bool> flag;
    int atom;

    explicit SegTree(int n) : data1((n << 1) + 10), data2((n << 1) + 10),
    data3((n << 1) + 10), data4((n << 1) + 10),
    lazy((n << 1) + 10), flag((n << 1) + 10, false), atom(-1) {}

    static inline int get(int l, int r) {
        return (l + r) | (l != r);
    }

    void up(int l, int r) {
        if (l == r) return;

        int mid = (l + r) >> 1;
        int cur = get(l, r), lx = get(l, mid), rx = get(mid + 1, r);
        flag[cur] = flag[lx] || flag[rx];
        data1[cur] = data1[lx];
        data2[cur] = data2[lx];
        data3[cur] = data3[rx];
        data4[cur] = data4[rx];
        if (data2[cur] < 0) data2[cur] = data1[rx];
        if (data3[cur] < 0) data3[cur] = data4[lx];
        if (flag[cur]) return;

        if (data4[lx] == data1[rx] || data4[lx] == data2[rx] || data3[lx] == data1[rx]) flag[cur] = true;
        else flag[cur] = false;
    }

    void build(int l, int r) {
        int cur = get(l, r);
        lazy[cur] = 0;
        if (l == r) {
            data2[cur] = atom--;
            data3[cur] = atom--;
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid);
        build(mid + 1, r);
        up(l, r);
    }

    void push(int l, int r) {
        int cur = get(l, r);
        if (!lazy[cur]) return;
        int mid = (l + r) >> 1;
        int lx = get(l, mid), rx = get(mid + 1, r);
        data1[lx] = (data1[lx] + lazy[cur]) % 26;
        data2[lx] = data2[lx] < 0 ? data2[lx] : (data2[lx] + lazy[cur]) % 26;
        data3[lx] = data3[lx] < 0 ? data3[lx] : (data3[lx] + lazy[cur]) % 26;
        data4[lx] = (data4[lx] + lazy[cur]) % 26;
        lazy[lx] = (lazy[lx] + lazy[cur]) % 26;

        data1[rx] = (data1[rx] + lazy[cur]) % 26;
        data2[rx] = data2[rx] < 0 ? data2[rx] : (data2[rx] + lazy[cur]) % 26;
        data3[rx] = data3[rx] < 0 ? data3[rx] : (data3[rx] + lazy[cur]) % 26;
        data4[rx] = (data4[rx] + lazy[cur]) % 26;
        lazy[rx] = (lazy[rx] + lazy[cur]) % 26;

        lazy[cur] = 0;
    }

    void update(int l, int r, int x, int y, int w) {
        if (l == x && y == r) {
            int cur = get(l, r);
            data1[cur] = (data1[cur] + w) % 26;
            data2[cur] = data2[cur] < 0 ? data2[cur] : (data2[cur] + w) % 26;
            data3[cur] = data3[cur] < 0 ? data3[cur] : (data3[cur] + w) % 26;
            data4[cur] = (data4[cur] + w) % 26;
            lazy[cur] = (lazy[cur] + w) % 26;
            return;
        }
        push(l, r);
        int mid = (l + r) >> 1;
        if (y <= mid) update(l, mid, x, y, w);
        else if (x > mid) update(mid + 1, r, x, y, w);
        else {
            update(l, mid, x, mid, w);
            update(mid + 1, r, mid + 1, y, w);
        }
        up(l, r);
    }

    bool query(int l, int r, int x, int y) {
        if (l == x && y == r) {
            return flag[get(l, r)];
        }
        push(l, r);
        int mid = (l + r) >> 1;
        if (y <= mid) return query(l, mid, x, y);
        else if (x > mid) return query(mid + 1, r, x, y);
        else {
            bool tmp = query(l, mid, x, mid) || query(mid + 1, r, mid + 1, y);
            if (tmp) return true;
            int lx = get(l, mid), rx = get(mid + 1, r);
            if (data4[lx] == data1[rx]) return true;
            if (x <= mid - 1 && data3[lx] == data1[rx]) return true;
            if (y > mid + 1 && data4[lx] == data2[rx]) return true;
        }
        return false;
    }

    void debug(int l, int r) {
        #ifdef ACM_LOCAL
        int cur = get(l, r);
        cerr << '[' << l << '-' << r << "]: " << flag[cur] << "\t"
        << (data1[cur] >= 0 ? char(data1[cur] + 'a') : ' ')
        << (data2[cur] >= 0 ? char(data2[cur] + 'a') : ' ')
        << (data3[cur] >= 0 ? char(data3[cur] + 'a') : ' ')
        << (data4[cur] >= 0 ? char(data4[cur] + 'a') : ' ') << endl;
        if (l == r) return;
        int mid = (l + r) >> 1;
        debug(l, mid);
        debug(mid + 1, r);
        #endif
    }
};

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, q;
        cin >> n >> q;
        string str;
        str.reserve(n);
        SegTree tree(n);
        cin >> str;
        for (int i = 0; i < n; ++i) tree.data4[(i + 1) << 1] = tree.data1[(i + 1) << 1] = (str[i] - 'a');
        tree.build(1, n);
        for (int i = 0; i < q; ++i) {
            int o, l, r, w;
            cin >> o >> l >> r;
            if (o == 1) {
                cin >> w;
                tree.update(1, n, l, r, w % 26);
            } else
            cout << (tree.query(1, n, l, r) ? "NO" : "YES") << endl;
        }
        tree.debug(1, n);
    }
}
☑️ ☆

Educational Codeforces Round 156 (Rated for Div. 2)

✇Shiroha白羽的博客
Shiroha

A. Sum of Three

大致题意

将一个数拆成三个数，要求这三个数不同且都不是 $3$ 的倍数，给出一种拆法即可

思路

要拆成三个不同的数，且都不是 $3$ 的倍数，那么最小之能拆成 $1, 2, x$ 且 $x \geq 4$，而且还得保证 $x$ 不是 $3$ 的倍数。若这样拆了之后 $x$ 还是 $3$ 的倍数，那就只能 $1, 4, x$ 这样拆

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        if (n <= 6 || n == 9) {
            cout << "NO" << endl;
        } else if (n % 3) {
            cout << "YES" << endl;
            cout << "1 2 " << n - 3 << endl;
        } else {
            cout << "YES" << endl;
            cout << "1 4 " << n - 5 << endl;
        }
    }
}

B. Fear of the Dark

大致题意

笛卡尔坐标系上有两个灯，一个目标点，现在需要从 $(0, 0)$ 出发，走到目标点，路径完全任意，但是必须在灯光下走，问这两盏灯的最小灯光范围是多少

思路

比较简单，只有两种可能：1、只用一盏灯，2、同时用两盏灯

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int px, py, ax, ay, bx, by;
        cin >> px >> py >> ax >> ay >> bx >> by;
        auto dist = [&](int a, int b, int x, int y) {
            return sqrt((a - x) * (a - x) + (b - y) * (b - y));
        };

        double a0 = dist(0, 0, ax, ay);
        double b0 = dist(0, 0, bx, by);
        double ap = dist(px, py, ax, ay);
        double bp = dist(px, py, bx, by);
        double ab = dist(ax, ay, bx, by);

        double ans = max(ap, a0);
        ans = min(ans, max(bp, b0));
        ans = min(ans, max(max(min(a0, b0), min(ap, bp)), ab / 2));
        cout << setprecision(10) << ans << endl;
    }
}

C. Decreasing String

大致题意

有一个初始的字符串，每次删除一个，使其每次都保证是字典序最小的方案，将每一次的结果字符串拼接，得到一个最终结果字符串，问这个字符串的第 $x$ 位的字母是什么

思路

也是比较简单的题，要保证字典序最小，那就得使得字符串前缀尽可能保证非递减即可。用单调栈模拟一下就行

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void solve() {
    int _;
    cin >> _;

    string str;
    str.reserve(1e6 + 10);
    for (int ts = 0; ts < _; ++ts) {
        int pos;
        cin >> str >> pos;

        // bs
        if (pos <= str.size()) {
            cout << str[pos - 1];
            continue;
        }

        int l = 0, r = str.size();
        while (l + 1 < r) {
            int mid = (l + r) >> 1;
            int tot = (str.size() + (str.size() - mid)) * (mid + 1) / 2;
            if (tot < pos) l = mid;
            else r = mid;
        }
        pos -= (str.size() + (str.size() - l)) * (l + 1) / 2 + 1;

        vector<char> st;
        int cur = 0;
        l++;
        while (l--) {
            while (cur < str.size() && (st.empty() || st.back() <= str[cur])) st.push_back(str[cur++]);
            if (cur == str.size()) st.pop_back();
            else if (!st.empty() && st.back() > str[cur]) st.pop_back();
        }
        while (cur < str.size()) st.push_back(str[cur++]);

        cout << st[pos];
    }
}
❌