看隔壁投票统计不难，代码量也较少，AC代码如下（回忆版本，大概没问题吧==）
更新：第二条问题不在循环输入，在更新，必须是值相等更新，不能是直接更新
1. 树的生长，动态规划，注意结果用long long即可（题目提示了树高是大数，结果用int存会超范围）
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
int n;
while (cin >> n) {
vector<int> trees(n, 0);
for (int i = 0; i < n; ++i) {
cin >> trees[i];
}
sort(trees.begin(), trees.end());
vector<long long> dp(n, 0); //可以滚动数组优化空间，不过我觉得dp数组写起来顺手
long long sum = 0; //注意树的高度可能很大，一定要long long。int爆0，笔试常见坑，我做完第二题回头才反应过来。====
for (int i = 1; i < n; ++i) {
dp[i] = dp[i - 1] + trees[i] - trees[i - 1];
sum += dp[i];
}
cout << sum << endl;
}
return 0;
} 2. 字符串字符替换，注意题意是要求模拟每步操作，不能忽略操作顺序 #include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
string S;
int n;
while (cin >> S >> n) {
vector<int> dict;
for (int i = 0; i < 10; ++i) {
dict.push_back(i);
}
int key, value;
//对操作过程进行模拟即可，保留最后一步的结果
//不能先哈希表保存再并查集/图搜索---忽略变换顺序，而且可能出环
for (int i = 0; i < n; ++i) {
cin >> key >> value;
for (int j = 0; j < 10; ++j) {
if (dict[j] == key)
dict[j] = value;
}
}
for (auto &c : S) {
if (dict[c - '0'] != c - '0')
c = dict[c - '0'] + '0';
}
cout << S << endl;
}
return 0;
} 
全部评论
(6) 回帖