Codeforces Round #826 (Div. 3) A-E
A
題解
知識點：模擬。
時間複雜度 \(O(n)\)
空間複雜度 \(O(n)\)
程式碼
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool solve() {
string a, b;
cin >> a >> b;
if (a.back() != b.back()) {
if (a.back() > b.back()) cout << '<' << '\n';
else if (a.back() == b.back()) cout << '=' << '\n';
else cout << '>' << '\n';
}
else if (a.back() == 'S') {
if (a.size() > b.size()) cout << '<' << '\n';
else if (a.size() == b.size()) cout << '=' << '\n';
else cout << '>' << '\n';
}
else if (a.back() == 'L') {
if (a.size() > b.size()) cout << '>' << '\n';
else if (a.size() == b.size()) cout << '=' << '\n';
else cout << '<' << '\n';
}
else cout << '=' << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
B
題解
知識點：構造。
除了 \(n = 3\) ，其餘取末尾兩個倒放在前面，然後從 \(1\) 按順序即可。
時間複雜度 \(O(n)\)
空間複雜度 \(O(n)\)
程式碼
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool solve() {
int n;
cin >> n;
if (n == 3) return false;
cout << n << ' ' << n - 1 << ' ';
for (int i = 1;i <= n - 2;i++) cout << i << ' ';
cout << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
C
題解
知識點：枚舉。
暴力枚舉可能的第一段作為基準劃分，找到合法劃分的中段的最大值，取所有合法的最小值。
時間複雜度 \(O(n^2)\)
空間複雜度 \(O(n)\)
程式碼
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[2007];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i], a[i] += a[i - 1];
int mi = n;
for (int i = 1;i <= n;i++) {
int tag = a[i] - a[0];
int l = i + 1, r = i + 1, tmx = i;
while (l <= n) {
while (r <= n) {
if (a[r] - a[l - 1] > tag) break;
r++;
}
if (a[r - 1] - a[l - 1] == tag) tmx = max(tmx, r - l);
else break;
l = r;
}
if (l > n) mi = min(mi, tmx);
}
cout << mi << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
D
題解
知識點：模擬，構造。
模擬這個過程，每次對數組元素分組，組大小從 \(2\) 開始倍增，因為大組交換不會改變組內兩邊元素相對位置，所以從最小的組開始排序。每組比較先把一組分為兩半，因為這兩半在上一輪的分組排序一定排序好了，然後把兩邊第一個元素作為代表元比較大小，每次只交換代表元即可，下一輪比較一定是其中較小的代表元比較。
注意到，無論如何交換，都不能改變原數組兩兩連續分組後的各個元素的相鄰元素 （如 12|34|56|78 ，其中兩兩元素一定相鄰）。因此，如果發現某次交換，一組中兩半的代表元差值，不是組大小的一半，那一定無解。
時間複雜度 \(O(m)\)
空間複雜度 \(O(m)\)
程式碼
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int p[300007];
bool solve() {
int m;
cin >> m;
for (int i = 1;i <= m;i++) cin >> p[i];
int cnt = 0;
for (int i = 1;(1 << i) <= m;i++) {
for (int j = 1;j <= m;j += 1 << i) {
if (abs(p[j] - p[j + (1 << i - 1)]) != (1 << i - 1)) return false;
if (p[j] > p[j + (1 << i - 1)]) swap(p[j], p[j + (1 << i - 1)]), cnt++;
}
}
cout << cnt << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
E
知識點：線性dp。
樸素dp，設 \(dp[i]\) 為 \([1,i]\) 是否合法。考慮 \(b[i]\) 時，可以把其放下一段左側或者是右側，因此有轉移方程：
if (i - b[i] - 1 >= 0) dp[i] |= dp[i - b[i] - 1];
if (i + b[i] <= n) dp[i + b[i]] |= dp[i - 1];
時間複雜度 \(O(n)\)
空間複雜度 \(O(n)\)
題解
程式碼
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int b[200007];
bool dp[200007];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> b[i], dp[i] = 0;
dp[0] = 1;
for (int i = 1;i <= n;i++) {
if (i - b[i] - 1 >= 0) dp[i] |= dp[i - b[i] - 1];
if (i + b[i] <= n) dp[i + b[i]] |= dp[i - 1];
}
if (dp[n]) cout << "YES" << '\n';
else cout << "NO" << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
