Practice.

A. Working Week

题意

给定 $n$ 个格子，规定第 $1$ 个格子不能标记，第 $n$ 个格子一定被标记。按照要求标记三个点后，格子被划分成三段，记长度为 $l_{1}, l_{2}, l_{3}$ 。

输出 $min (| l_{1} - l_{2} |, | l_{2} - l_{3} |, | l_{3} - l_{1} |)$ 的最大值。

思路

显然，我们可以在第二个点做上标记，这样就可以让差值尽可能大。

那么，我们来考虑剩下那个点。因为对称性，我们不妨令 $l_{2} \leq l_{3}$ 。

很明显， $min (| l_{1} - l_{2} |, | l_{2} - l_{3} |, | l_{3} - l_{1} |) = min (l_{2} - 1, n - 4 - 2 l_{2})$

如果前者更小，那就需要满足 $l_{2} \leq \frac{n}{3} - 1$ ，那么 $l_{2} - 1$ 的最大值就是 $\frac{n}{3} - 2$ 。

如果后者更小，那就需要满足 $l_{2} \geq \frac{n}{3} - 1$ ，那么 $n - 4 - 2 l_{2}$ 的最大值就是 $n - 4 - 2 (\frac{n}{3} - 1) = \frac{n}{3} - 2$ 。

所以，答案就是 $\frac{n}{3} - 2$ 。

时间复杂度： $O (1)$

对应AC代码

C++

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve(){
    int n;
    cin >> n;
    cout << n / 3 - 2 << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

其实也可以猜出来（x

B. Tea with Tangerines

题意

给定长度为 $n$ 的序列 $a$ ，其中 $a_{i}$ 可切割为任意段。在切割结束后，需要满足任意两段中较小的那段的两倍严格小于较长那段。输出需要切割的最小次数。

思路

首先，我们先设最小那段为 $x$ ，在按照同一长度 $2 x - 1$ 切割后，我们有可能会多出一小段长度小于 $x$ 的，但我们显然可以各取前面长为 $2 x - 1$ 的那几段的一部分来填补，而且一定不会让前面的那几段减到比 $x$ 小。

那么，答案就是 $\sum_{i = 1}^{n} ⌈ \frac{a_{i}}{2 \cdot x - 1} ⌉$

显然，我们希望尽可能减少切割次数，也就是说至少有一段是不用切的。

那么，升序排序 $a$ 后， $\sum_{i = 1}^{n} ⌈ \frac{a_{i}}{2 \cdot a_{1} - 1} ⌉$ 就是答案。

时间复杂度： $O (n)$

对应AC代码

C++

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve(){
    int n;
    cin >> n;
    int ans = 0, a0;
    cin >> a0;
    for(int i=1;i<n;i++){
        int cur;
        cin >> cur;
        ans += (cur - 1) / (2 * a0 - 1);
    }
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

有点抽象

C. Phase Shift

题意

给定一个由大写字母组成的字符串，构造一个字符串映射，满足映射对应的有向图为一个包含 $A - Z$ 内所有字母的单环。

输出映射后字典序最小的结果。

思路

我们可以暴力枚举每一位，对于该位，如果我们并没有创建映射，我们就暴力按字母表顺序枚举所有字母，找出第一个没有被创建且和原字母不一样的字母并创建映射；如果创建了映射，我们直接使用该映射即可。

时间复杂度： $O (n m)$

对应AC代码

C++

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7;

void init(){}

void solve() {
    int n;
    string t;
    cin >> n >> t;
    vector<int> e(26, -1), re(26, -1);
    for(int i=0;i<n;i++){
        int cur = t[i] - 'a';
        if(e[cur] == -1) {
            for (int j = 0; j < 26; j++) {
                if (re[j] == -1) {
                    int last = j, cnt = 0;
                    while (e[last] != -1) last = e[last], cnt++;
                    if (last != cur || cnt == 25) {
                        e[cur] = j, re[j] = cur;
                        break;
                    }
                }
            }
        }
        t[i] = (char) (e[cur] + 'a');
    }
    cout << t << '\n';
}


signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    cin >> t;
    while(t --) solve();
}

就很暴力（x

D. Meta-set

题意

给定 $n$ 个长度为 $m$ 的序列，序列元素由 $0, 1, 2$ 构成。

若一个由 $3$ 个不同序列组成的三元组满足对于所有序列的第 $i$ 个元素组成的新序列均为相等的值或为 $012$ 的排列，那么这个三元组是好的。

输出序列的所有五元组中有至少两个好三元组的个数。

思路

（题意还是介绍得有点绕，可以去看原题的样例）

首先，数据量并不大， $O (n^{2})$ 的复杂度是完全可以接受的，那么我们不妨去枚举所有的三元组中的其中两个序列，然后我们就可以按照题意构造出第三个序列，我们直接记录构造出的这个序列可以对应多少个 "两个序列"。

记录完后，我们直接枚举所有序列，对于对应的个数 $c n t$ ，我们就可以得到 $C_{c n t}^{2}$ 个满足条件的五元组。

时间复杂度： $O (n^{2} \log n)$

对应AC代码

C++

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7;

void init(){}

void solve() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> a(n, vector<int>(k));
    for(int i=0;i<n;i++)
        for(int j=0;j<k;j++)
            cin >> a[i][j];
    map<vector<int>, int> cnt;
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++){
            vector<int> need(k);
            for(int t=0;t<k;t++){
                need[t] = a[i][t] == a[j][t] ? a[i][t] : 3 - a[i][t] - a[j][t];
            }
            cnt[need] ++;
        }
    int ans = 0;
    for(int i=0;i<n;i++){
        if(cnt[a[i]] >= 2) ans += cnt[a[i]] * (cnt[a[i]] - 1) / 2;
    }
    cout << ans << '\n';
}


signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    //cin >> t;
    while(t --) solve();
}

有点像状压

A. Working Week

题意

思路

对应AC代码

B. Tea with Tangerines

题意

思路

对应AC代码

C. Phase Shift

题意

思路

对应AC代码

D. Meta-set

题意

思路

对应AC代码

微信扫一扫：分享