ABC345 A-D 题解

本文主要是介绍ABC345 A-D 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

A
- 题目
- AC Code：
B
- 题目
C
- 题目
- AC Code：
D
- 题目
- AC Code：

A

题目

我们判断输入的字符串两头是否是两个箭头，再判断中间共 $∣ s ∣ - 2$ 个字符是否是等号，如果全部是，说明这个字符串是符合条件的，否则，不符合条件。

AC Code：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
string s;int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> s;for (int i = 1; i < (int)s.size() - 1; i++) {if (s[i] != '=') {cout << "No";return 0;}}if (s[0] != '<' || s[s.size() - 1] != '>') cout << "No";else cout << "Yes";return 0;
}

B

题目

由于 c++ 的取整操作是向 $0$ 取整，所以如果 $X$ 为负数时，就不用执行额外的操作，直接输出 $X$ 整除 $10$ 即可。否则，为非负数时，如果 $X$ 除以 $10$ 的余数非零时，说明 $\frac{X}{10}$ 的小数部分要向整数部分加一个 $1$ ，在 $X$ 除以 $10$ 的商上加一就是正确答案。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
long long x;int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> x;long long ans = x / 10;if (x % 10 && x >= 0) ans++;cout << ans;return 0;
}

C

题目

~~题意害人不浅~~

此题是想让你求出对于一个字串 $S$ ，交换 $S$ 的任意两个字符一次，交换后的不同字符串一共有多少个？

当然，样例 $2$ 告诉我们，交换后的字串可以和交换前的字串相等。

我们先暂且不管题目中 $1\le i < j \le n$ 的条件，先来分析一下以下字符串：

abcabc

我们先讨论 $i$ 为 $1$ 的情况：这个时候要被交换的一个字符是 a，我们可以和后面的两个 b 和两个 c 交换，不必和 a 交换，因为这样交换后和之前是一样的，我们先不讨论这种情况。

在讨论 $i$ 为 $2$ 的情况：为了方便讨论，我们可以让这个字符和前面的字符交换，一共可以和两个 a 和两个 c 交换……

我们发现：对于每一个字符 $k$ ，这个字符可以和 $S|-cnt_k$ 个字符交换得到新的字符串，其中 $cnt_k$ 指字串中 $k$ 的数量。对于两个 $i$ 和 $j$ ，其中 $S_i \neq S_j$ ，我们在讨论 $i$ 时交换了 $i$ 和 $j$ ，又在讨论 $j$ 时交换了 $i$ 和 $j$ 。所以讨论完后答案要除以 $2$ 。

最后，我们还要讨论交换后和以前相等的情况：如果有一个字符 $k$ 满足 $cnt_k \ge 2$ ，就可以将两个 $k$ 交换得到和之前相等的字串，答案加上 $1$ 。

最后输出答案，完结撒花。

时间复杂度： $O (∣ S ∣)$ 。

AC Code：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
string s;
int cnt[30];
long long sum, ans;
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> s;for (int i = (int)s.size() - 1; i >= 0; i--) {cnt[(int)(s[i] - 'a')]++;}for (int i = 0; i < (int)s.size(); i++) {ans += (int)s.size() - cnt[(int)(s[i] - 'a')];}ans /= 2;for (int i = 0; i < 26; i++) {if (cnt[i] > 1) {ans++;break;}}cout << ans;return 0;
}

D

题目

如果你不知道什么是位运算，请做一个了解。

我们注意到 $H, W$ 很小，只有 $10$ ， $N$ 也很小，只有 $7$ ，这给我们提供了搜索的机会。

我们发现，对于每一个可以放置到的情况，如下图：

如果这种情况合法，那么 $(3, 3)$ 位置必须被放置，那么我们放置下一个方块时，可以直接讨论 $(3, 3)$ 为左上角的情况，因为这个位置无论如何也要被放置。

所以在 DFS 中，我们对于每一个未被放置的矩形，直接讨论左上角第一个未被放置的位置就行了。

