ABC271 复盘
[ABC271A] 484558
思路解析
根据小学学过的进制转换法可得,\(10\) 进制转换成 \(x\) 进制可以用 \(10\) 进制反复除 \(x^k\),其中 \(k\) 代表在 \(x\) 进制下的第 \(k\) 位,然后在每次除完后取余再反向排列即可求得。但是此题由于 \(0 \le N \le 255\) 所以只需要判断 \(16\) 进制下的前两位即可。
code
#include<bits/stdc++.h>
using namespace std;
int n;
int main() {
cin >> n;
int fir = n / 16;
if(fir > 9) {
cout << (char)(fir - 10 + 'A');
}
else {
cout << fir;
}
int sec = n % 16;
if(sec > 9) {
cout << (char)(sec - 10 + 'A');
}
else {
cout << sec;
}
return 0;
}
[ABC271B] Maintain Multiple Sequences
思路解析
首先,我们如果开二维矩阵肯定会爆,其次我们发现它的总空间占用不大,只是单列空间大,于是可以想到用 vector
做。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, l[N], q;
vector<int> a[N];
int main() {
cin >> n >> q;
for(int i = 1; i <= n; i++) {
cin >> l[i];
for(int j = 1, x; j <= l[i]; j++) {
cin >> x;
a[i].push_back(x);
}
}
while(q--) {
int s, t;
cin >> s >> t;
cout << a[s][t - 1] << "\n";
}
return 0;
}
[ABC271C] Manga
思路解析
求一个数的最值可以轻易想到用二分求,此题用二分答案。由于每一册书只要有一本就足够了,所以可以用一个桶装下每一个数是否出现,然后再对桶做前缀和,这样 \(b_i\) 就能表示第 \(1 \to i\) 册书总共有多少本,于是在 check
函数时我们就只需要比较 \(b_x\) 和 \(n-b_x\) 的数量关系即可。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int n, a[N];
int m;
int b[N];
bool check(int x) {
int have = b[x];
int lst = n - have;
if(have + lst / 2 >= x) {
return true;
}
else {
return false;
}
}
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
if(a[i] <= n) {
b[a[i]]= 1;
}
}
for(int i = 1; i <= n; i++){
b[i] += b[i - 1];
}
int l = 0, r = n, mid = (l + r) / 2;
int ans = 0;
while(l <= r) {
mid = (l + r) / 2;
if(check(mid)) {
ans = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
cout << ans;
return 0;
}
[ABC271D] Flip and Adjust
思路解析
典型的背包问题,\(f_{i,j}\) 表示已经选了 \(i\) 张卡片,和为 \(j\) 的情况是否有解,而对于输出情况则对于每一个 \(i,j\) 都用一个字符串存下,只需要在状态转移时同时转移字符串即可。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 10010;
int n, m;
int a[N], b[N];
bool f[N][M];
string v[N][M];
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
}
f[0][0] = true;
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= m; j++) {
if(f[i - 1][j]) {
f[i][j + a[i]] = true;
v[i][j + a[i]] = v[i - 1][j] + 'H';
f[i][j + b[i]] = true;
v[i][j + b[i]] = v[i - 1][j] + 'T';
}
}
}
if(f[n][m]) {
cout << "Yes\n";
cout << v[n][m];
}
else {
cout << "No";
}
return 0;
}
[ABC271E] Subsequence Path
思路解析
很好的一道题,很有迷惑性,表面上是一道图论实际上是 dp,定义 \(f_{i}\) 为从 \(1\) 到 \(i\) 的最短 “好路”。先把每条边对应的起点,终点和边权记录下来,然后输入每个 \(e\),由于是子序列顺序不会改变,因此可以顺序进行操作。对于每一个 \(e\),都有选和不选两种情况,若选,则相当于最短路算法中的松弛操作,转移 \(f_{a_{e}}\gets\min(f_{a_{e}},f_{b_{e}}+c_{e})\)(\(a_{i},b_{i},c_{i}\) 分别代表第 \(i\) 条边的起点,终点和边权)。
code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
ll n, m, k;
ll a[N], b[N], c[N];
ll e;
ll f[N];
int main() {
cin >> n >> m >> k;
for(int i = 1; i <= m; i++) {
cin >> a[i] >> b[i] >> c[i];
}
memset(f, 0x3f, sizeof(f));
f[1] = 0;
for(int i = 1; i <= k; i++) {
cin >> e;
f[b[e]] = min(f[b[e]], f[a[e]] + c[e]);
}
if(f[n] < 1e18) {
cout << f[n];
}
else {
cout << -1;
}
return 0;
}
[ABC271F] XOR on Grid Path
思路解析
首先看到数据范围 \(2 \le N \le 20\) 可以想到搜索,由于路径长度为 \(N\),所以复杂度 \(O(2^{2n})\),无法接受。考虑到 \(O(2^{n})\) 复杂度可以接受,可以想到 dfs 可以不跑完全程,分成两次,每次跑一半,分别跑左上和右下部分,在次对角线上相遇,复杂度就是 \(O(2 \times 2^n)\),可以接受。
code
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 25;
int n;
int a[N][N];
map<int, int> mp[N];
long long ans = 0;
void dfs1(int x, int y, int s) {
s ^= a[x][y];
if(x + y == n + 1) {
mp[x][s]++;
return;
}
dfs1(x + 1, y, s);
dfs1(x, y + 1, s);
}
void dfs2(int x, int y, int s) {
if(x + y == n + 1) {
if(mp[x].find(s) != mp[x].end()) {
ans += mp[x][s];
}
return;
}
s ^= a[x][y];
dfs2(x - 1, y, s);
dfs2(x, y - 1, s);
}
signed main() {
cin >> n;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
dfs1(1, 1, 0);
dfs2(n, n, 0);
cout << ans;
return 0;
}