Practice.
A. Compare T-Shirt Sizes
题意
比较 \(T\) 恤的尺码。
其中，\(XXL > XL, XXS < XS\)。
思路
我们记 \(M = 0\)，其余的按照 \(X\) 的个数计算即可。
时间复杂度：\(O(1)\)
对应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;
void init(){}
void solve() {
string a, b;
cin >> a >> b;
int na = a.size(), nb = b.size();
map<char, int> mp = {{'S', -1}, {'M', 0}, {'L', 1}};
int va = mp[a[na - 1]] * na, vb = mp[b[nb - 1]] * nb;
cout << (va == vb ? '=' : (va > vb ? '>' : '<')) << '\n';
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
init();
int t;
cin >> t;
while(t --) solve();
}无脑做即可
B. Funny Permutation
题意
给定整数 \(n\)，构造一个长为 \(n\) 的排列 \(a\)，满足 \(a_i\) 的至少一个相邻元素的值为 \(a_i ±1\)，且 \(a_i \neq i\)。
思路
首先，如果没有第二个条件，我们直接按顺序输出即可。
如果考虑第二个条件，如果 \(n\) 为偶数，那我们直接倒着输出即可。
但 \(n\) 为奇数的时候，我们就需要规避中间那个数不满足条件的情况了。
如何规避呢？我们只需先按顺序构造序列，然后把前 \(\frac{n + 1}{2}\) 个数移到最后就可以了。
可以证明，这种构造对任意长度的排列均满足。
时间复杂度：\(O(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;
void init(){}
void solve() {
int n;
cin >> n;
if (n == 3) cout << -1 << '\n';
else {
for(int i=n;i>n/2 + n % 2;i--) cout << i << ' ';
for(int i=1;i<=n/2+n%2;i++) cout << i << ' ';
cout << '\n';
}
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
init();
int t;
cin >> t;
while(t --) solve();
}很有趣的构造题（x
C. Minimize the Thickness
题意
给定一个序列，将其分割为若干段 元素和相等 的片段，输出最长片段的长度最小值。
思路
很暴力。我们直接枚举第一段的长度，然后去分割，找出最长片段。最后我们统计最小值即可。
时间复杂度：\(O(n^2)\)
对应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;
void init(){}
void solve() {
int n;
cin >> n;
vector<int> sum(n + 1);
for(int i=1;i<=n;i++) {
int cur;
cin >> cur;
sum[i] = sum[i - 1] + cur;
}
auto check = [n, sum](int cnt){
bool ans = true;
int pre = 0, mx = cnt;
for(int i=1;i<=n;i++){
if(sum[i] - sum[pre] > sum[cnt]){
ans = false;
break;
}else if(sum[i] - sum[pre] == sum[cnt]){
mx = max(mx, i - pre);
pre = i;
}
}
return make_pair(mx, ans && pre == n);
};
int ans = n;
for(int i=1;i<=n;i++){
auto e = check(i);
if(e.sc) ans = min(ans, e.fs);
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
init();
int t;
cin >> t;
while(t --) solve();
}无脑暴力.cpp
D. Masha and a Beautiful Tree
题意
给定一个满二叉树的所有叶节点的编号，规定编号序列为长度为 \(n\) 的排列。
判断是否可以通过 若干次 交换 任意 左右子树的位置 来让排列升序，若可以，输出最小操作数。
思路
显然，我们不难发现，两个父亲一样的叶节点的值相差 \(1\)。
有趣的是，我们规定这些父亲节点（即第二层叶节点）的值为子节点的最大值除以 \(2\)，那么依然需要满足上面的条件。
也就是说，我们只需从最底层向上合并并判断即可。
在每次判断的时候，我们比较一下左右两个节点的大小，如果左边的大，那么就需要一次操作，统计即可。
时间复杂度：\(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;
void init(){}
void solve() {
int n;
cin >> n;
vector<int> ori(n);
for(int i=0;i<n;i++) cin >> ori[i];
int p = 0, tp = n;
while(tp > 0) tp /= 2, p ++;
int ans = 0;
for(int i=1;i<p;i++){
int cnt = n / pow(2, i);
vector<int> now(cnt);
for(int j=0;j<cnt;j++){
if(abs(ori[j * 2] - ori[j * 2 + 1]) != 1){
ans = -1;
break;
}
if(ori[j * 2] > ori[j * 2 + 1]) ans ++;
now[j] = (ori[j * 2] + 1) / 2;
}
if(ans == -1) break;
ori = now;
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
init();
int t;
cin >> t;
while(t --) solve();
}找规律.jpg
E. Sending a Sequence Over the Network
题意
给定一种处理方式：将给定序列拆成若干段，在每段的前面或后面插入这一段的长度。
现在，给定一个序列，判断是否为处理后的序列。
思路
我们不妨考虑递推，即 \(dp\)，用递推的方式记录当前位置之前的元素是否满足条件。
那么， 如果这个数是个数：
他是前面序列的个数，那么 \(dp[i]\ |= dp[i - a_i - 1]\) （该序列有效，那么 \(dp_i\) 和跳过这个序列的前一个序列的 \(dp\) 值有关）
他是后面序列的个数，那么 \(dp[i + a_i]\ |= dp[i - 1]\)。
最后，\(dp[n]\) 即为答案。
时间复杂度：\(O(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;
void init(){}
void solve() {
int n;
cin >> n;
vector<int> dp(n + 1);
dp[0] = true;
for(int i=1;i<=n;i++){
int cur;
cin >> cur;
if(i - cur >= 1) dp[i] |= dp[i - cur - 1];
if(i + cur <= n) dp[i + cur] |= dp[i - 1];
}
cout << (dp[n] ? "YES\n" : "NO\n");
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
init();
int t;
cin >> t;
while(t --) solve();
}嘶，想到了还真不难