刷题记录（2023-08-12）

1. 小美的排列询问

AC代码：

#include <iostream>
#include <vector>
using namespace std;int main() {int n;cin >> n;vector<int> nums(n);int a, b;for (int i = 0; i < n; i++) {cin >> nums[i];}cin >> a >> b;for (int i = 0; i < n; i++) {if (nums[i] == a) {if (i - 1 > 0 && nums[i - 1] == b) {cout << "Yes";return 0;}if (i + 1 < n && nums[i + 1] == b) {cout << "Yes";return 0;}}}cout << "No";return 0;
}
// 64 位输出请用 printf("%lld")

2. 小美走公路

AC代码：

#include <iostream>
#include <vector>
using namespace std;int main() {int n;cin >> n;vector<int> lenRoad(n);for (int i = 0; i < n; i++) {cin >> lenRoad[i];}int x, y;cin >> x >> y;if (x > y) {swap(x, y);}long len1 = 0;long sumLen = 0;for (int i = 0; i < n; i++) {sumLen += lenRoad[i];if (i >= x - 1 && i < y - 1) {len1 += lenRoad[i];}}long len2 = sumLen - len1;cout << min(len1, len2);}
// 64 位输出请用 printf("%lld")

3. 小美的蛋糕切割

#include <iostream>
#include <vector>
using namespace std;int main() {int n, m;cin >> n >> m;vector<vector<int>> cakes(n, vector<int>(m));vector<long> rows(n);vector<long> cols(m);for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> cakes[i][j];rows[i] += cakes[i][j];cols[j] += cakes[i][j];}}for (int i = 1; i < n; i++) {rows[i] += rows[i - 1];}for (int j = 1; j < m; j++) {cols[j] += cols[j - 1];}long minVal1 = 0x3f3f3f3f;for (int i = 0; i < n - 1; i++) {int disVal = abs(rows[n - 1] - rows[i] - rows[i]);if (minVal1 > disVal) {minVal1 = disVal;}// else{//     break;// }}long minVal2 = 0x3f3f3f3f;for (int j = 0; j < m - 1; j++) {int disVal = abs(cols[m - 1] - cols[j] - cols[j]);if (minVal2 > disVal) {minVal2 = disVal;}// else{//     break;// }}cout << min(minVal1, minVal2);return 0;
}
// 64 位输出请用 printf("%lld")

有用例没过(后来发现是$10^{10}$，会超int范围，应该换成long的)：

4. 小美的字符串变换

#include <iostream>
#include <string>
#include <vector>
using namespace std;class UFSets {
public:vector<int> vec;UFSets(int sz) {vec = vector<int>(sz, -1);}int Find(int x) {while (vec[x] > 0)x = vec[x];return x;}bool Union(int root1, int root2) {int r1 = Find(root1);int r2 = Find(root2);if (r1 == r2) {return false;}if (vec[r1] < vec[r2]) {vec[r2] = vec[r1] + vec[r2];vec[r1] = r2;}else {vec[r1] = vec[r1] + vec[r2];vec[r2] = r1;}return true;}
};int main() {int n;cin >> n;string str;cin >> str;int minNumSets = 0x3f3f3f3f;// x=1 与 y=1效果一致，因此y直接从2开始就好了for (int x = 1; x < n / 2; x++) {if (n % x == 0) {int y = n / x;UFSets ufs(n);for (int i = 0; i < n; i++) {int posX = i / y;int posY = i % y;// 上边if (posX - 1 >= 0 && str[(posX-1)*x+posY] == str[i]) {// 合并ufs.Union((posX - 1) * x + posY, i);}// 左边if (posY - 1 >= 0 && str[posX * x + posY - 1] == str[i]) {// 合并ufs.Union(posX * x + posY - 1, i);}}// 检查ufs中的集合数量int numSets = 0;for (int i = 0; i < ufs.vec.size(); i++) {if (ufs.vec[i] < 0) {numSets++;}}if (numSets < minNumSets) {minNumSets = numSets;}}}cout << minNumSets;return 0;
}
// 64 位输出请用 printf("%lld")

这个边界条件有点问题，后来改了，但也只过了20% = =

5. 小美的树上染色

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;struct Node {int val;bool color;
};int main() {int n;cin >> n;vector<Node> nodes(n);for (int i = 0; i < n; i++) {cin >> nodes[i].val;nodes[i].color = false;}int a, b;int res = 0;for (int i = 0; i < n - 1; i++) {cin >> a >> b;if (!nodes[a].color && !nodes[b].color) { // 两个节点都是白色int sq = sqrt(nodes[a].val * nodes[b].val);if (sq * sq == nodes[a].val * nodes[b].val) {res += 2;nodes[a].color = true;nodes[b].color = true;}}}cout << res;
}
// 64 位输出请用 printf("%lld")

只过了10%