20200801 猿辅导 笔试编程题
看了前面两道笔试题,感觉比较友好。切到第三题,,窝服了。。。
Python 写了一个处理注释 提交了,0%。行吧,我也不想继续了。。。
PS:第一次写帖子。。只能将就着看哒~
第一题(100%)
区间计数的常用套路?
#include <bits/stdc++.h> using namespace std; const int MAXN = 200005; int n; int main() { cin >> n; vector<pair<int, int>> pos; for(int i = 0; i < n; ++i) { int st, ed; cin >> st >> ed; pos.push_back(make_pair(st, +1)); pos.push_back(make_pair(ed, -1)); } sort(pos.begin(), pos.end()); int cnt = 0, ans = 0; for(auto& pr : pos) { cnt += pr.second; ans = max(ans, cnt); } cout << ans << endl; return 0; }
第二题 (100%)
树形dp/dfs。
#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; const long long infl = 0x3f3f3f3f3f3f3f3fll; const long long MOD = 1e9+3; long long val[MAXN]; vector<int> edges[MAXN]; long long dfs(int rt, long long& ans) { long long ret = val[rt]; for(auto &v : edges[rt]) { ret = max(ret, ret + dfs(v, ans)); // ret = (ret + MOD) % MOD; } ans = max(ans, ret); return ret; } int main() { //freopen("input-1.txt", "r", stdin); int n, rt = -1; cin >> n; for(int i = 0; i < n; ++i) { int fa; cin >> val[i] >> fa; if(fa == 0) rt = i; else edges[fa - 2].push_back(i); } long long ans = -infl; dfs(rt, ans); cout << (ans + MOD) % MOD << endl; return 0; }
第三题(0%)
第三题感觉设置得不太科学。。。直接弃疗。。。
# encoding: utf8 import sys import json json_str = "" while True: line = sys.stdin.readline().strip("\n") if line == "": line = sys.stdin.readline().strip("\n") break json_str += line js_obj = json.loads(json_str) # print(js_obj) html_str = "" while True: line = sys.stdin.readline().strip("\n") if "<!--" == line[:4] and "-->" == line[-3:]: continue if line == "end": break html_str += line + "\n" print(html_str)