对于表示情况，因为 $W$ 很小，所以一排的情况可以被表示成一个二进制数，比如上图就可以被表示成这个二进制数组：

而我们如果要判断某一排是否从 $k$ 到 $k + l - 1$ 列都是 $0$ ，那么先创建一个数，它由 $l$ 个 $1$ 组成，可以这样写：

int p = (1 << l) - 1

其中我们创建了一个第 $l + 1$ 位为 $1$ ，其余位为 $0$ 的二进制数，再将其减一，那么第 $l + 1$ 位变成了 $0$ ，第 $l\dots1$ 位变成了 $1$ 。

我们令这一排为 $x$ ，那么如果这个条件成立：

((x >> (k - 1) & p) == 0)

就表明这一排从 $k$ 到 $k + l - 1$ 列都是 $0$ 成立。

原理解释：

我们将 $x$ 右移了 $k - 1$ 位，这时 $x$ 的第一位对应原来的 $k$ 位。与 $p$ 做按位和后，由于 $p$ 的 $l + 1$ 位都是 $0$ ，所以只会保留现在 $x$ 的 $l$ 位，其余位都是 $0$ ，如果这时 $x$ 是 $0$ ，说明 $x$ 的 $l\dots l + k - 1$ 位都是 $0$ 。

而如果我们要把 $x$ 的 $l\dots l + k - 1$ 全部赋值为 $1$ ，就把 p << (k - 1) 异或上原来的 $x$ ，按位或也可以。

然后把上面的位运算技巧结合起来，再 DFS 一遍，就完结撒花了。

AC Code：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
int n, h, w;
struct node{int a, b;
};
node a[100100];
int vis[100];
bool vis1[10];
void dfs(int dep, int area, int last_x, int last_y) {while (last_x <= h) {if (((vis[last_x] >> (last_y - 1)) & 1) == 0) {break;}last_y++;if (last_y > w) {last_y = 1;last_x++;}if (last_x > h) break;}if (area == h * w) {cout << "Yes";exit(0);}if (dep == n + 1) return;for (int k = 1; k <= n; k++) {if (!vis1[k]) {if (a[k].a + last_x - 1 <= h && a[k].b + last_y - 1 <= w) {bool flag = 0;int tmp = (1 << a[k].b) - 1;for (int l = 1; l <= a[k].a; l++) {if ((vis[last_x + l - 1] >> (last_y - 1)) & tmp) {flag = 1;break;}}if (!flag) {for (int l = 1; l <= a[k].a; l++) {vis[last_x + l - 1] ^= (tmp << (last_y - 1));}vis1[k] = 1;dfs(dep + 1, area + a[k].a * a[k].b, last_x, last_y);vis1[k] = 0;for (int l = 1; l <= a[k].a; l++) {vis[last_x + l - 1] ^= (tmp << (last_y - 1));}}}if (a[k].a != a[k].b) {swap(a[k].a, a[k].b);if (a[k].a + last_x - 1 <= h && a[k].b + last_y - 1 <= w) {bool flag = 0;int tmp = (1 << a[k].b) - 1;for (int l = 1; l <= a[k].a; l++) {if ((vis[last_x + l - 1] >> (last_y - 1)) & tmp) {flag = 1;break;}}if (!flag) {for (int l = 1; l <= a[k].a; l++) {vis[last_x + l - 1] ^= (tmp << (last_y - 1));}vis1[k] = 1;dfs(dep + 1, area + a[k].a * a[k].b, last_x, last_y);vis1[k] = 0;for (int l = 1; l <= a[k].a; l++) {vis[last_x + l - 1] ^= (tmp << (last_y - 1));}}}}}}
}
int main() {srand(time(NULL));ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> h >> w;for (int i = 1; i <= n; i++) cin >> a[i].a >> a[i].b;dfs(1, 0, 1, 1);cout << "No";return 0;
}