首页 > 深信服8.25笔试 AC代码
头像
牛客967113510号
编辑于 2020-08-25 21:33
+ 关注

深信服8.25笔试 AC代码

看隔壁投票统计不难,代码量也较少,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) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