**
PAT2022秋
**
有一题是卡着时间复杂度去做的结果AC了 希望大家也能来一起交流下最优解
- 踩气球 - AC
这道题调试了很久 才开始用的哈希表内存太大了
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <climits>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
using namespace std;
const int N = 2e6+3000, M = 1001000;
bool my_set[N];
int cnts_pre[N], cnts_post[N], cnts[N];
int n, m, x;
int l, r;
int main() {
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; ++i) {
scanf("%d", &x);
if(i == 1) l = x+M;
else if(i == n) r = x+M;
++cnts[x+M];
my_set[x+M] = 1;
}
if(m == 1) {
printf("%d %d", l-1-M, 1);
return 0;
}
for(int i = l; i <= r; ++i) {
cnts_pre[i] = cnts_pre[i-1];
if(my_set[i]) cnts_pre[i] += cnts[i];
}
for(int i = r; i >= l; --i) {
cnts_post[i] = cnts_post[i+1];
if(my_set[i]) cnts_post[i] += cnts[i];
}
int ans = 0, pos = l;
for(int i = l; i <= r; ++i) {
auto cur_pre = cnts_pre[i], nxt_pre = cnts_pre[i+m];
if(my_set[i]) cur_pre -= cnts[i];
auto cur_max = nxt_pre - cur_pre;
if(cur_max > ans) {
ans = cur_max;
pos = i;
}else if(cur_max == ans && pos > i) {
pos = i;
}
}
for(int i = r; i >= l; --i) {
auto cur_post = cnts_post[i], nxt_post = cnts_post[i-m];
if(my_set[i]) cur_post -= cnts[i];
auto cur_max = nxt_post - cur_post;
if(cur_max > ans) {
ans = cur_max;
pos = i;
}else if(cur_max == ans && pos > i) {
pos = i;
}
}
printf("%d %d", pos-M, ans);
return 0;
}
- 快排判断 - AC
就是这道题 时间复杂度感觉是卡着过的
#include <iostream>
#include <cstring>
#include <cstdio>
#include <climits>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
const int N = 1e5+10;
int left_max[N], right_min[N];
int nums[N];
int k, n, x;
bool check(int l, int r, int cnts) {
if(l > r) return false;
auto first_piv = -1;
for(int i = l; i <= r; ++i) {
if(left_max[i] < nums[i] && right_min[i] > nums[i]) {
first_piv = i;
if(cnts == 2) return true;
bool l_ans = false, r_ans = false;
l_ans = check(l, first_piv-1, cnts+1), r_ans = check(first_piv+1, r, cnts+1);
if(first_piv == l || first_piv == r) {
if(l_ans || r_ans) return true;
}else {
if(l_ans && r_ans) return true;
}
}
}
return false;
}
int main() {
scanf("%d", &k);
while(k--) {
memset(nums, 0, sizeof nums);
memset(left_max, -0x3f, sizeof left_max);
memset(right_min, 0x3f, sizeof right_min);
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d", &nums[i]);
}
for(int i = 2; i <= n; ++i) {
left_max[i] = max(left_max[i-1], nums[i-1]);
right_min[n-i+1] = min(right_min[n-i+2], nums[n-i+2]);
}
bool flag = check(1, n, 1);
if(flag) printf("Yes\n");
else printf("No\n");
}
return 0;
}
- 寻找领导 - AC
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;
const int N = 1e4+10;
int cnts_follow[N], cnts_by_follow[N];
unordered_set<int> op;
vector<int> res, tmp, by_follow[N];
int n, t, m, x;
int main() {
cin >> n >> t;
for(int i = 1; i <= n; ++i) {
cin >> m;
cnts_follow[i] += m;
for(int j = 0; j < m; ++j) {
cin >> x;
cnts_by_follow[x]++;
by_follow[x].emplace_back(i);
}
}
for(int i = 1; i <= n; ++i) {
double cur_res = (1.0 * cnts_by_follow[i])/cnts_follow[i];
if(cur_res >= t) {
op.emplace(i);
tmp.emplace_back(i);
}
}
int cur_max = 0;
for(int i = 0; i < tmp.size(); ++i) {
int cnts_tmp = 0;
for(auto& pre : by_follow[tmp[i]]) {
cnts_tmp += op.count(pre);
}
if(cur_max < cnts_tmp) {
cur_max = cnts_tmp;
res.clear(); res.emplace_back(tmp[i]);
}else if(cur_max == cnts_tmp) {
res.emplace_back(tmp[i]);
}
}
for(int i = 0; i < res.size(); ++i) {
if(i) cout << " ";
cout << res[i];
}
return 0;
}
- 树 - AC
当时写的时候想的是先写出来再优化，所以代码很长，很多地方可以放在一个函数里判断，由于这样也AC了所以就直接没有优化了就提交了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <algorithm>
using namespace std;
const int N = 2010;
vector<int> inorder, preorder, postorder;
int level_cnts[N];
unordered_map<int, int> l, r, pos;
int n, x;
int build(int l1, int r1, int l2, int r2) {
if(l1 > r1) return -1;
auto root = preorder[l1];
auto root_pos = pos[root];
auto left_nums = root_pos - l2, right_nums = r2 - root_pos;
l[root] = build(l1+1, l1+left_nums, l2, root_pos-1);
r[root] = build(r1-right_nums+1, r1, root_pos+1, r2);
return root;
}
void dfs(int u) {
if(l[u] != -1) dfs(l[u]);
if(r[u] != -1) dfs(r[u]);
postorder.emplace_back(u);
}
void print_pre() {
for(int i = 0; i < postorder.size(); ++i) {
if(i) cout << " ";
cout << postorder[i];
}
}
bool check_perfect(int u) {
queue<int> q;
q.push(u);
int cur_level = 0, max_level = 1;
while(q.size()) {
int sz = q.size();
++cur_level;
for(int i = 0; i < sz; ++i) {
auto t = q.front(); q.pop();
++level_cnts[cur_level];
if(l[t] != -1) q.push(l[t]);
if(r[t] != -1) q.push(r[t]);
}
max_level = max(max_level, cur_level);
}
int tmp = 1;
for(int i = 1; i <= max_level; ++i) {
if(level_cnts[i] != (int)pow(2, i-1)) {
return false;
}
}
return true;
}
bool check_complete(int u) {
queue<int> q;
q.push(u);
bool isend = false;
while(q.size()) {
int sz = q.size();
for(int i = 0; i < sz; ++i) {
auto t = q.front(); q.pop();
if(isend && (l[t] != -1 || r[t] != -1)) return false;
if(l[t] != -1) q.push(l[t]);
if(r[t] != -1) q.push(r[t]);
if(l[t] == -1 || r[t] == -1) isend = true;
}
}
return true;
}
bool check_pseudo(int u) {
queue<int> q;
q.push(u);
int isend = -1, cur_level = 0;
while(q.size()) {
int sz = q.size(); ++cur_level;
for(int i = 0; i < sz; ++i) {
auto t = q.front(); q.pop();
if(isend != -1 && cur_level > isend) {
return false;
}
if(l[t] != -1) q.push(l[t]);
if(r[t] != -1) q.push(r[t]);
if((l[t] == -1 || r[t] == -1) && isend == -1) {
isend = cur_level+1;
}
}
}
return true;
}
int main() {
cin >> n;
for(int i = 0; i < n; ++i) {
cin >> x;
inorder.emplace_back(x);
pos[x] = i;
}
for(int i = 0; i < n; ++i) {
cin >> x;
preorder.emplace_back(x);
}
auto root = build(0, n-1, 0, n-1);
dfs(root);
auto ret = check_perfect(root);
if(ret) {
printf("1\n");
print_pre();
return 0;
}
ret = check_complete(root);
if(ret) {
printf("2\n");
print_pre();
return 0;
}
ret = check_pseudo(root);
if(ret) {
printf("3\n");
print_pre();
return 0;
}
printf("0\n");
print_pre();
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
