小美走公路
题目描述
有一个环形的公路，上面共有 n 站，现在给定了顺时针第 i 站到第 i + 1 站之间的距离（特殊的，也给出了第 n 站到第 1 站的距离）。小美想沿着公路第 x 站走到第 y 站，她想知道最短的距离是多少？
输入：
第一行输入一个正整数 n（1 <= n <= 10^5），代表站的数量。
第二行输入 n 个正整数 ai（1 <= ai <= 10^9），前 n - 1 个数代表顺时针沿着公路走，i 站到第 i + 1 站之间的距离；最后一个正整数代表顺时针沿着公路走，第 n 站到第 1 站的距离。· 第三行输入两个正整数 x 和 y（1 <= x, y <= n），代表小美的出发地和目的地。
输出：
一个正整数，代表小美走的最短距离。
样例输入：
3
1 2 2
2 3
样例输出：
2
思路
这题当时我钻牛角尖了，非要把输入按照要求存好再处理，脑子瓦特了吧。
我们知道这是一条环形道路，头尾相连，那么从第x站走到第y站总是有两条路，即顺时针和逆时针，然而它们两的和就是整个环形的周长。
实际上，我们只用记录从起始点走到第i站的距离s[i]就可以，这样就顺其自然地得到了环形周长s。计算第x站到第y站的距离，也就是s[y-1]-s[x-1]或者是s-(s[y-1]-s[x-1])，我们选择距离最小的那个就可以。
哦对，注意这里要用long long，有的样例计算距离时会超过int最大值，不然ac不了。
代码
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n; // 站的数量
cin >> n;
vector<long long> a; // a[i]是顺时针走到第i站的距离
long long sum = 0;
a.push_back(sum); // 初始站a[0]=0，因为我们是从第一站开始走
int num;
while(cin >> num){
sum += num;
a.push_back(sum);
if(cin.get()=='\n') break;
}
int x,y;
scanf("%d %d", &x, &y);
if(x>y) swap(x, y);
long long all_len = a[a.size()-1]; // 环形总距离
long long min_len = min(a[y-1]-a[x-1], all_len-(a[y-1]-a[x-1]));
cout << min_len << endl;
return 0;
}
小美的蛋糕切割
题目描述
小美有一个矩形的蛋糕，共分成了 n 行 m 列，共 n * m 个区域，每个区域是一个小正方形，已知蛋糕每个区域都有一个美味度。
她想切一刀把蛋糕切成两部分，自己吃一部分，小团吃另一部分。
小美希望两个人吃的部分的美味度之和尽可能接近，请你输出|s1 - s2|的最小值。（其中 s1 代表小美吃的美味度，s2 代表小团吃的美味度）。 请务必保证，切下来的区域都是完整的，即不能把某个小正方形切成两个小区域。
输入：
第一行输出两个正整数 n 和 m（1 <= n, m <= 10^3），代表蛋糕区域的行数和列数。接下来的 n 行，每行输入 m 个正整数 aij（1 <= aij <= 10^4），用来表示每个区域的美味度。
输出：
一个整数，代表|s1-s2|的最小值。
样例输入：
2 3
1 1 4
5 1 4
样例输出：
0
思路
这题完全就是上题的演变啊，环形变成矩阵了。我们统计行和与列和，然后用sx[i]和sy[j]分别来统计前i行的总和，以及前j列的总和。那么从第i行横着切割的话，就很容易算出两个部分之差，竖着切同理。
代码
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int n, m;
const int N = 1004; //1 <= n, m <= 10^3
int x[N] = {0}; // 行和
int y[N] = {0}; // 列和
ll sx[N] = {0}; // sx[i]前i行的总和
ll sy[N] = {0}; // sy[j]前j列的总和aa
int main() {
scanf("%d %d", &n, &m);
int num;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &num);
x[i] += num; // 统计每一行的和
y[j] += num; // 统计每一列的和
}
}
for (int i = 1; i <= n; i++) {
sx[i] = sx[i-1] + x[i-1]; // 前i行的总和包含第i行
}
for (int j = 1; j <= m; j++) {
sy[j] = sy[j - 1] + y[j-1]; // 前i行的总和包含第i行
}
ll result = sy[m];
// 横切
for (int k = 1; k < n; k++) {
result = min(result, abs(sx[k] - (sx[n] - sx[k])));
}
// 竖切
for (int k = 1; k < m; k++) {
result = min(result, abs(sy[k] - (sy[m] - sy[k])));
}
cout << result << endl;
return 0;
}
小美的字符串变换
题目描述
小美拿到了一个长度为 n 的字符串，她希望将字符串从左到右平铺成一个矩阵（先平铺第一行，然后是第二行，以此类推，矩阵有 x 行 y 列，必须保证 x * y=n，即每 y 个字符换行，共 x 行）。
该矩阵的权值定义为这个矩阵的连通块数量。小美希望最终矩阵的权值尽可能小，你能帮小美求出这个最小权值吗？
注：我们定义，上下左右四个方向相邻的相同字符是连通的。
输入：
第一行输入一个正整数 n（1 <= n <= 10^4），代表字符串的长度。
第二行输入一个长度为 n 的、仅由小写字母组成的字符串。
输出：
输出一个整数表示最小权值。
样例输入：
9
aababbabb
样例输出：
2
思路
难点在于统计连通区域的个数。实际上是一个广度优先遍历，我们按顺序查看每个元素的位置附近的连通块，然后标记连通的地方，之后的遍历就不会再访问这个地方。有一个技巧是先定义好要查询的方向（包括x轴和y轴），也就是：
// 查询方向(x, y)
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
代码
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define pi pair<int, int>
int n; // 字符串长度
string s; // 输入字符串
vector<vector<char>> m; // 存放平铺后的矩阵
vector<char> vec; // 存放每一行的元素
// 查询方向(x, y)
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
int main() {
cin >> n;
cin >> s;
int min_result = n;
for (int row = 2; row < n; row++) {
// 1. 先完成平铺问题
if (n % row == 0) { // 判断n是否能被i整除（i是行）
m.clear();
int col = n / row;
int i = 0; // 第几行
while (i < row) { // 按照row*col排列字符串
vec.clear();
for (int j = 0; j < col; j++) vec.push_back(s[j + i * col]);
m.push_back(vec);
i++;
}
// 2. 针对每一种平铺方式计算连通量
vector<vector<int>> visited(row, vector<int>(col)); // 用来存放已经检查过的字符
queue<pi> q; // 队列存放距离相同的元素
int result = 0; // 记录连通区域总数
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
// 如果当前字符没有被访问过，则增加一个连通区
if (visited[i][j] == 0) {
result++;
q.push(pi(i, j)); // 将当前目标字符的index放入队列
while (!q.empty()) {
pi cur = q.front();
int cur_x = cur.first;
int cur_y = cur.second;
q.pop();
for (int k = 0; k < 4; k++) { // 按照查询方向进行连通判断
int q_x = cur_x + dx[k];
int q_y = cur_y + dy[k];
if (q_x < 0 || q_x >(row - 1) || q_y < 0 || q_y >(col - 1) || visited[q_x][q_y] == 1 || m[cur_x][cur_y] != m[q_x][q_y])
continue; // 如果查询index超出范围，或查询元素已经被访问过，或查询元素与目标字符不等
visited[q_x][q_y] = 1;
q.push(pi(q_x, q_y));
}
}
}
}
}
min_result = min(min_result, result);
}
}
cout << min_result << endl;
return 0;
}
小美的树上染色
题目描述
小美拿到了一棵树，每个节点有一个权值。初始每个节点都是白色。
小美有若干次操作，每次操作可以选择两个相邻的节点，如果它们都是白色且权值的乘积是完全平方数，小美就可以把这两个节点同时染红。
小美想知道，自己最多可以染红多少个节点？
输入：
第一行输入一个正整数 n（1 <= n <= 10^5），代表节点的数量。第二行输入 n 个正整数 ai（1 <= ai <= 10^9），代表每个节点的权值。接下来的 n - 1 行，每行输入两个正整数 u，v（1 <= u, v <= n），代表节点 u 和节点 v 有一条边连接。
输出：
输出一个整数，表示最多可以染红的节点数量。
样例输入：
3
3 3 12
1 2
2 3
样例输出：
2
思路
这题实在是困住我了QAQ，目前只能搞懂暴力法。
代码
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
typedef long long ll;
using namespace std;
const int N = 100001;
int n; // 节点数量
ll a[N]; // 节点权值
vector<int> g[N]; // 存放节点连接情况
int colored[N]; // 是否染色
int ans = 0;
// 判断乘积是否是完全平方数
int cal(ll a, ll b) {
double x = sqrt(a * b);
if (x * x == a * b) return 1;
else return 0;
}
// dps
void dfs(int u, int fa) {
for (int v : g[u]) { // 遍历u的子节点
if (v == fa) continue;
dfs(v, u);
if (colored[v] || colored[u]) continue;
if (cal(a[u], a[v])) {
ans += 2;
colored[u] = 1;
colored[v] = 1;
}
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
scanf("%lld", &a[i]);
}
int u, v;
for (int i = 0; i < n - 1; i++) {
scanf("%d %d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
cout << ans << endl;
return 0;
}
