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 - 2l_2)\)
如果前者更小，那就需要满足 \(l_2 \leq \frac{n}{3} - 1\)，那么 \(l_2 - 1\) 的最大值就是 \(\frac{n}{3} - 2\)。
如果后者更小，那就需要满足 \(l_2 \geq \frac{n}{3} - 1\)，那么 \(n - 4 - 2l_2\) 的最大值就是 \(n - 4 - 2(\frac{n}{3} - 1) = \frac{n}{3} - 2\)。
所以，答案就是 \(\frac{n}{3} - 2\)。
时间复杂度：\(O(1)\)
对应AC代码
#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\)，在按照同一长度 \(2x-1\) 切割后，我们有可能会多出一小段长度小于 \(x\) 的，但我们显然可以各取前面长为 \(2x - 1\) 的那几段的一部分来填补，而且一定不会让前面的那几段减到比 \(x\) 小。
那么，答案就是 \(\displaystyle{\sum_{i=1}^{n}\left\lceil\frac{a_i}{2 \cdot x - 1}\right\rceil}\)
显然，我们希望尽可能减少切割次数，也就是说至少有一段是不用切的。
那么，升序排序 \(a\) 后，\(\displaystyle{\sum_{i=1}^{n}\left\lceil\frac{a_i}{2 \cdot a_1 - 1}\right\rceil}\) 就是答案。
时间复杂度：\(O(n)\)
对应AC代码
#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(nm)\)
对应AC代码
#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)\) 的复杂度是完全可以接受的，那么我们不妨去枚举所有的三元组中的其中两个序列，然后我们就可以按照题意构造出第三个序列，我们直接记录构造出的这个序列可以对应多少个 "两个序列"。
记录完后，我们直接枚举所有序列，对于对应的个数 \(cnt\)，我们就可以得到 \(C^2_{cnt}\) 个满足条件的五元组。
时间复杂度：\(O(n^2 \log n)\)
对应AC代码
#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();
}有点像状压