题目给定一个序列是 (1,2,3,4,5) 的一个排列，问，经过一次相邻元素交换后，是否能使得序列变回 (1,2,3,4,5)
注意：是一定且只能进行一次操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| void solve(){
int a[6], b[6];
for (int i = 1; i <= 5; i++) {
cin >> a[i];
b[i] = a[i];
}
sort(a + 1, a + 5 + 1);
int cnt = 0;
for (int i = 1; i <= 5; i++) {
if (a[i] != b[i]) {
if (a[i + 1] != b[i + 1]) {
cnt++, i++;
}
else {
cout << "No";
return;
}
}
}
cout << (cnt == 1 ? "Yes" : "No");
}
|
给定一个数列，判断这个数列是否是等比数（ geometric progression ）
# sb 乱写写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void solve(){
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
double q = a[2] / a[1];
for (int i = 3; i <= n; i++)
if (a[i] != a[i - 1] * q) {
cout << "No";
return;
}
cout << "Yes";
}
|
显然，这样写的话精度会有问题
# 正解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void solve(){
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
int fz = a[2] % a[1], fm = a[1];
for (int i = 3; i <= n; i++) {
int ffz = a[i] % a[i - 1], ffm = a[i - 1];
if (ffz * fm != fz * ffm) {
cout << "No" << endl;
return;
}
}
cout << "Yes" << endl;
}
|
通过
分子分母 + 假分数的写法，只要两两之间比相同，即为等比数列
水题水题大水题，找到给定棋盘的黑色方块的 (x1,y1,x2,y2) 即可，内部不能出现 .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void solve(){
cin >> n >> m;
int x1 = 0x3f3f3f3f, y1 = 0x3f3f3f3f, x2 = 0, y2 = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
if (a[i][j] == '#')
x1 = min(x1, i), y1 = min(y1, j), x2 = max(i, x2), y2 = max(j, y2);
}
for (int i = x1; i <= x2; i++)
for (int j = y1; j <= y2; j++)
if (a[i][j] == '.') {
cout << "No" << endl;
return;
}
cout << "Yes" << endl;
return;
}
|
观察到，n 的范围只有 12，考虑搜索
但是这题的数据大小到了 1e17，卡 map，用 unordered_map 能过
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| int n, a[N], ans = 0;
unordered_map<int, int> mp;
void dfs(int u, int res) {
if (u > n) {
if (!mp[res])
ans++;
mp[res] = 1;
return;
}
dfs(u + 1, res ^ a[u]);
for (int i = 1; i < u; i++) {
if (a[i] != 0) {
int x = a[i];
a[i] = 0, a[u] += x;
dfs(u + 1, res ^ a[u] ^ x);
a[i] = x, a[u] -= x;
}
}
}
void solve(){
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
dfs(1, 0);
cout << ans << endl;
}
|
拼尽全力但无法战胜的 DP
题目传送门
