ABC221 复盘
[ABC221A] Seismic magnitude scales
思路解析
数据范围 \(B \le A \le 10\)，可以发现能直接暴力求解。注意开 long long。
code
//ABC221A
#include<bits/stdc++.h>
using namespace std;
int a, b;
int main() {
cin >> a >> b;
a -= b;
long long ans = 1;
for(int i = 1; i <= a; i++) {
ans *= 32;
}
cout << ans;
return 0;
}
[ABC221B] typo
思路解析
直接按照题意遍历 \(s\) 的每个下标与下一个下标交换，然后判断是否相同即可。注意可以不进行任何操作，要多一次判断。
时间复杂度：需要遍历每个下标\(O(\left\vert S \right\vert)\)，而每次交换后的判断也需要 \(O(\left\vert S \right\vert)\)，因此总复杂度为 \(O(\left\vert S \right\vert ^2)\)。
code
//ABC221B
#include<bits/stdc++.h>
using namespace std;
string s, t;
int main() {
cin >> s >> t;
if(s == t) {
cout << "Yes";
return 0;
}
for(int i = 1; i < s.size(); i++) {
swap(s[i], s[i - 1]);
if(s == t) {
cout << "Yes";
return 0;
}
swap(s[i], s[i - 1]);
}
cout << "No";
return 0;
}
[ABC221C] Select Mul
思路解析
可以想到想让乘积最大尽量让位数更平均，而同时我们也需要让更大的位数排在更前面，于是我们可以先将原数存成数组从大到小排个序，然后贪心取即可。
时间复杂度：设 \(x=\log_{10}N+1\)，有一层排序，因此复杂度为 \(O(x \log x)\)。
code
//ABC221C
#include<bits/stdc++.h>
using namespace std;
int n;
int main() {
cin >> n;
vector<int> v;
while(n > 0) {
v.push_back(n % 10);
n /= 10;
}
sort(v.begin(), v.end(), [](int x, int y) {
return x > y;
});
int x = 0, y = 0;
for(int i = 0; i < v.size(); i++) {
if(x <= y) x = x * 10 + v[i];
else y = y * 10 + v[i];
}
cout << x * y;
return 0;
}
[ABC221D] Online games
思路解析
首先可以想到先用差分打标记，最后结束时在统计即可。但可惜数据范围 \(A_i \le 10^9\)，不能存下来每一个时间点，于是想到离散化。将每个区间离散成 \(2\) 个点存下来，这样总点数就只有 \(2 \times N\) 个，可以通过。最后拿区间之间的人数乘上区间长度即可。
时间复杂度：一次排序加去重，复杂度为 \(O(N \log N)\)。
code
//ABC221D
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, a[N], b[N], c[5 * N], ans[N];
int main() {
cin >> n;
vector<int> v;
for(int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
v.push_back(a[i]);
v.push_back(a[i] + b[i]);
}
v.push_back(n + 1);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for(int i = 1; i <= n; i++) {
int pa = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
int pb = lower_bound(v.begin(), v.end(), a[i] + b[i]) - v.begin() + 1;
c[pa]++; c[pb]--;
}
for(int i = 1; i < v.size(); i++) {
c[i] += c[i - 1];
ans[c[i]] += v[i] - v[i - 1];
}
for(int i = 1; i <= n; i++) {
cout << ans[i] << ' ';
}
return 0;
}
[ABC221E] LEQ
思路解析
很有思维量的一道题。首先根据题目要求发现，新求的子序列只跟子序列的头尾有关，而在确定头尾之后中间的元素选或不选没有任何关系。也就是确定新子序列的头尾下标分别为 \(i,j\)，那么以当前头尾的可行子序列个数就是 \(2^{j-i-1}=2^j \div 2^{i+1}\) 种可能。
接下来我们思考，根据题目要求，上方的 \(i,j\) 一定有 \(a_i \le a_j\)，于是我们要做的其实就是找固定 \(j\)，有多少个 \(i\) 使得 \(i<j,a_i \le a_j\)，也就是个二维偏序。但事实上不需要那么复杂，假设有 \(i_1,i_2,\dots,i_k\) 都满足题目的条件，那么以 \(j\) 结尾的子序列的个数就是 \(2^j \div 2^{i_1+1}+2^j \div 2^{i_2+1}+\dots+2^j \div 2^{i_k+1}=2^j \div (2^{i_1+1}+2^{i_2+1}+\dots+2^{i_k+1})\)。
那么接下来就很轻松了，由于上方的 \(i,j\) 一定有 \(a_i \le a_j\)，所以我们可以用一个 \(rk_i\) 存下 \(a_i\) 的排名，设 \(v_{rk_i}=2^{i+1}\)，然后求 \(\sum_{k=1}^{rk_j-1}v_k\)，这样我们就可以求得满足 \(a_i \le a_j\) 的条件所有的 \(i\) 对答案的贡献，还要继续考虑 \(i<j\) 这个条件。我们其实可以不先处理出来 \(v\) 的值，而是在 \(j \to j+1\) 时处理 \(v_j\) 的值，这样就能保证所有 \(v\) 当中有值的 \(v_{rk_i}\) 都有 \(i<j\)。由于 \(v\) 需要满足单点修改和区间求和的操作，所以需要使用树状数组优化。
注意：由于有取模和乘方，所以需要使用逆元和快速幂求解。
时间复杂度：需要遍历每个下标，都需要一次区间查询和单点修改，复杂度为 \(O(n \log n)\)。
code
//ABC211E
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5 + 10;
const ll mod = 998244353;
int n, m;
ll a[N], c[N], b[N];
map<ll, int> rk;
ll ksm(ll a, ll b, ll p) {
ll ans = 1;
while(b) {
if(b & 1) {
ans = ans * a % p;
}
a = a * a % p;
b >>= 1;
}
return ans;
}
ll niyuan(ll a, ll p) {
return ksm(a, p - 2, p);
}
void add(ll x, ll y) {
for(; x <= n; x += (x & -x)) {
c[x] = (c[x] + y) % mod;
}
}
ll ask(ll x) {
ll sum = 0;
for(; x > 0; x -= (x & -x)) {
sum = (sum + c[x]) % mod;
}
return sum;
}
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
b[i] = a[i];
}
sort(b + 1, b + n + 1);
for(int i = 1; i <= n; i++) {
rk[b[i]] = i;
}
ll ans = 0;
for(int i = 1; i <= n; i++) {
ans = (ans + (ksm(2, i, mod) * ask(rk[a[i]])) % mod) % mod;
add(rk[a[i]], ksm(niyuan(2, mod), i + 1, mod));
}
cout << ans;
return 0;
}
[ABC221G] Jumping sequence
思路解析
题意很好理解，四向移动，步长确定，可见移动方式非常复杂，\(x,y\) 轴分别有三种可能的偏移量，于是我们选择将整个坐标系顺时针旋转 \(45^\circ\)，这样偏移量就只有加减两种可能，同时终点也变成了 \((x-y,x+y)\)。如此题目就变成了一道可行性背包问题，可以用 \(f_{i,j}\) 表示走了 \(i\) 步，第 \(j\) 行/列能否到达，由于每次行和列的偏移量的值相同，因此可以存在一个数组内。最后就是用 bitset 优化然后判断一下能否到达并根据 dp 过程中的值输出路径即可。
时间复杂度：\(O(N)\)。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 2010, M = 3.6e6 + 10;
int n, a, b, d[N], x, y, ans[N];
bitset<M> f[N];
int main() {
cin >> n >> a >> b;
x = a - b, y = a + b;
int sum = 0;
for(int i = 1; i <= n; i++) {
cin >> d[i];
sum += d[i];
}
if(sum < abs(x) || sum < abs(y)) {cout << "No"; return 0;}
if((x + sum) % 2 == 1 || (y + sum) % 2 == 1) {cout << "No"; return 0;}
x = (x + sum) / 2, y = (y + sum) / 2;
f[0][0] = true;
for(int i = 1; i <= n; i++) {
f[i] = f[i - 1] | (f[i - 1] << d[i]);
}
if(!f[n][x] || !f[n][y]) {cout << "No"; return 0;}
cout << "Yes\n";
for(int i = n; i >= 1; i--) {
if(f[i - 1][x] && f[i - 1][y]) ans[i] = 0;
else if(!f[i - 1][x] && f[i - 1][y]) ans[i] = 1;
else if(f[i - 1][x] && !f[i - 1][y]) ans[i] = 2;
else if(!f[i - 1][x] && !f[i - 1][y]) ans[i] = 3;
if(ans[i] & 1) x -= d[i];
if(ans[i] & 2) y -= d[i];
}
for(int i = 1; i <= n; i++) {
if(ans[i] == 0) cout << "L";
else if(ans[i] == 1) cout << "D";
else if(ans[i] == 2) cout << "U";
else if(ans[i] == 3) cout << "R";
}
return 0;
}