ABC 261 复盘
[ABC261A] Intersection
思路解析
因为这题czl错了所以我特地来写个复盘
可以想到两条线段的关系只有不相交，相交，包围三种，于是我们可以直接判断每种情况然后输出就好了，可以在判断前先将两条线段的位置判断一下交换方便之后操作。
#include<bits/stdc++.h>
using namespace std;
int l1, r1, l2, r2;
signed main() {
cin >> l1 >> r1 >> l2 >> r2;
if(l1 > l2) swap(l1, l2), swap(r1, r2);
if(r1 >= r2) cout << r2 - l2;
else if(r1 >= l2) cout << r1 - l2;
else cout << 0;
return 0;
}
[ABC261D] Flipping and Bonus
思路解析
是一个简单 dp。用 \(f_{i,j}\) 表示现在是第 \(i\) 轮抛硬币，计数器上的数是 \(j\)，同时设 \(t_{C_i}=Y_i\)。分为两种情况转移；若当前硬币为正面，则 \(f_{i,j} \gets f_{i-1,j-1}+X_i+t_j\)；若当前硬币为反面，则 \(f_{i,0} \gets f_{i-1,j}\)。
最后注意判断转移时传过来的元素是否有值。
code
#include<bits/stdc++.h>
#define int long long
#define PII pair<long long, long long>
#define fir first
#define sec second
using namespace std;
const int N = 5010;
int n, m, c[N], f[N][N];
PII s[N];
map<int, int> mp;
signed main() {
memset(f, -1, sizeof(f));
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> c[i];
for(int i = 1; i <= m; i++) {
cin >> s[i].fir >> s[i].sec;
mp[s[i].fir] = s[i].sec;
}
f[0][0] = 0;
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= n; j++){
if(f[i - 1][j] >= 0) f[i][0] = max(f[i][0], f[i - 1][j]);
if(j > 0 && f[i - 1][j - 1] >= 0) f[i][j] = max(f[i][j], f[i - 1][j - 1] + c[i] + mp[j]);
}
}
int ans = 0;
for(int i = 0; i <= n; i++) ans = max(ans, f[n][i]);
cout << ans;
return 0;
}
[ABC261E] Many Operations
思路解析
首先可以发现，如果直接跑肯定会炸，于是考虑优化。首先发现操作有很多重复的，所以可以考虑把每一个数经过所有操作后的值都预处理下来，但这样显然空间也会炸。然后我们又想到可以不需要求下每个数经过操作后的值，可以把每一位二进制上在开始前是 \(0\) 还是 \(1\) 的情况记录下来，然后在需要查询时遍历每一位，把每一位上对应二进制的值取出来再相加即可。
还有就是尽量不要用我的代码的实现去写，看上去十分丑陋不便于调试，可以直接用 bitset 或整形变量存储，没必要使用 dp。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n, c;
int f[2][N][32];
signed main() {
cin >> n >> c;
for(int i = 0; i <= 30; i++) f[1][0][i] = 1;
for(int i = 1, op, x; i <= n; i++) {
cin >> op >> x;
for(int j = 0; j <= 30; j++) {
int t = ((x >> j) & 1);
for(int k = 0; k < 2; k++) {
if(op == 1) f[k][i][j] = f[k][i - 1][j] & t;
else if(op == 2) f[k][i][j] = f[k][i - 1][j] | t;
else if(op == 3) f[k][i][j] = f[k][i - 1][j] ^ t;
}
}
int res = 0;
for(int j = 0; j <= 30; j++) {
int t = ((c >> j) & 1);
res += (f[t][i][j] << j);
} c = res;
cout << res << '\n';
}
return 0;
}
[ABC261F] Sorting Color Balls
思路解析
首先我们可以考虑如果没有 \(C\) 的情况下那答案就是 \(X\) 中逆序对的个数。接下来想如果加入了 \(C\)，那答案减去的部分的每个逆序对 \((i,j)\)，都有 \(C_i=C_j\)；也就是说，只有对于 \(C_i=C_j\) 的数对 \((i,j)\) 才有可能对答案造成贡献；而同时，只有 \(X_i>X_j\) 才会对答案造成贡献，所以我们只需要对于每一个 \(C_{d_1}=C_{d_2}=C_{d_3}\dots\) 求序列 \(W_{d_1},W_{d_2},W_{d_3}\dots\) 的逆序对数即可。
求逆序对的方法很多，这里我用的是树状数组法，记得要在每次求完逆序对后撤销原来的操作。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
namespace BIT {
const int B_SIZE = 5e5 + 10;
int B[B_SIZE + 10];
void add(int x, int y) {
for(; x <= B_SIZE; x += (x & -x)) B[x] += y;
}
int ask(int x) {
int sum = 0;
for(; x > 0; x -= (x & -x)) sum += B[x];
return sum;
}
}
using namespace BIT;
int n, c[N], d[N];
vector<int> v[N];
long long nxd(int x) {
long long res = 0;
for(auto it : v[x]) {
res += ask(n + 1) - ask(it);
add(it, 1);
}
for(auto it : v[x]) add(it, -1);
return res;
}
signed main() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> c[i];
for(int i = 1; i <= n; i++) cin >> d[i];
long long ans = 0;
for(int i = 1; i <= n; i++) {
ans += ask(n + 1) - ask(d[i]);
add(d[i], 1);
}
for(int i = 1; i <= n; i++) add(d[i], -1);
for(int i = 1; i <= n; i++) v[c[i]].push_back(d[i]);
for(int i = 1; i <= n; i++) ans -= nxd(i);
cout << ans;
return 0;
}